LIP6 2001/016
- Reports
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 - A. Munier-Kordon
- 14 pages - 06/11/2001- document en - http://www.lip6.fr/lip6/reports/2001/lip6.2001.016.pdf - 172 Ko
- Contact : Alix.Munier (at) nulllip6.fr
- Ancien Thème : SYSDEF
- Keywords : Sceduling, precedence delays, bipartite graph
- Publisher : Valerie.Mangin (at) nulllip6.fr
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.
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.