Issue |
RAIRO-Oper. Res.
Volume 41, Number 3, July-September 2007
Journées Polyèdres et Optimisation Combinatoire
|
|
---|---|---|
Page(s) | 235 - 251 | |
DOI | https://doi.org/10.1051/ro:2007021 | |
Published online | 21 August 2007 |
A branch-and-cut algorithm for a resource-constrained scheduling problem
1
Service d'architecture BSC (PC 12A7), Nortel GSM Access R&D, Parc d'activités de Magny-Châteaufort, 78928 Yvelines Cedex 09, France; renauds@nortel.com
2
UMR CNRS Heudiasyc (Université de Technologie de Compiègne), Centre de recherches de Royallieu, BP 20529, 60205 Compiègne Cedex, France.
3
UMR CNRS Limos (Université de Clermont-Ferrand II), Complexe scientifique des Cézeaux, 63177 Aubière Cedex, France; kerivin@math.univ-bpclermont.fr
Received:
16
March
2006
Accepted:
21
December
2006
This paper is devoted to the exact resolution of a strongly NP-hard resource-constrained scheduling problem, the Process Move Programming problem, which arises in relation to the operability of certain high-availability real-time distributed systems. Based on the study of the polytope defined as the convex hull of the incidence vectors of the admissible process move programs, we present a branch-and-cut algorithm along with extensive computational results demonstrating its practical relevance, in terms of both exact and approximate resolution when the instance size increases.
Mathematics Subject Classification: 90C57 / 68M14
Key words: Polyhedral combinatorics / scheduling / branch-and-cut / distributed systems
© EDP Sciences, ROADEF, SMAI, 2007
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.