# A branch-and-cut algorithm for a resource-constrained scheduling problem

Renaud Sirdey; Hervé L. M. Kerivin

RAIRO - Operations Research (2007)

- Volume: 41, Issue: 3, page 235-251
- ISSN: 0399-0559

## Access Full Article

top## Abstract

top## How to cite

topSirdey, Renaud, and Kerivin, Hervé L. M.. "A branch-and-cut algorithm for a resource-constrained scheduling problem." RAIRO - Operations Research 41.3 (2007): 235-251. <http://eudml.org/doc/250106>.

@article{Sirdey2007,

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.
},

author = {Sirdey, Renaud, Kerivin, Hervé L. M.},

journal = {RAIRO - Operations Research},

keywords = {Polyhedral combinatorics; scheduling; branch-and-cut; distributed systems; polyhedral combinatorics},

language = {eng},

month = {8},

number = {3},

pages = {235-251},

publisher = {EDP Sciences},

title = {A branch-and-cut algorithm for a resource-constrained scheduling problem},

url = {http://eudml.org/doc/250106},

volume = {41},

year = {2007},

}

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

DA - 2007/8//

PB - EDP Sciences

VL - 41

IS - 3

SP - 235

EP - 251

AB -
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.

LA - eng

KW - Polyhedral combinatorics; scheduling; branch-and-cut; distributed systems; polyhedral combinatorics

UR - http://eudml.org/doc/250106

ER -

## References

top- Computational infrastructure for operations research (www.coin-or.org), last access on July the 18th (2006).
- G. Aggarwal, R. Motwani and A. Zhu, The load rebalancing problem, in Proceedings of the Fifteenth Annual ACM Symposium on Parallel Algorithms and Architectures (2003) 258–265. Zbl1110.68011
- E. Anderson, J. Hall, J. Hartline, M. Hobbs, A.R. Karlin, J. Saia, R. Swaminathan and J. Wilkes, An experimental study of data migration algorithms. In Proceedings of the 5th International Workshop on Algorithm Engineering. Lect. Notes Comput. Sci. (2001) 145. Zbl1002.68626
- J. Carlier. Le problème de l'ordonnancement des paiements de dettes. RAIRO: Oper. Res.18 février (1984).
- T. Christof and G. Reinelt, Algorithmic aspects of using small instance relaxations in parallel branch-and-cut. Technical report, Heidelberg University (1998). Zbl0973.90064
- E.G. Coffman, M.R. Garey, D.S. Johnson and A.S. Lapaugh, Scheduling file transfers in distributed networks, in Proceedings of the 2nd Annual ACM Symposium on Principles of Distributed Computing (1983) 254–266. Zbl0604.68039
- E.G. Coffman, M.R. Garey, D.S. Johnson and A.S. Lapaugh, Scheduling file transfers. SIAM J. Comput.14 (1985). Zbl0604.68039
- M. Demange and V.T. Paschos, On an approximation measure founded on the links between optimization and polynomial approximation theory. Theor. Comput. Sci.158 (1996) 117–141. Zbl0871.90069
- P.C. Fishburn, Induced binary probabilities and the linear ordering polytope: a status report. Math. Social Sci.23 (1992) 67–80. Zbl0751.90004
- M.R. Garey and D.S. Johnson, Computers and intractability|A guide to the theory of NP-completeness. W. H. Freeman and Company (1979). Zbl0411.68039
- M. Grötschel, M. Jünger and G. Reinelt, A cutting plane algorithm for the linear ordering problem. Oper. Res.32 (1984) 1195–1220.
- M. Grötschel, M. Jünger and G. Reinelt, Facets of the linear ordering polytope. Math. Program.33 (1985) 43–60.
- M. Grötschel, M. Jünger and G. Reinelt, On the acyclic subgraph polytope. Math. Program.33 (1985) 28–42.
- M. Grötschel, L. Lovász and A. Schrijver, Geometric algorithms and combinatorial optimization, Vol. 2 Algorithms and Combinatorics. Springer (1988).
- J. Hall, J. Hartline, A.R. Karlin, J. Saia and J. Wilkes, On algorithms for efficient data migration. In Proceedings of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms (2001) 620–629. Zbl0987.68006
- P. Jalote, Fault tolerance in distributed systems. Distributed Systems. Prentice Hall (1994).
- H. Kellerer, U. Pferschy and D. Pisinger, Knapsack problems. Springer (2004). Zbl1103.90003
- H. Kerivin and R. Sirdey, 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).
- J. E. Mitchell and B. Borchers, Solving linear ordering problems with a combined interior point/simplex cutting plane algorithm, in High performance optimization, 349–366. Kluwer, 2000. Zbl0965.90057
- M. Queyranne and A.S. Schulz, Polyhedral approaches to machine scheduling. Technical Report 408/1994, Berlin University of Technology (1994).
- G. Reinelt, The linear ordering problem: algorithms and applications, volume 8 of Research and exposition in mathematics. Heldermann Verlag, Berlin (1985).
- J.C. Saia, Data migration with edge capacities and machine speeds. Technical report, Washington University (2001).
- R. Sirdey, J. Carlier, H. Kerivin and D. Nace, On a resource-constrained scheduling problem with application to distributed systems reconfiguration. Eur. J. Oper. Res. (to appear, DOI : ) (2005). Zbl1180.90137DOI10.1016/j.ejor.2006.10.011
- R. Sirdey, J. Carlier and D. Nace, Approximate resolution of a resource-constrained scheduling problem. J. Heuristics (in press) (2006). Zbl1180.90138
- R. Sirdey, J. Carlier and D. Nace, 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). Zbl1180.90138
- R. Sirdey and H. Kerivin, 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).
- R. Sirdey, D. Plainfossé and J.-P. Gauthier, 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.

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.