LAUSR

Abstract This paper proposes a robust scheduling method based on hybridization of EDA and GA, dealing with resource constrained scheduling problems with uncertainty of activity duration times. Two kinds of robust measures on time-based-robust and capacity-based-robust are introduced to evaluate the robustness of scheduling solutions, and the robust scheduling problem is formulated as bi-objective of minimizing makespan and maximizing time based robustness under a chance constraint of satisfying the threshold of capacity based robustness. By using scenario-based simulation, a stochastic multi-phased robust optimization method is proposed. In the first phase, with the average duration, the problem is solved as the deterministic multi-objective scheduling problem without considering duration uncertainty and chance constraints, and some candidate solutions are collected. In the second phase, the alternative solutions are checked by the chance constraints of capacity-based-robust measure and then, robustness measure is evaluated by using scenario-based simulation. Moreover, one problem-specific local search with considering both makespan and robustness is designed to increase the solution quality. Experiment results based on a benchmark (PSPLIB) and comparisons demonstrate that our approach is highly effective and tolerant of uncertainty.