Minimizing the makespan for a UET bipartite graph on a single processor with an integer precedence delay

A. Munier-Kordon

LIP6 2001/016: Rapport de Recherche LIP6 / LIP6 research reports
14 pages - Juin/June 2001 - Document en anglais.

Get it : 168 Ko /Kb

Contact : par mail / e-mail

Thème/Team: Systèmes d'Aide à la Décision et à la Formation

Titre français : Minimiser la durée d'un ordonnancement pour un graphe biparti sur un processeur avec un délai entier et des tâches de durée unitaire
Titre anglais : Minimizing the makespan for a UET bipartite graph on a single processor with an integer precedence delay

Résumé : Nous considèrons un ensemble de tâches de durée unitaire et un graphe de delais de précédence biparti avec une valeur du delai d: tout arc (i,j) de ce graphe signifie que j doit être exécutée au moins d unités de temps après l'exécution de i. Le problème est alors de déterminer un ordonnancement des tâches sur un processeur de durée minimale.
Dans un premier temps, nous montrons que le problème de décision associé est NP-complet. Puis, nous développons un algorithme polynomial non trivial dans le cas ou le degré de toutes les tâches de l'un des deux ensembles du graphe biparti est 2. Finalement, nous développons un algorithme approché de ratio de performance 3/2.

Abstract : We consider a set of tasks of unit execution times and a bipartite precedence delays graph with a positive precedence delay d: an arc (i,j) of this graph means that j can be executed at least d time units after the completion time of i. The problem is to sequence the tasks in order to minimize the makespan.
Firstly, we prove that the associated decision problem is NP-complete. Then, we provide a non trivial polynomial time algorithm if the degree of every tasks from one of the two sets is 2. Lastly, we give an approximation algorithm with ratio 3/2.

Mots-clés : Ordonnancement, délais de précédence, graphe biparti

Key-words : Sceduling, precedence delays, bipartite graph

Publications internes LIP6 2001 / LIP6 research reports 2001

Responsable Éditorial / Editor :Valerie.Mangin@lip6.fr