A branch and bound algorithm for resource leveling problem

Download

index.pdf

Date

2010

Author

Mutlu, Mustafa Çağdaş

Metadata

Show full item record

Item Usage Stats

227
views

83
downloads

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 resource distributions for 4 different types of resource leveling metrics can be obtained via the developed procedure. To prune more of the search tree and thereby reduce the computation time, several lower bound calculation methods are employed. Experiment results from 20 problems showed that the suggested algorithm can successfully locate optimal solutions for networks with up to 20 activities. The algorithm presented in this study contributes to the literature in two points. First, the new lower bound improvement method (maximum allowable daily resources method) introduced in this study reduces computation time required for achieving the optimal solution for the RLP. Second, optimal solutions of several small sized problems have been obtained by the algorithm for some traditional and recently suggested leveling metrics. Among these metrics, Resource Idle Day (RID) has been utilized in an exact method for the first time. All these solutions may form a basis for performance evaluation of heuristic and metaheuristic procedures for the RLP. Limitations of the developed branch and bound procedure are discussed and possible further improvements are suggested.

Subject Keywords

Management of engineering works.

URI

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

Collections

Graduate School of Natural and Applied Sciences, Thesis

Suggestions

OpenMETU
Core

An Efficient branch and bound algorithm for the resource leveling problem Yeniocak, Hüseyin; Sönmez, Rifat; Department of Civil Engineering (2013) 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...
A Heuristic for Obtaining and Initial Solution for the Transportation Problem Kirca, Ömer; Şatır, Ahmet (JSTOR, 1990-9) A heuristic for obtaining an initial solution for the transportation problem is presented. Comparison of findings obtained by the new heuristic and Vogel's approximation method (VAM) are tabulated for 480 examples. Superior performance of the new heuristic over VAM is discussed in terms of total costs obtained, number of iterations required to reach the final solution, and CPU time required to solve the problems. Experimental design aspects are also presented.
Discrete tomographic reconstruction methods from the theories of optimization and inverse problems : application in VLSI microchip production Özgür, Osman; Weber, Gerhard Wilhelm; Department of Scientific Computing (2006) Optimization theory is a key technology for inverse problems of reconstruction in science, engineering and economy. Discrete tomography is a modern research field dealing with the reconstruction of finite objects in, e.g., VLSI chip design, where this thesis will focus on. In this work, a framework with its supplementary algorithms and a new problem reformulation are introduced to approximately resolve this NP-hard problem. The framework is modular, so that other reconstruction methods, optimization techniq...
A resource investment problem with time/resource trade-offs Colak, Erdem; Azizoğlu, Meral (Informa UK Limited, 2014-05-01) In this study, we consider a Resource Investment Problem with time/resource trade-offs in project networks. We assume that there is a single renewable resource and the processing requirement of an activity can be reduced by investing extra resources. Our aim is to minimize the maximum resource usage, hence, the total amount invested for the single resource, while meeting the pre-specified deadline. We formulate the problem as a mixed integer linear model and find optimal solutions for small-sized problem in...
Identification of risk paths in international construction projects Eybpoosh, Matineh; Dikmen Toker, İrem; Birgönül, Mustafa Talat; Department of Civil Engineering (2010) Within the context of construction projects, risk is generally defined as an uncertain happening which is the function of its occurrence probability and the severity of its possible impacts on pre-defined objectives. According to this definition, international construction projects are high-risk endeavors, since they are known with their complex natures, large sizes, multidisciplinary frameworks, and unfamiliar and uncertain environments. International construction projects have more complex risk emergence ...

Citation Formats

M. Ç. Mutlu, “A branch and bound algorithm for resource leveling problem,” M.S. - Master of Science, Middle East Technical University, 2010.