A robust optimization approach for the unrelated parallel machine scheduling problem

In this paper, we address the Unrelated Parallel Machine Scheduling Problem (UPMSP) with sequence- and machine-dependent setup times and job due-date constraints. Different uncertainties are typically involved in real-world production planning and scheduling problems. If ignored, they can lead to suboptimal or even infeasible schedules. To avoid this, we present two new robust optimization models for this UPMSP variant, considering stochastic job processing and machine setup times. To the best of our knowledge, this is the first time that a robust optimization approach is used to address uncertain processing and setup times in the UPMSP with sequence- and machine-dependent setup times and job due-date constraints. We carried out computational experiments to compare the performance of the robust models and verify the impact of uncertainties to the problem solutions when minimizing the production makespan. The results of computational experiments indicate that the robust models incorporate uncertainties appropriately into the problem and produce effective and robust schedules. Furthermore, the results show that the models are useful for analyzing the impact of uncertainties in the cost and risk of the scheduling solutions.