Multi-Project Scheduling using Competent Genetic Algorithms

In a multi-project environment, many projects are to be completed that rely on a common pool of scarce resources. In addition to resource constraints, there exist precedence relationships among activities of individual projects. This project scheduling problem is NP-hard and most practical solutions that can handle large problem instances rely on priority-rule heuristics and meta-heuristics rather than optimal solution procedures. In this paper, a Competent Genetic Algorithm (CGA), hybridized with a local search strategy, is proposed to minimize the overall duration or makespan of the resource constrained multi-project scheduling problem (RCMPSP) without violating inter-project resource constraints or intra-project precedence constraints. The proposed Genetic Algorithm (GA) with several varied parameters is tested on sample scheduling problems generated according to two popular multi-project summary measures, Average Utilization Factor (AUF) and Average Resource Load Factor (ARLF). The superiority of the proposed CGA over simple GAs and well-known heuristics is demonstrated