Optimize the Activity-on-Arc Network Planning Through the Structure Matrix and Genetic Algorithm

Abstract

The resource-constrained project scheduling problem (RCPSP) poses several challenges for optimizing activity-on-arc network planning. The existing genetic algorithms for solving this problem have high computational complexity and low efficiency in terms of running and optimization. To address this issue, this study proposes an algorithm based on the structure matrix and genetic algorithm (SM-GA). First, information about activities in the activity-on-arc network was represented in the structure matrix (SM), and a data storage format and a coordinate-coded structure were constructed. Then, a chromosome correction operator and serial schedule generation scheme were designed based on the SM. Further, an adaptive probability operator, along with its related similar-uniform crossover operator and hybrid mutation operator, were designed based on the level of population diversity. Finally, Python programs were written in combination with a case study, and the efficiency of the algorithm was statistically analyzed from two aspects: data formats, and operators. SM-GA enhances the running efficiency by approximately 36 times compared to the genetic algorithm using a traditional data format. Compared to the genetic algorithm using traditional crossover and mutation operators, SM-GA improves the optimization efficiency by approximately four times. The results show that SM-GA could solve the RCPSP of activity-on-arc network planning more efficiently.

Keywords

• Activity-on-arc network
• genetic algorithm
• resource-constrained project scheduling problem (RCPSP)
• structure matrix