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.