Unrelated parallel machine scheduling problem with setup times and additional resources: an enhanced metaheuristic to address resource-related infeasibilities

Abstract

Efficient scheduling tools are essential for managing production environments where both machine availability and additional resource constraints play a significant role. This paper addresses the Unrelated Parallel Machine scheduling problem with setup times and additional resources in the Setups (UPMSR-S), an NP-hard problem that models real-world production settings where setups require limited resources, such as personnel or specialized equipment. We propose an enhanced algorithm designed to better handle resource-related infeasibilities and consistently outperform state-of-the-art methods. This is demonstrated through an extensive computational campaign on 1,000 benchmark instances, with improvements in Relative Percentage Deviation (RPD) exceeding 70% for several instance sizes. The proposed approach is well suited to large production environments involving setup and resource constraints, showing strong performance in challenging scheduling settings. Statistical analysis confirms that the method is highly effective across a wide range of instance sizes and scenarios, with particularly strong performance as the number of jobs and machines increases.