多機開放工廠最小化總完工時間之動態排程

本研究探討多機開放型生產型態之動態排程問題，以最小化總完工時間為衡量指標，此問題已被證實為NP-Hard，因此發展啟發式演算法以縮短求解時間，使適用於實務上。本研究將文獻所提幾個用在多機開放工廠靜態排程的派工法則擴展，使適用於本研究，並且提出考量不同優先條件的啟發式演算法，最後擷取這些方法之優點發展啟發式演算法MDLTRP。此法搜尋工作或機台最先可以開始的時間，接著排入此時間點可以排的作業，此作業必須是後續加工時間總和最大的。最後測試機台數與工作數相同的大規模問題。而依據實驗結果顯示，本研究所提方法之績效遠大於標準測試問題，顯示本研究方法有實際的應用價值。

關鍵字

總完工時間；動態；啟發式方法；多機；開放工廠

並列摘要

This study considers the dynamic open shop scheduling problem with the objective of minimizing the makespan. It has been established that the problem is NP-hard. An efficient heuristic, MDLTRP( modified longest total remaining processing on other machines first), is therefore proposed. A point of time is picked among the earliest available job release time and machine ready time. A job with the largest remaining processing time is selected to process at that time. Computational results show that the heuristic outperforms the existing algorithm.

並列關鍵字

multiple machines ； dynamic ； open shop ； makespan

參考文獻

5. Brasel, H., Kleinau, M., ”On the number of feasible schedules of the open shop problem - an application of special Latin rectangles.” Optimization 23(1992) 251-260.

6. Brasel, H., Tautenhahn, T., and Werner, F., Magdeburg, “Constructive Heuristic Algorithms For The Open Shop Problem,” Computering, 51(1993), 95-110.

7. Brucker, P., Hurink, J., Jurisch, B., and Wostmann,“A branch & bound algorithm for the open shop problem,”Discrete Applied Mathematics, 76(1997), 43-59.

8. Brucker, P., Jurisch, B., Sievers, B., “A fast branch and bound algorithm for the job shop scheduling problem.” Discrete Appl. Math. 49(1994) 107-127.

9. Campbell, H. G., Dudek, R. A., Smith, M. L., “A heuristic for the n job, m machine sequence problem.” Management Science16,10(1970)630-637.

國際替代計量

多機開放工廠最小化總完工時間之動態排程

未授權

主題瀏覽