Precedence-Preserving GAs Operators for Scheduling Problems with Activities’ Start Times Encoding

Abstract

Precedence-preserving crossover and mutation operators for scheduling problems with activities’ start times encoding are proposed and employed in this paper. The objective is to tackle the incapability of the genetic algorithms (GAs) operators to preserve the precedence relationships among activities and generate feasible solutions in scheduling problems. The proposed operators employ an embedded precedence-preserving algorithm that determines the activities’ forward free float and backward free float and utilize them in randomly selected backward and forward paths, respectively. The proposed operators were evaluated using finance-based scheduling problems for large-scale projects of 120 repetitive activities. Moreover, the proposed operators were validated by comparing the results with the optimum results of a resource-constrained scheduling problem reported in the literature. The results exhibited the robustness of the proposed operators to reduce the computational costs. In addition, the results demonstrated the high potential and effectiveness of the proposed operators to capture the optimal solutions of the problems considered.