Peter Brucker, Sigrid Knust, Arno Schoo, Olaf Thiele
A Branch & Bound Algorithm for the Resource-Constrained Project Scheduling Problem
The paper is published:
European Journal Operational Research 107 (1998), 272--288.
- MSC:
- 90B35 Scheduling theory, See also {68M20}
Abstract: A branch & 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 a constant amount of
certain renewable resources is needed where the available capacity of each
resource type is limited. Furthermore, 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 to add conjunctions as well as further
disjunctions and parallelity relations.
Computational results based on the test data of Kolisch et al. [1995] are
reported.
Keywords: branch & bound method, immediate selection, resource-constrained, scheduling problem, disjunctive graph model