SEMINAIRES DU  GOTHA
			____________________

	Vendredi 3 décembre 1999, 14h30 
        à l'Université de Technologie de Compiègne (Amphi Bessel).
	(http://www.utc.fr)

	Exposé de
			David Rivreau
			(IMA)	


TITRE : Problèmes d'Ordonnancement Disjonctif : 
        Règles d'Élimination et Bornes inférieures


RESUME :
*****************************************************************************

 Les problèmes d’ordonnancement disjonctifs constituent un des archétypes de
 problèmes d’optimisation combinatoire difficiles à ce jour. Cette thèse est
 consacrée à l’étude des outils qui conditionnent la performance des
 techniques de résolution exacte pour ce type de problème.
 
 Dans la première partie du mémoire, nous passons en revue les principales
 règles disjonctives classiques et proposons quelques règles originales, dont
 le shaving local sur ensembles. Nous définissons également une nouvelle
 procédure qui calcule les ajustements optimaux des bornes de fenêtres
 temporelles. Les expérimentations numériques effectuées à l’aide de cette
 technique sur le problème de job-shop montrent que les ajustements sur
 ensembles ascendants/descendants proposés par J. Carlier et E. Pinson
 combinés au shaving local sur ensembles permettent d’obtenir la quasi
 totalité des ajustements réalisables au niveau d’une machine.
 
 Ceci considéré, nous proposons dans un second temps d’étendre ces règles
 classiques dans le cas particulier du flow-shop de permutation, en examinant
 cette fois des couples de machines. Les propriétés spécifiques de ce
 problème permettent en effet de définir de nouvelles règles et bornes à
 partir de sous-problèmes polynomiaux à deux machines (via l’algorithme
 Série-Parallèle de C. L. Monma et J. B. Sidney). Les tests effectués
 indiquent que les règles à deux machines apportent un gain significatif pour
 les flow-shop associant des jobs de tailles hétérogènes.
 
 Pour compléter l’étude, nous nous intéressons finalement à la minimisation
 du coût total pour le problème à une machine. Nous montrons en particulier
 qu’une technique de Programmation Dynamique indexée sur le temps utilisant
 une mémoire tampon résout une classe de problèmes à fenêtres temporelles
 contraintes. L’intégration de cet algorithme dans une relaxation
 Lagrangienne permet d’obtenir une borne inférieure qui s’avère d’excellente
 qualité pour le problème de la minimisation du nombre de tâches en retard.