An Efficient branch and bound algorithm for the resource leveling problem

Download

index.pdf

Date

2013

Author

Yeniocak, Hüseyin

Metadata

Show full item record

Item Usage Stats

147
views

82
downloads

Resource leveling problem (RLP) focuses on optimizing resource utilization curves obtained by using Critical Path Method (CPM). This thesis presents a new and efficient branch and bound algorithm for the RLP. The proposed algorithm has been compared with mixed-integer linear modeling methods and previous branch and bound algorithms. An adaptive branch and bound heuristic has been developed for a good upper bound calculation. A new lower bound calculation strategy has been introduced and dual calculation has been used to obtain better lower bound values. Activity selection methods for branching process have been proposed to improve lower bounds and accelerating techniques have been implemented to achieve an efficient branch and bound algorithm for the RLP. Extensive computational experiments have been conducted using test problems from the literature including instances from Project Scheduling Problem Library (PSPLIB), Kolisch et al. (1999), Franck et al. (2001) and Rieck et al. (2012). The branch and bound algorithm has proven the best performance in terms of computational times for problems up to 20 activities for all objective functions. Moreover, for resource idle days optimization, problems up to 30 activities were solved for the first time in literature. Mixed-integer linear model could only solve problems with 10 activities for resource idle days and its performance highly depends on the type of the objective function. The proposed branch and bound algorithm provides a powerful method for the RLP due to its flexibility in applying several accelerating techniques and it can solve optimization functions in all forms.

Subject Keywords

Resource allocation., Feasibility studies., Engineering mathematics., Engineering, Engineering, Atan, Tankut.

URI

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

Collections

Graduate School of Natural and Applied Sciences, Thesis

Suggestions

OpenMETU
Core

A branch and bound algorithm for resource leveling problem Mutlu, Mustafa Çağdaş; Sönmez, Rifat; Department of Civil Engineering (2010) Resource Leveling Problem (RLP) aims to minimize undesired fluctuations in resource distribution curves which cause several practical problems. Many studies conclude that commercial project management software packages can not effectively deal with RLP. In this study a branch and bound algorithm is presented for solving RLP for single and multi resource, small size networks. The algorithm adopts a depth-first strategy and stores start times of non-critical activities in the nodes of the search tree. Optimal...
Development of high performance heuristic and meta-heuristic methods for resource optimization of large scale construction projects Abbasi Iranagh, Mahdi; Sönmez, Rifat; Department of Civil Engineering (2015) Despite the importance of resource optimization in construction scheduling, very little success has been achieved in solving the resource leveling problem (RLP) and resource constrained discrete time-cost trade-off problem (RCDTCTP), especially for large-scale projects. The major objective of this thesis is to design and develop new heuristic and meta-heuristic methods to achieve fast and high quality solutions for the large-scale RLP and RCDTCTP. Two different methods are presented in this thesis for the R...
New approaches for performance evaluation using data envelopment analysis Özpeynirci, Nail Özgür; Köksalan, Murat; Department of Industrial Engineering (2004) Data Envelopment Analysis (DEA) assigns efficiency values to decision making units (DMU) in a given period by comparing the outputs with the inputs. In many applications, inputs and outputs of DMUs are monitored over time. There might be a time lag between the consumption of inputs and production of outputs. We develop approaches that aim to capture the time lag between the outputs and the inputs in assigning the efficiency values to DMUs. We present computational results on randomly generated problems as w...
A genetic algorithm for 2d shape optimization Chen, Wei Hang; Oral, Süha; Department of Mechanical Engineering (2008) In this study, an optimization code has been developed based on genetic algorithms associated with the finite element modeling for the shape optimization of plane stress problems. In genetic algorithms, constraints are mostly handled by using the concept of penalty functions, which penalize infeasible solutions by reducing their fitness values in proportion to the degrees of constraint violation. In this study, An Improved GA Penalty Scheme is used. The proposed method gives information about unfeasible ind...
Linear static analysis of large structural models on pc clusters Özmen, Semih; Toker, Kurç; Department of Civil Engineering (2009) This research focuses on implementing and improving a parallel solution framework for the linear static analysis of large structural models on PC clusters. The framework consists of two separate programs where the first one is responsible from preparing data for the parallel solution that involves partitioning, workload balancing, and equation numbering. The second program is a fully parallel nite element program that utilizes substructure based solution approach with direct solvers. The first step of data...

Citation Formats

H. Yeniocak, “An Efficient branch and bound algorithm for the resource leveling problem,” M.S. - Master of Science, Middle East Technical University, 2013.