Skip to Main content Skip to Navigation

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.
Document type :
Complete list of metadata
Contributor : Thèses UL Connect in order to contact the contributor
Submitted on : Thursday, March 29, 2018 - 12:29:59 PM
Last modification on : Saturday, October 16, 2021 - 11:26:08 AM
Long-term archiving on: : Friday, September 14, 2018 - 9:04:46 PM


Files produced by the author(s)


  • HAL Id : tel-01749855, version 1



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⟩



Record views


Files downloads