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

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

RAIRO - Operations Research - Recherche Opérationnelle, Tome 41 (2007) no. 3, pp. 235-251.

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.

[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. | Zbl

[4] J. Carlier. Le problème de l'ordonnancement des paiements de dettes. RAIRO: Oper. Res. 18 février (1984). | EuDML

[5] T. Christof and G. Reinelt, Algorithmic aspects of using small instance relaxations in parallel branch-and-cut. Technical report, Heidelberg University (1998). | Zbl

[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). | MR | Zbl

[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. | Zbl

[9] P.C. Fishburn, Induced binary probabilities and the linear ordering polytope: a status report. Math. Social Sci. 23 (1992) 67-80. | Zbl

[10] M.R. Garey and D.S. Johnson, Computers and intractability | MR | Zbl

[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. | Zbl

[12] M. Grötschel, M. Jünger and G. Reinelt, Facets of the linear ordering polytope. Math. Program. 33 (1985) 43-60. | Zbl

[13] M. Grötschel, M. Jünger and G. Reinelt, On the acyclic subgraph polytope. Math. Program. 33 (1985) 28-42. | Zbl

[14] M. Grötschel, L. Lovász and A. Schrijver, Geometric algorithms and combinatorial optimization, Vol. 2 Algorithms and Combinatorics. Springer (1988). | MR | Zbl

[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. | Zbl

[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). | MR | Zbl

[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. | Zbl

[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). | MR | Zbl

[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 : 10.1016/j.ejor.2006.10.011) (2005). | MR

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