Skip to Main content Skip to Navigation
New interface
Journal articles

A branch-and-cut algorithm for a resource-constrained scheduling problem

Abstract : 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.
Document type :
Journal articles
Complete list of metadata

Cited literature [26 references]  Display  Hide  Download
Contributor : Renaud Sirdey Connect in order to contact the contributor
Submitted on : Monday, August 18, 2008 - 9:59:44 PM
Last modification on : Tuesday, November 16, 2021 - 4:30:26 AM
Long-term archiving on: : Thursday, June 3, 2010 - 6:31:36 PM


Files produced by the author(s)



Renaud Sirdey, Hervé Kerivin. A branch-and-cut algorithm for a resource-constrained scheduling problem. RAIRO - Operations Research, 2007, 41 (3), pp.235-251. ⟨10.1051/ro:2007021⟩. ⟨inria-00311533⟩



Record views


Files downloads