!  " #    $ 

                           !  " #    $   %   &   '  ( )    &   *      *  &   * ( + ,     -   &   '  . /    /    0 % 1 2 3       4 5 62 7 , &   '  * ( 0  -   &   '  ( 2, /    '  8 2 9   , *  , :   ;$ <  = > ?  #  @ A    $   B    ! ! C !  D B !  E        F  G H   ! !   B ! I J "    !  C E  !      $   !  H    $ K  L     M N O  P &  Q R M Q (  P    /  & &  * *    S  &  T = $ E E       ! 2U V % 4 W 1 6 1 8  1 6 1 LL , : 7      - * *   ( . /   * 2  *  L    8 1    2U X % 3 % Y 4 0 5     Z    - * *   ( 4   P  *  ,  ) / 7       )   [ *  G $ B $     ! 2U \ 6 % 2%X P *    - * *   ( 4   P  *  ,  3  ]  2U 2Y 4 ^ 6 0 2 % 9  9    - * *   ( 4   P  *  ,  ) / 7       \  & :  ]            _ D !  2& L % 4 1 6O  7      - * *   ( 4   P  *  ,  3       `  a           _ D !  2U L % 4 b 1 X\ 7   *  : 7 2 c   /   - ,   / * ( 4   P  *  ,  3       Résumé Ce sujet de thèse concerne de manière générale l'évaluation des performances et l'ordonnancement dans des systèmes de production flexibles et principalement les problèmes d'ordonnancement d'atelier de type Flow-Shop et Flow-Shop hybride. Le problème d'ordonnancement d'un Flow-Shop peut être défini ainsi : un ensemble de N jobs composés chacun de M opérations, doivent passer sur M machines dans le même ordre. Une machine peut exécuter une seule opération à la fois, chaque job ne peut avoir qu'une seule opération en cours de réalisation simultanément et la préemption n'est pas autorisée. Dans le cas des Flow-Shops hybrides, Mk machines identiques sont disponibles à chaque étage k en un ou plusieurs exemplaires. Pour cette étude, notre objectif est toujours de minimiser le temps total d'exécution aussi appelé makespan. Les problèmes d'ordonnancement les plus répandus sont de type Flow-Shop classique où les espaces de stockage entre les machines sont considérées comme infinies. D’autres problèmes sont caractérisés par des capacités de stockage limitées ou nulles qui engendre une seule contrainte de blocage. Cette contrainte peut être un blocage classique (de type RSb) ou particulier (de type RCb ou RCb*). Dans nos travaux de recherche, nous présentons un cas général qui peut être tiré de l'industrie et modélisé sous forme de systèmes de type Flow-Shop et Flow-Shop hybride soumis simultanément à plusieurs types de blocage. Pour résoudre ce genre de problèmes, nous avons étudié dans cette thèse la complexité de ces systèmes et nous avons proposé des méthodes exactes, des méthodes approchées ainsi que des bornes inférieures. Mots clés Systèmes de production flexibles, Flow-Shop, blocage, ordonnancement, optimisation. Abstract This thesis deals mainly with makespan minimization in Flow-Shop and hybrid Flow-Shop scheduling problems where mixed blocking constraints are considered. In Flow-Shop scheduling problem, a set of N jobs must be executed on a set of M machines. All jobs require the same operation order that must be executed according to the same manufacturing process. Each machine can only execute one job at any time. Pre-emptive operation is not authorized in presented work. In case of hybrid Flow-Shop, at any processing stage k, there exist one or more identical machines Mk. Objective function consists in determining best schedule in order to reduce makespan, i.e. time where all operations are completed. The most common scheduling problem is classical flowshop where buffer space capacity between machines is considered as unlimited. Other problems are characterized by the fact that the storage capacity is limited or null and which generates one blocking constraint. This constraint can be a classical blocking (RSb) or particular blocking (RCb or RCb*). In our works, we present a general case which can be derived from industry and modeled as Flow-Shop and hybrid Flow-Shop systems subject simultaneously to different blocking. To solve these problems, we studied in this thesis complexity of these systems and we proposed exact methods, approached methods and lower bounds. Keywords Flexible production systems, flowshop, blocking, scheduling, optimization 6 Table des matières Introduction générale ...................................................................................................................... 14 Première partie : Présentation du problème et état de l'art .................................................... 16 Chapitre 1 Présentation du problème ......................................................................................... 20 1. 1. Introduction .................................................................................................................... 20 1. 2. Systèmes de production de type Flow-Shop .................................................................. 21 1. 2. 1. Flow-Shop classique .............................................................................................. 21 1. 2. 2. Flow-Shop hybride ................................................................................................. 22 1. 3. Contraintes de blocage ................................................................................................... 23 1. 3. 1. Contrainte de blocage classique (blocage RSb) ...................................................... 24 1. 3. 2. Contrainte de blocage particulière (blocage RCb) ................................................. 25 1. 3. 3. Nouvelle contrainte de blocage (blocage RCb*) .................................................... 27 1. 3. 4. Blocage mixte ......................................................................................................... 28 1. 4. Notations ........................................................................................................................ 29 1. 5. Conclusion ...................................................................................................................... 29 Chapitre 2 État de l'art ................................................................................................................ 30 2. 1. Introduction .................................................................................................................... 30 2. 2. Les méthodes de résolution ............................................................................................ 30 2. 2. 1. Les méthodes exactes ............................................................................................. 31 2. 2. 2. Les méthodes approchées ....................................................................................... 32 2. 3. Flow-Shop ...................................................................................................................... 33 2. 3. 1. Flow-Shop classique (Wb) ..................................................................................... 33 Table des matières _______________________________________________________________ 7 2. 3. 2. Flow-Shop avec blocage (RSb, RCb, RCb*, mixte) ............................................... 36 2. 1. Flow-Shop hybride ......................................................................................................... 39 2. 1. 1. Flow-Shop hybride classique (Wb) ........................................................................ 39 2. 1. 2. Flow-Shop hybride avec blocage (RSb, RCb, RCb*, mixte) .................................. 42 2. 1. Conclusion ...................................................................................................................... 44 Deuxième partie : Le Flow-Shop avec blocage mixte ................................................................ 46 Chapitre 3 Complexité ............................................................................................................... 48 3. 1. Introduction .................................................................................................................... 48 3. 2. Modélisation ................................................................................................................... 48 3. 2. 1. Graphe disjonctif .................................................................................................... 48 3. 2. 2. Graphe disjonctif avec blocage RSb ....................................................................... 50 3. 2. 3. Graphe disjonctif avec blocage RCb ...................................................................... 51 3. 2. 4. Graphe disjonctif avec blocage RCb* .................................................................... 51 3. 3. Complexité ..................................................................................................................... 53 3. 3. 1. Flow-Shop avec la contrainte de blocage RCb*..................................................... 53 3. 3. 2. Flow-Shop avec blocage mixte (2 contraintes) ...................................................... 56 3. 3. 3. Flow-Shop avec blocage mixte (3 contraintes) ...................................................... 61 3. 4. Conclusion ...................................................................................................................... 61 Chapitre 4 Méthodes de résolution exacte ................................................................................. 64 4. 1. Introduction .................................................................................................................... 64 4. 2. Modèle mathématique .................................................................................................... 64 4. 3. Conclusion ...................................................................................................................... 69 Chapitre 5 Méthodes approchées ............................................................................................... 70 _______________________________________________________________ Table des matières 8 5. 1. Introduction .................................................................................................................... 70 5. 2. Borne inférieure .............................................................................................................. 70 5. 3. Heuristiques .................................................................................................................... 75 5. 3. 1. Heuristique NEH .................................................................................................... 76 5. 3. 2. Heuristique TSS ..................................................................................................... 77 5. 3. 3. Amélioration locale NEH ....................................................................................... 80 5. 3. 4. Amélioration locale TSS ........................................................................................ 81 5. 3. 5. Résultats expérimentaux ........................................................................................ 82 5. 4. Métaheuristique .............................................................................................................. 84 5. 4. 1. Algorithme génétique ............................................................................................. 85 5. 4. 2. Résultats expérimentaux ........................................................................................ 87 5. 5. Conclusion ...................................................................................................................... 89 Troisième partie : Le Flow-Shop hybride avec blocage mixte ................................................. 92 Chapitre 6 Méthode de résolution exacte ................................................................................... 94 6. 1. Introduction .................................................................................................................... 94 6. 2. Modèle mathématique .................................................................................................... 94 6. 3. uploads/Industriel/ these-trabelsi-2012-pdf.pdf

Documents similaires

DEVOIR DE MAISON A la suite d'un audit, l'équipe de direction du Croissant d'or 0 0

Sommaire Introduction ......................................................... 0 0

LES MISES EN OEUVRE Parts de marchés Injection Thermoplastiques Granulés The 0 0

1 Introduction générale Les grandes évolutions industrielles et économiques du 0 0

Pr. Hassan BELLIHI Cours de Gestion de Production 1 ENCG AGADIR Université Ibn 0 0

EXPOSÉ : SMED EKOBO ERIKA PROF : MR TCHUENKAM CHRISTOPHE FAIT PAR : EKOBO ÉRIKA 0 0

6 qualités indispensables pour devenir programmeur Ce guide est issu du site we 0 0

PSA PEUGEOT - CITROËN Normes Biens d'Equipement E03.65.036.G ICS : 25.040.01, 3 0 0

MEMOIRE DE PROJET DE FIN D’ETUDES Pour l’Obtention du Diplôme de Mater Sciences 0 0

Rapport de TP Prélude Production :l’usine Picaso Réalisé par : Nanna EL KOURI R 0 0

• Détails
• Publié le Jan 05, 2023
• Catégorie Industry / Industr...
• Langue French
• Taille du fichier 3.3831MB