Algorithmes de dénombrement d'extensions linéaires d'un ordre partiel et application aux problèmes d'ordonnancement disjonctif

En programmation par contraintes, une contrainte de ressource unaire est un ensemble de permutations valides des activités chacune avec une fenêtre de temps et une durée. Cette contrainte est généralisée si on considère des préséances entre activités données sous la forme d'un ensemble partiellement ordonné. Un problème d'ordonnancement disjonctif peut être modélisé par une ou plusieurs contraintes de ressource unaire auxquelles s'ajoutent des contraintes supplémentaires telles que des disjonctions entre activités de différentes ressources ou des contraintes de séquences. La recherche d'une solution au problème se fait par une série de décisions de la position relative d'une paire d'activités associées à une contrainte dont l'ordre n'est pas encore connu. L'algorithme utilisé dans le choix de la paire ainsi que la position relative est appelé heuristique de branchement. Dans le contexte de l'heuristique maxSD, il s'agit de calculer les densités de solutions de toutes les assignations de paires d'activités à un ordre et ensuite de brancher sur celle de densité maximum. Pour adapter cette heuristique aux problèmes d'ordonnancement avec contraintes de ressource unaire, on considérera les densités de permutations dans lesquelles une activité est placée avant l'autre dans l'ordre partiel associé à chaque contrainte. Pour ce faire, on propose deux algorithmes exact et heuristique pour le calcul des densités de permutations dans un ensemble partiellement ordonné. Ces algorithmes sont utilisés dans l'heuristique de branchement pour résoudre la version de satisfaction de contraintes du problème Job-Shop, un cas typique d'ordonnancement avec ressources unaires.