考慮機台與資源限制下平行機台總完工時間最小化問題

Minimize the total completion times on parallel machines subject to both machine eligibilities resource constraints

蔡誌翔(Zhi-Xiang Cai)

指導教授 ： 蘇玲慧

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

https://doi.org/10.6840/cycu201700719

摘要

本研究探討平行機台(Parallel machine)在有資源與機台限制下之排程問題，由於工件在每個機台上處理時間皆相同，故為等效平行機台(Identical Parallel Machine)。資源可被分派至可使用的工件，工件可以使用的資源有很多種，但是在機台上處理時僅能選擇使用其中一種。機台限制是指並非所有機台都可以加工所有的工件。工件有抵達時間(Arrival time)，必須在抵達時間後才可以開始加工，目標為總完工時間最小化，數學式表示為├ P┤| A_j ,〖Eg〗_ji ,〖res〗_jv |∑_(j=1)^n▒C_j ┤。

本研究問題為NP-hard，因此本研究提出啟發式演算法及數學規劃模型，藉由數學規劃模型得到之最佳解，並且提出一啟發式演算法比較兩個結果之差距。啟發式演算法利用LFM決定機台的第一個工件以及利用SPT將剩餘工件排入來進行求解，結果顯示在工件n=6、8、10時得到的平均誤差為3.49％，而啟發式演算法得執行時間不到1秒比起數學規劃模型的執行時間要來的快。

關鍵字

機台限制 ； 平行機台 ； 最小化總完工時間 ； 資源限制

並列摘要

This study considers the identical parallel machine scheduling problem with arrival times, machine eligibility and resource constraints. Machine eligibility means that not all machines can process all jobs. Each job requires resource. There is upper limit on each resource. Each jobs must be processed after the arrival time. The objective is to minimize the total completion time and the problem is denote as ├ P┤| A_j ,〖Eg〗_ji ,〖res〗_jv |∑_(j=1)^n▒C_j ┤.

Because the problem is NP-hard, this study presents a heuristic algorithm to solve the problem within a short time and an integer programming model to solve the problem optimality. The solution of the heuristic algorithm is compared with the optimal solution of integer programming. The heuristic algorithm uses LFM rules to discharge the first jobs of all machines and SPT rules to sort the remaining jobs. The heuristic algorithm has an average execution time of less than 1 second.

並列關鍵字

machine eligibility ； parallel machine ； total completion time ； resource constraint

參考文獻

Afzalirad, M., & Rezaeian, J. (2016). Resource-constrained unrelated parallel machine scheduling problem with sequence dependent setup times, precedence constraints and machine eligibility restrictions. Computers & Industrial Engineering, 98, 40-52.

Centeno, G., & Armacost, R. L. (2004). Minimizing makespan on parallel machines with release time and machine eligibility restrictions. International Journal of Production Research, 42(6), 1243-1256.

Chen, J.-F. (2005). Unrelated parallel machine scheduling with secondary resource constraints. The International Journal of Advanced Manufacturing Technology, 26(3), 285-292.

Chen, J.-F., & Wu, T.-H. (2006). Total tardiness minimization on unrelated parallel machine scheduling with auxiliary equipment constraints. Omega, 34(1), 81-89.

Chung, T.-P., Liao, C.-J., & Su, L.-H. (2010). Scheduling on identical machines with batch arrivals. International Journal of Production Economics, 123(1), 179-186.