以改良式分枝界限演算法求解允許中斷開放型工廠排程問題

An Improved Branch-and-Bound Algorithm For Preemptive Open Shop Scheduling Problems

陳盈如(Ying-Ru Chen)

指導教授 ： 廖經芳

朝陽科技大學/理工學院/工業工程與管理系/碩士(2013年)

摘要

本論文將探討開放型工廠(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.

並列關鍵字

Preemptive ； Total Completion Time ； Open Shop ； Branch-and-Bound Algorithm

參考文獻

[35] 曾佳盈，「以分枝界限法求解可中斷式開放工廠排程問題」，碩士論文，私立朝陽科技大學工業工程與管理研究所，台中(2011)

[1] Graham, T., Lawer, E.L., Lenstra, J.K., Rinnooy Kan, A.H.G., “Optimization and approximation in eterministic sequence and scheduling a survey”, Annals of Discrete Mathematics, Vol.5, pp.287-326 (1979).

[2] Emmons, H., “One machine sequencing to minimize mean flow time with minimum number tardy”, Naval Research Logistics Quarterly, Vol.22, No.3, pp.585-592 (1975)

[3] Koksalan, M., Azizoglu, M., Kondakci, Koksalan, S., “Minimizing flowtime and maximum earliness on a single machine”, Institute of Industrial Engineerings, Vol.30, No.2, pp.192-200 (1998)

[4] Zaloom, V., Vatz, D., “A note on the optimal scheduling of two parallel processors”, Naval Research Logistics Quarterly, Vol.22, No.4, pp.823-827 (1975)