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

Abstract

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

How to cite

top

Sirdey, 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
  1. Computational infrastructure for operations research (www.coin-or.org), last access on July the 18th (2006).  
  2. 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.  
  3. 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.  
  4. J. Carlier. Le problème de l'ordonnancement des paiements de dettes. RAIRO: Oper. Res.18 février (1984).  
  5. T. Christof and G. Reinelt, Algorithmic aspects of using small instance relaxations in parallel branch-and-cut. Technical report, Heidelberg University (1998).  
  6. 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.  
  7. E.G. Coffman, M.R. Garey, D.S. Johnson and A.S. Lapaugh, Scheduling file transfers. SIAM J. Comput.14 (1985).  
  8. 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.  
  9. P.C. Fishburn, Induced binary probabilities and the linear ordering polytope: a status report. Math. Social Sci.23 (1992) 67–80.  
  10. M.R. Garey and D.S. Johnson, Computers and intractability|A guide to the theory of NP-completeness. W. H. Freeman and Company (1979).  
  11. M. Grötschel, M. Jünger and G. Reinelt, A cutting plane algorithm for the linear ordering problem. Oper. Res.32 (1984) 1195–1220.  
  12. M. Grötschel, M. Jünger and G. Reinelt, Facets of the linear ordering polytope. Math. Program.33 (1985) 43–60.  
  13. M. Grötschel, M. Jünger and G. Reinelt, On the acyclic subgraph polytope. Math. Program.33 (1985) 28–42.  
  14. M. Grötschel, L. Lovász and A. Schrijver, Geometric algorithms and combinatorial optimization, Vol. 2 Algorithms and Combinatorics. Springer (1988).  
  15. 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.  
  16. P. Jalote, Fault tolerance in distributed systems. Distributed Systems. Prentice Hall (1994).  
  17. H. Kellerer, U. Pferschy and D. Pisinger, Knapsack problems. Springer (2004).  
  18. 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).  
  19. 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.  
  20. M. Queyranne and A.S. Schulz, Polyhedral approaches to machine scheduling. Technical Report 408/1994, Berlin University of Technology (1994).  
  21. G. Reinelt, The linear ordering problem: algorithms and applications, volume 8 of Research and exposition in mathematics. Heldermann Verlag, Berlin (1985).  
  22. J.C. Saia, Data migration with edge capacities and machine speeds. Technical report, Washington University (2001).  
  23. 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).  DOI10.1016/j.ejor.2006.10.011
  24. R. Sirdey, J. Carlier and D. Nace, Approximate resolution of a resource-constrained scheduling problem. J. Heuristics (in press) (2006).  
  25. 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).  
  26. 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).  
  27. 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 ?

top

You must be logged in to post comments.

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

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.