Skip to Main content Skip to Navigation
Journal articles

On a resource-constrained scheduling problem with application to distributed systems reconfiguration

Abstract : This paper is devoted to the study of a resource-constrained scheduling problem, the Process Move Programming problem, which arises in relation to the operability of certain high availability real-time distributed systems. Informally, this problem consists, starting from an arbitrary initial distribution of processes on the processors of a distributed system, in finding the least disruptive sequence of operations (non-impacting process migrations or temporary process interruptions) at the end of which the system ends up in another predefined arbitrary state. The main constraint is that the capacity of the processors must not be exceeded during the reconfiguration. After a brief survey of the literature, we prove the NP-hardness of the problem and exhibit a few polynomial special cases. We then present a branch-and-bound algorithm for the general case along with computational results demonstrating its practical relevance.
Document type :
Journal articles
Complete list of metadata

Cited literature [22 references]  Display  Hide  Download
Contributor : Renaud Sirdey Connect in order to contact the contributor
Submitted on : Thursday, August 14, 2008 - 6:53:35 PM
Last modification on : Tuesday, November 16, 2021 - 4:30:44 AM
Long-term archiving on: : Thursday, June 3, 2010 - 6:23:42 PM


Files produced by the author(s)



Renaud Sirdey, Jacques Carlier, Hervé Kerivin, Dritan Nace. On a resource-constrained scheduling problem with application to distributed systems reconfiguration. European Journal of Operational Research, Elsevier, 2007, 183, pp.546-563. ⟨10.1016/j.ejor.2006.10.011⟩. ⟨inria-00311377⟩



Record views


Files downloads