Volume 46, Number 4, October-December 2012
|Page(s)||373 - 409|
|Published online||21 December 2012|
Flow Polyhedra and Resource Constrained Project Scheduling Problems
1 LIMOS, UMR CNRS 6158, Bat. ISIMA, Université Blaise Pascal, Campus des Cézeaux, BP 125, 63173 Aubiere, France
Received: 17 April 2011
Accepted: 8 October 2012
This paper aims at describing the way Flow machinery may be used in order to deal with Resource Constrained Project Scheduling Problems (RCPSP). In order to do it, it first introduces the Timed Flow Polyhedron related to a RCPSP instance. Next it states several structural results related to connectivity and to cut management. It keeps on with a description of the way this framework gives rise to a generic Insertion operator, which enables programmers to design greedy and local search algorithms. It ends with numerical experiments.
Mathematics Subject Classification: 90-08
Key words: Scheduling with resource constraints / network flow theory
© EDP Sciences, ROADEF, SMAI, 2012
Current usage metrics show cumulative count of Article Views (full-text article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.
Data correspond to usage on the plateform after 2015. The current usage metrics is available 48-96 hours after online publication and is updated daily on week days.
Initial download of the metrics may take a while.