雙階段流程型工廠包含等效平行機台之工作延遲個數最小化問題

本研究主旨在探討具有等效平行機台的雙階段流程型工廠之生產排程問題。研究目標為總延遲工作個數最小化。第一階段與第二階段皆為等效平行機台，等效平行機台一次處理一個工作。本問題在過去的文獻中提到類似問題已證明為NP-Hard，故本研究提出了兩個啟發式演算法，同時建立下限值演算法驗證啟發式演算法之求解品質。實驗結果得知，啟發式演算法ㄧ的平均求解時間較快，但平均求解品質則是啟發式演算法二為最好。

關鍵字

工作延遲個數；下限值；雙階段流程型工廠；等效平行機台

並列摘要

This research explores two-stage flowshop including identical parallel machines and the main purpose is to minimize the number of tardy jobs. At the first stage and the second stage, the identical parallel machine can only process one task at a time. The restricted version of the problem under study is strongly NP-hard, which implies the general problem is also strongly NP-hard. This paper proposes two heuristics. Two kinds of algorithms will be adopted and along with a lower bound algorithm in order to solve the problem in this study. Experiment results show that the CPU time for heuristic one is less than the others, and the solution for heuristic two is best.

並列關鍵字

number of tardy jobs ； two-stage flowshop ； identical parallel machines ； lower bound

參考文獻

[1]Allaoui H., Artiba A., Scheduling two-stage hybrid flow shop with availability constraints, Computers & Operations Research 33 (2006) 1399-1419.

[2]Baptiste P., Peridy L, Pinson E., A branch and bound to minimize the number of late jobs on a single machine with release time constraints, European Journal of Operational Research 144 (2003) 1-11.

[3]Bulfin R.L., M’Hallah R., Minimizing the weighted number of tardy jobs on a two-machine flow shop, Computers & Operations Research 30 (2003) 1887-1900.

[4]Gupta J.N.D., Hariri A.M.A., Two-machine flowshop scheduling to minimize the number of tardy jobs, Journal of the Operational Research Society 48 (1997) 212-220.

[5]Gupta J.N.D., Tunc E.A., Minimizing tardy jobs in a two-stage hybrid flowshop, International Journal of Production Research 36 (1998) 2397-2417.

國際替代計量

雙階段流程型工廠包含等效平行機台之工作延遲個數最小化問題

全文下載

主題瀏覽