Knowledge-based Evolutionary Multi-objective Approach for Stochastic Extended Resource Investment Project Scheduling Problems

Planning problems, such as mission capability planning in defence, can traditionally be modelled as a resource investment project scheduling problem (RIPSP) with unconstrained resources and cost. This formulation is too abstract in some real-world applications. In these applications, the durations of tasks depend on the allocated resources. In this paper, we first propose a new version of RIPSP, namely extended RIPSP (ERIPSP), in which the durations of tasks are a function of allocated resources. Moreover, we introduce a resource proportion coefficient to manifest the contribution degree of various resources to activities. Since the more realistic nature of projects in practice implies that the circumstances under which the plan will be executed are stochastic in nature, we present a stochastic version of ERIPSP, namely SERIPSP. To solve SERIPSP, we first use scenarios to capture the space of possibilities (i.e. stochastic elements of the problem). We focus on three sources of uncertainty: duration perturbation, resource breakdown and precedence alteration. We propose a robustness measure for the solutions of SEPIPSP when uncertainties interact. We then formulate SERIPSP as a multi-objective optimization model with three optimization objectives: makespan, cost, and robustness. A knowledge-based multi-objective evolutionary algorithm (KMOEA) is proposed to solve the problem. The mechanism of KMOEA is simple and time efficient. The algorithm has two main characteristics: The first is that useful information (knowledge) contained in the obtained approximated non-dominated solutions is extracted during the evolutionary process. The second is that extracted knowledge is utilized by updating the population periodically to guide subsequent search. The approach is illustrated using a synthetic case study. Randomly generated benchmark instances are used to analyze the performance of the proposed K-MOEA. The experimental results illustrate the effectiveness of the proposed algorithm and its potential for solving SERIPSP.