Skip to Main content Skip to Navigation
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 metadatas

Cited literature [26 references]  Display  Hide  Download

https://hal.inria.fr/inria-00311533
Contributor : Renaud Sirdey <>
Submitted on : Monday, August 18, 2008 - 9:59:44 PM
Last modification on : Monday, January 20, 2020 - 12:12:05 PM
Long-term archiving on: : Thursday, June 3, 2010 - 6:31:36 PM

Files

RAIRO.pdf
Files produced by the author(s)

Identifiers

Citation

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

Share

Metrics

Record views

287

Files downloads

292