next up previous
suivant: Un exemple simple : le monter: Le problème précédent: Les contraintes cumulatives

Contraintes disjonctives

Ces contraintes permettent de spécifier que 2 tâches ne peuvent pas avoir lieu en même temps (par exemple, les entrepreneurs qui en sont chargés ne s'entendent pas). La première méthode pour modéliser cette contrainte consiste à utiliser un ou logique sur les deux contraintes de potentiel suivantes :
$\displaystyle t_i + d_i \leqslant t_j
$      
$\displaystyle t_j + d_j \leqslant t_i$      

Aussi élégante soit elle, cette méthode n'est guère recevable car elle entraîne des difficultés algorithmiques non négligeables. En particulier, le nombre de cas à traiter séparément explose lorsque l'on augment le nombre de disjonctions. L'autre méthode consiste à introduire une contrainte d'allocation de ressource entre ces deux tâches. De toute manière, le traitement de ces contraintes est malaisé dans le cas général. Dans la suite de cet exposé, nous ne considérerons que des contraintes de potentiel simples.

Bruno Garcia 2000-12-17