Multiprocessor Scheduling under Precedence Constraints: Polyhedral Results
Pablo Coll (pecolldc.uba.ar)
Abstract: We consider the problem of scheduling a set of tasks related by precedence constraints to a set of processors, so as to minimize their makespan. Each task has to be assigned to a unique processor and no preemption is allowed. A new integer programming formulation of the problem is given and strong valid inequalities are derived. A subset of the inequalities in this formulation has a strong combinatorial structure, which we use to define the polytope of partitions into linear orders. The facial structure of this polytope is investigated and facet defining inequalities are presented which may be helpful to tighten the integer programming formulation of other variants of multiprocessor scheduling problems.
Keywords: Multiprocessor scheduling, precedence constraints, polyhedral results, integer programming
Category 1: Applications -- OR and Management Sciences (Scheduling )
Category 2: Combinatorial Optimization (Branch and Cut Algorithms )
Category 3: Integer Programming (0-1 Programming )
Citation: Research report, submitted for publication, 2003.
Entry Submitted: 10/12/2003
Modify/Update this entry
|Visitors||Authors||More about us||Links|
Search, Browse the Repository
Give us feedback
|Optimization Journals, Sites, Societies|