本論文將探討開放型工廠(Open Shop)在允許中斷(Preemption)限制下,最小化總完工時間(Minimize Total Completion Time)之排程問題,以排程符號表示為 問題,此問題已被證明為NP-hard問題。 本研究旨在發展一分枝界限演算法(Branch-and-Bound Algorithm)來求解上述問題。其中結合線性規劃(Linear Programming)、上限值演算法及下限值演算法等,使分枝的過程中,有效刪除無用節點數,加快求解的效率。 最後,經由電腦大量隨機產生的測試例題,評估所發展之分枝界限演算法與其他現有方法的結果進行比較,結果顯示此分枝界限演算法可有效地縮短執行時間,而且本研究所設計之上限值演算法及下限值演算法均有較佳的品質。
This paper examines the open shop scheduling problem with preemption under the objective of minimize total completion time. The problem is denoted by , and is known to be a NP-hard problem. An improved branch-and-bound algorithm is developed to solve problems under completion. A linear programming model is used to determine the optimal job completion times when the job completion sequence is fixed. Also, both upper bound and lower bound are incorporated into the algorithm to effectively prune unpromising nodes during the search process. The performance of the proposed branch-and-bound algorithm is evaluated through randomly generated test problems. The algorithm is compared with other existing algorithms in the literature. The results show that the proposed algorithm significantly improves other existing algorithms in terms of computation time. Moreover, the proposed upper and lower bounds can effectively cut down the search space and improve the algorithm’s efficiency.
為了持續優化網站功能與使用者體驗,本網站將Cookies分析技術用於網站營運、分析和個人化服務之目的。
若您繼續瀏覽本網站,即表示您同意本網站使用Cookies。