等速率平行機台在工件具有抵達時間和群組限制下求解最小化總延遲時間之排程問題

Minimizing total tardiness on uniform parallel machine with job arrival and incompatible job families

朱良琪(Liang-Chi Chu)

指導教授 ： 蘇玲慧

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

https://doi.org/10.6840/cycu201300739

摘要

本研究探討等速率平行機台(Uniform Parallel Machine)之排程問題，考慮n個工件f個群組在m台等速率平行機台上加工，工件具有抵達時間和群組限制，同一部機台上，如果正準備處理的工件與上一個工件所屬群族不同時，則必須加上整備時間。本研究以總延遲時間最小化為目標。
首先，利用啟發式演算法，將群組排入機台，以減少整備時間，再利用貪婪演算法找出重複時間(Overlap)較大的群組，移除工件並嘗試排入機台上每個位置，排入機台時需考慮工件之抵達時間，直到找到最小總延遲時間則停止。本研究在機台數為30台、群組數為50個、工件量為512個，當處理時間為[1,100]時，求解時間為248.02秒。

關鍵字

等速率平行機台 ； 群組限制 ； 抵達時間 ； 總延遲時間

並列摘要

We consider the problem of scheduling n jobs with f families on m uniform parallel machines. Every job has arrival time and belongs to one family. We have to add setup time when machine is processing one job( this job’s family is different to last job ). Our objective is to minimize total tardiness.
First, we use heuristic assign family into machine for reducing setup time then we find families with greater overlap and using greedy algorithm to remove jobs from machine . For those jobs witch are removed we try assign them into every position. When we are assigning jobs into machine , we must consider it’s arrival time. The average execution time of problem with 30 machines, 50 families, 512 jobs and processing time [1,00] can be solved in 286.79 seconds.

並列關鍵字

uniform parallel machine ； job arrival ； incompatible job families ； total tardiness

參考文獻

Pfund, Michele, Fowler, John W, and Gupta, Jatinder ND (2004), 'A survey of algorithms for single and multi-objective unrelated parallel-machine deterministic scheduling problems', Journal of the Chinese Institute of Industrial Engineers, 21 (3), 230-41.

Alidaee, Bahram and Rosa, Duane (1997), 'Scheduling parallel machines to minimize total weighted and unweighted tardiness', Computers & Operations Research, 24 (8), 775-88.

Arkin, Esther M and Roundy, Robin O (1991), 'Weighted-tardiness scheduling on parallel machines with proportional weights', Operations Research, 39 (1), 64-81.

Azizoglu, Meral and Kirca, Omer (1998), 'Tardiness minimization on parallel machines', International Journal of Production Economics, 55 (2), 163-68.

Biskup, Dirk, Herrmann, Jan, and Gupta, Jatinder N. D. (2008), 'Scheduling identical parallel machines to minimize total tardiness', International Journal of Production Economics, 115 (1), 134-42.