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

Renaud Sirdey (renaudsnortel.com)
Hervé L. M. Kerivin (kerivinmath.univ-bpclermont.fr)

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.

Keywords: Polyhedral combinatorics, scheduling, branch-and-cut, distributed systems.

Category 1: Combinatorial Optimization (Branch and Cut Algorithms )

Category 2: Applications -- OR and Management Sciences (Scheduling )

Category 3: Applications -- OR and Management Sciences (Telecommunications )

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.

Download: [Postscript]

Entry Submitted: 04/10/2006
Entry Accepted: 04/11/2006
Entry Last Modified: 10/02/2006

Modify/Update this entry