Iterated greedy with strategic reconstruction for parallel machine problem with weighted tardiness and setup times

Abstract On-time delivery is becoming increasingly crucial for industrial companies, due to their customers’ need for deliveries by specific dates. This paper investigates parallel machine scheduling problems with sequence-dependent setup times, a combinatorial challenge that has gained significant attention due to its practicality and relevance in real-world applications. Aiming to reduce total weighted tardiness, we introduce a mixed integer linear programming model and an effective iterated greedy approach with a strategic reconstruction operator. We evaluate the performance of our methods by comparing it with six well-established and related approaches. Our experiments, using a benchmark set of 900 instances, validate that the introduced iterated greedy algorithm consistently produces high-quality solutions.