Abstract FR:

Les problemes d'ordonnancement d'atelier a taches sont np-complets; ainsi leur resolution peut etre simplifiee considerablement par la decomposition en sous-problemes. Quand la decomposition est parfaite (i. E. Il n'existe pas de liens entre les sous-problemes), les methodes connues sont satisfaisantes puisqu'elles diminuent le volume des calculs. Dans le cas contraire, elles deviennent discutables car leur complexite est inconnue et elles ne peuvent pas garantir une qualite donnee pour les solutions fournies. Pour pallier ces lacunes, nous proposons dans cette these une methode par decomposition pour une classe de job-shop. La fonction de complexite algorithmique et la qualite des solutions obtenues par cette methode font son interet. Dans un but purement didactique nous presentons dans le chapitre 1 quelques elements de base de la theorie d'ordonnancement; les deuxieme et troisieme chapitres sont consacres a la construction des outils de base pour le developpement de notre methode qui est presentee dans le chapitre iv. Dans le chapitre v nous presentons brievement notre programme informatique (realise en c sur une station de travail sun), ce dernier chapitre est complete avec la presentation de la resolution de quelques exemples d'ordonnancement d'atelier a taches