Coopération homme-machine et aide à la décision

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. Une telle coopération est pilotée par un système d’aide à la décision. Dans ce cadre, nous nous intéressons à améliorer le système d’aide à la décision afin de tirer pleinement avantage de la coopération homme-machine en ordonnancement sous incertitudes. Le contexte de la résolution proposée est centré sur la méthode d’ordonnancement de groupes. Cette méthode est une des approches les plus étudiées dans la littérature consacrées à l’ordonnancent sous incertitudes et a été implémentée dans plusieurs entreprises industrielles en France. Elle est constituée en deux phases, une première phase dite hors-ligne permettant de proposer un ensemble de solutions admissibles non énumérées au lieu d’un seul ordonnancement. Ensuite, une de ces solutions est sélectionnée en temps-réel durant la phase de décision. L’opérateur doit choisir à l’aide d’un système d’aide à la décision, la solution/l’ordonnancement la/le plus adapté(e) aux changements survenus dans l’atelier.

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).

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

La qualité d’un ordonnancement est mesurée au travers différents critères de performance, généralement par des fonctions des dates de fin des opérations (Ci ). Un critère de performance est dit régulier s’il s’agit d’une fonction croissante des dates de fin des opérations (Ci ). Cette caractéristique signifie que, terminer une opération plus tôt ne peut dégrader un critère régulier. On cherche donc à exécuter les opérations au plus tôt dans le cas de critères réguliers. Un critère régulier de type minsum est représenté par la formule ∑ fi = ∑i fi(Ci).

Un critère régulier de type minmax est représenté par la formule max fi = maxi fi(Ci). L’objectif makespan est l’objectif régulier le plus utilisé dans la littérature et représente la date de fin maximale de toutes les opérations de l’ordonnancement noté Cmax = maxi Ci.

Table des matières

Introduction générale
I Ordonnancement
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
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
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
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
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
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
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 et perspectives
Bibliographie

Télécharger le rapport complet