Journée Automatique et Optimisation – Université de Paris 12 – 20 Mars 2003 1 Problèmes dordonnancement dans les systèmes de production Michel Gourgand

11 Journée “Automatique et Optimisation” – Université de Paris 12 – 20 Mars 2003

Problèmes d’ordonnancementProblèmes d’ordonnancementdans les systèmes de productiondans les systèmes de production

Michel GourgandMichel GourgandUniversité Blaise Pascal – Clermont FerrandUniversité Blaise Pascal – Clermont FerrandLIMOS CNRS UMR 6158LIMOS CNRS UMR 6158


Le LIMOSLe LIMOSLaboratoire d’Informatique, de Laboratoire d’Informatique, de Modélisation et d’Optimisation des Modélisation et d’Optimisation des SystèmesSystèmes

L’activité du LIMOS est globalement centrée L’activité du LIMOS est globalement centrée sur la conception d’outils et de modèles sur la conception d’outils et de modèles informatiques pour l’optimisation, le contrôle et informatiques pour l’optimisation, le contrôle et l’évaluation des systèmes organisationnels. l’évaluation des systèmes organisationnels.

Elle se décline selon trois orientations Elle se décline selon trois orientations principales :principales :- Algorithmique et Aide à la Décision - Algorithmique et Aide à la Décision - Systèmes d’Information et de Communication- Systèmes d’Information et de Communication- Modélisation, Organisation et Pilotage des - Modélisation, Organisation et Pilotage des Systèmes de ProductionSystèmes de Production


Plan de l’exposéPlan de l’exposé

IntroductionIntroduction DéfinitionsDéfinitions Les problèmes théoriquesLes problèmes théoriques Les méthodesLes méthodes Exemples industrielsExemples industriels Conclusion et PerspectivesConclusion et Perspectives Le groupe BermudesLe groupe Bermudes Quelques référencesQuelques références


Définition du dictionnaire :Définition du dictionnaire :

Ordonnancement : organisation méthodique (de Ordonnancement : organisation méthodique (de la fabrication, d’un processus, …)la fabrication, d’un processus, …)

Contexte : Contexte :

Fonction de décision dans les systèmes de Fonction de décision dans les systèmes de production de biens et de servicesproduction de biens et de services

IntroductionIntroduction


DéfinitionsDéfinitions

OrdonnancementOrdonnancement TâchesTâches Problème d’optimisationProblème d’optimisation Problème d’évaluationProblème d’évaluation Organisation hiérarchique fonctionnelleOrganisation hiérarchique fonctionnelle Le thème de l’ordonnancementLe thème de l’ordonnancement


Définitions de Définitions de l’ordonnancementl’ordonnancement

Définition 1Définition 1 Ordonnancer (ou planifier) le fonctionnement d'un Ordonnancer (ou planifier) le fonctionnement d'un système industriel de production consiste à gérer système industriel de production consiste à gérer l'allocation (ou l'accès) à des ressources au cours du l'allocation (ou l'accès) à des ressources au cours du temps, tout en satisfaisant au mieux un ensemble de temps, tout en satisfaisant au mieux un ensemble de critères.critères.

Définition 2Définition 2 Une tâche est un travail élémentaire nécessitant un Une tâche est un travail élémentaire nécessitant un certain nombre d'unités de temps et de ressources. certain nombre d'unités de temps et de ressources. Ordonnancer un ensemble de tâches, c'est programmer Ordonnancer un ensemble de tâches, c'est programmer leur exécution en leur allouant les ressources requises et leur exécution en leur allouant les ressources requises et en fixant leur date de début.en fixant leur date de début.



Définition 3Définition 3L'ordonnancement concerne l'affectation de ressources L'ordonnancement concerne l'affectation de ressources limitées aux tâches dans le temps. C'est un processus de limitées aux tâches dans le temps. C'est un processus de prise de décision dont le but est d'optimiser un ou prise de décision dont le but est d'optimiser un ou plusieurs objectifs.plusieurs objectifs.

Définition 4Définition 4Le problème d’ordonnancement consiste à organiser Le problème d’ordonnancement consiste à organiser dans le temps la réalisation de tâches, compte tenu de dans le temps la réalisation de tâches, compte tenu de contraintes temporelles (délais, contraintes contraintes temporelles (délais, contraintes d’enchaînement, …) et de contraintes portant sur d’enchaînement, …) et de contraintes portant sur l’utilisation et la disponibilité des ressources requises.l’utilisation et la disponibilité des ressources requises.



Définition 5Définition 5

Un problème d'ordonnancement consiste à : Un problème d'ordonnancement consiste à :

- déterminer les dates d'entrée des produits,déterminer les dates d'entrée des produits,

- trouver un ordre de traitement admissibletrouver un ordre de traitement admissible(le problème peut être surcontraint),(le problème peut être surcontraint),

- constituer des campagnes de production,constituer des campagnes de production, - déterminer une planification robuste aux - déterminer une planification robuste aux événements aléatoires.événements aléatoires.


Définition : Les tâchesDéfinition : Les tâches

Les tâches sont le dénominateur commun des Les tâches sont le dénominateur commun des problèmes d'ordonnancement, leur définition n'est problèmes d'ordonnancement, leur définition n'est ni toujours immédiate, ni toujours triviale.ni toujours immédiate, ni toujours triviale.

Une tâche est caractérisée par :Une tâche est caractérisée par :

- une durée, - une durée,

- une date de disponibilité,- une date de disponibilité,

- une date de fin au plus tard,- une date de fin au plus tard,

- une quantité de ressources, - une quantité de ressources,

- …- …


Le problème d’optimisationLe problème d’optimisation

Etant donnés un ensemble de tâches et un Etant donnés un ensemble de tâches et un ensemble de ressources, il faut programmer les ensemble de ressources, il faut programmer les tâches et affecter les ressources de façon à tâches et affecter les ressources de façon à optimiser un objectif ou plusieurs (un objectif optimiser un objectif ou plusieurs (un objectif correspondant à un critère de performance), en correspondant à un critère de performance), en respectant un ensemble de contraintesrespectant un ensemble de contraintes..

Problème d’optimisation Problème d’optimisation combinatoire (méthodes exactes et combinatoire (méthodes exactes et approchées)approchées)


Le problème d’évaluationLe problème d’évaluation

Critères de performance :Critères de performance : Temps total de traitement,Temps total de traitement, Retard,Retard, Temps d’attente,Temps d’attente, Taux d’occupation,Taux d’occupation, Nombre de changements d’outils,Nombre de changements d’outils, ……

Problème d’évaluation de critères Problème d’évaluation de critères de performance (modélisation, de performance (modélisation, spécification, simulation, …)spécification, simulation, …)


Le problème d’évaluationLe problème d’évaluation

Compréhension du fonctionnement interne Compréhension du fonctionnement interne et spécification des règles de gestionet spécification des règles de gestion

Pour assurer au système un fonctionnement « satisfaisant », il Pour assurer au système un fonctionnement « satisfaisant », il faut : faut :

spécifier de bonnes politiques de gestion (gestion des spécifier de bonnes politiques de gestion (gestion des ressources de transport, des stocks, de l'utilisation des ressources de transport, des stocks, de l'utilisation des machines,...), machines,...),

déterminer les goulets d'étranglement, déterminer les goulets d'étranglement, mieux gérer les ressources critiques, mieux gérer les ressources critiques, s'assurer que les ressources sont utilisées au mieux. s'assurer que les ressources sont utilisées au mieux.

Des règles de gestion classiques peuvent être utilisées mais Des règles de gestion classiques peuvent être utilisées mais d'autres d'autres

règles spécifiques au problème peuvent être proposées.règles spécifiques au problème peuvent être proposées.Panwalker et Iskander, ont référencé 113 règles différentesPanwalker et Iskander, ont référencé 113 règles différentes


Organisation hiérarchique Organisation hiérarchique fonctionnellefonctionnelle

StratégiqueStratégique

TactiqueTactique

OpérationnelOpérationnel

- SurchargeSurcharge- AléaAléa

Délais de Délais de livraison livraison trop trop longslongs

Conception : choix Conception : choix des ressources, des ressources, programme de programme de productionproduction

Planification : choix Planification : choix des quantités de des quantités de produits à fabriquerproduits à fabriquer

Ordonnancement et Ordonnancement et pilotagepilotage


le thème de l’ordonnancementle thème de l’ordonnancement

L'ensemble des tâches (travaux, opérations, ) à réaliser est connu a L'ensemble des tâches (travaux, opérations, ) à réaliser est connu a priori. Lepriori. Le

problème est alors dit problème est alors dit statiquestatique, par opposition à un problème , par opposition à un problème dynamique dynamique

pour lequel l'ensemble des tâches évolue avec le temps. pour lequel l'ensemble des tâches évolue avec le temps.

On considère généralement que les ressources sont renouvelables On considère généralement que les ressources sont renouvelables (machine, fichier, processeur, homme, …). Parmi les ressources (machine, fichier, processeur, homme, …). Parmi les ressources renouvelables, on distingue les ressources disjonctives, qui ne peuvent renouvelables, on distingue les ressources disjonctives, qui ne peuvent exécuter qu'une opération à la fois et les ressources cumulatives, qui exécuter qu'une opération à la fois et les ressources cumulatives, qui peuvent exécuter un nombre limité d'opérations simultanément.peuvent exécuter un nombre limité d'opérations simultanément.

Le thème de l’ordonnancement concerne la mise au point Le thème de l’ordonnancement concerne la mise au point d’algorithmes de résolution performants, exacts ou approchés,d’algorithmes de résolution performants, exacts ou approchés,pour résoudre des problèmes d’ordonnancement académiques pour résoudre des problèmes d’ordonnancement académiques ou industrielsou industriels


Les problèmes Les problèmes théoriquesthéoriques

Les problèmes d’atelierLes problèmes d’atelier Flow shopFlow shop Job shopJob shop Flow shop hybrideFlow shop hybride RCPSPRCPSP Hoist Scheduling ProblemHoist Scheduling Problem Job shop avec transportJob shop avec transport


Les problèmes d’atelierLes problèmes d’atelier

Pas de ressource (Problème central, PERT)Pas de ressource (Problème central, PERT)

RessourcesRessources

ConsommablesConsommables RenouvelablesRenouvelables

Disjonctives Disjonctives CumulativesCumulatives

Problèmes d’atelierProblèmes d’atelier

Ressource uniqueRessource unique Ressources multiplesRessources multiples

Une machineUne machine flow shop, job shop, open shop, …flow shop, job shop, open shop, …


Les problèmes d’atelierLes problèmes d’atelier

Les systèmes étudiés peuvent être de différentes Les systèmes étudiés peuvent être de différentes natures :natures :

systèmes industriels de production, systèmes industriels de production, systèmes informatiques,systèmes informatiques, systèmes administratifs,systèmes administratifs, systèmes hospitaliers,systèmes hospitaliers, systèmes de transport, …systèmes de transport, …

Dans ces systèmes, les problèmes d’ordonnancement Dans ces systèmes, les problèmes d’ordonnancement sont souvent résolus à travers des modèles sont souvent résolus à travers des modèles

théoriques théoriques tels que : flow-shop, flow-shop hybride, job-shop, …tels que : flow-shop, flow-shop hybride, job-shop, …


Flow Shop, Job ShopFlow Shop, Job Shop

Flow Shop : Atelier à cheminement uniqueFlow Shop : Atelier à cheminement unique

Exemple : Chaîne de montageExemple : Chaîne de montage

Job Shop : Atelier à cheminements multiplesJob Shop : Atelier à cheminements multiples


Flow Shop HybrideFlow Shop Hybride

EtageEtageStockStock

MachineMachineProblème d’ordonnancement et d’affectationProblème d’ordonnancement et d’affectation


Flow Shop Hybride Flow Shop Hybride déterministedéterministe

H1H1 La date de disponibilité des produits est connue, La date de disponibilité des produits est connue,H2H2 Les machines sont toujours disponibles, Les machines sont toujours disponibles,H3H3 Les temps de traitement sont déterministes et indépendants, Les temps de traitement sont déterministes et indépendants,H4H4 Les temps de montage et de démontage sont inclus dans les Les temps de montage et de démontage sont inclus dans les

temps de traitement,temps de traitement,H5H5 Les temps de transport sont négligeables, Les temps de transport sont négligeables,H6H6 Il n'y a pas de fragmentation de lots, Il n'y a pas de fragmentation de lots,H7H7 Une machine ne peut pas traiter plus d'un produit à un instant Une machine ne peut pas traiter plus d'un produit à un instant

donné,donné,H8H8 Un produit est traité par au plus une machine à un instant Un produit est traité par au plus une machine à un instant

donné,donné,H9H9 Les produits peuvent attendre dans des stocks de capacité Les produits peuvent attendre dans des stocks de capacité

illimitée entre les étages,illimitée entre les étages,H10H10 Un produit est traité par une seule machine de chaque étage, Un produit est traité par une seule machine de chaque étage,H11H11 Les machines d'un étage peuvent être identiques, Les machines d'un étage peuvent être identiques,

proportionnelles ou non identiques.proportionnelles ou non identiques.


Flow Shop Hybride Flow Shop Hybride stochastiquestochastique

Si on considère les événements aléatoires, les trois premières Si on considère les événements aléatoires, les trois premières hypothèses peuvent être remplacées par les hypothèses hypothèses peuvent être remplacées par les hypothèses suivantes :suivantes : H'1H'1 La date de disponibilité des produits est inconnue, La date de disponibilité des produits est inconnue,

H'2H'2 Les machines peuvent tomber en panne, Les machines peuvent tomber en panne,

H'3H'3 Les temps de traitement sont modélisés par des variables Les temps de traitement sont modélisés par des variables aléatoires.aléatoires.


RCPSPRCPSPResource Constrained Project(s) Scheduling Resource Constrained Project(s) Scheduling ProblemProblem

Problème d’ordonnancement de projet Problème d’ordonnancement de projet sous contraintes de ressources sous contraintes de ressources : :

Systèmes dans lesquels on doit trouver pour Systèmes dans lesquels on doit trouver pour chaque tâche à réaliser la (ou les) chaque tâche à réaliser la (ou les) ressource(s) à utiliser et dans quelle quantité, ressource(s) à utiliser et dans quelle quantité, ainsi qu’une séquence des tâches sur ces ainsi qu’une séquence des tâches sur ces ressources.ressources.


RCPSPRCPSPResource Constrained Project(s) Scheduling Resource Constrained Project(s) Scheduling ProblemProblem

ii 11 22 33 44 55

aaii 33 22 22 11 11

rrii 00 22 33 11 33

ttii 33 22 11 33 11

ddii 55 55 66 66 55

Exemple simpleExemple simple

1122

4433

44

55

tempstemps55

ressource Rressource R

1 2 3 4

3

2

1


Hoist Scheduling ProblemHoist Scheduling Problem

Le Hoist Scheduling Problem concerne les lignes Le Hoist Scheduling Problem concerne les lignes de production dotées d’une ressource de transport de production dotées d’une ressource de transport critique. Il faut ordonnancer simultanément les critique. Il faut ordonnancer simultanément les tâches de production (bornées par des valeurs tâches de production (bornées par des valeurs minimales et maximales) et celles de transport. Ce minimales et maximales) et celles de transport. Ce problème peut être traité en répétitif si tous les problème peut être traité en répétitif si tous les produits sur la ligne sont identiques.produits sur la ligne sont identiques.

Problème académiqueProblème académique

Problème industrielProblème industriel


Cuve de Cuve de chargementchargement

Cuve 1Cuve 1

Cuve 2Cuve 2

Cuve 3Cuve 3

Cuve de déchargementCuve de déchargement

Cuve mCuve m

robotrobot

porteurporteur

Hoist Scheduling ProblemHoist Scheduling Problem


Job Shop avec transportJob Shop avec transport

M1M1 M2M2 M3M3 M4M4

LULU

Exemple d’une Exemple d’une topologietopologie


Les méthodesLes méthodes

Complexité algorithmiqueComplexité algorithmique Méthodes exactesMéthodes exactes Méthodes approchéesMéthodes approchées Algorithme de Johnson pour FS2| |CmaxAlgorithme de Johnson pour FS2| |Cmax Heuristique CDS pour FSm| |CmaxHeuristique CDS pour FSm| |Cmax Méthodes pour le problème du Job ShopMéthodes pour le problème du Job Shop Algorithme du recuit simuléAlgorithme du recuit simulé Systèmes de voisinageSystèmes de voisinage Algorithme du kangourouAlgorithme du kangourou Méthode tabouMéthode tabou Autres méthodesAutres méthodes La double complexitéLa double complexité


La complexité algorithmiqueLa complexité algorithmique

Les problèmes étudiés sont en Les problèmes étudiés sont en général NP-completsgénéral NP-complets

Un algorithme est considéré Un algorithme est considéré comme efficace si et seulement si comme efficace si et seulement si il est polynomialil est polynomial


Méthodes exactesMéthodes exactes

Procédures d’exploration Procédures d’exploration arborescentes (Branch and arborescentes (Branch and Bound, …)Bound, …)

Programmation mathématique Programmation mathématique (PLNE, programmation (PLNE, programmation dynamique, …)dynamique, …)


Méthodes approchéesMéthodes approchées

HeuristiquesHeuristiques Méthodes déterministes (méthode Méthodes déterministes (méthode

tabou, …)tabou, …) Méthodes stochastiques (recuit simulé, Méthodes stochastiques (recuit simulé,

algorithmes génétiques, …)algorithmes génétiques, …) Hybridation de méthodesHybridation de méthodes … …


Algorithme de Johnson pour le Algorithme de Johnson pour le problème du flow-shop à 2 problème du flow-shop à 2 machinesmachines

Le travail i précède le travail j dans une séquence optimale si :Le travail i précède le travail j dans une séquence optimale si :

Min(tMin(ti1i1,t,tj2j2) < Min(t) < Min(tj1j1,t,ti2i2))

Algorithme polynomialAlgorithme polynomial

Machine 1Machine 1 Machine 2Machine 2

Flow shop à deux machinesFlow shop à deux machines


Algorithme de Johnson pour le Algorithme de Johnson pour le problème du flow-shop à 2 problème du flow-shop à 2 machinesmachines


Heuristique CDS pour le Heuristique CDS pour le problème du flow-shop à m problème du flow-shop à m machinesmachines

Dans le cas où le nombre de machines est > 2, Dans le cas où le nombre de machines est > 2, il n’existe pas de méthode exacte polynomiale.il n’existe pas de méthode exacte polynomiale.

Heuristique de Campbell, Dudek et Smith :Heuristique de Campbell, Dudek et Smith :A partir du problème à m machines, on génère A partir du problème à m machines, on génère m-1 problèmes à 2 machines.m-1 problèmes à 2 machines.


Méthodes pour le problème du Job Méthodes pour le problème du Job ShopShop

Algorithme de Jackson pour 2 Algorithme de Jackson pour 2 machinesmachines

Méthode graphique pour 2 tâchesMéthode graphique pour 2 tâches

Méthodes d’énumération, Méthodes d’énumération, heuristiques, … dans le cas généralheuristiques, … dans le cas général


L’algorithme du recuit simuléL’algorithme du recuit simulé

T est une température, T est une température,

X est l'état initial, X est l'état initial,

RX:=X (état record)RX:=X (état record)

tant quetant que nécessaire nécessaire fairefaire

Choisir Y dans V(X) aléatoirement et uniformément ;Choisir Y dans V(X) aléatoirement et uniformément ;

sisi H(Y) < H(RX) H(Y) < H(RX) alorsalors RX:=Y; RX:=Y; finsifinsi

sisi H(Y) <= H(X) H(Y) <= H(X) alorsalors X:=Y X:=Y

sinonsinon X:=Y avec la probabilité exp(-(H(Y)-H(X))/T)X:=Y avec la probabilité exp(-(H(Y)-H(X))/T)

finsifinsi

Générer une nouvelle température ;Générer une nouvelle température ;

faitfait


1

2

3

4

5

6

7

(1 2 3 4 5 6 7 1) devient (1 2 5 4 3 7 6 1)

1

2

3

4

5

6

7

Arêtes enlevées

Arêtes ajoutées

Systèmes de voisinageSystèmes de voisinage

Exemple de mouvement r-opt avec r=3 pour le TSPExemple de mouvement r-opt avec r=3 pour le TSP


Systèmes de voisinageSystèmes de voisinage

1

2

3

4

5

6

7

(1 2 3 4 5 6 7 1) devient (1 6 2 3 4 5 7 1)

1

2

3

4

5

6

7

Arêtes enlevées

Arêtes ajoutées

Exemple de mouvement insertion pour Exemple de mouvement insertion pour le TSPle TSP


L’algorithme du kangourouL’algorithme du kangourou

Choisir A; c:=0; X est l'état initial; RX:=X; (RX est l'état record)Choisir A; c:=0; X est l'état initial; RX:=X; (RX est l'état record)tant quetant que nécessaire nécessaire fairefaire sisi (c < A) (c < A) alorsalors Choisir aléatoirement et uniformément Y dans V(X) ;Choisir aléatoirement et uniformément Y dans V(X) ; sisi H(Y) <= H(X) H(Y) <= H(X) alorsalors sisi H(Y) < H(X) H(Y) < H(X) alorsalors c:=0; c:=0; sisi H(Y) < H(RX) H(Y) < H(RX) alorsalors RX:=Y RX:=Y finsifinsi finsifinsi X:=Y;X:=Y; sinon sinon c:=c+1;c:=c+1; finsifinsi sinonsinon (* effectuer un saut *) (* effectuer un saut *) Choisir aléatoirement et uniformément Y dans W(X) ; c:=0;Choisir aléatoirement et uniformément Y dans W(X) ; c:=0; sisi H(Y) < H(RX) H(Y) < H(RX) alorsalors RX:=Y; RX:=Y; finsifinsi X:=Y;X:=Y; finsifinsifaitfait


L’algorithme du kangourouL’algorithme du kangourou

itérations600000

610000

620000

630000

640000

650000

660000

vale

ur

du c

ritè

re


La méthode TABOULa méthode TABOU

Initialiser la liste tabou ;Initialiser la liste tabou ;

Construire l'état initial X;Construire l'état initial X;

Tant queTant que nécessaire nécessaire fairefaire

Choisir Y le meilleur voisin de X qui Choisir Y le meilleur voisin de X qui n'est pas dans la liste tabou;n'est pas dans la liste tabou;

X:=Y;X:=Y;

Mettre à jour la liste tabouMettre à jour la liste tabou

faitfait


Autres méthodesAutres méthodes

Algorithmes génétiquesAlgorithmes génétiques Algorithmes évolutionnistesAlgorithmes évolutionnistes Colonies de fourmisColonies de fourmis Scatter searchScatter search Hybridation de méthodesHybridation de méthodes ……


ProblèmesProblèmesNP-completsNP-complets Systèmes complexesSystèmes complexes

Complexité algorithmiqueComplexité algorithmiqueComplexité structurelleComplexité structurelle

et fonctionnelleet fonctionnelle

Recherche opérationnelle Couplages SimulationRecherche opérationnelle Couplages Simulation

La double complexitéLa double complexité


Exemples industrielsExemples industriels

Flow shop hybrideFlow shop hybride– Atelier de fabrication de faisceauxAtelier de fabrication de faisceaux– Usine manufacturière (version Usine manufacturière (version

simplifiée)simplifiée)– Usine manufacturièreUsine manufacturière

Job shop avec transportJob shop avec transport Chantiers polyvalentsChantiers polyvalents Line balancingLine balancing Système d’assemblageSystème d’assemblage


Exemple : Flow Shop HybrideExemple : Flow Shop Hybride

Exemple 1 : Atelier de confection de faisceaux Exemple 1 : Atelier de confection de faisceaux électriquesélectriques

FabricationFabrication PréparationPréparation ConstitutionConstitutiondes faisceauxdes faisceaux

- Comparaison de règles de gestion des stocksComparaison de règles de gestion des stocks- Prise en compte des temps de changement d’outilsPrise en compte des temps de changement d’outils



Objectif : Trouver un ordonnancement des travaux en Objectif : Trouver un ordonnancement des travaux en entrée et une affectation des travaux aux machines qui entrée et une affectation des travaux aux machines qui minimisent le temps total de production et le nombre de minimisent le temps total de production et le nombre de changements d’outilschangements d’outils

20 20 88 2525 4242

Exemple 2 : Usine manufacturière simplifiée(7000 pièces et 10 familles)Exemple 2 : Usine manufacturière simplifiée(7000 pièces et 10 familles)



Exemple 3 : Usine manufacturièreExemple 3 : Usine manufacturière


M1 M2 M3 M4

LU

Exemple d’une topologie

Exemple : Job Shop avec Exemple : Job Shop avec transporttransport


Exemple : Job Shop avec transportExemple : Job Shop avec transport

ComplexitéComplexité

Résolution conjointe de deux problèmes NP-complets :Résolution conjointe de deux problèmes NP-complets :

Job Shop Scheduling ProblemJob Shop Scheduling Problem

Vehicle Scheduling ProblemVehicle Scheduling Problem


Exemple : Job Shop avec transportExemple : Job Shop avec transport

Couplage méthode - Couplage méthode - modèlemodèle

Modèle de simulation àModèle de simulation àévénements discretsévénements discrets

Méthode deMéthode derésolutionrésolution

Evaluation du critèreEvaluation du critère

Solution à évaluerSolution à évaluer



Jeux d’essai Jeux d’essai [Ulusoy & Bilge, 1993][Ulusoy & Bilge, 1993]

40 instances :40 instances :

4 machines, 2 véhicules4 machines, 2 véhicules

10 jeux de données :10 jeux de données :

5 à 8 pièces, 13 à 23 opérations5 à 8 pièces, 13 à 23 opérations

4 topologies4 topologies



Résultats : comparaison avec la Résultats : comparaison avec la littératurelittératureLes trois méthodes mises en œuvre (méthode de recherche locale Les trois méthodes mises en œuvre (méthode de recherche locale itérée, recuit simulé, méthode hybride) sont toujours au moins itérée, recuit simulé, méthode hybride) sont toujours au moins aussi bonnes que le meilleur résultat de la littérature.aussi bonnes que le meilleur résultat de la littérature.

23 nouvelles bornes supérieures (sur 40 instances)23 nouvelles bornes supérieures (sur 40 instances)

InstancInstancee

LittératLittérat..

Résult.Résult. InstancInstancee

LittératLittérat..

Résult.Résult.

Ex24Ex24 113113 108108 Ex71Ex71 118118 111111

Ex31Ex31 105105 9999 Ex72Ex72 8585 7979

Ex44Ex44 126126 121121 Ex104Ex104 164164 159159


Exemple : Chantiers Exemple : Chantiers polyvalentspolyvalents

pincespinces

portiqueportique

railrail

Lot de piècesLot de piècesChantier polyvalentChantier polyvalentdécoupé en surfaces découpé en surfaces

élémentairesélémentairesFabricants et monteursFabricants et monteurs



Vue de dessus du chantierVue de dessus du chantier

portiqueportique

carrouselcarrousel

railrail

stock de pincesstock de pinces


Exemple : Chantiers polyvalentsExemple : Chantiers polyvalents

ressourceressource

tempstemps

Ressources :- Surface élémentaire- Pince- Rail- Armoire électrique- Carrousel- Monteur- Fabricant

Une ressource est globale ou locale



ChantierChantier Ressources localesRessources localesau chantier au chantier

Ressources globalesRessources globales

Lot de piècesLot de pièces




Exemple : Line balancingExemple : Line balancing

poste de travail (opérateur)poste de travail (opérateur)

aire de aire de stockage stockage des des composantscomposants

tronçon tronçon 11

tronçon tronçon 33

tronçon 2tronçon 2

ObjectifsObjectifs - minimiser le nombre de - minimiser le nombre de gammes déplacéesgammes déplacées - n’ouvrir que les postes - n’ouvrir que les postes nécessairesnécessaires - lisser la charge de travail- lisser la charge de travail


Exemple : Système Exemple : Système d’assemblaged’assemblage


ConclusionConclusion

Problématique très largeProblématique très large Ordonnancement d’entités de fluxOrdonnancement d’entités de flux Affectation de ressources, d’opérationsAffectation de ressources, d’opérations Planification des mouvements des Planification des mouvements des

moyens de transportmoyens de transport AgencementAgencement DimensionnementDimensionnement Planification de la productionPlanification de la production


PerspectivesPerspectives

Job shop flexibleJob shop flexible Problèmes de transportProblèmes de transport Extensions du RCPSPExtensions du RCPSP Problèmes multi-critèresProblèmes multi-critères Systèmes intégrés de gestionSystèmes intégrés de gestion Contexte stochastiqueContexte stochastique ……


Le groupe BermudesLe groupe Bermudes

Le thème de recherche du groupe Le thème de recherche du groupe Bermudes est l’ordonnancement au sens Bermudes est l’ordonnancement au sens large.large.

Le groupe de travail Bermudes, créé en Le groupe de travail Bermudes, créé en Juin 1996, est composé de 26 laboratoires Juin 1996, est composé de 26 laboratoires et comprend environ 250 membres.et comprend environ 250 membres.

Site Web :Site Web :http://bermudes.univ-bpclermont.frhttp://bermudes.univ-bpclermont.fr


Hybrid Flow ShopHybrid Flow ShopScheduling ProblemScheduling Problem

Hoist Scheduling ProblemHoist Scheduling ProblemHoist Scheduling ProblemHoist Scheduling Problem

Flexible Manufacturing SystemsFlexible Manufacturing SystemsScheduling ProblemsScheduling Problems

Le groupe Bermudes : la problématiqueLe groupe Bermudes : la problématique


Le groupe Bermudes : objectifsLe groupe Bermudes : objectifs

Offrir aux doctorants un cadre d’expression Offrir aux doctorants un cadre d’expression et d’échangeset d’échanges

Faciliter l’accès à la connaissance dans le Faciliter l’accès à la connaissance dans le domaine de l’ordonnancementdomaine de l’ordonnancement

Réaliser une typologie des problèmes et Réaliser une typologie des problèmes et définir et valider les notations pour les définir et valider les notations pour les problèmes étudiésproblèmes étudiés

Proposer des méthodes de résolutionProposer des méthodes de résolution Renforcer et développer la collaboration Renforcer et développer la collaboration

entre les laboratoiresentre les laboratoires


Le groupe Bermudes : Le groupe Bermudes : ProblématiqueProblématique

Résolution de classes de problèmes Résolution de classes de problèmes d’ordonnancement complexes d’ordonnancement complexes résistant aux techniques classiquesrésistant aux techniques classiques

Proposition de méthodes et d’outils Proposition de méthodes et d’outils de résolution de problèmes de résolution de problèmes théoriques et de problèmes théoriques et de problèmes industriels industriels


Liens du groupe Bermudes Liens du groupe Bermudes avec d’autres groupesavec d’autres groupes

BermudesBermudes

- VendômeVendôme- ERPERP

- GOThAGOThA- METAMETA- ORDOORDO

- MMSMMS- ModélisationModélisation- EvaluationEvaluation

- INFORSIDINFORSID- RdPRdP

Chaîne logistiqueChaîne logistique

MéthodesMéthodesModélisationModélisation

Systèmes d’InformationSystèmes d’Information


Actualités et perspectives du Actualités et perspectives du groupe Bermudesgroupe Bermudes

Participation aux Actions Spécifiques CNRS « Recherche Opérationnelle » Participation aux Actions Spécifiques CNRS « Recherche Opérationnelle » et « Production et Logistique »et « Production et Logistique »

Action transversale inter-GDRs :Action transversale inter-GDRs :- GOThA : GDR ALP- GOThA : GDR ALP

- ORDO : GDR ARP- ORDO : GDR ARP - Bermudes : GDR MACS- Bermudes : GDR MACS

Nouveau GDR MACS (Modélisation, Analyse et Conduite de Systèmes)Nouveau GDR MACS (Modélisation, Analyse et Conduite de Systèmes)composé de deux pôles :composé de deux pôles :

- Automatique- Automatique- Sciences et Techniques de la Production- Sciences et Techniques de la Production(de biens et de services)(de biens et de services)

Prochaines réunions : Clermont (13 Juin) et Tours (Septembre) Prochaines réunions : Clermont (13 Juin) et Tours (Septembre)


Quelques référencesQuelques références

Ouvrage collectif : Ordonnancement de la production, Ouvrage collectif : Ordonnancement de la production, coordonné par P. Lopez et F. Roubellat, HERMEScoordonné par P. Lopez et F. Roubellat, HERMES

P. Brucker : Scheduling algorithms, Springer, 2001P. Brucker : Scheduling algorithms, Springer, 2001 J. Carlier, P. Chrétienne : Problèmes J. Carlier, P. Chrétienne : Problèmes

d’ordonnancement (modélisation / complexité / d’ordonnancement (modélisation / complexité / algorithmes), Masson, 1988algorithmes), Masson, 1988

M. Pinedo : Scheduling, theory, algorithms, and M. Pinedo : Scheduling, theory, algorithms, and systems, Prentice Hall, 1995systems, Prentice Hall, 1995

M. R. Garey,D. S. Johnson : Computers and M. R. Garey,D. S. Johnson : Computers and Intractability – A Guide to the Theory of NP-Intractability – A Guide to the Theory of NP-Completeness, W.H.Freeman And Company, 1979Completeness, W.H.Freeman And Company, 1979

……

Documents

Journée Automatique et Optimisation – Université de Paris 12 – 20 Mars 2003 1 Problèmes dordonnancement dans les systèmes de production Michel Gourgand