A branch and bound algorithm for the resource-constrained project scheduling problem

A branch and bound algorithm for the resource-constrained project scheduling problem

0.00 Avg rating0 Votes
Article ID: iaor19992287
Country: Netherlands
Volume: 107
Issue: 2
Start Page Number: 272
End Page Number: 288
Publication Date: Jun 1998
Journal: European Journal of Operational Research
Authors: , , ,
Keywords: allocation: resources
Abstract:

A branch and bound algorithm is presented for the resource-constrained project scheduling problem. Given are n activities which have to be processed without preemptions. During the processing period of an activity constant amounts of renewable resources are needed where the available capacity of each resource type is limited. Furthermore, finish–start precedence relations between the activities are given. The objective is to determine a schedule with minimal makespan. The branching scheme starts from a graph representing a set of conjunctions (the classical finish–start precedence constraints) and disjunctions (induced by the resource constraints). Then it either introduces disjunctive constraints between pairs of activities or places these activities in parallel. Concepts of immediate selection are developed in connection with this branching scheme. Immediate selection allows us to add conjunctions as well as further disjunctions and parallelity relations. Computational results based on the test data of Kolisch et al. and Kolisch and Sprecher are reported.

Reviews

Required fields are marked *. Your email address will not be published.