Improved Genetic Algorithm for Finance-Based Scheduling

Abstract

Currently, the genetic algorithm (GA) technique has been used in finance-based scheduling to devise critical path method (CPM) schedules exhibiting cash flows of periodical finance needs below preset cash constraints. The chromosomes of the schedules that violate this condition are referred to as finance-infeasible chromosomes. Infeasibility related to finance is peculiar to finance-based scheduling problems. In scheduling problems, chromosomes that are infeasible based on precedence relationships are typically penalized. This paper introduces a repair algorithm for the finance-infeasible chromosomes generated within the GA systems. The repair algorithm identifies the periods exhibiting finance needs that exceed the constrained cash, calculates the amounts of finance needs above the constraints, identifies the ongoing activities, selects randomly an activity for delaying its start time, determines the impact of the delay on the finance needs, and repeats the procedure until finance feasibility is attained. A 13-activity project was used to demonstrate the proposed repair algorithm. The performance of the repaired-chromosome GA system is evaluated through comparison against replaced-chromosome and penalized-chromosome GA systems using a fairly big project of 210 activities. Finally, the results that were validated using the integer programming technique proved the superior performance of the repaired-chromosome GA in terms of the computational cost and quality of solutions.