包含批量機台與等效平行機台在目標為最小化完工時間下雙階段流程型工廠之排程問題

本研究主要為研究雙階段流程型工廠包含批次機台與等效平行機台，以最小總完工時間（Makespan）為目標。第一階段為單一批次機台，第二階段為等效平行機台；單一批次機台一次可以同時處理數個工作，批次處理時間為該批次內所有工作的最大處理時間，等效平行機台一次處理一個工作。此問題為一NP-hard問題，因此提出三個啟發式演算法，此三個啟發式演算法均是利用Johnson’s Rule發展而成，同時建立兩個下限值驗證啟發式演算法之求解品質。

關鍵字

總完工時間；下限值；等效平行機台；批次機台；雙階段流程型工廠

並列摘要

This study is focused on two-stage flowshop including batch machines and identical parallel machines and adopting makespan as the goal. At the first stage, the single batch machine can handle multiple tasks simultaneously, whereas at the second stage, the identical parallel machine can only process one task at a time. This kind of problem is called NP-hard problem. Based on Johnson’s Rule, three kinds of algorithms will be adopted and along with two lower bounds algorithms in order to solve the problem in this research.

並列關鍵字

lower bound ； makeapan ； identical parallel machine ； batch machine ； two-stage flowshop

參考文獻

[1]Javad, H. A. , Reza, H. A. , Sriram, D., and Christopher, S. T. , 1992 , Batching and scheduling jobs on batch and discrete processors, Operations Research, 39 , 750-763.

[2]Chandru, V. , Lee, C. Y., Uzsoy, R., 1993 , Minimizing total completion time onbatch processing machines , International Journal of Production Research , 31 , p 2097 - 2121

[3]Chou, F.D. , 2007 , A joint GA+DP approach for single burn-in oven schedulingproblems with makespan criterion , The International Journal of Advanced Manufacturing Technology, 35 , p587-595

[4]Christos, K. and George, J. K. , 2007 , A note on performance guarantees forsequencing three-stage flexible flowshops with identical machines to minimize makespan , IIE Transactions , 39 , p559-563

[5]Chung, K. P. and Wenci, Y. , 2005 , A flexible on-line scheduling algorithm forbatch machine with infinite capacity , A nnals of Operations Research , 133 ,p175-181

國際替代計量

包含批量機台與等效平行機台在目標為最小化完工時間下雙階段流程型工廠之排程問題

未授權

主題瀏覽