Improving Robustness For Stochastic Parallel Machine Scheduling With Robustness Measures

Abstract

In this thesis we look at the stochastic parallel machine scheduling problem with precedence constraints, release dates and a deadline. To deal with uncertainty in the job processing times, it is desirable to create robust schedules. Because many machine scheduling problems are complex, they are often solved with local search methods. To include robustness into the objective of a local search approach, an efficient way to quantify the robustness of a solution is required. Since exact computation of the robustness of a schedule is complex and simulation is computationally expensive, the need for surrogate robustness measures arises. Therefore, we evaluated several existing and new proposed robustness measures on their ability to estimate the true robustness, with the aim of creating stable baseline schedules bounded by a deadline. We compared the estimates of the robustness measures with the results of a Monte Carlo simulation by reporting their Spearman’s rank correlation coefficients for various notions of robustness and several processing time probability distributions. Furthermore, we implemented a local search algorithm which uses the robustness measures to evaluate the quality of the schedule. We showed the effectiveness of robustness measures as indicators of true robustness and their practical application in generating stable baseline schedules.