A robust optimization approach for the unrelated parallel machine scheduling problem

Abstract

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.

Appendix A: Additional computational results

See Tables 6, 7, and 8.

Table 6 Average computational results for different values of $\Gamma$

Table 7 Average computational results for different values of ${\delta }$

Table 8 Average objective function cost (OF), expected cost of the solution (Exp. Cost), price of robustness (PoR), and empirical probability of constraints violation (Risk) for the different sets of instances with ${\delta }=0.5$