加權機組負載最小化之流線型排程

Abstract

本計畫考慮供應鍊管理中差異延遲所涉及之一項雙階段流線型生產模式。在此生產模 式下，所有產品共用第一階段之機器，當個別產品完成第一階段作業，即進入其所屬 的第二階段機器以完成全部作業。不同於以往排程以工作(或訂單)品項為主，本計畫 考慮之目標函數為機器之加權負載，亦即各機器耗用時間之加權總和。計畫中，我們 首先要確認各項研究問題之時間複雜度，所涉及的研究方法為提供NP-completeness 證 明以及設計多項式演算法。對於經證明複雜較高之問題，我們將設計分支與界定法以 及動態規劃法求最佳解。另外，我們也將設計簡潔之經驗法則以及近似規劃，我們的 研究重點將著重於分析其誤差與效能。