An Effective Multi-objective EDA for Robust Resource Constrained Project Scheduling with Uncertain Durations

AbstractProject scheduling is a complex process involving many resource types and activities that require optimizing. The resource- constrained project scheduling problem (rcPSP) is one of well-known NP-hard problems where activities of a project must be scheduled to minimize the project duration. This paper presents a stochastic multiple mode resource constrained project scheduling problem (S-mrcPSP) with the uncertainty of durations. An effective multi-objective estimation distribution algorithm (moEDA) is proposed to solve S-mrcPSP to minimize its robustness and expected makespan. The proposed moEDA employs Markov network modelling activity assignment where the effects between decision variables are represented as an undirected graph model. Furthermore, slack-based metric based assessing algorithm is used to measure the robustness, where a free slack based heuristic method is adopted to achieve better performance. We demonstrate an empirical validation for the proposed method by applying it to solve various benchmark resource constrained project scheduling problems