Abstract FR:

Le probleme de job-shop est couramment modalise par un graphe disjonctif. Pour la resolution, il faut arbitrer rapidement un grand nombre de disjonctions. Une nouvelle approche de resolution basee sur la notion d'arbitrage trivial est developpee. Un algorithme polynomial est propose, il est utilise pour la construction d'une heuristique et d'une methode exacte