Multiprocessor Scheduling under Precedence Constraints: Polyhedral Results

Pablo Coll (pecolldc.uba.ar)
Celso Ribeiro (celsoinf.puc-rio.br)
Cid Souza (cidic.unicamp.br)

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.

Download: [Postscript]

Entry Submitted: 10/12/2003
Entry Accepted: 10/12/2003
Entry Last Modified: 10/12/2003

Modify/Update this entry