Télécharger le fichier original (Mémoire de fin d’études)
Pr´esentation du probl`eme
Le probl`eme trait´e dans ce chapitre concerne un des probl`emes que rencontre l’entreprise et qui a ´et´e mentionn´e dans le chapitre 1, `a savoir la minimisation des pertes.
En effet, nous rappelons qu’il s’agit d’un atelier de production de type flow shop hybride `a deux ´etages. Le premier ´etage contient deux machines parall`eles d´edi´ees et le second ´etage comporte dix machines identiques parall`eles. Il y a deux s´eries de jobs : J1 = 1..n1, J2 = 1..n2. A chaque fois qu’il y a un changement de produit ; il y a un changement de moule. Cela n´ecessite un temps de setup. De plus, un time lag maximal est autoris´e entre les deux ´etages.
D’autre part, les ouvriers doivent nettoyer les machines sur le premier ´etage. Dans ce cas, o`u la production est interrompue pour plus de = 30 min, le r´esidu de pˆates coinc´e `a l’int´erieur de la
machine ne pouvait plus ˆetre recycl´e. Ce r´esidu repr´esente une quantit´e non n´egligeable. Il y a
environ 50 kilogrammes de produit perdu `a chaque arrˆet de machine. Par cons´equent, l’objectif est de minimiser les d´echets de produits en minimisant les occurrences de temps d’inactivit´e (idle-time) qui d´epasse les 30 minutes. En suivant la classification ||
[Graham et al., 1979], ce probl`eme pourrait ˆetre not´e comme FH2 (PD2,Pm) | STg,sd, li | Nidle−time−max. Il convient de signaler que nous ne traiterons pas un probl`eme bi-objectif. Nous nous int´eressons `a chaque objectif `a part. Pour chaque solution g´en´er´ee dans le cadre de la minimisation des nombres de temps morts d´epassant , nous calculons le Cmax correspondant et pour chaque solution g´en´er´ee dans le cadre de la minimisation du Cmax, nous d´eterminons le nombre d’arrˆets correspondant.
Travaux li´es
Des nombreux chercheurs ont d´ecrit des applications sur l’ordonnancement de permutation avec no-idle-time (no-idle permutation flow shop scheduling (NIPFS)) tels que les op´erations de fonderie et de traitement des fibres en verre pr´esent´e respectivement par [Saadani et al., 2005] et
[Kalczynski and Kamburowski, 2005]. R´ecemment [Tasgetiren et al., 2011] ont pr´esent´e de larges
exemples pratiques d’ordonnancement des jobs dans des environnements no-idle-time.
La contrainte de non-inactivit´e (no-idle time) apparaˆıt lorsque chaque machine doit traiter des travaux sans interruption de d´ebut du traitement du premier job dans la s´equence jusqu’`a l’ach`evement du traitement du dernier job. Autrement, il ne doit pas y avoir des intervalles de non-inactivit´e entre le traitement de toutes les op´erations cons´ecutives sur chaque machine.
[Ruiz et al., 2009] et [Goncharov and Sevastyanov, 2009] ont publi´e des revues r´ecentes sur le NPFSP dans lesquelles les auteurs ont confirm´e qu’il y a peu de travaux consid´erant deux contraintes simultan´ees : no-wait et no-idle-time. `A notre connaissance, la contrainte no-idle-time et celle de no-wait ont ´et´e ´etudi´ees pour la premi`ere fois par [Adiri and Pohoryles, 1982] dans un PFS afin de minimiser la somme de makespan. Plus tard, [Kalczynski and Kamburowski, 2007] ont ´etudi´e aussi les mˆemes contraintes simultan´ement.
De plus, [Baraz and Mosheiov, 2008] ont pr´esent´e un algorithme de glouton hybrid´e avec une heuristique am´elioratrice pour r´esoudre un NIPFS afin de minimiser le makespan. Plus r´ecemment, [Shao et al., 2017] a propos´e un algorithme mim´etique hybride pour r´esoudre un NIPFSP. Les auteurs ont travaill´e sur le crit`ere de makespan et ils ont compar´e leurs r´esultats avec des algorithmes existants.
D’apr`es la litt´erature, il semble que le seul travail concernant un flow shop hybride, et qui traite
le no-idle time, est celui de [Yazdani and Naderi, 2016]. En effet, les auteurs ont propos´e dans un
premier temps un MIP pour r´esoudre les petites instances `a l’optimalit´e. Dans un second temps,
deux m´eta-heuristiques, bas´ees sur la recherche au voisinage et les algorithmes g´en´etiques, sont d´evelopp´ees pour r´esoudre des instances les plus grandes.
En r´evisant la litt´erature, les contraintes li´ees aux arrˆets des machines : idle time et no-idle time
concernent le temps d’inactivit´e des ressources utilis´ees dans les ateliers de travail. Ceci est totalement diff´erent de l’objectif trait´e dans cette th`ese qui concerne le nombre de idle-time d´epassant une borne bien d´etermin´ee. Autrement dit, nous ne sommes pas int´eress´es `a minimiser la dur´ee d’inactivit´e des machines de l’E1 mais plus tˆot l’objectif souhait´e est de minimiser le nombre d’occurrences de ces arrˆets.
Adaptation du MIP au probl`eme trait´e
En partant du premier mod`ele math´ematique propos´e dans le chapitre 4, nous ajoutons la
donn´ee et les variables de d´ecisions suivantes :
1. Donn´ee : la dur´ee limite qui entraine une perte non n´egligeable
2. Variables de d´ecision TMm,1
i,j : dur´ee de temps mort entre le traitement du job i et j sur
la machine m de l’´etage 1
v1
i =
1 s’il y a un idle-time qui d´epasse apr´es le traitement du job i
0 sinon
3. Mod`ele math´ematique
Dans ce mod`ele, nous gardons les mˆemes contraintes (1),(2),(3),(4),(5), (6),(7), (8), (9), (10), (11)
et(12) que le premier mod`ele o`u on minimise Cmax comme objectif.
En premier temps, nous changeons l’objectif en minimiser le nombre des arrˆets de machines de
dur´ees maximales sur l’´etage 1. Ensuite, nous ajoutons les contraintes suivantes :
contrainte (13) calcule le temps mort entre 2 jobs affect´es `a une mˆeme machine
contrainte (14) exprime le temps mort qui ne doit pas d´epasser une dur´ee
contrainte (15) d´eclare xmk
ij , am,k
i et v1
i sont binaires, ´egale `a 30 minutes
contrainte (16) contrainte de non n´egativit´
Table des matières
Liste des tableaux
Table des figures
1 Introduction
2 Contexte du probl`eme
2.1 Description du probl`eme r´eel
2.1.1 D´efinition et caract´eristiques du cas d’´etude
2.1.2 Pr´esentation de l’entreprise
2.1.3 Description de la gamme de production
2.1.4 Description des lignes de production de l’entreprise
2.1.5 Description du s´echage
2.1.6 Description des contraintes
2.1.7 Description des objectifs
2.1.8 D´efinition des probl`emes d’ordonnancement
2.1.9 Classification scientifique du probl`eme
2.2 Complexit´e
2.3 Notations g´en´erales
2.4 G´en´eration de jeux de donn´ees
2.4.1 Donn´ees de test
2.4.2 G´en´eration de jeux d’instances
2.4.3 ´Etude de la difficult´e des instances de donn´ees
3 ´Etat de l’art
3.1 Introduction
3.2 FH Standard
3.3 Revue de la litt´erature du FH suivant les contraintes additionnelles
3.3.1 FH avec no-wait
3.3.2 FH avec time lag maximal
3.3.3 FH avec setup
3.4 FH avec machines d´edi´ees
3.5 R´esum´e des travaux de la litt´erature
3.6 Contributions scientifiques
3.7 Conclusion
4 Mod´elisation math´ematique et r´esolution
4.1 Mod´elisation math´ematique
4.1.1 1erMod`ele math´ematique pour minimiser Cmax
4.1.2 2`emeMod`ele math´ematique pour minimiser Cmax
4.2 Bornes inf´erieures
4.2.1 Pr´esentation des bornes
4.2.2 Comparaison des bornes inf´erieures
4.3 ´Evaluation de la meilleure borne
4.3.1 Comparaison de LBbest et LBCplex pour la cat´egorie 1 de jeu de donn´ees
4.3.2 Comparaison de LBbest et LBCplex pour la cat´egorie 2 de jeu de donn´ees
4.4 Exp´erimentations num´eriques
4.4.1 Comparaison de la taille des deux mod`eles math´ematiques
4.4.2 Comparaison des bornes de relaxation
4.4.3 R´esultats num´eriques des MIPs : Cat´egorie 1
4.4.4 R´esultats num´eriques des MIPs : Cat´egorie 2
4.5 Conclusion
5 M´ethodes approch´ees : algorithmes ´evolutionnistes
5.1 Introduction
5.2 Algorithme g´en´etique I
5.2.1 Codage de la solution
5.2.2 G´en´eration de la population initiale
5.2.3 ´Evaluation : calcul de Fitness
5.2.4 Op´erateurs g´en´etiques : s´election, croisement et mutation
5.3 Algorithme g´en´etique II
5.3.1 Codage de la solution
5.3.2 G´en´eration de la population initiale
5.3.3 ´Evaluation : Calcul de la Fitness
5.3.4 Op´erateurs g´en´etiques
5.4 Comparaison des AGs
5.5 Param´etrage des algorithmes
5.5.1 Les param`etres test´es
5.5.2 Choix des param`etres
5.6 Combinaison des AGs avec une recherche locale it´erative
5.6.1 Fonctionnement de la recherche locale
5.6.2 Fonctionnement de la recherche locale it´erative
5.7 Algorithme m´em´etique bas´e sur la recherche locale it´erative
5.8 Comparaison empirique des AGs
5.8.1 Comportement des AGs suivant le crit`ere d’arrˆet : nombre d’it´erations
5.8.2 Comportement des AGs suivant le crit`ere d’arrˆet : dur´ee d’ex´ecution
5.9 Analyse des r´esultats dans les deux cat´egories de donn´ees
5.10 Comparaison AG+RLI avec l’algorithme m´em´etique
5.11 Conclusion
6 M´ethode arborescente approch´ee
6.1 Introduction
6.2 Principe g´en´eral
6.3 Description du l’algorithme HA
6.3.1 Les notations propres `a l’heuristique HA
6.3.2 Sch´ema de branchement
6.3.3 Estimation des bornes au niveau des noeuds
6.3.4 Synth`ese de l’algorithme HA
6.4 Analyse empirique
6.4.1 ´Evaluation de
6.4.2 ´Evaluation de HA
6.4.3 Validation et r´esolution par MIP start de CPLEX
6.4.4 R´eglage des param`etres CPLEX
6.4.5 Comparaison des instances r´esolues `a l’optimalit´e par HA et MIP start
6.5 Conclusion
7 Gestion de pertes de mati`eres
7.1 Introduction
7.2 Pr´esentation du probl`eme
7.3 Travaux li´es
7.4 Adaptation du MIP au probl`eme trait´e
7.5 Adaptation du AG1 au probl`eme trait´e
7.5.1 Codage de la solution et g´en´eration de la population initiale
7.5.2 Classement des solutions et fonctions de fitness
7.5.3 Op´erateurs g´en´etiques
7.6 ´Etude de la minimisation des pertes et ses effets sur le comportement de Cmax
7.6.1 R´esultats trouv´es par les deux MIP
7.6.2 R´esultats trouv´es avec AGCmax et AGidle
7.7 Comparaison AG(Cmax,
7.8 Conclusion
8 Conclusion g´en´erale
A Analyse des param`etres AG
B Publications scientifiques
Bibliographie
