Nowadays, construction projects grow in complexity and size. So, finding feasible schedules which efficiently use scarce resources is a challenging task within project management. 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 well-known resource constrained project scheduling 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 [20]. This paper presents two approaches for the project scheduling problem. The first approach combines a new implementation of a genetic algorithm with a discrete system simulation. This approach generates non-delay schedules. This study also proposes applying a local search procedure trying to yield a better solution (GA-RKV-ND). The second approach combines a new implementation of a genetic algorithm with a discrete system simulation. This approach generates active schedules. This study also proposes applying a local search procedure trying to yield a better solution (GA-RKV-AS). The chromosome representation of the problem is based on random keys. 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 [27]. The good computational results on benchmark instances enlighten the interest of the best approach (GA-RKV-AS).
Citation
WP 30.12.2008 GICEC.DEC, Instituto Superior de Engenharia do Porto, Portugal