最小化總完工時間非等效平行機台及非等效批次平行機台之兩階段彈性流程式生產

Minimizing total completion time on two stage flexible flowshop with uniform parallel machines in the first stage and uniform batch parallel machines in the second stage

李姝嫺(Shu-Shian Li)

指導教授 ： 蘇玲慧

中原大學/電機資訊學院/工業與系統工程研究所/碩士(2013年)

https://doi.org/10.6840/cycu201300823

摘要

本研究探討兩階段彈性流程型工廠包含合批之排程問題，針對不同類型工件排列於第一階段非等效平行機台(Uniform Parallel Machines)，再至第二階段非等效批次平行機台(Uniform Batch Parallel Machines)加工，而批次僅相同類型之工件可合批操作，以總完工時間最小化為目標。
本問題為NP-Hard問題，因此提出啟發式演算法，利用SPT-FOE法將工件分批，以似Backward方式排列批次於第二階段，再依第二階段批次虛擬開始時間排序工件於第一階段以最早完工之機台，以此為基礎並利用貪婪演算法修正機台閒置時間，提早工件完工時間而發展出啟發式演算法。

關鍵字

非等效平行機台 ； 批次 ； 總完工時間 ； 彈性流程型生產 ； 工件類型

並列摘要

This research consider two-stage flexible flow shop with batching scheduling problem. This research have a different type of jobs scheduling, first stage is on uniform parallel machines and the second stage is process of uniform batch parallel machines. The batches only include jobs on the same type. The objective is to minimize the total completion time.
This problem is shown to be NP-Hard, therefore propose a heuristic algorithms. First using SPT-FOE rule batching jobs to arranged batch in the second stage like Backward rule, then with taking the virtual start time of second stage of batch to assign jobs. Furthermore put the earliest completion time in the first stage machine. Basis on this, this research using greedy algorithm to reduce idle time of machine and early jobs of completion time to develop heuristic.

並列關鍵字

flexible flow shop ； total completion time ； batch ； uniform parallel machine ； job type

參考文獻

Ahmadi J. H., Ahmadi R. H., Dasu S., Tang C. S. (1992) “Batching and scheduling jobs on batch and discrete processors”, Operations Research 40 (4), 750-63.

Azizoğlu M., Cakmak E., Kondakci S. (2001) “A flexible flowshop problem with total flow time minimization”, European Journal of Operational Research, 132 (3), 528-38.

Blazewicz J., Dror M., Weglarz J. (1991) “Mathematical programming formulations for machine scheduling: a survey”, European Journal of Operational Research, 51 (3), 283-300.

Cakici E., Mason S. J., Fowler J. W., Geismar H. N. (2013) “Batch scheduling on parallel machines with dynamic job arrivals and incompatible job families”, International Journal of Production Research, 51 (8), 2462-77.

Chandru V., Lee C. Y., Uzsoy R. (1993) “Minimizing total completion time on batch processing machines”, International Journal of Production Research, 31 (9), 2097-121.