A linear programming and constraint propagation-based lower bound for the RCPSP

Autor(en): Brucker, P
Knust, S 
Stichwörter: ALGORITHM; BRANCH; Business & Economics; column generation; constraint propagation; lower bounds; Management; Operations Research & Management Science; PROJECT SCHEDULING PROBLEM; RESOURCE; resource-constrained project scheduling problem; scheduling
Erscheinungsdatum: 2000
Herausgeber: ELSEVIER SCIENCE BV
Journal: EUROPEAN JOURNAL OF OPERATIONAL RESEARCH
Volumen: 127
Ausgabe: 2
Startseite: 355
Seitenende: 362
Zusammenfassung: 
A new destructive lower bound for the resource-constrained project scheduling problem (RCPSP) is presented. 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 lower bound calculations are based on two methods for proving infeasibility of a given threshold value T for the makespan. The first uses constraint propagation techniques, while the second is based on a linear programming formulation. A column generation procedure is presented for the linear programming formulation and computational results are reported for an algorithm combining both concepts. (C) 2000 Elsevier Science B.V. All rights reserved.
Beschreibung: 
6th International Workshop on Project Management and Scheduling, ISTANBUL, TURKEY, JUL 07-09, 1998
ISSN: 03772217
DOI: 10.1016/S0377-2217(99)00489-0

Show full item record

Page view(s)

2
Last Week
0
Last month
1
checked on Feb 21, 2024

Google ScholarTM

Check

Altmetric