Research Article

A new formulation for scheduling unrelated processor under precedence constraints

Maculan, Nelson^a1, Porto, Stella C.S.^a2, Ribeiro, Celso C.^a3 and Cid Carvalho de Souza^a4

^a1 Universidade Federal do Rio de Janeiro COPPE - Engenharia de Sistemas e Computaçao Caixa Postal 68511, Rio de Janeiro 21945-970 Brazil, e-mail: maculan@cos.ufrj.br

^a2 Universidade Federal Fluminense Dept. of Telecommunication Engineering Rua Passos da Pátria 156, Niterói 24210, Brazil, e-mail: stella@caa.uff.br

^a3 Pontifícia Universidade Católica Departamento de Informática Rua Marquès de São Vicente 225, Rio de Janeiro 22453-900, Brazil, e-mail: celso@inf.puc.rio.br

^a4 Universidade Estadual de Campinas Departamento de Ciência de Computação Caixa Postal 6065, Campinas 13081, Brazil, e-mail: cid@dcc.unicamp.br

Abstract

We give a new formulation for the problem of task scheduling into unrelated processors under precedence constraints. This formulation has a polynomial number of variables and does not require that the processing times be integer valued.

Résumé

Nous donnons ici une formulation nouvelle du problème de l'ordonnancement des tâches utilisant des processeurs indépendants sous contraintes de cette formulation à un nombre polynomial de variables et n'exige pas que les temps de traitement aient des valeurs entières.

(Received September 1996)

(Online publication August 15 2002)

Key Words:

• Parallel processing;
• scheduling;
• unrelated processors;
• precedence constraints;
• makespan.