[PDF] [PDF] RÈGLES DÉLIMINATION POUR FLOW-SHOP DE PERMUTATION

[PDF] Les problèmes dordonnancement de type « flow-shop - Numdam

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 

[PDF] Flow-shop à deux machines avec des temps de - Archipel UQAM

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 pas 

ordonnancement dans les systèmes de production de type Flow

dans un Flow-Shop de permutation avec des stocks de capacité illimitée, par des problèmes d'ordonnancement, leur définition n'est ni toujours immédiate, 

[PDF] Ce document est le fruit dun long travail approuvé par le jury de

Nous avons rappelé la définition des systèmes de production de type Flow- Shop et Flow-Shop hybride en premier lieu Puis, nous avons présenté différentes 

[PDF] Ordonnancement datelier

Nous rappelons la définition et la classification des problèmes d'atelier ainsi que les α1 = O pour l'open-shop, F pour le flow-shop et J pour le job-shop

[PDF] ORDONNANCEMENT EN ATELIERS SPÉCIALISÉS - LAMSADE

Système Productif en AS, job shop, atelier à cheminements multiples) • pb NP dur Cas particulier des ateliers à cheminement unique (flow shop) où possibilité tij = 0 Définition d'un Système Interactif d'Aide à la Décision de Lancement

[PDF] RÈGLES DÉLIMINATION POUR FLOW-SHOP DE PERMUTATION

27 avr 2001 · La relation binaire ≼ peut donc s'étendre à des séquences ininterrompues de jobs via la définition de jobs compo- sites J1 J1 J2 J2 J3 J3 0

[PDF] flow shop et job shop

[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

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ÈNES

Laurent 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èle

1. 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=åltôt où le jobJipeut commencer son opération surMket parqi;k=ål>kpi;lla durée de latence (temps mini-

mal s"écoulant entre la fin d"exécution deJisurMket la fin de l"ordonnancement). Ces quantités seront égale- ment définies pour tout sous-ensembleJvia les formules r

J;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 J

21 4 3 3

J

34 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 3M

4J1J1J1J1J2J2J2J2J3J3J3J3C?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-1

32hJ1;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-> Z

ZZ~-->-ZZZ~

>-ZZZ~1 432
7 65
8S 1 S P 8 S S P P 47
2

3 5 6#

#cc #cc QQ #ccAA AAAA

Figure 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;2

On 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;Jii

Cas (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;Jii

1.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 et

A. 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 kNous noteronsP?Ja(J;Mk;Ml)la solution optimale de Jackson-Mitten du sous-problème obtenu en considérant l"ensemble de jobsJet les machinesMketMl. B. J. Lageweget al.obtiennent ainsi la borne inférieure (de complexitéO(m2nlogn)): LB

PLLR(J) =max1k (i;j)2J2;i6=j(ri;k+qj;l)gquotesdbs_dbs21.pdfusesText_27