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

https://hal.inria.fr/inria-00311377
Contributor : Renaud Sirdey <>
Submitted on : Thursday, August 14, 2008 - 6:53:35 PM
Last modification on : Wednesday, April 21, 2021 - 8:52:04 AM
Long-term archiving on: : Thursday, June 3, 2010 - 6:23:42 PM

Files

EJOR.pdf
Files produced by the author(s)

Identifiers

Citation

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⟩

Share

Metrics

Record views

333

Files downloads

381