混合啟發式演算法求解非等效平行機台排程之研究

A Hybrid Metaheuristic for the Unrelated Parallel Machine Scheduling Problem

黃子芸(Tzu-Yun Huang)

指導教授 ： 林東盈

國立清華大學/工學院/工業工程與工程管理學系/碩士(2021年)

摘要

非等效平行機台問題旨在多部功能相似機台，可同時進行加工且不會互相影響，而不同機台的加工效率不盡相同。針對此問題實務上多以人工進行排程，但需要考量的限制及條件繁複，再加上急/插單等突發狀況，人工作業勢難以應付。有鑑於此，本篇研究在考量諸多實務限制條件下，建構一個以模擬退火法(Simulated Annealing)為基礎，結合變鄰域下降法(Variable Neighborhood Descent )之啟發式演算法，針對排程問題，以最小化最晚完工時間(Minimum Makespan)以及符合Burn-In機台加工比例為目標，期能找出符合實務需求之優化排程，研究中考量之限制條件包括每日工時上限、機台可行性、設置時間、Burn In級距限制等。實證結果表明，本研究所提出的方法能解決商業求解軟體無法在短時間內求解之中大型規模問題，且能透過調整參數的方式，適應不同的生產條件，並在有限的時間內求得優化解。

關鍵字

非等效平行機台排程問題 ； 模擬退火法 ； 變鄰域下降法 ； 生產排程 ； 整數規劃

並列摘要

The unrelated parallel machine scheduling problem aims to assign jobs to independent machines with sequence-dependent setup times so that the makespan is minimized. When many practical considerations are introduced, solving the resulting problem is challenging, especially when problems of realistic sizes are of interest. In this study, in addition to the conventional objective of minimizing the makespan, we further consider the burn-in (B/I) procedure that is required in practice; we need to ensure that the scheduling results satisfy the B/I ratio constrained by the equipment. To solve the resulting complicated problem, we propose a population-based simulated annealing algorithm embedded with a variable neighborhood descent technique. Empirical results show that the proposed solution strategy outperforms a commonly used commercial optimization package. It can find the optimal solution for small problem instances and is scalable to solve problem instances of realistic sizes in a limited time.

並列關鍵字

unrelated parallel machine scheduling ； simulated annealing ； variable neighborhood descent ； metaheuristic ； production scheduling ； integer programming

參考文獻

1.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. doi:10.1016/j.cie.2016.05.020

2.Al-Harkan, I. M., & Qamhan, A. A. (2019). Optimize Unrelated Parallel Machines Scheduling Problems With Multiple Limited Additional Resources, Sequence-Dependent Setup Times and Release Date Constraints. Ieee Access, 7, 171533-171547. doi:10.1109/Access.2019.2955975

3.Bai, D. Y., Zhang, Z. H., & Zhang, Q. (2016). Flexible open shop scheduling problem to minimize makespan. Computers & Operations Reearch, 67, 207-215. doi:10.1016/j.cor.2015.10.012

4.Che, A., Wu, X. Q., Peng, J., & Yan, P. Y. (2017). Energy-efficient bi-objective single-machine scheduling with power-down mechanism. Computers & Operations Research, 85, 172-183. doi:10.1016/j.cor.2017.04.004

5.Cheng, C. Y., & Huang, L. W. (2017). Minimizing total earliness and tardiness through unrelated parallel machine scheduling using distributed release time control. Journal of Manufacturing Systems, 42, 1-10. doi:10.1016/j.jmsy.2016.10.005