Soutenance mémoire
L’ordonnancement d’un atelier de production consiste à allouer dans un horizon de temps précis un ensemble de machines limitées à un ensemble de jobs tout en satisfaisant un ensemble de contraintes et en optimisant un ou plusieurs objectifs. La résolution de cette problématique a constitué un nombre important de sujets de recherches depuis les années cinquante. Différentes méthodes exactes et approchées ont été proposées sous l’hypothèse que les variables de l’atelier sont déterministes. Cependant, en réalité et dans un contexte industriel, cette hypothèse est généralement incorrecte ; les variables de l’atelier subissent des changements liés à des perturbations incontrôlables, telles que, les pannes des machines, les retards de livraison, l’arrivée des jobs urgents, etc. Ces perturbations, une fois qu’elles se produisent dans l’atelier, empêchent l’exécution de l’ordonnancement exactement comme planifié.
Afin de palier ces incertitudes, différentes méthodes, dites robustes, sont proposées dans la littérature. Ces méthodes motivées par leurs applications industrielles, cherchent soit, à intégrer des modèles d’incertitudes a priori dans l’ordonnancement, soit à corriger ce dernier à l’aide d’algorithmes dits réactifs, tout en évitant la détérioration des performances attendues.
Différentes études de la littérature montrent que l’opérateur humain est considéré comme l’acteur approprié pour la prise de décision en ordonnancement. Malgré des tentatives pour remplacer le travail de l’humain par des programmes et algorithmes de l’intelligence artificielle, la recherche actuelle avec des cas d’études réels prouvent que l’humain expert est irremplaçable surtout dans des situations imprévues grâce à sa capacité d’adaptation à l’environnement. Cependant, le cerveau humain est limité face à des calculs complexes où la machine s’avère très efficace. Pour toutes ces raisons, une coopération homme-machine est crucial.
Ordonnancement
Définition de l’ordonnancement
L’ordonnancement consiste à affecter un ensemble de travaux (jobs) à un ensemble de ressources à capacité limitées (machines) en un temps précis afin de satisfaire un ou plusieurs objectifs. Dans la pratique, les notions de jobs et machines peuvent prendre différents sens, selon le contexte de mise en œuvre. Par exemple :
— En informatique, il s’agit de choisir l’ordre des processus à exécuter et leur affectation à des processeurs parallèles.
— Dans un atelier manufacturier, il s’agit d’établir un planning de fabrication où la séquence des opérations à réaliser sur les différentes ressources de l’atelier est définie de manière très précise.
— Dans un système logistique, il s’agit d’établir l’ordre des livraisons aux clients et leur affectation aux différentes ressources de transport.
— Dans un hôpital, il s’agit par exemple d’établir une programmation pour des blocs opératoires ou d’organiser le circuit du patient hospitalisé.
— En gestion de projet il s’agit de déterminer les dates de début et de fin des activités du projet, sans qu’il y ait forcément de ressources dans ce dernier cas.
— etc.
Dans ce mémoire, nous nous intéressons exclusivement aux problèmes d’ordonnancement d’atelier. Nombreuses sont les définitions de l’ordonnancement d’atelier, certaines de ces définitions sont évoquées dans la littérature comme suit : « ordonnancer un ensemble de tâches, c’est programmer leur exécution en leur allouant les ressources requises et en fixant leurs dates de début » (Gotha 1993) « Résoudre un problème d’ordonnancement c’est résoudre un problème d’optimisation combinatoire constitué d’un ensemble de tâches, d’un ensemble de ressources, d’un ensemble d’objectifs et d’un ensemble de contraintes. La solution à ce problème est un ordonnancement qui donne des indications sur les dates de début des tâches ou qui propose une relation d’ordre total ou partiel sur la séquence de réalisation des tâches » (Artigues 2004) « Scheduling is a decision making process that is used on a regular basis in many manufacturing and services industries. It deals with the allocation of resources to tasks over given time periods and its goal is to optimize one or more objectives » (Pinedo 2012) .
Éléments d’un problème d’ordonnancement
Dans un problème d’ordonnancement, quatre éléments fondamentaux sont nécessaires à la définition et la résolution d’un problème d’ordonnancement : les tâches, les ressources, les contraintes et les objectifs. Les définitions représentées dans cette section sont issue des références suivantes Gotha (1993), Esswein (2003), Pinedo (2012), Mebarki (2012).
Tâches
Une tâche est une entité de travail localisée dans le temps par une date de disponibilité ri , une date de début ti , une durée de traitement ρi , une date d’échéance di et une date de fin Ci . La réalisation d’une tâche nécessite une certaine durée (ρi) à passer sur un certain nombre d’unités de ressources tel que ρi= Ci − ti .
Ressources
Une ressource peut être vue comme un moyen technique (machine) ou humain requis pour l’exécution d’une tâche dans la disponibilité limitée ou non est connue a priori. On distingue deux types de ressources :
— Ressources renouvelables : sont des ressources disponibles après consommation par d’autres tâches avec les mêmes quantités (machines, humains, processeur, etc).
— Ressources consommables (non renouvelables) : ces ressources sont représentées par une matière première ou un budget par exemple. Contrairement aux ressources renouvelables, elles ne deviennent pas disponibles après consommation.
Certaines ressources peuvent exécuter plusieurs tâches à la fois et sont appelées des ressources partageables. Contrairement à ces ressources, les ressources dites non partageables ou disjonctives ne peuvent exécuter qu’une seule tâche à la fois. En ordonnancement d’atelier, on parle généralement de machines. Dans ce mémoire, nous nous intéressons qu’aux machines renouvelables et disjonctives. k et m représentent respectivement l’indice de la machine (Mk ) et le nombre de machine dans un problème d’ordonnancement d’atelier. MOi désigne la machine exécutant l’opération Oi .
Contraintes
Les contraintes sont les restrictions que peuvent prendre les valeurs de décisions. Trois types de contraintes sont distingués dans un problème d’ordonnancement :
— Contraintes de temps : elles sont généralement représentées par les dates d’échéances (di) et les dates de disponibilités (ri) des opérations. Un ordonnancement admissible doit donc satisfaire la contrainte suivante : ti ≥ ri De plus, dans un ordonnancement sans retard, la contrainte des dates d’échéances doit être satisfaite (Ci ≤ di).
— Contraintes d’enchaînement : les opérations sont souvent liées entre elles par des contraintes de précédences Γ− (resp. de succession Γ+). Une relation de précédence (resp. de succession) de l’opération Oj par l’opération Oi est représentée par la formule suivante :
tj ≥ Ci (resp. ti ≥ Cj)
— Contraintes de ressources : une contrainte d’une ressource représente la nature et la quantité de la ressource utilisée pour l’exécution d’une opération Oi au cours du temps. Dans le cas des ressources disjonctives renouvelables dans un ordonnancement d’atelier, une machine ne peut traiter qu’une seule opération à la fois. Une relation de deux opérations disponibles à un même instant dans une même machine est représentée comme suit :
∀(Oi ,Oj)MOi = MOj tel que Ci ≤ tj ou Cj ≤ ti .
|
Table des matières
Introduction générale
I Ordonnancement
Préliminaires
1.1 Définition de l’ordonnancement
1.2 Éléments d’un problème d’ordonnancement
1.2.1 Tâches
1.2.2 Ressources
1.2.3 Contraintes
1.2.4 Objectifs
1.2.5 Modèles d’ateliers
1.2.6 Notation des variables d’un problème d’ordonnancement
Problème de Job Shop
2.1 Définition
2.2 Représentation d’un problème de Job Shop par un graphe disjonctif
2.3 Méthodes de résolution d’un problème de Job Shop
2.3.1 Méthodes exactes
2.3.2 Méthodes approximatives
L’ordonnancement sous incertitudes
3.1 Définitions
3.1.1 Phases de l’ordonnancement
3.1.2 Incertitudes
3.1.3 Scénarios
3.1.4 Robustesse
3.1.5 Flexibilité
3.2 Approches de résolution
3.2.1 Approches proactives
3.2.2 Approches réactives
3.2.3 Approches proactives-réactives
3.3 Quelle méthode proactive-réactive ?
3.3.1 Ordre partiel
II Ordonnancement de groupes
Groupes d’opérations permutables
4.1 Définition
4.1.1 Formulation
4.1.2 Exemple
4.1.3 Qualité d’un ordonnancement de groupes
4.1.4 Flexibilité d’un ordonnancement de groupes
4.1.5 Construction des groupes
Le meilleur des cas
5.1 Borne inférieure pour le problème de job shop
5.2 Borne inférieure pour la date de début/fin au plus tôt des opérations dans le meilleur des cas
5.2.1 Amélioration des dates de début/fin au plus tôt des opérations
5.3 Borne inférieure pour le meilleur des cas
5.3.1 Expérimentations et résultats
5.4 Méthode de séparation et d’évaluation pour le meilleur des cas
5.5 Amélioration de la procédure de séparation pour le meilleur des cas
5.5.1 Expérimentations et résultats
III Coopération homme-machine et aide à la décision
L’ordonnancement de groupes : une méthode qui favorise la coopération homme-machine
6.1 Le facteur humain dans l’ordonnancement
6.2 IHM pour l’ordonnancement de groupes
6.3 L’utilité du meilleur des cas dans un système d’aide à la décision
6.3.1 Expérimentations et résultats
Étude de cas
7.1 Le meilleur des cas en pratique
7.2 Nouvelle expérimentation
7.2.1 Protocole de l’expérimentation
7.2.2 Résultats
7.2.3 Discussion
Conclusion générale
Bibliographie
