Volume 42, Number 3, July-September 2008
|Page(s)||325 - 359|
|Published online||20 August 2008|
Polyhedral Reformulation of a Scheduling Problem And Related Theoretical Results
LIMOS, UMR CNRS 6158, Bât ISIMA, Université Blaise Pascal, Campus des Cézeaux,
BP 125, 63173 Aubière, France;
email@example.com, firstname.lastname@example.org, email@example.com
Accepted: 11 November 2007
We deal here with a scheduling problem GPPCSP (Generalized Parallelism and Preemption Constrained Scheduling Problem) which is an extension of both the well-known Resource Constrained Scheduling Problem and the Scheduling Problem with Disjunctive Constraints. We first propose a reformulation of GPPCSP: according to it, solving GPPCSP means finding a vertex of the Feasible Vertex Subset of an Antichain Polyhedron. Next, we state several theoretical results related to this reformulation process and to structural properties of this specific Feasible Vertex Subset (connectivity, ...). We end by focusing on the preemptive case of GPPCSP and by identifying specific instances of GPPCSP which are such that any vertex of the related Antichain Polyhedron may be projected on its related Feasible Vertex Subset without any deterioration of the makespan. For such an instance, the GPPCSP problem may be solved in a simple way through linear programming.
Mathematics Subject Classification: 90B35
Key words: Partially ordered sets / hypergraphs / linear programming / polyhedra / multiprocessor scheduling / resource constrained project scheduling problem.
© EDP Sciences, ROADEF, SMAI, 2008
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.