等效平行機台在工件可切割且有整備時間下求解最小化總完工時間之排程問題

Parallel machine scheduling with splitting jobs and setup times to minimize total completion times.

張維真(Wei-Chen Chang)

指導教授 ： 蘇玲慧

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

https://doi.org/10.6840/cycu201200759

摘要

本研究探討等效平行機台(Identical Parallel Machine)之排程問題，考慮n個工件在m台等效平行機台上加工，工件具整備時間。工件可切割至其他機台同時進行加工，但只要工件切割，則必須加上整備時間。本研究以總完工時間最小化為目標，數學表示式為 。
首先，將所有工件之整備及作業時間相加後，以SPT法排序，再依序排入可最早開始進行加工之機台，此方法可得到 問題之最佳解。在本研究中提出五個Lemmas以證明只需切割每機台上最後一個工件可以得到最佳解。本研究提出以數學規劃模式為基礎之反覆演算法，實驗證明此方法是有效率的。本研究在n=1025, m=50，當工件之處理時間為 時，平均求解時間為1.568秒，當工件之處理時間為 時，平均求解時間為1.578秒。

關鍵字

等效平行機台 ； 工件可切割 ； 總完工時間 ； 整備時間

並列摘要

We consider the problem of scheduling n jobs on m identical parallel machines with job setup time. Job can split arbitrarily to any machine with setup time incurred. Our objective is to minimize total completion and the problem is denoted as .
We first sequence the job with the smallest sum of setup time and processing time to the earliest available machine. This rule gives the optimal solution to the problem. Five lemmas are proposed to prove that the optimal solution can be obtained by splitting only the last positional job on each machine. A Linear Programming model is developed to formulate this scheduling problem into an iterative procedure. Computational results indicate that our iterative algorithm is effective. The average execution time of the problem with n = 1025 combined with m = 50 and processing time and can be solved in 1.568 seconds and 1.578 seconds on average,respectively.

並列關鍵字

setup time ； total completion time ； splitting jobs ； identical parallel machine

參考文獻

Allahverdi, A., Ng, C.T., Cheng, T.C.E, Kovalyov, M.Y.(2008)“A survey of scheduling problems with setup times or costs”, European Journal of Operational Research 187, 985-1032.

Allahverdi, A., Gupta, N.D.J., Aldowaisan, T.(1999). “A review of scheduling research involving setup considerations”, Omega, The International Journal of Management Science 27, 219-239.

Chen, Z. L. (1996). “Parallel machine scheduling with time dependent processing times”, Discrete Applied Mathematics 70, 81-93.

Cheng, B., Yang, S., Hu, X., Chen, B.(2012). “Minimizing makespan and total completion time for parallel batch process machines with non-identical job sizes”, Applied Mathematical Modelling 36, 3161-3167.

Cheng, T. S. E., Chen, Z. L. (1994). “Parallel machine scheduling with batch setup times”, Operational Research 42, 1171-4.