Ordonnancement d'atelier avec contraintes temporelles entre opérations

Nous étudions les problèmes d'ordonnancement d'atelier avec contraintes temporelles d'écart minimal et maximal entre opérations. Avec écarts maximaux, la construction d'une solution valide est un problème NP-complet pour certains cas généraux dès une machine. Nous généralisons les algorithmes de construction à base de règles de priorité ou de liste d'ordre strict. Nous utilisons la partition des opérations selon les composantes fortement connexes du graphe conjonctif et démontrons que, sous certaines hypothèses, nos algorithmes produisent des ordonnancements actifs. Nous nous intéressons ensuite à l'optimisation du makespan pour le problème de type flowshop avec contraintes temporelles. Nous développons une approche génétique consistant à travailler avec un pool d'opérateurs de croisement et à sélectionner automatiquement l'opérateur le plus approprié à la problématique et à la population courante. Nous hybridons notre méthode avec un algorithme d'optimisation locale.We study scheduling problems with minimal and maximal time lags between operations. The construction of a feasible solution with maximal time lags is a NP-complete problem for some cases including single machine problems. In order to obtain a feasible solution, we generalize priority rule construction algorithms. We design an algorithm using a decomposition of the operations according to the strong components of the conjunctive graph. We demonstrate that under some realistic hypotheses, our algorithms generate active schedules. In a second part, we study the minimization of the makespan for flow shop problems. For this purpose, we develop a genetic algorithm. The main feature is that we are working with a pool of crossover operators and an automatic selection method of the most adapted operator according to the problem and the current state of the population. We finally couple our genetic algorithm with a local search procedure.NANCY/VANDOEUVRE-INPL (545472102) / SudocSudocFranceF