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;
logistics@3mE.tudelft.nl
, TU Delft
/ 3mE
/ TT
/ LT.