A genetic algorithm for the resource constrained project scheduling problem

Download

index.pdf

Date

2011

Author

Özleyen, Erdem

Metadata

Show full item record

Item Usage Stats

171
views

50
downloads

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.

Subject Keywords

Project management.

URI

http://etd.lib.metu.edu.tr/upload/12613795/index.pdf
https://hdl.handle.net/11511/21084

Collections

Graduate School of Natural and Applied Sciences, Thesis

Suggestions

OpenMETU
Core

A modified heuristic procedure for materials management in project networks Erbasi, A; Sepil, C (1999-06-01) A heuristic procedure for determining the tradeoff between expediting the ordering of materials and delaying the project is presented. The heuristic procedure is a modification of the procedure taken from the literature. With the use of an illustrative example, it has been shown that the modified procedure provides schedules with lower total cost values. Experimental results performed on randomly generated problems reveal that the modification can bring a decrease in total cost values as much as 52%.
Hybrid meta-heuristic algorithms for the resource constrained multi-project scheduling problem Uysal, Furkan; Sönmez, Rifat; Department of Civil Engineering (2014) The general resource constrained multi-project scheduling problem (RCMPSP) consists of simultaneous scheduling of two or more projects with common resource constraints, while minimizing duration of the projects. Critical Path Method and other scheduling methods do not consider resource conflicts and practically used commercial project management software packages and heuristic methods provide very limited solutions for the solution of the RCMPSP. Considering the practical importance of multi-project schedul...
A genetic algorithm for resource leveling of construction projects Iranagh, Mahdi Abbasi; Sönmez, Rifat (2012-01-01) Critical path method (CPM) is commonly used in scheduling of construction projects. However, CPM only considers the precedence relations between the activities and does not consider resource optimization during scheduling of projects. Optimal allocation of resources can be achieved by resource levelling. Resource levelling is crucial for effective use of construction resources particularly to minimize the project costs. However, commercial scheduling software has very limited capabilities for solving the re...
An exploratory study on utilization of BIM for risk management Kaya, Hazal Deniz; Dikmen, İrem; Atasoy, Güzide; Birgönül, Mustafa Talat (İstanbul Teknik Üniversitesi; 2020-11-14) It is a well-known fact that BIM application in construction projects enables several advantages such as better collaboration and communication, effective project visualization before construction, more efficient cost estimation and scheduling, and an increase in productivity. Although many of these advantages that BIM contributes to construction projects may result in opportunities for better risk management, there are limited studies in the construction management literature that investigate this subject....
A mixed integer model for optimization of discrete time cost tradeoff problem Tatar, Ali Can; Bilir, Mert; Sönmez, Rifat; Atan, Sabri Tankut (null; 2016-06-25) In construction projects, activity durations can be expedited by allocating additional resources. Decreasing activity durations by means of crashing, usually leads to increase in the direct expenses. This trade-off between time and cost is called as the time-cost trade-off problem. Since in practice many resources are available in discrete units, numerous research has focussed on the discrete version of this problem called the discrete time-cost trade-off problem (DTCTP). Achieving the project schedule that...

Citation Formats

E. Özleyen, “A genetic algorithm for the resource constrained project scheduling problem,” M.S. - Master of Science, Middle East Technical University, 2011.