Résumé: La programmation par contrainte est l’une des techniques qu’il est possible d’utiliser pour s’attaquer aux problèmes NP-Difficiles. Elle est particulièrement efficace pour résoudre des problèmes d’ordonnancement. La contrainte Cumulative est l’une des clés du succès de la programmation par contrainte en ordonnancement. Cette contrainte limite la quantité d’une ressource qui peut être utilisée par des tâches à tout moment. On pourrait, par exemple, avoir 100 personnes (les tâches) qui doivent aller faire l’épicerie, alors que les règles gouvernementales limitent la capacité d’accueil à 30 personnes à la fois (la ressource). Jusqu’à maintenant, la programmation par contraintes ne disposait pas de contraintes globales pour le problème inverse, c’est-à-dire avoir une quantité minimale de la ressource utilisée. C’est cependant un scénario fréquent dans la réalité. On peut vouloir avoir au moins 5 employés en tout temps dans l’épicerie pour en assurer le bon fonctionnement. Nous proposons la MinCumulative, une contrainte globale pour modéliser et résoudre ce problème. Lors du séminaire, nous nous assurerons d’introduire les notations préalables en programmation par contraintes et en ordonnancement. Nous présenterons ensuite la MinCumulative et démontrerons, à l’aide d’une réduction, que décider si la contrainte admet une solution est NP-Complet. Nous introduirons ensuite les algorithmes de vérification et de filtrage qui permettent à la MinCumulative d’être efficace. Nous terminerons par la présentation de résultats expérimentaux démontrant l’efficacité pratique de la nouvelle contrainte.
Les enregistrements sont disponibles ici: http://www2.ift.ulaval.ca/~quimper/Seminaires/
