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

  • Hervé L. M. Kerivin
  • Renaud Sirdey
    • Categories Branch and Cut Algorithms, Scheduling, Telecommunications Tags , , , Short URL: https://optimization-online.org/?p=9906

    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.

    Citation

    Report n° PE/BSC/INF/017912, Nortel GSM Access R&D, march 2006. To appear in the special issue on Polyhedra and Combinatorial Optimization of RAIRO - Operations Research.

    Article

    Download

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