SEMINAIRES DU  GOTHA

Prochaine réunion le vendredi 24 mars au LIP6 (Site Scott) Salle C769
à 10h00.

EXPOSE d'Emmanuel (Cosytec)

TITRE : Contrainte cumulative pour des problèmes où les tâches ont une
consommation linéaire par morceaux.

RESUME :

La majorité des travaux sur les problèmes d'ordonnancement est
consacrée à des problèmes où les tâches sont modélisées par des
rectangles. Cependant, dans la plupart des problèmes cumulatifs, les
quantités de ressources consommées varient en fonction du temps. Deux
problèmes se présentent alors : la gestion instantanée des ressources
et la gestion cumulée des ressources. On peut distinguer le cas où les
ressources sont discrètes (hommes, machines) de celui où elles sont
continues (électricité, eau, matières premières). Dans le cas de
ressources discrètes, les tâches peuvent alors être modélisées par des
suites de rectangles contigus et dans celui de ressources continues
par des suites de trapèzes contigus représentant une fonction linéaire
par morceaux. Dans le cas continu, une modélisation utilisée est
l'approximation des tâches par des rectangles liés entre eux par des
contraintes externes. Mais un nombre élevé de rectangles est
nécessaire pour une bonne approximation ce qui entraîne une forte
augmentation de la taille du problème. De plus, dans les deux cas
(discret et continu) le morcellement des tâches en sous-tâches
(rectangles ou trapézoïdales) appauvrit les déductions possibles. Nous
allons présenter, dans le cadre de la programmation par contrainte,
une nouvelle contrainte globale permettant de considérer dans leur
ensemble et non pas par morceaux des tâches définies par des suites de
trapèzes contigus. Cette nouvelle contrainte permet, entre autres, de
modéliser les problèmes décrits ci-dessus sans utiliser
d'approximation, ni de morcellement de tâches. Nous présenterons une
extension de la notion de partie obligatoire ainsi que diverses
applications possibles de cette nouvelle contrainte (ordonnancement
cumulatif, gestion de stock (problèmes producteur/consommateur),
condition nécessaire de placement de formes polygonales).