  


Polyhedral combinatorics of a resourceconstrained ordering problem part I: on the partial linear ordering polytope
Renaud Sirdey (renaudsnortel.com) Abstract: This paper is the first of a series of two devoted to the polyhedral study of a strongly NPhard resourceconstrained scheduling problem, referred to as the process move programming problem. This problem arises in relation to the operability of certain highavailability 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 facetdefining. 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 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  