A Hybrid Metaheuristic for the Unrelated Parallel Machine Scheduling Problem

Dung-Ying Lin and Tzu-Yun Huang
Additional contact information
Dung-Ying Lin: Department of Industrial Engineering and Engineering Management, National Tsing Hua University, Hsinchu 30013, Taiwan
Tzu-Yun Huang: Department of Industrial Engineering and Engineering Management, National Tsing Hua University, Hsinchu 30013, Taiwan

Mathematics, 2021, vol. 9, issue 7, 1-20

Abstract: 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 obtain schedules that are better than the schedules used in practice, and it does so in a more efficient manner.

Keywords: unrelated parallel machine scheduling; simulated annealing; variable neighborhood descent; metaheuristic; production scheduling (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2021
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
https://www.mdpi.com/2227-7390/9/7/768/pdf (application/pdf)
https://www.mdpi.com/2227-7390/9/7/768/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jmathe:v:9:y:2021:i:7:p:768-:d:528578

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().