A Knowledge-Based Evolutionary Multiobjective Approach for Stochastic Extended Resource Investment Project Scheduling Problems

作者：Xiong, Jian^*; Liu, Jing; Chen, Yingwu; Abbass, Hussein A.

来源：IEEE Transactions on Evolutionary Computation, 2014, 18(5): 742-763.

DOI：10.1109/TEVC.2013.2283916

• Combinatorial optimization
• evolutionary application
• knowledge-based evolutionary algorithm
• stochastic extended resource investment project scheduling problems (SERIPSPs)

Planning problems, such as mission capability planning in defense, can traditionally be modeled 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 RIPSPs, namely extended RIPSPs (ERIPSPs), 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 ERIPSPs, namely stochastic extended RIPSPs (SERIPSPs). To solve SERIPSPs, 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 SEPIPSPs when uncertainties interact. We then formulate an SERIPSP as a multiobjective optimization model with three optimization objectives: makespan, cost, and robustness. A knowledge-based multiobjective evolutionary algorithm (K-MOEA) is proposed to solve the problem. The mechanism of K-MOEA is simple and time efficient. The algorithm has two main characteristics. The first is that useful information (knowledge) contained in the obtained approximated nondominated 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 SERIPSPs.

• 出版日期2014-10
• 单位西安电子科技大学; 中国人民解放军国防科学技术大学