Keywords: construction management, project management, evolutionary algorithms, simulation, scheduling, genetic algorithms, random keys, RCPSP.

Nowadays, construction projects grow in complexity and size. So, finding feasible schedules which efficiently use scarce resources is a challenging task within project management. In this context, the well-known resource constrained project scheduling problem (RCPSP) has been studied during the last decades. Project scheduling consists of determining the starting and finishing times of the activities in a project. These activities are linked by precedence relations and their processing requires one or more resources. The resources are renewable, that is, the availability of each resource is renewed at each period of the planning horizon. The objective of the RCPSP problem is minimizing the makespan. While the exact methods are available for providing an optimal solution for small problems, its computation time is not feasible for large-scale problems, see Mendes [4].

This paper presents an evolutionary algorithm (EVA) for the resource constrained project scheduling problem. The idea of this new approach is to integrate a genetic algorithm with a discrete system simulation. This study also proposes applying a local search (LS) procedure trying to yield a better solution when EVA obtains a solution.

The chromosome representation of the problem is based on random keys, see [1,2,3]. The dynamic behaviour of the system simulation is studied by tracing various system states as a function of time and then collecting and analysing the system statistics. The events that change the system state are generated at different points in time, and the passage of time is represented by an internal clock which is incremented and maintained by the simulation program. The simulation strategy is the event oriented simulation where the clock is incremented from time t to the next event time t', see Neelamkavil [5]. The feasible schedules are constructed using the new discrete event oriented simulation in which the priorities of the activities are defined by genetic algorithm. The procedure generates active schedules.

The experimental results of EVA-LS on the standard set of the project instances show that EVA-LS is an effective method for solving the RCPSP.

1

J.J.M. Mendes, J.F.Gonçalves, M.C.G. Resende, "A Random Key Based Genetic Algorithm for the Resource Constrained Project Scheduling Problem", Computers and Operations Research, In Press, Corrected Proof, available online 25 July 2007. doi:10.1016/j.cor.2007.07.001

2

J.J.M. Mendes, J.F.Gonçalves, "A Memetic Algorithm-Based Heuristics for the Resource Constrained Project Scheduling Problem", Proceedings of II International Conference on Computational Methods for Coupled Problems in Science and Engineering, International Centre Congress of Santa Eulália, Spain, 2007.

3

J.F. Gonçalves, J.J.M. Mendes, M.C.G. Resende "A hybrid genetic algorithm for the job shop scheduling problem", European Journal of Operational Research, 167, 77-95, 2005. doi:10.1016/j.ejor.2004.03.012

4

J.J.M. Mendes, "Sistema de Apoio à Decisão para Planeamento de Sistemas de Produção do Tipo Projecto", Ph. D. Thesis, Departamento de Engenharia Mecânica e Gestão Industrial, Faculdade de Engenharia da Universidade do Porto, Portugal, 2003. (In portuguese)

5

F. Neelamkavil, "Computer Simulation and Modelling", John Wiley & Sons Ltd, 1990.

purchase the full-text of this paper (price £20)

go to the previous paper
go to the next paper
return to the table of contents
return to the book description
purchase this book (price £95 +P&P)