A hybrid multi-objective EDA for robust resource constraint project scheduling with uncertainty. (April 2019) - Tian, Jing; Hao, Xinchang; Gen, Mitsuo
Highlights: New RCSP model with bi-objective under chance constraint is formulated. Two novel robustness measures based on time and capacity are proposed. One robust MOEA is developed by using hybrid GA and Markov network based EDA. Experiments are designed to demonstrate effective and tolerant of uncertainty. Abstract: This paper presents a multi-phased algorithm hybrid genetic algorithm and multi-objective Markov network based Estimation of Distribution Algorithm (robust hGMEDA), to solve the robust scheduling problem for resource constrained scheduling problem (RCSP) with time uncertainty. Firstly, for modelling, two kinds of robust measures on time-based-robust and capacity-based-robust are introduced to evaluate the robustness of scheduling solutions. Secondly, for solving methodology, within the multi stage architecture based on sequential co-evolutionary paradigm, genetic algorithm (GA) is used to find feasible solution for sequencing sub-problem, and multi-objective Markov network based Estimation of Distribution Algorithm (MMEDA) is adopted to model the interrelation for resource allocation and calculate the Pareto set with the scenario based approach. Next, the alternative solutions are checked by the chance constraints by using scenario-based simulation. Moreover, one problem-specific local search with considering both makespan and robustness is designed to improve the solution quality. The implementation results provide practical support that experiment results based on a benchmark "Project Scheduling Problems Library" (PSPLIB) and comparisons demonstrate that our approach is highly effective and tolerant of uncertainty.