This paper is devoted to the exact resolution of a strongly -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.
Mots-clés : polyhedral combinatorics, scheduling, branch-and-cut, distributed systems
@article{RO_2007__41_3_235_0,
author = {Sirdey, Renaud and Kerivin, Herv\'e L. M.},
title = {A branch-and-cut algorithm for a resource-constrained scheduling problem},
journal = {RAIRO - Operations Research - Recherche Op\'erationnelle},
pages = {235--251},
publisher = {EDP-Sciences},
volume = {41},
number = {3},
year = {2007},
doi = {10.1051/ro:2007021},
mrnumber = {2348000},
zbl = {1213.90126},
language = {en},
url = {http://www.numdam.org/articles/10.1051/ro:2007021/}
}
TY - JOUR AU - Sirdey, Renaud AU - Kerivin, Hervé L. M. TI - A branch-and-cut algorithm for a resource-constrained scheduling problem JO - RAIRO - Operations Research - Recherche Opérationnelle PY - 2007 SP - 235 EP - 251 VL - 41 IS - 3 PB - EDP-Sciences UR - http://www.numdam.org/articles/10.1051/ro:2007021/ DO - 10.1051/ro:2007021 LA - en ID - RO_2007__41_3_235_0 ER -
%0 Journal Article %A Sirdey, Renaud %A Kerivin, Hervé L. M. %T A branch-and-cut algorithm for a resource-constrained scheduling problem %J RAIRO - Operations Research - Recherche Opérationnelle %D 2007 %P 235-251 %V 41 %N 3 %I EDP-Sciences %U http://www.numdam.org/articles/10.1051/ro:2007021/ %R 10.1051/ro:2007021 %G en %F RO_2007__41_3_235_0
Sirdey, Renaud; Kerivin, Hervé L. M. A branch-and-cut algorithm for a resource-constrained scheduling problem. RAIRO - Operations Research - Recherche Opérationnelle, Tome 41 (2007) no. 3, pp. 235-251. doi : 10.1051/ro:2007021. http://www.numdam.org/articles/10.1051/ro:2007021/
[1] Computational infrastructure for operations research (www.coin-or.org), last access on July the 18th (2006).
[2] , and, The load rebalancing problem, in Proceedings of the Fifteenth Annual ACM Symposium on Parallel Algorithms and Architectures (2003) 258-265.
[3] ,,,,,, and, An experimental study of data migration algorithms. In Proceedings of the 5th International Workshop on Algorithm Engineering. Lect. Notes Comput. Sci. (2001) 145. | Zbl
[4] . Le problème de l'ordonnancement des paiements de dettes. RAIRO: Oper. Res. 18 février (1984). | EuDML
[5] and, Algorithmic aspects of using small instance relaxations in parallel branch-and-cut. Technical report, Heidelberg University (1998). | Zbl
[6] ,, and, Scheduling file transfers in distributed networks, in Proceedings of the 2nd Annual ACM Symposium on Principles of Distributed Computing (1983) 254-266.
[7] ,, and, Scheduling file transfers. SIAM J. Comput. 14 (1985). | MR | Zbl
[8] and, On an approximation measure founded on the links between optimization and polynomial approximation theory. Theor. Comput. Sci. 158 (1996) 117-141. | Zbl
[9] , Induced binary probabilities and the linear ordering polytope: a status report. Math. Social Sci. 23 (1992) 67-80. | Zbl
[10] and, Computers and intractability | MR | Zbl
[11] , and, A cutting plane algorithm for the linear ordering problem. Oper. Res. 32 (1984) 1195-1220. | Zbl
[12] , and, Facets of the linear ordering polytope. Math. Program. 33 (1985) 43-60. | Zbl
[13] , and, On the acyclic subgraph polytope. Math. Program. 33 (1985) 28-42. | Zbl
[14] , and, Geometric algorithms and combinatorial optimization, Vol. 2 Algorithms and Combinatorics. Springer (1988). | MR | Zbl
[15] ,,, and, On algorithms for efficient data migration. In Proceedings of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms (2001) 620-629. | Zbl
[16] , Fault tolerance in distributed systems. Distributed Systems. Prentice Hall (1994).
[17] , and, Knapsack problems. Springer (2004). | MR | Zbl
[18] and, Polyhedral combinatorics of a resource-constrained ordering problem part II: on the process move program polytope. Technical Report PE/BSC/INF/017913 V01/EN, service d'architecture BSC, Nortel GSM Access R&D, France (submitted to Math. Program. (2006).
[19] and, Solving linear ordering problems with a combined interior point/simplex cutting plane algorithm, in High performance optimization, 349-366. Kluwer, 2000. | Zbl
[20] and, Polyhedral approaches to machine scheduling. Technical Report 408/1994, Berlin University of Technology (1994).
[21] , The linear ordering problem: algorithms and applications, volume 8 of Research and exposition in mathematics. Heldermann Verlag, Berlin (1985). | MR | Zbl
[22] , Data migration with edge capacities and machine speeds. Technical report, Washington University (2001).
[23] ,, and, On a resource-constrained scheduling problem with application to distributed systems reconfiguration. Eur. J. Oper. Res. (to appear, DOI : 10.1016/j.ejor.2006.10.011) (2005). | MR
[24] , and, Approximate resolution of a resource-constrained scheduling problem. J. Heuristics (in press) (2006).
[25] , and, A fast heuristic for a resource-constrained scheduling problem. Technical Report PE/BSC/INF/017254 V01/EN, service d'architecture BSC, Nortel GSM Access R&D, France (2005).
[26] and, Polyhedral combinatorics of a resource-constrained ordering problem part I: on the partial linear ordering polytope. Technical Report PE/BSC/INF/017912 V01/EN, service d'architecture BSC, Nortel GSM Access R&D, France (submitted to Math. Program.) (2006).
[27] , and, A practical approach to combinatorial optimization problems encountered in the design of a high availability distributed system. in Proceedings of the International Network Optimization Conference (2003) 532-539.
Cité par Sources :
