考量能源耗用與工作負荷平衡之非相關平行機台排程問題之啟發式解法研究

Metaheuristics for Unrelated Parallel Machines Scheduling Problem with Energy Concern and Workload Balance

麗佩(Rujapa Nanthapodej)

指導教授 ： 劉正祥

國立屏東科技大學/國際學院/熱帶農業暨國際合作系/博士(2022年)

https://doi.org/10.6346/NPUST202200099

摘要

現如今，同時考量環境與經濟因素已是製造業面臨的主要課題之一。因此，企業在進行生產規劃時，不僅要平衡機台負荷，用以提高生產效率，也要積極減少能源的耗用。本研究針對考量能源耗用與機台負荷平衡的非相關平行機台排程進行研究，其目標為最小化總成本。本研究中主要提出結合兩個啟發式演算法：差分進化演算法(Differential Evolution，DE)與自適應大鄰域搜尋法(Adaptive Large Neighborhood Search，ALNS)，進而發展出 HyDE-ALNS 演算法進行求解；同時，也進行模擬實驗評估其求解的品質與效率。模擬實驗中將納入數學規劃模式、差分進化演算法、自適應大鄰域搜尋法、修正式差分進化演算法進行績效比較。根據實驗結果顯示，隨著問題規模的擴大，本研究所發展的 HyDE-ALNS 演算法的求解品質與效率均較其他啟發式演算法優異。

關鍵字

綠色排程 ； 自適應大鄰域搜尋法 ； 混合差分進化演算法 ； 能源耗用 ； 機台負荷平衡 ； 平行機台排程

並列摘要

Environmental and economic considerations create a challenge for manufacturers. The main priority concerns for production planning in green manufacturing industries are reducing energy consumption and improving productivity by optimizing machine efficiency and balancing machine load. This research focuses on minimizing energy consumption and balancing machine-load, which are the indicates of environmental sustainability, on unrelated parallel machine scheduling problem. Therefore, in this study, various methods are proposed in order to solve the problem which are as follow; (1) Mathematical model, (2) Differential Evolution (DE) algorithm, (3) Adaptive Large Neighborhood Search (ALNS), (4) Modified Differential Evolution (MDE) Algorithms, (5) Hybrid Differential Evolution Algorithms and Adaptive Large Neighborhood Search (HyDE-ALNS). A mathematical model was formulated to solve the considered problem and was tested using a set of problem groups as small, medium and large problems. The findings indicated that the mathematical model found an optimal solution within a limited calculation time for some small problems. For medium and large problems, the mathematical model could only found the best bound solution within a limited calculation time and the solution was worse than all metaheuristics. Not all factories have access to computational model within limited time. Thus, metaheuristics, differential evolution (DE) algorithm, and adaptive large neighborhood search (ALNS), modified differential evolution (MDE-1, MDE-2, MDE-3) algorithms, and hybrid differential evolution algorithms and adaptive large neighborhood search (HyDE-ALNS-1, HyDE-ALNS-2, HyDE-ALNS-3) were proposed in this research to solve large-scale of the problem. The new mutation and recombination formula for DE, five new removal methods and one insertion method for ALNS have been proposed in this study for improving solution quality. The experimental results showed that the HyDE-ALNS-3 was the superior method for all problem test instances in term of solution quality and computational time.

並列關鍵字

Green scheduling ； adaptive large neighborhood search ； hybrid differential evolution algorithm ； energy consumption ； machine load balance ； unrelated parallel machine scheduling

參考文獻

References

Abikarram, J. B., McConky, K., and Proano, R. 2019. Energy Cost Minimization for Unrelated Parallel Machine Scheduling under Real Time and Demand Charge Pricing. J. Clean. Prod. 208, 232–242.

Angel, E., Bampis, E., and Kacem, F. 2012. Energy Aware Scheduling for Unrelated Parallel Machines. 2012 IEEE International Conference on Green Computing and Communications. 533-540.

Arnaout, J. P. 2019. A Worm Optimization Algorithm to Minimize the Makespan on Unrelated Parallel Machines with Sequence-Dependent Setup Times. Ann. Oper. Res. 285, 273–293.

Baker, K. R. 1974. Introduction to Sequencing and Scheduling John. New York: Wiley & Sons, Inc.