An evolutionary algorithm for the resource-constrained project scheduling problem with minimum and maximum time lags

作者：Ballestin Francisco^*; Barrios Agustin; Valls Vicente

来源：Journal of Scheduling, 2011, 14(4): 391-406.

DOI：10.1007/s10951-009-0125-9

• Resource-constrained project scheduling
• Maximum time lags
• Meta-heuristic algorithms

In this paper, we present an evolutionary algorithm (EVA) for solving the resource-constrained project scheduling problem with minimum and maximum time lags (RCPSP/max). EVA works on a population consisting of several distance-order-preserving activity lists representing feasible or infeasible schedules. The algorithm uses the conglomerate-based crossover operator, the objective of which is to exploit the knowledge of the problem to identify and combine those good parts of the solution that have really contributed to its quality. In a recent paper, Valls et al. (European J. Oper. Res. 165, 375-386, 2005) showed that incorporating a technique called double justification (DJ) in RCPSP heuristic algorithms can produce a substantial improvement in the results obtained. EVA also applies two double justification operators DJmax and DJU adapted to the specific characteristics of problem RCPSP/max to improve all solutions generated in the evolutionary process. Computational results in benchmark sets show the merit of the proposed solution method.

• 出版日期2011-8