Optimisation Algorithms for Parallel Machine Scheduling Problems with Setup Times

Kittel, Fabian; Enekel, Jannik; Guckert, Michael; Holznigenkemper, Jana; Urquhart, Neil

Abstract

Parallel machine scheduling is a problem of high practical relevance for the manufacturing industry. In this paper, we address a variant in which an unweighted combination of earliness, tardiness and setup times aggregated in a single objective function is minimised. We compare an Evolutionary Algorithm (EA) approach with a variant of local search implementing a probabilistic Best Response Dynamic algorithm (p-BRD) inspired by game theoretic considerations. Our p-BRD algorithm achieved promising results outperforming the EA on a series of test sets.

• Presentation Conference Type: Conference Paper (Published)
• Conference Name: Genetic and Evolutionary Computation Conference (GECCO '21)
• Start Date: Jul 10, 2021
• End Date: Jul 14, 2021
• Acceptance Date: Mar 26, 2021
• Online Publication Date: Jul 7, 2021
• Publication Date: 2021
• Deposit Date: Apr 8, 2021
• Publicly Available Date: Apr 12, 2021
• Publisher: Association for Computing Machinery (ACM)
• Pages: 131-132
• Book Title: GECCO '21: Proceedings of the Genetic and Evolutionary Computation Conference Companion
• ISBN: 978-1-4503-8351
• DOI: https://doi.org/10.1145/3449726.3459487
• Keywords: Best Response Dynamics, Parallel Machine Scheduling with Setup Times, Heuristics
• Public URL: http://researchrepository.napier.ac.uk/Output/2759790