Analyse de conflit non-standard pour résoudre le problème de Job-Shop

International audienceNous proposons une nouvelle méthode hybride SAT/PPC pour résoudre le problème de Job-Shop à minimisation de makespan. Dans ce contexte d'hybridation, chaque propagateur implémente une routine d'explication à travers la quelle il est capable de représenter les filtrages et échecs qu'il provoque sous forme de clauses (appelées explications). Les littéraux figurant dans les explications représentent des contraintes unaires sur les bornes (inférieure ou supérieure) ou d'(in)égalité. Considérons le problème de Job-Shop où les contraintes de partage de ressources sont exprimées à travers des disjonctions. Par exemple si t1 et t2 partagent la même machine, la contrainte de disjonction associée sera [ t1+a