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 :
Theses
Complete list of metadatas

https://hal.univ-lorraine.fr/tel-01749855
Contributor : Thèses Ul <>
Submitted on : Thursday, March 29, 2018 - 12:29:59 PM
Last modification on : Tuesday, April 24, 2018 - 1:30:05 PM
Long-term archiving on : Friday, September 14, 2018 - 9:04:46 PM

File

INPL_T_2004_DEPPNER_F.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : tel-01749855, version 1

Collections

Citation

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⟩

Share

Metrics

Record views

58

Files downloads

408