The resource-constrained project scheduling problem (RCPSP) aims to find a
schedule of minimum makespan by starting each activity such that resource
constraints and precedence constraints are respected. However, as the problem
is NP-hard (Non-Deterministic Polynomial-Time Hard) in the strong sense, the
performance of exact procedures is limited and can only solve small-sized
project networks. In this study a genetic algorithm is proposed for the RCPSP.
The proposed genetic algorithm (GA) aims to find near-optimal solutions and
also overcomes the poor performance of the exact procedures for large-sized
project networks. Contrarily to a traditional GA, the proposed algorithm
employs two independent populations: left population that consist of leftjustified
(forward) schedules and right population that consist of right-justified
(backward) schedules. The repeated cycle updates the left (right) population by
maintaining it with transformed right (left) individuals. By doing so, the
algorithm uses two different scheduling characteristics. Moreover, the
algorithm provides a new two-point crossover operator that selects the parents
according to their resource requirement mechanism. The algorithm also
includes a modified mutation operator which just accepts the improved
solutions. Experiment results show that the suggested algorithm outperforms the well
known commercial software packages / Primavera Project Planner (P6 version
7.0) and Microsoft Project 2010 for the RCPSP. In addition, the algorithm is
tested with problems obtained from literature as well as the benchmark
PSPLIB (Project Scheduling Problem Library) problems. The proposed
algorithm obtained satisfactory results especially for the problems with 120 and
300 activities. Limitations of the proposed genetic algorithm are addressed and
possible further studies are advised.
| Identifer | oai:union.ndltd.org:METU/oai:etd.lib.metu.edu.tr:http://etd.lib.metu.edu.tr/upload/12613795/index.pdf |
| Date | 01 October 2011 |
| Creators | Ozleyen, Erdem |
| Contributors | Sonmez, Rifat |
| Publisher | METU |
| Source Sets | Middle East Technical Univ. |
| Language | English |
| Detected Language | English |
| Type | M.S. Thesis |
| Format | text/pdf |
| Rights | To liberate the content for public access |
Page generated in 0.0026 seconds