A Continuous-Time Formulation for the Unrelated Parallel Machine Scheduling Problem with Setup Times and Additional Resources in the Setups

Abstract

Production planning in environments with unrelated parallel machines, sequence-dependent setup times and scarce auxiliary resources can be formalized as the Unrelated Parallel Machine scheduling problem with setup times and additional resources in the setups (UPMSR-S), an NPhard problem that arises in several industrial contexts where setup operations consume limited resources such as skilled operators or specialized equipment. We introduce a new mathematical formulation for the UPMSR-S that significantly reduces the number of decision variables while preserving the essential interactions between machine assignment, job sequencing, setup times, and resource availability. By compactly modelling resource-dependent setup feasibility, the proposed formulation improves scalability and provides a more efficient basis for solution methods. Computational experiments on a large benchmark set show that the new formulation leads to substantial reductions in model size and computational effort when compared with existing formulations, while maintaining solution quality. These results highlight the effectiveness of the proposed formulation for tackling large and difficult scheduling instances, and demonstrate its potential as a robust modelling framework for advanced solution approaches in production environments with setup and resource constraints