Delft University of Technology
Faculty Mechanical, Maritime and Materials Engineering
Transport Technology / Logistic Engineering

J.J.A. Budding A genetic algorithm for the multi-mode resource constraint project scheduling problem.
Computer program, Report 98.3.LT.5042, Transport Technology, Logistic Engineering.

In this report a genetic algorithm for solving multi-mode resource constrained project scheduling problems (MMRCPSP's) is described. The MMRCPSP is a problem in which a number of activities must be scheduled, subject to constaints of order (some activities cannot start untill others are finished) and available resources per unit time. An activity can be performed in a number of modes, i.e. combinations of duration and resource requirements. The goal is to minimize project duration.

In literature an algorithm is described to optimize the MMRCPSP through finite steps. For large and complex problems however this method becomes computationaly unfeasible. In the Genetic Algorithm (GA) described in this paper, an optimal solution is sought for in a process of evolution through natural selection. The genetic algorithm starts by creating a population of random schedules, and then simulates a process of evolution in which the schedules with minimum makespan move on to the next generation, and evolve through genetic operators such as mutation and crossing over. To test this algorithm on a number of complex and diverse MMRCPSP's, a random activity network generator was programmed. The algorithms underlying this generator are described. Also a description is given of a GA-application developed in Delphi, using the algorithms described.

This report is entirely based on a paper by M. Mori and C.C. Tseng, "A genetic algorithm for the multi-mode resource constrained project scheduling problem" (European Journal of Operational Research, Vol.100 No.1 (1997) pp.134-141), and a paper by E. Demeulemeester, B. Dodin and W.S. Herroelen, "A Random Activity Network Generator" (Operations Research, Vol.41 No.5 (1993) pp.972-980).

Reports on Logistic Engineering (in Dutch)
Modified: 2000.02.27; , TU Delft / 3mE / TT / LT.