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.
Type de document :
Article dans une revue
European Journal of Operational Research, Elsevier, 2007, 183, pp.546-563. 〈10.1016/j.ejor.2006.10.011〉
Liste complète des métadonnées

Littérature citée [22 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00311377
Contributeur : Renaud Sirdey <>
Soumis le : jeudi 14 août 2008 - 18:53:35
Dernière modification le : jeudi 11 janvier 2018 - 06:26:36
Document(s) archivé(s) le : jeudi 3 juin 2010 - 18:23:42

Fichiers

EJOR.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

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〉

Partager

Métriques

Consultations de la notice

153

Téléchargements de fichiers

106