Polyhedral combinatorics of a resource-constrained ordering problem part I: on the partial linear ordering polytope

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

Abstract: This paper is the first of a series of two devoted to the polyhedral study of a strongly NP-hard resource-constrained scheduling problem, referred to as the process move programming problem. This problem arises in relation to the operability of certain high-availability real time distributed systems. After a brief introduction to the problem as well as a summary of previous results, we formulate it as an integer linear program using linear ordering variables. We then drop the capacity constraints and introduce the partial linear ordering polytope, defined as the convex hull of all incidence vectors of arc sets of linear orderings of a node subset of the complete digraph on n nodes (the nodes not in the subset being looped), study its basic properties as well as show several classes of inequalities to be facet-defining. The companion paper is devoted to the study of the process move program polytope which is obtained when the capacity constraints are put back into the picture.

Keywords: Polyhedral combinatorics, scheduling.

Category 1: Combinatorial Optimization

Category 2: Combinatorial Optimization (Polyhedra )

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

Citation: Technical report Nortel GSM Access R&D PE/BSC/INF/017912 V01/EN. Submitted to Mathematical Programming.

Download: [Postscript]

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

Modify/Update this entry