Optimization Online


Multiprocessor Scheduling under Precedence Constraints: Polyhedral Results

Pablo Coll (pecoll***at***dc.uba.ar)
Celso Ribeiro (celso***at***inf.puc-rio.br)
Cid Souza (cid***at***ic.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

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society