SEMINAIRES DU  GOTHA
			____________________

	vendredi 15 juin 2001 au LIP6 (Site Scott) Salle C769 à 10h00.

	Exposé de Stephane Dauzere-Peres et Chams Lahlou (EMN)


TITRE : 

Ordonnancement sur une machine de taches dont les durees dependent de
fenetres de temps



RESUME :

Un certain nombre de travaux ont ete consacres a l'ordonnancement sur
1 machine dans le cas ou la duree d'une tache est une fonction du
temps, selon plusieurs criteres (principalement la minimisation du
C_max). Cette modelisation est utilisee pour differents problemes
reels, comme par exemple lorsque l'on utilise un four pour fabriquer
une piece : la duree de fabrication va augmenter avec le temps car le
four se refroidit et doit etre rechauffe. La fonction donnant la duree
d'une tache est generalement lineaire : p_j = l_j +b*t_j (avec l_j =
duree de base d'une tache j, t_j = date de demarrage de j, et p_j =
duree d'execution reelle de j).

Dans notre cas on s'interesse a l'hypothese d'une duree d'execution
qui depend, pour chaque tache j, de sa duree de base l_j et de la
fenetre dans laquelle elle demarre. On considere pour cela 2 modeles :
p_j = l_j + w_ij (modele M+) et p_j = l_j * w_ij (modele M*) avec w_ij
= coefficient associe au couple (tache j, fenetre i) et l'on cherche a
minimiser C_max.

On montre tout d'abord que trouver un ordonnancement optimal est un
probleme polynomial pour M+ et M* dans 2 cas :
1) si la sequence de passage des taches sur la machine est fixee
2) si les taches ont la meme duree de base et w_ij = w_i pour toute
fenetre i
La complexite de l'algorithme vaut alors O(n.w) si l'on a n taches et w
fenetres.

Lorsque la sequence n'est pas fixee et lorsque le nombre de fenetres
est fixe (2 pour M* et 3 pour M+) on montre que le probleme est
NP-difficile dans 2 cas :
1) les taches n'ont pas la meme duree de base et w_ij = w_i pour toute
fenetre i
2) les taches ont la meme duree de base mais les w_ij sont quelconques

On propose un algorithme pseudo-polynomial dans le cas du modele M*
lorsque l'on a 2 fenetres et l'on termine l'expose en presentant la
complexite de certains cas particuliers.