ET-RCPSP: a novel RCPSP variant with earliness-tardiness penalties solved by enhanced evolutionary algorithm

Hao Nguyen Thi, Loc Nguyen The, Huu Dang Quoc

Abstract


The resource-constrained project scheduling problem (RCPSP) and its multi-skill variant (MS-RCPSP) are widely applied in manufacturing, logistics, construction, and software project management. Existing research predominantly focuses on minimizing total project completion time, with limited consideration of practical costs incurred when tasks finish earlier or later than their specified due dates. This study introduces the earliness-tardiness RCPSP (ET-RCPSP), which incorporates task-specific earliness-tardiness penalties to achieve more realistic schedule efficiency. To address this NP-hard problem, we propose an enhanced earliness-tardiness genetic algorithm (ET-GA) with two novel mechanisms: i) priority resource allocation for independent tasks to reduce early-phase congestion and ii) elitism preservation to enhance convergence and stability. Experimental results on the iMOPSE benchmark demonstrate that ET-GA achieves optimal or near-optimal solutions on 90% of test instances, with average earliness-tardiness penalties reduced by 98.71%, 99.24%, and 99.19% compared to differential evolution (DE), standard genetic algorithm (GA), and particle swarm optimization (PSO), respectively. ET-GA exhibits exceptional consistency, with 40% perfect reproducibility (where the best result equals the average), while baseline algorithms achieve 0%. Statistical tests confirm substantial improvements (Wilcoxon signed-rank, p<0.000001), demonstrating the method's effectiveness for practical multi-skill project scheduling with earliness-tardiness considerations.

Keywords


Earliness-tardiness; Evolutionary algorithm; Multi-skill resource-constrained project scheduling problem; NP-hard problem; Project scheduling

Full Text:

PDF


DOI: https://doi.org/10.11591/eei.v15i6.12147

Refbacks

  • There are currently no refbacks.


Creative Commons License
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.

Bulletin of EEI Statistics

Bulletin of Electrical Engineering and Informatics (BEEI)
ISSN: 2089-3191 , e-ISSN: 2302-9285
This journal is published by the Institute of Advanced Engineering and Science (IAES) .