×
Sirdey, Renaud; Kerivin, Hervé L. M.

A branch-and-cut algorithm for a resource-constrained scheduling problem. (English) Zbl 1213.90126

RAIRO, Oper. Res. 41, No. 3, 235-251 (2007).
Summary: 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.

Cited in 2 Documents

MSC:

90B35 Deterministic scheduling theory in operations research
90C57 Polyhedral combinatorics, branch-and-bound, branch-and-cut
90C10 Integer programming
68M14 Distributed systems

Keywords:

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

Software:

LOLIB
Cite Review PDF
Full Text: DOI EuDML Link

References:

[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. · Zbl 1110.68011
[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. Zbl1002.68626 · Zbl 1002.68626
[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). · Zbl 0973.90064
[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. · Zbl 0604.68039
[7] E.G. Coffman, M.R. Garey, D.S. Johnson and A.S. Lapaugh, Scheduling file transfers. SIAM J. Comput.14 (1985). Zbl0604.68039 · Zbl 0604.68039 · doi:10.1137/0214054
[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. Zbl0871.90069 · Zbl 0871.90069 · doi:10.1016/0304-3975(95)00060-7
[9] P.C. Fishburn, Induced binary probabilities and the linear ordering polytope: a status report. Math. Social Sci.23 (1992) 67-80. Zbl0751.90004 · Zbl 0751.90004 · doi:10.1016/0165-4896(92)90038-7
[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). · Zbl 0411.68039
[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. Zbl0554.90077 · Zbl 0554.90077 · doi:10.1287/opre.32.6.1195
[12] M. Grötschel, M. Jünger and G. Reinelt, Facets of the linear ordering polytope. Math. Program.33 (1985) 43-60. Zbl0577.05035 · Zbl 0577.05035 · doi:10.1007/BF01582010
[13] M. Grötschel, M. Jünger and G. Reinelt, On the acyclic subgraph polytope. Math. Program.33 (1985) 28-42. · Zbl 0577.05034 · doi:10.1007/BF01582009
[14] M. Grötschel, L. Lovász and A. Schrijver, Geometric algorithms and combinatorial optimization, Vol. 2 Algorithms and Combinatorics. Springer (1988). Zbl0634.05001 · Zbl 0634.05001
[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. Zbl0987.68006 · Zbl 0987.68006
[16] P. Jalote, Fault tolerance in distributed systems. Distributed Systems. Prentice Hall (1994). Zbl0900.68072 · Zbl 0900.68072
[17] H. Kellerer, U. Pferschy and D. Pisinger, Knapsack problems. Springer (2004). · Zbl 1103.90003
[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. Zbl0965.90057 · Zbl 0965.90057
[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). Zbl0565.68058 · Zbl 0565.68058
[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 · Zbl 1180.90137 · doi:10.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). · Zbl 1180.90138
[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). · Zbl 1180.90138
[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.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.