Ordonnancement des job-shops flexibles sous contraintes de disponibilité des machines LAGIS - Ecole Centrale de Lille Nozha ZRIBI

Ordonnancement des job-shops Ordonnancement des job-shops flexibles sous contraintes de flexibles sous contraintes de disponibilité des machinesdisponibilité des machines

LAGIS - Ecole Centrale de LilleLAGIS - Ecole Centrale de Lille

Nozha ZRIBI

27 Janvier 2006 Réunion Gotha 2

Deux formulationsDeux formulations

Cadre de l’étude Cadre de l’étude Job-shop flexible Job-shop flexible

(1)(1)

OO1,11,1 O O1,21,2 O O1,31,3 OO2,12,1 O O2,22,2 OO3,13,1 O O3,23,2

M1 M2 M3 M4M1 M2 M3 M4

Job1 Job2 Job3Job1 Job2 Job3

MPM JSP MPM JSP

FJSPFJSP

ppijkijk

Indisponibilité durant certaines périodes Indisponibilité durant certaines périodes connues a prioriconnues a priori


PlanPlan

Durées indépendantes de la Durées indépendantes de la flexibilitéflexibilité Approche par phases Approche par phases

Approche intégrée basée sur la Approche intégrée basée sur la résolution exacte du problème à 2-résolution exacte du problème à 2-jobsjobs

Périodes d’indisponibilité flexiblesPériodes d’indisponibilité flexibles


Approche par phases Approche par phases principeprincipe

Problème d’affectation

Problème de séquencement

Heuristique d’affectation

Borne inférieure du Critère global étudié

Approche évolutionniste

-Détermination de la solution initiale avec des règles de priorité

- Définition d’un critère intermédiaire

-Amélioration de l’affectation par une Recherche Tabou

-Mesure de la qualité de la solution d’affectation

-Choix de la solution


Problème d’affectation Problème d’affectation Solution Solution

initialeinitiale

Relaxation des contraintes de précédence Relaxation des contraintes de précédence Définition d’une date de début au plutôt pour Définition d’une date de début au plutôt pour

chaque opérationchaque opération

Le problème est équivalent à un problème à Le problème est équivalent à un problème à machines parallèlesmachines parallèles Flexibilité partielleFlexibilité partielle Dates de début au plus tôtDates de début au plus tôt Contraintes de disponibilitéContraintes de disponibilité



initialeinitiale

Schéma de l’heuristique d’affectationSchéma de l’heuristique d’affectation A chaque itération du programmeA chaque itération du programme

Détermination de l’ensemble d’opérations affectables Détermination de l’ensemble d’opérations affectables sur Msur Mk k

Détermination de la charge de MDétermination de la charge de Mkk

Pour chaque opération affectable de MPour chaque opération affectable de Mkk

Tester si l’opération peut être placée avant la prochaine Tester si l’opération peut être placée avant la prochaine période d’indisponibilitépériode d’indisponibilité

Choisir un couple (opération, machine) selon une Choisir un couple (opération, machine) selon une règle de prioritérègle de priorité



initialeinitiale

Règle de prioritéRègle de priorité Sélectionner la machine la moins chargée Sélectionner la machine la moins chargée MMkk

Trier Les opérations affectables selon leur degré de Trier Les opérations affectables selon leur degré de flexibilitéflexibilité

Affecter à Affecter à MMkk la première opération pouvant être placée la première opération pouvant être placée avant la prochaine période d’indisponibilitéavant la prochaine période d’indisponibilité

Tenir compte deTenir compte de charge des machinescharge des machines

degré de flexibilité des opérationsdegré de flexibilité des opérations

Occuper les intervalles d’accueil avant Occuper les intervalles d’accueil avant chaque période d’indisponibilité chaque période d’indisponibilité


Problème d’affectationProblème d’affectationCritère Critère

intermédiaireintermédiaire

Pour une affectation Pour une affectation SS Critère intermédiaire : Critère intermédiaire : basé sur le calcul d’une basé sur le calcul d’une

borne inférieure du makespan (Cr=BI(S))borne inférieure du makespan (Cr=BI(S)) A chaque machine A chaque machine MMk k

Problème Problème ππk k à une machineà une machine Dates de début au plus tôtDates de début au plus tôt Durées de latenceDurées de latence Périodes d’indisponibilitéPériodes d’indisponibilité

Autorisation de la préemption et Autorisation de la préemption et utilisation de la règle de Jackson utilisation de la règle de Jackson afin de calculer une borne afin de calculer une borne inférieure pour chaque inférieure pour chaque problème problème ππkk

Valeur maximale de ces Valeur maximale de ces ordonnancements ordonnancements préemptifspréemptifs


Problème d’affectationProblème d’affectationCritère Critère

intermédiaireintermédiaire

Introduction d’ une opération virtuelle à Introduction d’ une opération virtuelle à chaque période d’ indisponibilitéchaque période d’ indisponibilité Date de début au plutôt : date de début de la Date de début au plutôt : date de début de la

période d’indisponibilitépériode d’indisponibilité Durée de latence : constante Durée de latence : constante GG

Utilisation de la règle de JacksonUtilisation de la règle de Jackson Autorisation de la préemptionAutorisation de la préemption Ordonnancement à chaque itération d’une unité Ordonnancement à chaque itération d’une unité

de la tâche disponible de plus grande durée de de la tâche disponible de plus grande durée de latencelatence

1. Les périodes d’ indisponibilité sont 1. Les périodes d’ indisponibilité sont traitées comme des opérations de traitées comme des opérations de production : JPS donne la solution optimaleproduction : JPS donne la solution optimale2. Les périodes d’indisponibilité débutent 2. Les périodes d’indisponibilité débutent bien à leur date de début au plus tôt et bien à leur date de début au plus tôt et elles ne sont jamais interrompues : elles elles ne sont jamais interrompues : elles ont la plus grande durée de latenceont la plus grande durée de latence

Critère intermédiaire Critère intermédiaire Valeur maximale des durées de ces Valeur maximale des durées de ces ordonnancements préemptifsordonnancements préemptifs

Objectif de RTObjectif de RTTrouver l’affectation S minimisant ce critèreTrouver l’affectation S minimisant ce critère


Séquencement Séquencement Approche de Approche de

résolutionrésolution

Adaptation de l’AG utilisé pour le problAdaptation de l’AG utilisé pour le problème classiqueème classique

Fonction de décodageFonction de décodage Définition d’un opérateur de mutation Définition d’un opérateur de mutation

dirigée adapté au problèmedirigée adapté au problème Solutions initialesSolutions initiales

Nécessité d’un test de Nécessité d’un test de disponibilité avant le calcul des disponibilité avant le calcul des dates de début et de fin de dates de début et de fin de chaque opérationchaque opération


Opérateur de mutation Opérateur de mutation dirigéedirigée

ObjectifObjectif Améliorer le makespan en réduisant le temps mort Améliorer le makespan en réduisant le temps mort

avant les périodes d’indisponibilitéavant les périodes d’indisponibilité PrincipePrincipe

Déterminer la machine critiqueDéterminer la machine critique Tester les permutations possibles d’opérations Tester les permutations possibles d’opérations

ordonnancées avant et après les périodes ordonnancées avant et après les périodes d’indisponibilité d’indisponibilité

Sélectionner la permutation minimisant le makespanSélectionner la permutation minimisant le makespan


Exemple illustratifExemple illustratif Approche par phases Approche par phases

(1)(1) JMPM s.c disponibilitéJMPM s.c disponibilité (15 (15 xx 5 5 xx 5) 5)

2 périodes d’indisponibilité par machine2 périodes d’indisponibilité par machine Étape d’affectationÉtape d’affectation

Solution initiale d’affectationSolution initiale d’affectation Somme des durées des Somme des durées des opérations pouvant être opérations pouvant être ordonnancées avant les ordonnancées avant les périodes d’indisponibilitépériodes d’indisponibilitéMM11 MM22 MM33 MM44 MM55

19197 7

202077

7575 373788

222255

165165 121299

320320 124 124

572572

202011

262622

101044

383811

232333

168168 131377

321321 129129 596596 Longueur des intervalles Longueur des intervalles d’accueil d’accueil



(1)(1) Comparaison entre la solution initiale et la Comparaison entre la solution initiale et la

solution donnée par l’algorithme de recherche solution donnée par l’algorithme de recherche TabouTabou

Solution Solution initialeinitiale

Solution Solution après RTaprès RT

MM11 MM22 MM33 MM44 MM55

ChargeCharge 714714 782782 868 868 789789 839839OrdonnancemeOrdonnancement préemptifnt préemptif

812812 907907 995995 887887 997997

MM11 MM22 MM33 MM44 MM55

ChargeCharge 815815 812812 790790 818818 757757

OrdonnancemeOrdonnancement préemptifnt préemptif

913913 915915 917917 916916 915915



(2)(2) Étape de séquencementÉtape de séquencement

Opérateur de mutation dirigéeOpérateur de mutation dirigée Chromosome initialChromosome initial

Makespan: 1236, Machine critique: MMakespan: 1236, Machine critique: M33

Chromosome résultatChromosome résultat Makespan: 1190, temps mort (71-> 28)Makespan: 1190, temps mort (71-> 28)

O15,1 O11,2

0 225 233 331 428 499 528 1236

O15,1O11,2

0 225 233 331 471 499 528 1190



(2)(2) Influence de l’opérateur de mutation Influence de l’opérateur de mutation

dirigéedirigée ConvergenceConvergence

Convergence avec mutation Convergence avec mutation aléatoirealéatoire

800850

900950

10001050

11001150

12001250

1300

1 50 99 148 197 246 295 344 393 442

Générations

Makespan

972972

800850

900950

10001050

11001150

12001250

1300

1 50 99 148 197 246 295 344 393

Générations

Makespan

968968

111144

181833

Convergence avec mutation dirigéeConvergence avec mutation dirigée



(3)(3) MakespanMakespan

SolutionSolution

initialeinitialeSolution après Solution après RTRT

BIBI 10171017 966966

SolSol 10231023 968968

ParamètresParamètres

Taille de la populationTaille de la population

Taux de croisementTaux de croisement

Taux de mutationTaux de mutation

Méthode de sélectionMéthode de sélection

Nombre de Nombre de générationsgénérations

Nombre d’exécutionNombre d’exécution

200200

0.850.85

0.150.15

RoulettRoulettee

300300

1010


MPM job-shop MPM job-shop Approche intégréeApproche intégrée

Basée sur la résolution exacte du Basée sur la résolution exacte du problème à deux jobsproblème à deux jobs

Extension de l’approche Extension de l’approche géométriquegéométrique


Approche géométrique Approche géométrique Rappel Rappel

(1)(1)

ObjectifObjectif Réduire la résolution du problème à deux Réduire la résolution du problème à deux

jobs en un problème de recherche de plus jobs en un problème de recherche de plus court chemincourt chemin

PrincipePrincipe Représentation du problème dans le plan à Représentation du problème dans le plan à

deux dimensions avec obstaclesdeux dimensions avec obstacles Construction d’un réseau décrivant la Construction d’un réseau décrivant la

progression dans le planprogression dans le plan


Approche géométrique Approche géométrique Rappel Rappel

(2)(2)

ExempleExemple

JJ11={(M={(M11,2),(M,2),(M22,1),(M,1),(M33,1)},1)}

JJ22= {(M= {(M33,2),(M,2),(M11,1),(M,1),(M22,1)},1)}

Obstacle Obstacle correspondant à un correspondant à un partage de ressourcepartage de ressource

Job1Job1

proportionnel au proportionnel au temps opératoire temps opératoire de l’opérationde l’opération

Job2Job2

Chaque sommet a au plus Chaque sommet a au plus deux successeursdeux successeurs

Coins SE et NWCoins SE et NW

Point final FPoint final F


Extensions de L’AG Extensions de L’AG Rappel Rappel (2)(2)

Autorisation de la préemptionAutorisation de la préemption Flexibilité des ressourcesFlexibilité des ressources Contraintes de blocageContraintes de blocage Contraintes de disponibilité sur les Contraintes de disponibilité sur les

machines: cas de Job-shop (AGT) machines: cas de Job-shop (AGT) (Aggoune 02)(Aggoune 02)

Problèmes avec flexibilité des ressources Problèmes avec flexibilité des ressources et contraintes de disponibilitéet contraintes de disponibilité


Extension Extension prise en compte de la prise en compte de la

flexibilitéflexibilité

Définition des obstacles potentielsDéfinition des obstacles potentiels Définition des successeurs d’un sommetDéfinition des successeurs d’un sommet

Détermination des combinaisons de Détermination des combinaisons de machines permettant la progression machines permettant la progression diagonale diagonale

Progression diagonale jusqu’à la rencontre Progression diagonale jusqu’à la rencontre d’une horizontale où une verticaled’une horizontale où une verticale

Mis à jour des données: - tempsMis à jour des données: - temps

- Coordonnées géometriques- Coordonnées géometriques

Test de Test de DisponibilitéDisponibilité

InitialisationInitialisation

Cas Partage des ressources Cas Partage des ressources : :

Successeurs: SE et NWSuccesseurs: SE et NW

Pour chaque couple de machinesPour chaque couple de machines

Cas indisponibilitéCas indisponibilité


Progression horizontaleProgression horizontale

ou verticaleou verticale

Mis à jour des données:Mis à jour des données:

- temps- temps

- Coordonnées - Coordonnées géométriquesgéométriques

Test de Test de DisponibilitéDisponibilité

InitialisationInitialisation

Problème de Problème de disponibilité dans les disponibilité dans les deux directionsdeux directions

Successeur: Sommet Successeur: Sommet d’attented’attente

Problème de disponibilité Problème de disponibilité dans l’une des deux dans l’une des deux directionsdirections

Fin Fin indisponibilitéindisponibilité

Successeur: Sommet Successeur: Sommet singulier ou réguliersingulier ou régulier

Fin d’une Fin d’une opérationopération

Extension Extension prise en compte de la prise en compte de la

flexibilitéflexibilité

Pour chaque couple de machinesPour chaque couple de machines

Complexité Complexité polynomialepolynomiale


Heuristique pour le problème Heuristique pour le problème généralgénéral

Ordonnancement de Ordonnancement de deux jobs avec deux jobs avec

l’algorithme polynomiall’algorithme polynomial

Des périodes Des périodes d’indisponibilité d’indisponibilité

additionnelles sont fixéesadditionnelles sont fixées

Séquence initiale des Séquence initiale des jobs jobs (J(J11, J, J22..., J..., JNN) )

Fin de Fin de la la séquenséquencece ArrêtArrêt

Principe Principe Résolution des jobs deux à deux avec Résolution des jobs deux à deux avec

l’algorithme polynomiall’algorithme polynomial


ComparaisonComparaison

0

200

400

600

800

1000

1200

1400

1 2 3 4 5 6 7 8 9 10

Instances

Makespan Borne inférieure

Approche par phases

Approche intégrée

Calculée en Calculée en considérant considérant tous les tous les paires de paires de jobsjobs

-L’approche par phases donne de bons résultats L’approche par phases donne de bons résultats -L’'approche intégrée est beaucoup plus L’'approche intégrée est beaucoup plus complexe (temps de calcul, pas de solution complexe (temps de calcul, pas de solution pour les trois dernières instances)pour les trois dernières instances)-La solution donnée par l’approche intégrée La solution donnée par l’approche intégrée varie avec la séquence d’entréevarie avec la séquence d’entrée

un algorithme d’optimisation est un algorithme d’optimisation est nécessairenécessaire

Une approche évolutionniste intégrée


Périodes d’indisponibilité ne sont pas Périodes d’indisponibilité ne sont pas fixes fixes Une fenêtre de temps est allouée à Une fenêtre de temps est allouée à

l’exécution de chaque tâchel’exécution de chaque tâche

Périodes d’indisponibilité Périodes d’indisponibilité flexiblesflexibles

Hypothèse se rapprochant de la Hypothèse se rapprochant de la réalité industrielleréalité industrielle


Principe de résolution Principe de résolution

Optimiser les opérations de productionOptimiser les opérations de production Utilisation de l’approche évolutionniste développée Utilisation de l’approche évolutionniste développée

pour le FJSPpour le FJSP II** : Meilleur chromosome obtenu : Meilleur chromosome obtenu

Insérer les tâches de maintenance tout en Insérer les tâches de maintenance tout en respectant leurs fenêtres temporellesrespectant leurs fenêtres temporelles

Date de début au plus tôt : Date de début au plus tôt : Date de début au plus tard :Date de début au plus tard : Intervalle de tolérance : Intervalle de tolérance :

1kA

klkl WD ],[ '

klklkl WDA


Heuristique HSHeuristique HS11insertioninsertion au plus au plus

tardtard

Heuristique HSHeuristique HS11

Ordonnancement des opérations de Ordonnancement des opérations de production dans l’ordre de leur apparition production dans l’ordre de leur apparition dans Idans I**

Insertion des périodes d’indisponibilité le Insertion des périodes d’indisponibilité le plus tard possible dans leurs fenêtres plus tard possible dans leurs fenêtres temporellestemporelles

Réduction du temps mortRéduction du temps mort



I*=I*= 11 22 33 11 22 11 22 3 33 33 2 2 1 3 2 1 3 13 2 2 1 3 2 1 3 1

- Test de disponibilitéTest de disponibilité- Décalage de la tâche de Décalage de la tâche de maintenancemaintenance-Mise à jour de la date de Mise à jour de la date de disponibilité de la machinedisponibilité de la machine-Calcul de la date de début et de fin Calcul de la date de début et de fin de l’opérationde l’opération


Heuristique HSHeuristique HS2 2 Recherche Recherche

arborescentearborescente

Ordonnancement des opérations de production Ordonnancement des opérations de production dans l’ordre de leur apparition dans Idans l’ordre de leur apparition dans I**

Insertion des périodes d’indisponibilité machine Insertion des périodes d’indisponibilité machine par machinepar machine

Pour chaque machine : tous les emplacements Pour chaque machine : tous les emplacements possibles de chaque période sont testéspossibles de chaque période sont testés

Tenir compte de l’intervalle de tolérance Tenir compte de l’intervalle de tolérance attribué à chaque période attribué à chaque période d’indisponibilitéd’indisponibilité



e1 e23

Périodes d’indisponibilitéPériodes d’indisponibilité

Intervalles de toléranceIntervalles de tolérance

e3 e4

Deux emplacements sont possibles Deux emplacements sont possibles A la fin de chaque tâche qui se trouve à A la fin de chaque tâche qui se trouve à

l’intérieur de l’intervallel’intérieur de l’intervalle A la date de début de l’intervalleA la date de début de l’intervalle

Insertion de la 1Insertion de la 1ère ère

tâche de tâche de maintenancemaintenanceInsertion de la 2Insertion de la 2ème ème

tâche de tâche de maintenancemaintenance

e1e2

e3e4e3e4

e0

Ordonnancement initialOrdonnancement initial

MMkk


Heuristique HS2Heuristique HS2

Détermination des Détermination des différentes solutions différentes solutions d’insertion possiblesd’insertion possibles

Mise à jour des données Mise à jour des données de productionde production

Séquence initiale de Séquence initiale de Machines Machines (M(M11, M, M22..., M..., MMM) )

Test de Test de validitévalidité

Solution partielle Solution partielle écartéeécartée

Certaines tâches Certaines tâches déjà placées déjà placées risquent d’être risquent d’être décalées au delà de décalées au delà de leurs intervalles de leurs intervalles de tolérancetolérance

tenir compte tenir compte des périodes des périodes d’indisponibilité d’indisponibilité déjà placéesdéjà placées


Heuristique HSHeuristique HS3 3 Règle de prioritéRègle de priorité

Définir une fenêtre de temps pour chaque Définir une fenêtre de temps pour chaque opération de productionopération de production Date de début au plus tôt d’une opération : date de Date de début au plus tôt d’une opération : date de

fin de la tâche qui la précède dans le job fin de la tâche qui la précède dans le job Date de fin au plus tard : date de début de la tâche Date de fin au plus tard : date de début de la tâche

qui la suit dans le job qui la suit dans le job

I*=I*= 1 2 3 1 2 1 2 3 33 2 2 1 1 2 3 1 3



Réordonnancer les tâches de production et Réordonnancer les tâches de production et de maintenance selon la règlede maintenance selon la règle Ordonnancement de l’opération ayant la plus Ordonnancement de l’opération ayant la plus

petite date de fin au plus tard parmi les petite date de fin au plus tard parmi les opérations disponibles (production ou opérations disponibles (production ou maintenance)maintenance)

Un test est nécessaire avant de placer une Un test est nécessaire avant de placer une opération de productionopération de production

Vérifier si le placement peut entraîner le dépassement Vérifier si le placement peut entraîner le dépassement de son deadline de la prochaine tâche de maintenance à de son deadline de la prochaine tâche de maintenance à programmerprogrammer



I*=I*= 11 22 33 11 22 11 22 3 33 33 2 2 1 1 2 3 1 33 2 2 1 1 2 3 1 3


Un bon Un bon ordonnancement de ordonnancement de production, ne le reste production, ne le reste pas systématiquementpas systématiquementaprès insertion de la après insertion de la maintenancemaintenance

Heuristique HS3Heuristique HS3


Comparaison des Comparaison des heuristiquesheuristiques

INSTINST1 1 (10 x 6 x 55)(10 x 6 x 55)

1 période 1 période d’indisponibilitéd’indisponibilité

INSTINST2 2 (10 x 6 x 55)(10 x 6 x 55)

2 période 2 période d’indisponibilitéd’indisponibilité

HSHS11 5555 350350

HSHS22 4848 334334

HSHS33 5252 337337

Merci pour votre attentionMerci pour votre attention

Documents

Ordonnancement des job-shops flexibles sous contraintes de disponibilité des machines LAGIS - Ecole Centrale de Lille Nozha ZRIBI