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

Autor(en): Brucker, P
Knust, S 
Schoo, A
Thiele, O
Stichwörter: branch and bound method; Business & Economics; disjunctive graph model; immediate selection; Management; MULTIPLE-RESOURCE; Operations Research & Management Science; resource-constrained project scheduling problem
Erscheinungsdatum: 1998
Herausgeber: ELSEVIER SCIENCE BV
Journal: EUROPEAN JOURNAL OF OPERATIONAL RESEARCH
Volumen: 107
Ausgabe: 2
Startseite: 272
Seitenende: 288
Zusammenfassung: 
A branch and bound algorithm is presented for the resource-constrained project scheduling problem (RCPSP). 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 to add conjunctions as well as further disjunctions and parallelity relations. Computational results based on the test data of Kolisch ct al. (Kolisch, R., Sprecher, A., Drexl. A., 1995. Management Science 41, 1693-1703.) and Kolisch and Sprecher (Kolisch, R., Sprecher, A., 1997. PSPLIB - A project scheduling problem library, EJOR 96, pp. 205-216.) are reported. (C) 1998 Elsevier Science B.V. All rights reserved.
Beschreibung: 
5th International Workshop on Project Management and Scheduling, POZNAN, POLAND, APR 11-13, 1996
ISSN: 03772217
DOI: 10.1016/S0377-2217(97)00335-4

Show full item record

Page view(s)

5
Last Week
0
Last month
2
checked on Feb 26, 2024

Google ScholarTM

Check

Altmetric