Polyhedral combinatorics of a resource-constrained ordering problem part II: on the process move program polytope
Hervé Kerivin (kerivinmath.univ-bpclermont.fr)
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.
Entry Submitted: 10/02/2006
Modify/Update this entry
|Visitors||Authors||More about us||Links|
Search, Browse the Repository
Give us feedback
|Optimization Journals, Sites, Societies|