Resource-Constrained Project Scheduling

Chan Wai Kin

Abstract

Traditionally, Linear Programming (LP) has always been used to solve scheduling problems including resource-constrained ones. Though it provides the best possible solution to a scheduling problem, researches have shown that for larger problems, it takes a considerable amount of time for LP to generate a solution. Recent developments in optimizations have led to the evolution of other search methods such as Tabu Search and Genetic Algorithms. The quality of solutions obtained from these methods are inferior to that obtained from LP, but this sacrifice of quality may be worthwhile as these methods generally take a relatively shorter time to generate a reasonably good solution. It is well known that the run time of LP escalates as the problem size grows larger. The objective of this project is to investigate the capabilities of Genetic Algorithms (GA) in generating near-optimal solutions.

Genetic Algorithms was developed by John Holland[1975] who was inspired by the ability of biological systems to adapt to their environment and eventually evolve into highly successful organisms over many generations. GA involves generating a population of feasible solutions, measuring their fitness and selecting solutions to be crossover or mutated to produce new solutions for the next population. This process will gradually transform the population and the solutions will converge to the near optimal.

The application of GA to RCPS problems requires the representation of chromosome in the form of an array of project start times. Algorithms are formulated to generate the initial population, select chromosomes according to the tournament method and conduct crossover and mutation operations. A wastage variable or fitness is defined to judge the quality of the solutions obtained.

The results obtained from GA were compared to those from the Mixed Integer Programming (MIP) and the results proved that MIP outperformed GA for small sized problem. Sensitivity analysis were conducted to investigate the effects of varying the makespan, number of generations and operator probabilities on the wastage values. The results obtained showed that a mixed use of crossover and mutation produce better solutions as compared to the use of a single operator. The drawback is that the run time will increase with the use of both operators as compared to the use of only crossover.

The project proved that for small sized problems such as the 38 projects case study, MIP is preferred over GA. However the situation is reversed when tackling larger problems. It is well known that the run time of MIP increases exponentially. GA performs better than MIP in terms of the speed in generating a solution, producing a solution that is inferior to that of the MIP solution. Thus there is a trade-off between the quality of the solution and the speed in generating it. This sacrifice may be worthwhile especially when the time taken for MIP to come out with a solution is long.