Ordonnancement d'atelier avec contraintes temporelles entre opérations - Université de Lorraine Access content directly
Theses Year : 2004

Scheduling problems with minimal and maximal time lag constraints

Ordonnancement d'atelier avec contraintes temporelles entre opérations

Abstract

In this thesis we study scheduling problems with minimal and maximal time lags between operations. A minimal time lag specifies that an operation can't start its execution before a given amount of time has elapsed since the beginning or the end of a previous operation. Conversely, with a maximal time lag, the operation must start its execution within a given delay. Despite many industrial processes are subjected to such time constraints, publications on the topic rernain poor. A possible éxplanation could be that the proble:rn of designing a feasible solution with maximal time lags is NP-complete for sorne cases including single machine problems. In order to obtain a feasible solution, we generalize various priority rule construction algorithms. We design an algorithm using a decomposition of the set of operations into clusters defined as the strong components of the conjunctive graph. We demonstrate that under sorne realistic hypotheses, our algorithms converge and 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 a selection method that automatically chooses 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.
Cette thèse traite des problèmes d'ordonnancement d'atelier avec contraintes temporelles d'écart minimal et maximal entre opérations. Une contrainte d'écart minimal stipule qu'une opération ne peut débuter son exécution avant qu'un laps de temps ne se soit écoulé depuis le début ou la fin d'une opération précédente. Une contrainte d'écart maximal impose au contraire que l'opération débute son exécution dans un délai imparti. Bien que de nombreux cas industriels soient soumis à ce genre de contraintes, la littérature sur le sujet reste réduite. Une explication possible tient au fait qu'en présence d'écarts maximaux, le problème de la construction d'une solution valide est NP-complet, dans les cas les plus généraux, même pour une machine. Pour obtenir une solution faisable nous généralisons les algorithmes de construction à base de règles de priorité ou de liste d'ordre strict. Nous étudions un algorithme utilisant une partition des opérations en sous ensembles définis à partir des composantes fortement connexes du graphe conjonctif. Nous démontrons que, sous certaines hypothèses, nos algorithmes convergent et produisent des ordonnancements actifs. Qui dit ordonnancement sous-entend optimisation d'un objectif. Nous nous intéressons à l'optimisation de la durée totale (makespan) pour des problèmes de machines en série (flowshop) avec contraintes d'écart minimal et maximal, organisation d'atelier rencontrée le plus fréquemment au cours de nos études de cas. Nous développons une approche génétique dont l'originalité consiste à travailler avec un pool d'opérateurs de croisement et à utiliser une méthode d'autodétermination qui sélectionne l'opérateur le plus approprié à la problématique et à l'état courant de la population. Nous hybridons notre méthode avec un algorithme d'optimisation locale de plus forte pente après avoir étudié et généralisé les voisinages en présence d'écarts maximaux.
Fichier principal
Vignette du fichier
INPL_T_2004_DEPPNER_F.pdf (11.92 Mo) Télécharger le fichier
Origin : Files produced by the author(s)

Dates and versions

tel-01749855 , version 1 (29-03-2018)

Identifiers

  • HAL Id : tel-01749855 , version 1

Cite

Freddy Deppner. Ordonnancement d'atelier avec contraintes temporelles entre opérations. Autre [cs.OH]. Institut National Polytechnique de Lorraine, 2004. Français. ⟨NNT : 2004INPL021N⟩. ⟨tel-01749855⟩
193 View
860 Download

Share

Gmail Facebook X LinkedIn More