雙階段流程型工廠包含兩開放機台與單機之最小化最大完工時間排程問題

Minimizing makespan in a two-stage system with open and discrete shop

潘宣佑(hsuan-Yu Pan)

指導教授 ： 蘇玲慧

中原大學/工學院/工業工程研究所/碩士(2006年)

https://doi.org/10.6840/cycu200600525

摘要

本研究將針對雙階段流程型工廠包含兩開放機台與單機排程問題加以探討， 以最小化最大完工時間為目標，提出最佳化演算法與三個啟發式演算法。最佳化演算法為分支界限演算法，啟發式演算法一主要考慮在第一階段雙機開放型工廠中，以作業最大完工時間為最小值的情況下，再進行第二階段作業排序；啟發式演算法二乃從流程型工廠演算法Johnson’s Rule發展而成；啟發式演算法三為根據本研究之排程特性，建立一排序指標值，依此指標建立作業加工順序；透過實驗測試得到三個啟發式演算法求解品質分別在84%、96%、97%以上。最後提出當作業在第三台機器的加工時間大於第一、二機器的加工時間時，為本研究的特殊問題（Special Case）並提出特殊問題最佳解演算法。

關鍵字

分支界限演算法 ； 開放機台 ； 雙階段流程型工廠 ； 最小化最大完工時間 ； 啟發式演算法 ； 特殊問題

並列摘要

This paper addresses the two-stage system with open shop in the first stage and discrete shop in the second stage. The performance considered is the minimum makespan. The approaches includes one optimization algorithm and three heusitic algorithms. The optimization algorithm is the branch and bound algorithm. The first heuristic algorithm is developed by construct a sequence with the minimum makespan to the open shop and then use the FCFS rule to sequence the job in discrete processor. The second heuristic algorithm is generated by adopting the Johnson's rule to the open shop and also use the FCFS rule to the discreate processor. The last heuristic adopts an index according to the property developed in this work . Experimental results show that the solution qualities of these three heursitic are 84%, 96% and 97%, respectively. Finally, an optimal algorithm of specail case in which the minimum processing time of discreate processor is larger than the maximum processing time of the open shop is developoed.

並列關鍵字

heuristic algorithm ； branch and bound ； two-stage system ； open shop ； special case

參考文獻

[3] 丁威清, 雙階段流程型與開放型生產型態之排程研究, 中原大學工業工程學系碩士學位論文,（2002）.

[4] Adiri, I., Aizikowitz, N., Open-shop scheduling problems with dominated machines, Naval research logistics 36（1989）273-281.

[5] Chung, Y. L., Cheng, T. C. E., Lin, B.M., Minimizing the Makespan in the 3-machine assembly-type flowshop scheduling problem, Management science 39（1993）616-625.

[6] Gonzalez, T., Sahni, S., Open shop scheduling to minimize finish time, Journal of the association for computiong machinery 23（1976）665-679.

[7] Johnson, S. M., Optimal two- and three- stage production schedules with setup times included, Naval research logistics Quarterly 1（1954）61-68.