以分枝界限法求解可中斷式開放工廠排程問題

Branch-and-Bound Algorithms for Preemptive Open Shop Scheduling Problems

曾佳盈(Jia-Ying Zeng)

指導教授 ： 廖經芳

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

摘要

在生產過程中，在製品為製造上的一大成本，欲減少生產成本則須降低在製品個數，而總完工時間即為生產排程中評估在製品的重要準則；準時交貨滿足顧客需求，為目前企業所重視的議題，因此降低總延遲時間即可降低工廠延遲交貨的程度。
本研究目的在探討總完工時間及總延遲時間最小化之可中斷式開放工廠排程問題，Gonzalez與Sahni（1976）提出在給定工件完工順序（C1≦C2≦…≦Cn）的前提下，可利用線性規劃（Linear Programming）的方法求解總完工時間及總延遲時間最小化的問題；為得到工件最佳的完工順序，本研究利用分枝界限法進行順序的搜尋。
本研究分別針對總完工時間及總延遲時間最小化的問題，各自發展了上限值、下限值及淘汰法則，加快其搜尋的速度；最後透過大量隨機的例題，將問題分為n=m（如：3×3、4×4、5×5等）及n>m（如：6×3、8×4、9×3等）兩種類型進行績效評估。

關鍵字

淘汰法則 ； 延遲時間 ； 完工時間 ； 分枝界限法 ； 完工順序

並列摘要

In the production process, WIP (work in process) accounts for a major part of manufacturing cost. Hence, reducing the number of WIP is a good way to cut down production cost. It is well known that the total completion time is an effective criterion for assessing WIP cost in the production process. Also, Delivery on time and meet customer needs is an important issue for enterprises. Thus, it is important to reduce the total tardiness time of the products manufactured in the factory.
This study aim is to investigate the problem of minimizing the total completion time and minimizing the total tardiness time in preemptive open shops. Gonzalez and Sahni (1976) showed that given a job Completion Sequence (C1 ≦ C2 ≦ ... ≦ Cn), the problem can be solved by linear programming. In this study, a branch-and-bound mechanism is used to determine the best completion sequence of jobs.
This study proposes branch-and-bound methods for the problems under consideration. Upper bounds, lower bounds and dominance rules are developed to speed up search speed. Finally, the performance of the proposed methods is evaluated by a large number of randomly generated problems, including n=m and n>m two types of instances.

並列關鍵字

Dominance Rules ； Tardiness Time ； Completion Time ； Completion Sequence ； Branch-and-Bound

參考文獻

[1] Achugbue, J. O., and Chin, F. Y., “Scheduling the open shop to minimize mean flow time”, SIAM J. COMPUT., Vol. 11, pp.709-720 (1982).

[3] Alidaee Bahrama, and Duaneb Rosa, “Scheduling Parallel Machines To Minimize Total Weighted And Unweighted Tardiness”, Computers & Operations Research, Vol. 24, No. 8, pp.775-788 (1997).

[4] Amaral Armentano, V. V., and Rigao Scrich, C., “Tabu Search For Minimizing Total Tardiness In A Job Shop”, International Journal Of Production Economics, Vol. 63, No. 2, pp.131-140 (2000).

[5] Deman, V., John, M., and Baker, K. R., “Minimizing mean flow time in the flow shop with no intermediate queues”, AIIE Transactions, Vol. 6, No. 1, pp.28-34 (1974).

[6] Du, J. Z., and Leung, Y. T., “Minimizing Total Tardiness On One Processor Is NP Hard”, Mathematics Of Operations Research, Vol. 3, pp.483-495 (1990).