L’ordonnancement
Un problème d’ordonnancement consiste à organiser dans le temps la réalisation de tâches, compte tenu de contraintes temporelles et de contraintes portant sur la disponibilité des ressources requises.
Un ordonnancement constitue une solution à ce problème. Il vise à satisfaire un ou plusieurs objectifs. Un ordonnancement est une compilation des dates de début et de fin des différentes opérations couplées à leurs ressources. On utilise généralement la formule «l’ordonnancement» pour décrire le domaine de l’ordonnancement .
En général, la solution d’un problème d’ordonnancement est donnée sous forme d’une séquence d’opérations sur chaque machine. Une telle solution est appelée «séquence», et est une solution du problème de «séquencement». L’ordonnancement est un problème très complexe. Les problèmes sont le plus souvent NP-difficiles, comme par exemple, le flow shop à 3 machines avec comme critère le Cmax (voir [BK07] pour plus d’informations sur les problèmes NP-complet en ordonnancement). Pour résoudre ces problèmes, l’optimisation combinatoire est l’outil le plus commun. Des méthodes d’optimisation exactes (et exponentielles) et des méthodes d’optimisation heuristiques permettent de résoudre ces problèmes.
Satisfaction de contraintes
Trouver une solution à un problème d’ordonnancement consiste tout d’abord à trouver une solution satisfaisant toutes les contraintes : une solution réalisable.
Généralement, trouver un ordonnancement réalisable est une tâche aisée : un algorithme constructif arrive à prendre en compte les principales contraintes de l’ordonnancement (notamment les contraintes de ressources, de précédences et les dates de début au plus tôt), et permet donc la construction d’une telle solution rapidement et simplement.
Cependant, certaines contraintes ne peuvent être prises en compte facilement lors de la construction d’un ordonnancement. Par exemple, les dates de fin impératives ne peuvent être prises en compte simplement, et peuvent même engendrer des problèmes ne possédant pas de solution.
Lors de la résolution d’un problème de satisfaction de contraintes, l’algorithme tente de trouver une solution réalisable. S’il en trouve une, il la propose, et le problème est résolu. Par contre, lorsque le problème ne possède pas de solution réalisable, l’algorithme ne peut rien proposer à l’utilisateur. Pour pallier ce défaut, on reformule généralement de tels problèmes avec des contraintes molles : au lieu de rendre les solutions réalisables difficiles à trouver, on modélise le problème sous forme de préférences, et on cherche à obtenir une solution réalisable qui maximise nos préférences. On obtient alors un problème d’optimisation.
Ordonnancements actifs, semi-actifs et sans délai
La plupart des algorithmes de résolution de problème d’ordonnancement donnent en solution des classes spécifiques d’ordonnancement. Ces classes sont la classe des ordonnancements sans délai, la classe des ordonnancements actifs et la classe des ordonnancements semi-actifs.
Un ordonnancement semi-actif est un ordonnancement calé à gauche. Cela correspond donc à un ordonnancement où on exécute la tâche prévue au plus tôt.
Nous avons donc une bijection entre séquencement et ordonnancement semi-actif. Dans un ordonnancement actif, il est impossible d’avancer une tâche sans en reculer une autre. Cela signifie que l’ordonnancement est calé à gauche et sans période de disponibilité suffisamment importante entre deux tâches pour y insérer une autre tâche sans violer de contraintes. Un ordonnancement actif est également un ordonnancement semi-actif.
Un ordonnancement sans délai est un ordonnancement où une machine n’est jamais laissée inutilisée alors qu’elle pourrait l’être. Cela signifie que s’il y a une tâche dans la file d’attente d’une machine, alors cette machine exécute une tâche.
Les ordonnancements à règles de priorité génèrent généralement de tels ordonnancements. Un ordonnancement sans délai est également un ordonnancement actif.
Contexte productique de l’ordonnancement d’atelier
L’ordonnancement d’atelier se fait dans un contexte particulier. Ce contexte est défini par la gestion de la production utilisée par l’entreprise.
En général, on effectue : La planification à long terme. Elle se fait sur plusieurs années. Elle exprime la stratégie de l’entreprise.
La planification à moyen terme, qui s’effectue sur plusieurs mois. Elle prévoit la charge de l’atelier et constitue l’entrée du calcul des besoins.
La planification à court terme. Elle génère les ordres de fabrications et d’approvisionnements. Cette planification est généralement réalisée par un ordonnancement à capacité infinie. L’ordonnancement d’atelier en lui-même. Il utilise la planification à court terme comme entrée et génère l’affectation des tâches aux ressources.
On remarquera que, typiquement, les dates de début au plus tôt des opérations ainsi que les dates de fin souhaitées sont déterminées pendant la planification à court terme. En pratique, il est possible de renégocier ces dates données par la planification. L’ordonnancement se trouve donc au sein d’une organisation complexe gérée par des hommes.
Les Phases de l’ordonnancement
Une méthode d’ordonnancement peut se découper en plusieurs parties. En pratique, on distingue deux parties principales : la phase prédictive, qui a lieu avant l’exécution de l’ordonnancement dans l’atelier, et la phase réactive, qui a lieu pendant l’exécution.
La phase prédictive a lieu avant l’exécution de l’ordonnancement, c’est-à-dire que l’exécution de l’ordonnancement est «prédit». Cette phase n’est pas soumise à des contraintes fortes de temps : il n’est pas nécessaire de répondre à des sollicitations en un temps imparti. Cette phase dure généralement un certain temps, entre quelques heures et quelques semaines suivant le problème et le type d’atelier. Cette phase repose intégralement sur un modèle : elle n’est pas réalisée sur l’atelier, mais hors ligne, le plus souvent en utilisant un ordinateur. L’efficacité de cette phase repose essentiellement sur la modélisation du problème, et les outils disponibles pour le résoudre. Cette phase peut également être appelée «phase proactive» si une méthode proactive ou proactive-réactive est utilisée.
La phase réactive a lieu pendant l’exécution de l’ordonnancement, c’est-à-dire qu’elle «réagit» aux événements réels qui ont lieu dans l’atelier. Durant cette phase, les décisions à réaliser par le système doivent être prises rapidement, avec généralement un temps de réaction imposé. Ce temps varie en pratique entre quelques secondes et quelques heures suivant le problème. Il n’est donc pas envisageable d’utiliser des algorithmes très coûteux en temps de calcul dans cette phase. Comme le but de cette phase est de réagir en temps réel aux événements de l’atelier, la méthode de résolution possède une connaissance exacte des événements tels qu’ils se sont passés, car ils sont rapportés par le système réel, et non par un modèle comme dans la phase prédictive. Ces deux phases sont des notions primordiales pour l’ordonnancement sous incertitudes : chaque phase possède des données différentes sur les incertitudes.
Table des matières
Introduction
I Choix de la méthode d’ordonnancement
1 L’ordonnancement d’atelier
1.1 Définitions générales
1.1.1 L’ordonnancement
1.1.2 Les tâches
1.1.3 Les ressources
1.1.4 Les contraintes
1.1.4.1 Les contraintes temporelles
1.1.4.2 Les contraintes de ressources
1.1.5 Les objectifs
1.1.5.1 Satisfaction de contraintes
1.1.5.2 Optimisation d’un objectif
1.1.5.3 Optimisation multiobjectif
1.1.6 Ordonnancements actifs, semi-actifs et sans délai
1.2 Classification des problèmes d’ordonnancement
1.2.1 Le champ α
1.2.2 Le champ β
1.2.3 Le champ γ
1.2.4 Quelques exemples
1.3 Ordonnancement théorique et pratique
1.3.1 Contexte productique de l’ordonnancement d’atelier
1.3.2 Ordonnancement et déterminisme
2 Les incertitudes en ordonnancement
2.1 Définitions
2.1.1 Les Phases de l’ordonnancement
2.1.2 Incertitudes
2.1.3 Flexibilité et robustesse
2.1.3.1 Flexibilité
2.1.3.2 Robustesse
2.2 Méthodes pour l’ordonnancement sous incertitudes
2.2.1 Approche proactive
2.2.2 Approche réactive
2.2.2.1 L’approche dynamique
2.2.2.2 Approche prédictive-réactive
2.2.3 Approche proactive-réactive
2.3 Choix de la méthode d’ordonnancement
3 L’ordonnancement de groupes
3.1 Description de l’ordonnancement de groupes
3.1.1 Définitions
3.1.2 Évaluation de la qualité d’un ordonnancement de groupes
3.1.3 Représentation graphique
3.1.4 Évaluation de la flexibilité
3.1.4.1 Le nombre de séquences dans un ordonnancement de groupes
3.1.4.2 Flexibilité et nombre de groupe
3.1.4.3 Comparaison des deux mesures de flexibilité
3.1.5 Exemple
3.1.6 Exécution d’un ordonnancement de groupes
3.1.7 Propriétés
3.1.8 Contraintes prises en compte
3.2 Les principaux algorithmes
3.2.1 Calcul des dates de fin au plus tôt dans le pire des cas
3.2.2 Calcul des dates de début au plus tard dans le pire des cas
3.2.3 Marge libre séquentielle
3.2.4 Génération d’un ordonnancement de groupes
3.2.4.1 Les différents algorithmes
3.2.4.2 EBJG
3.2.4.3 Améliorations apportées à EBJG
3.3 Robustesse de l’ordonnancement de groupes
3.3.1 Étude de Wu et al
3.3.2 Étude d’Esswein
3.4 L’ordonnancement de groupes sur une chaîne de production flexible
3.4.1 Adaptation de l’ordonnancement de groupes pour une chaîne de production flexible
3.4.2 Expérimentations
3.4.3 Discussion
3.4.3.1 VT > 1,4 ud/ut
3.4.3.2 0,7 ud/ut < VT < 1,4 ud/ut .
3.4.3.3 VT < 0,7 ud/ut
3.4.3.4 Analyse globale
3.5 Robustesse et coopération homme-machine
II Coopération homme-machine pour la mise en œuvre d’un ordonnancement de groupes
4 Coopération homme-machine pour l’ordonnancement
4.1 Notions sur la coopération homme-machine
4.1.1 L’outil et la prothèse
4.1.2 Utilisation active et passive
4.1.3 Influences des systèmes d’aide à la décision sur l’humain
4.1.4 Les compromis
4.2 Coopération homme machine et ordonnancement
4.2.1 Homme, machine et système homme-machine
4.2.2 Compréhension du fonctionnement de la machine
4.2.3 Les différences interindividuelles
4.2.4 Niveau de coopération et caractéristiques de la tâche
5 Coopération pour la phase proactive
5.1 L’approche d’ORABAID
5.1.1 Description du système homme-machine
5.1.2 Analyse du système homme-machine
5.2 Reformulation multiobjectif d’Esswein
5.2.1 Le modèle multiobjectif
5.2.2 Compréhension de la mesure de la flexibilité
5.2.3 Décision grâce à l’approche epsilon contrainte
5.2.4 Décision grâce à un ensemble de solutions non dominées
6 Coopération pour la phase réactive
6.1 Analyse de la phase réactive d’ORABAID
6.2 Propositions pour la phase réactive
6.3 Expérimentation
6.3.1 Objectif
6.3.2 Plan de l’expérience
6.3.3 Procédure expérimentale
6.3.4 Résultats
6.4 Réalisation de l’expérimentation
6.5 Outils nécessaires
III Le meilleur des cas
7 Les bornes inférieures
7.1 La date de fin au plus tôt dans le meilleur des cas
7.1.1 L’algorithme
7.1.2 Exemple de l’exécution de l’algorithme
7.1.3 Complexité
7.2 Bornes inférieures pour les objectifs réguliers
7.3 Bornes inférieures pour le makespan
7.3.1 Utilisation de la formulation pour les objectifs réguliers
7.3.2 La borne inférieure classique du job shop
7.3.3 Une borne inférieure améliorée pour le makespan
7.4 Utilisation des bornes inférieures
8 Les heuristiques
8.1 Règles de priorité
8.1.1 Most work remaining
8.1.2 Une règle utilisant la durée de latence
8.1.3 Utilisation d’une borne inférieure dans une règle de priorité
8.2 Un shifting bottleneck pour l’ordonnancement de groupes
8.2.1 Le shifting bottleneck
8.2.2 Adaptation pour l’ordonnancement de groupes
8.3 Expérimentation
8.3.1 Protocole
8.3.2 Discussion
8.4 Conclusion
9 La méthode exacte
9.1 Description de l’algorithme
9.1.1 Procédure de séparation
9.1.1.1 Description de la procédure
9.1.1.2 Exemple
9.1.2 Diminution de l’espace de recherche
9.1.2.1 Une condition suffisante pour diminuer l’espace de recherche
9.1.2.2 Exemple
9.1.3 Stratégies de recherche
9.2 Expérimentations
9.2.1 Protocole
9.2.2 Résultats
9.2.3 Discussion
9.2.3.1 Analyse de la variante Défaut
9.2.3.2 Comparaison des différentes variantes
9.2.3.3 Instances difficiles
9.3 Conclusion
10 Utilisation du meilleur des cas
10.1 Utilisation dans la phase proactive
10.1.1 Utilisation de la qualité optimale
10.1.2 Utilisation des bornes inférieures et supérieure
10.1.3 Adaptation au contexte de la phase proactive
10.2 Utilisation dans la phase réactive
10.2.1 Utilisation des bornes inférieure et supérieure
10.2.2 Utilisation de la qualité optimale
10.2.3 Adaptation au contexte de la phase réactive
10.3 Conclusion
Conclusions et perspectives
Bibliographie
