摘要
In this paper, we study an important real-life scheduling problem that can be formulated as an unrelated parallel machine scheduling problem with sequence-dependent setup times, due dates, and machine eligibility constraints. The objective is to minimise total tardiness and makespan. We adapt and extend a mathematical model to find optimal solutions for small instances. Additionally, we propose several variants of simulated annealing to solve very large-scale instances as they appear in practice. We utilise several different search neighbourhoods and additionally investigate the use of innovative heuristic move selection strategies. Further, we provide a set of real-life problem instances as well as a random instance generator that we use to generate a large number of test instances. We perform a thorough evaluation of the proposed techniques and analyse their performance. We also apply our metaheuristics to approach a similar problem from the literature. Experimental results show that our methods are able to improve the results produced with state-of-the-art approaches for a large number of instances.
学科与关键词
- A Hybrid Metaheuristic for the Unrelated Parallel Machine Scheduling ProblemLin, Dung-Ying*; Huang, Tzu-YunMathematics, 2021, 9(7): 768.被引 10
- Minimising total tardiness for the identical parallel machine scheduling problem with splitting jobs and sequence-dependent setup timesKim, Jae-Gon; Song, Seokwoo; Jeong, BongJoo*International Journal of Production Research, 2020, 58(6): 1628-1643.被引 38
- A Statistical Comparison of Metaheuristics for Unrelated Parallel Machine Scheduling Problems with Setup TimesAntunes, Ana Rita; Matos, Marina A.; Rocha, Ana Maria A. C.*; Costa, Lino A.; Varela, Leonilde R.Mathematics, 2022, 10(14): 2431.被引 4
