Polyhedral combinatorics of a resource-constrained ordering problem part II: on the process move program polytope

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

Abstract: This paper is the second 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. In the present paper, we put back into the picture the capacity constraints which were ignored in the first paper. In doing so, we introduce the process move program polytope, study its basic properties and show several classes of inequalities to be facet-defining. Some of the latter were proved to be facet-defining for the partial linear ordering polytope which was both introduced and studied in the companion paper.

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/017913 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