Chapitre 2 : Lordonnancement de la production
Nombreuses sont les définitions proposées au problème d'ordonnancement Problèmes Flow-Shop : les ateliers de type Flow-Shop appelés également ateliers à.
Les problèmes dordonnancement de type « flow-shop » hybride
Définition du flow-shop hybride. Nous concentrons désormais nos réflexions sur une organisation du processus de production en série « MASSE-ATELIER » telle
Problèmes dordonnancement dans les systèmes de production de
Les modèles théoriques que nous avons étudiés sont le modèle du Flow-Shop et le modèle des problèmes d'ordonnancement leur définition n'est ni toujours ...
Résolution de problèmes dordonnancement de type Flow-Shop de
crée à la résolution des problèmes d'ordonnancement Flow-Shop avec contraintes nition les différentes notions qui interviennent dans cette définition
MEMOIRE de fin détude SUJET Un problème Flow Shop à deux
17?/09?/2020 Résolution du problème Flow Shop à deux machines avec des temps de ... Sur cette définition du problème de flow-shop peuvent venir se ...
Sur lordonnancement dateliers job-shop flexibles et flow-shop en
16?/03?/2011 flow-shop en industries pharmaceutiques: optimisation ... définition des paramètres des variables
RÈGLES DÉLIMINATION POUR FLOW-SHOP DE PERMUTATION
27?/04?/2001 flow-shop de permutation à 3 jobs et 4 machines dont les ... ininterrompues de jobs via la définition de jobs compo-.
Ordonnancement dateliers en présence dopérateurs
tâches sur chaque machine est identique on parle de flow shop de permutation. Il découle de cette définition que si ? est NP-complet et n'est pas un ...
Flow-shop à deux machines avec des temps de latence : approche
Il est alors clair que cet ordonnancement est actif car si on place le JI avant le job J2 sur M2 la troisième condition de la Définition 3 (ci dessous) ne sera
A Novel Hybrid Algorithm for Permutation Flow Shop Scheduling
The processing time for each operation has been determined. Machine Sequence is defined for each job. There is a pre-defined sequence of operations that has to.
L ‘IMPLANTATION DES MOYENS DE PRODUCTION
>L ‘IMPLANTATION DES MOYENS DE PRODUCTIONhttps://d1n7iqsz6ob2ad cloudfront net/document/ pdf /532741d2de · Fichier PDF
3eConférence Francophone de MOdélisation et SIMulation "Conception, Analyse et Gestion des Systèmes Industriels»
MOSIM"01 - du 25 au 27 avril 2001 - Troyes (France)RÈGLES D"ÉLIMINATION POUR FLOW-SHOP DE PERMUTATION:
CAS DES GAMMES HOMOGÈNES ET HÉTÉROGÈNESLaurent PÉRIDY, Éric PINSON, David RIVREAU
Institut de Mathématiques Appliquées
Université Catholique de l"Ouest
BP 808
Angers, 49008 Angers Cedex, France
Mél: david.rivreau@ima.uco.fr
RÉSUMÉ:Le problème de Flow-Shop de Permutation est un problème d"ordonnancement typique des ateliers agencés
en lignes qui consiste à séquencer l"exécution de gammes opératoires sur la ligne de production. Dans cet article, nous
montrons que l"utilisation de règles d"élimination spécifiques peut limiter le combinatoire inhérent aux méthodes de réso-
lution exactes lorsqu"il existe des familles de gammes opératoires à durées hétérogènes.
MOTS-CLÉS:flow-shop de permutation, règles d"élimination, lags, série-parallèle1. INTRODUCTION
1.1. Flow-Shop de Permutation
Dans un problème de flow-shop de permutation, un en- sembleJdengammes (oujobs) doit être séquencé sur une ligne de production constituée demmachines. Sans perte de généralité, nous supposerons que les machines sont indicées dans l"ordre de leur apparition sur la ligne. Les gammes se succédant chronologiquement sur cette ligne, l"ordre de passage des jobs est identique sur toutes les machines. On suppose que les opérations ne peuvent être interrompues et que les machines exécutent au plus une opération à la fois. L"objectif sur lequel nous nous concentrons ici est la minimisation de la durée totale de l"ordonnancement. L"exécution du jobJisur la machineMkest appelée opérationOi;ket sa durée sera notéepi;k. Nous dési- gnerons également parri;k=ålJ;k=mini2Jri;ketqJ;k=mini2Jqi;k.
Nous reproduisons en figure 1 la solution optimale d"un flow-shop de permutation à 3 jobs et 4 machines dont les données sont indiquées dans le tableau 1. p i;kM1M2M3M4J11 1 3 2 J21 4 3 3
J34 1 1 3
Tableau 1. Exemple de flow-shop de permutationLeproblèmedeflow-shopà2machinespeutêtrerésoluen
O(nlogn)par une procédure due à S. M. Johnson (John- son, 1954) alors que M. R. Garey, D. S. Johnson et R. Sethi (Gareyet al., 1976) ont montré que le problème de flow-shop devientNP-difficile au-delà de 3 machines.M1M 2M 3M4J1J1J1J1J2J2J2J2J3J3J3J3C?PFS=15
Figure 1. Solution optimale de l"exemple
Cet article, consacré à l"étude de nouvelles règles d"élimi- nation spécifiques à ce problème, montre que ces règles peuvent avoir un impact non négligeable en terme de ré- duction d"arborescence de recherche dans le cas de fa- milles de jobs à durées fortement hétérogènes. Le para- graphe suivant répertorie un ensemble de propriétés de cas particuliers de flow-shop qui nous permettront de définir ces règles spécifiques.1.2. Flow-Shop à 2 machines avec lags et précédences
La première variante à laquelle nous nous intéressons est le problème de flow-shop à 2 machines dans lequel on a substitué la notion delagà celle de précédence. Un lag l jreprésente la durée minimale (éventuellement négative) séparant le début de l"exécution du jobJjsur la seconde machine de la fin de son exécution sur la première ma- chine. Nous noteronsla relation transitive définie surJpar: J Laurent PÉRIDY, Éric PINSON, David RIVREAU, ART_140, 1/7 MOSIM"01 - du 25 au 27 avril 2001 - Troyes (France) J. R. Jackson (Jackson, 1956) et L. G. Mitten (Mitten,1959) ont démontré que la solution optimale du problème
de flow-shop de permutation avec lags peut s"obtenir en O(nlogn)par construction d"un ordonnancement compa- tible avec la relation. Une propriété fort intéressante du problème avec lags identifiée par T. Kurisu (Kurisu, 1976) est la possibilité de substituer un job dit composite à toute séquence inin- terrompue de jobs, et ce, sans modifier la durée de l"or- donnancement résultant. Ainsi, le triplet caractéristique du job compositehJi;Jji constitué par les jobsJietJjvaut: -phi;ji;1=pi;1+pj;1 -lhi;ji=max(li+pi;2;pj;1+lj)pi;2pj;1 -phi;ji;2=pi;2+pj;2 La relation binairepeut donc s"étendre à des séquences ininterrompues de jobs via la définition de jobs compo- sites.J1J1J2J2J3J30 2 3 5 8 10 11 12-132hJ1;J2;J3ihJ1;J2;J3i0 5 8 12-3
Figure 2. Flow-shop avec lags et job composite associé Le résultat précédent est à la base de l"algorithme de C. L. Monma (Monma, 1979) et J. B. Sidney (Sidney,1979) qui permet de résoudre enO(nlogn)le problème à
2 machines et lags en présence d"un réseau de précédences
de type série-parallèle. Par précédence, il est ici entendu que la séquence job doit respecter d"éventuelles relations de précédences entre jobs (on ne peut ordonnancer un job que lorsque tous ses prédécesseurs ont déja été séquen- cés sur la ligne). Rappelons qu"un graphe est dit série- parallèle s"il peut se décomposer récursivement à l"aide de relations de type série ou de type parallèle. Pour plus d"informations sur cette classe particulière de graphe, on pourra se reporter à Valdeset al.(1982). p ppp p pp p-> ZZZ~-->-ZZZ~
>-ZZZ~1 4327 65
8S 1 S P 8 S S P P 47
2
3 5 6#
#cc #cc QQ #ccAA AAAAFigure 3. Graphe série-parallèle et décompositionNous reproduisons ci-dessous un résultat intermédiaire de
la preuve de l"algorithme de Monma et Sidney qui sera utilisé pour définir nos règles d"élimination spécifiques.Lemme 1.1 (Sidney, 1979)
Supposons que J
iest le prédécesseur immédiat de Jjdans une chaîne d"un réseau de précédence, et que J jJi. Dans ce cas, il existe un ordonnancement optimal dans lequel J jest ordonnancé immédiatement après Ji. Outre cette proposition, nous ferons également intervenir ultérieurement la propriété suivante:Lemme 1.2
Si J iJjalors Ji hJj;Jii Jj.Démonstration.
Nous nous contentons ici de montrer queJiJjimplique J i hJj;Jii(la relationhJj;Jii Jjs"en déduisant par sy- métrie).Rappelons queJiJjest équivalent à:
et que le job compositehJj;Jiiest caractérisé par: p hj;ii;1=pj;1+pi;1 l hj;ii=max(lj+pj;2;pi;1+li)pj;2pi;1 p hj;ii;2=pj;2+pi;2 Nous allons distinguer deux cas suivant la valeur de la quantité min(pi;1+li;lj+pj;2).Cas (1):pi;1+lilj+pj;2
D"après (1), on déduit immédiatement:
l j+pj;2min(pi;1+li;li+pi;2;pj;1+lj)(2) En outre, par définition du job composite, on a: l hj;ii=lipj;2On obtient ainsi:
p hj;ii;1+lhj;ii=pj;1+pi;1+lipj;2(3) p hj;ii;2+lhj;ii=pi;2+li(4)Or, d"après (2),lj+pj;2pj;1+lj, soitpj;2pj;1.
On en déduit:
p hj;ii;1+lhj;iipi;1+li(5)De (4) et (5), on tire:
min(pi;1+li;li+pi;2) =min(pi;1+li;lhj;ii+phj;ii;2) et Laurent PÉRIDY, Éric PINSON, David RIVREAU, ART_140, 2/7 MOSIM"01 - du 25 au 27 avril 2001 - Troyes (France)On a donc:
soit J i hJj;JiiCas (2):pi;1+lilj+pj;2
De la même façon que précédemment, on obtient: p i;1+limin(li+pi;2;pj;1+lj;lj+pj;2)(6) p hj;ii;1+lhj;ii=pj;1+lj(7) p hj;ii;2+lhj;ii=pj;2+pi;2+lipi;1(8)De (7), on tire:
min(phj;ii;1+lhj;ii;li+pi;2) =min(pj;1+lj;li+pi;2)De même, (6) nous donne:
p i;1+limin(pj;1+lj;li+pi;2) Or, clairement: min(pi;1+li;lhj;ii+phj;ii;2)pi;1+li. En combinant les trois dernières relations, on obtient: soit J i hJj;Jii1.3. Bornes Inférieures
La borne inférieure la plus connue pour le flow-shop de permutation est celle de B. J. Lageweg, J. K. Lenstra etA. H. G. Rinnooy Kan (Lageweget al., 1978).
Le point clé réside dans l"utilisation des valeurs des so- lutions optimales de sous-problèmes à 2 machines avec lags. Considérant deux machines donnéesMketMl(avec kPLLR(J) =max1k (i;j)2J2;i6=j(ri;k+qj;l)gquotesdbs_dbs21.pdfusesText_27
[PDF] flow shop hybride
[PDF] flowchart processus achat
[PDF] flsh kenitra doctorat 2017
[PDF] fluctuation d'échantillonnage definition
[PDF] fluctuation economique definition ses
[PDF] fluctuation économique terminale es
[PDF] fluctuations économiques def
[PDF] fluidité du marché définition
[PDF] flux d'hydrocarbures
[PDF] flux de fonds
[PDF] flux de matière et d'énergie dans un écosystème pdf
[PDF] flux de production définition
[PDF] flux de revenus
[PDF] flux de trésorerie d'exploitation calcul
