SEMINAIRES DU  GOTHA
			____________________

	vendredi 6 octobre au LIP6 (Site Scott) Salle C769 à 10h00.

	Exposé de Safia Kedad-Sidhoum et Francis Sourd


TITRE : 

Le problème à une machine avec pénalités d'avance et de retard

RESUME :

Dans sa formulation la plus générale, le problème à une machine
avec pénalités d'avance et de retard autorise pour chaque tâche
une date d'échéance, un coût de pénalité d'avance (par unité de
temps) et un coût de pénalité de retard. De ce fait, le problème
est réputé très difficile. Dans le but de résoudre ce problème de
manière exacte, nous présentons une borne inférieure basée sur la
décomposition de chaque tâche en opérations unitaire suivie d'une
affectation. Le temps de calcul de cette borne dépend bien entendu
de l'horizon de l'ordonnancement: une grande partie de notre 
travail a alors consisté à réduire le temps de calcul de cette
borne. Nous présentons également plusieurs règles de dominance
valables pour ce problème.