Keywords: construction management, project management, scheduling, genetic algorithms, random keys, MRCPSP.

As the complexity of projects increases, the requirement for an organized planning and scheduling process becomes more significant. The need for organized planning and scheduling of a construction project is influenced by a variety of factors (e.g. project size and number of project activities). To plan and schedule a construction project, activities must be defined sufficiently. The level of detail determines the number of activities contained within the project plan and schedule. 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 recent decades [1,2].

In the RCPSP the activities of a project have to be scheduled such that the makespan of the project is minimized. So, the technological precedence constraints have to be observed as well as limitations of the renewable resources required to accomplish the activities. Once started, an activity may not be interrupted.

This problem has been extended to a more realistic model, the multi-mode resource constrained project scheduling problem (MRCPSP), where each activity can be performed in one of several modes. Each mode of an activity represents an alternative way of combining different levels of the resource requirements with a related duration. Each renewable resource has a limited availability such as manpower and machines for the entire project.

The objective of the MRCPSP problem is minimizing the makespan. While the exact methods are available for providing optimal solution for small problems, its computation time is not feasible for large-scale problems.

This paper presents a genetic algorithm-based approach (RKV-MM) for the multi-mode resource constrained project scheduling problem. The idea of this new approach is to integrate a genetic algorithm with a schedule generation scheme. This study also proposes applying a local search procedure to improve the initial solution.

The chromosome representation of the problem is based on random keys [1, 2]. The schedule is constructed using a schedule generation scheme in which the priorities of the activities are defined by the genetic algorithm.

The experimental results of the RKV-MM on project instances show that the RKV-MM is an effective method for solving the MRCPSP.

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 & Operations Research, 36, 92-109, 2009. doi:10.1016/j.cor.2007.07.001

2

J. Magalhães-Mendes, "An Evolutionary Algorithm for the Resource Constrained Project Scheduling Problem", in "Proceedings of the Sixth International Conference on Engineering Computational Technology", M. Papadrakakis, B.H.V. Topping, (Editors), Civil-Comp Press, Stirlingshire, United Kingdom, paper 67, 2008. doi:10.4203/ccp.89.67

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 £78 +P&P)