Les problèmes d'ordonnancement sont généralement vastes et complexes et sont classés mathématiquement dans un groupe de problèmes appelés NP-Hard (non-deterministic polynomial-time hard). En termes non mathématiques, il s'agit des problèmes informatiques les plus difficiles pour lesquels il n'existe pas d'algorithmes optimaux pratiques. Par conséquent, toutes les solutions d'ordonnancement utilisent des heuristiques et donc aucune ne produit une solution optimale (indépendamment de ce que les vendeurs pourraient suggérer). Le mieux que l'on puisse espérer avec cette classe de problèmes est une "bonne" solution qui est meilleure et plus facile à obtenir que d'essayer de générer manuellement une solution à l'aide d'Excel ou d'un tableau de planification. Dans ce livre blanc, nous comparerons brièvement les approches basées sur l'optimisation et la simulation pour le problème de l'ordonnancement.
Planification basée sur l'optimisation
Malgré leur nom, les outils d'ordonnancement basés sur l'optimisation utilisent des approches heuristiques qui tentent de générer une solution satisfaisant une liste de contraintes mathématiques et offrant des performances raisonnables sur des mesures clés telles que le nombre de travaux en retard. Il n'y a aucune garantie quant à la qualité de l'ordonnancement par rapport à d'autres ordonnances possibles ou quant au temps de calcul qui pourrait être nécessaire pour obtenir un ordonnancement réalisable ou bon.Ces outils s'efforcent généralement de générer d'abord un programme réalisable, puis d'améliorer ce programme en explorant des variantes du programme réalisable afin d'améliorer les mesures de performance. La qualité de la réponse finale sera limitée par le temps accordé à l'algorithme pour rechercher de meilleures solutions. Généralement, une limite de temps est fixée (par exemple une heure) pour la recherche algorithmique et la meilleure solution trouvée pendant ce temps de recherche est utilisée comme programme.
L'algorithme (parfois appelé solveur) effectue ses recherches sur la base d'un modèle mathématique du système de production configuré lors de l'installation du logiciel. Le modèle mathématique décrit les contraintes du système en matière de ressources et, dans certains cas, peut inclure des détails tels que les temps de préparation d'une ressource en fonction de la séquence. Toutefois, ce modèle mathématique a une structure limitée et ne peut pas prendre en compte toutes les contraintes, par exemple la manutention de matériaux complexes tels que le mouvement des AGV ou de plusieurs grues qui se chevauchent.Même dans le cadre des capacités du modèle mathématique, il est souvent nécessaire d'omettre des détails de l'installation (par exemple, les temps de préparation dépendant de la séquence) pour maintenir le temps de calcul requis pour l'algorithme de recherche dans des limites acceptables.Le problème est que les plannings obtenus sont souvent infaisables dans le système réel en raison des contraintes qui ont été ignorées par l'outil de planification. En raison des limites du modèle mathématique, les outils basés sur l'optimisation fonctionnent mieux dans des applications simples et directes avec peu de contraintes complexes.
L'un des outils de planification basés sur l'optimisation les plus connus est PP/DS de SAP. Cet outil propose deux solveurs alternatifs pour générer des solutions au modèle mathématique. Le premier solveur est un algorithme de programmation basé sur les contraintes qui est le meilleur choix pour rechercher une solution réalisable lorsque de nombreuses contraintes complexes sont présentes. Cependant, ce solveur est moins efficace pour trouver de bonnes solutions.Le succès de l'un ou l'autre de ces solveurs à fournir une solution raisonnable dans les limites d'un temps de recherche pratique dépend de la complexité du modèle mathématique et de son adéquation approximative au système réel.
Les solveurs ne sont souvent pas capables de résoudre le problème en un temps pratique, et c'est pourquoi PP/DS fournit également un ensemble d'algorithmes heuristiques simples pour générer un programme réalisable. La plupart des implémentations de PP/DS utilisent en fait ces heuristiques simples et n'utilisent pas les deux solveurs disponibles.
Ordonnancement basé sur la simulation
L'approche de la planification basée sur la simulation remplace l'ensemble des contraintes mathématiques par un modèle de simulation de l'installation. Certains outils basés sur la simulation (par exemple Preactor) utilisent un modèle de simulation codé en dur de l'installation qui est configuré à l'aide d'une base de données. Ces outils sont limités aux applications pour lesquelles le modèle basé sur les données est raisonnablement adapté à l'installation. D'autres outils de simulation (par exemple Simio) prennent en charge à la fois une approche basée sur les données (pour les applications standard) et permettent la création personnalisée du modèle de simulation sous-jacent de l'installation (pour les applications complexes). Cette dernière approche offre une flexibilité totale dans la capture des contraintes détaillées du processus dans le système et une plus grande transparence dans le processus de génération du calendrier.
Dans un outil basé sur la simulation, le planning est généré en simulant le flux de travail à travers le modèle de l'installation. Au fur et à mesure que les tâches se déplacent dans l'installation simulée, elles font la queue devant les machines, attendent que le matériel, les outils et les opérateurs soient disponibles avant de continuer. Le mouvement du travail à travers le modèle de l'installation simulée est enregistré et affiché sous la forme de diagrammes de Gantt qui montrent le flux de chaque tâche à travers le système.Le diagramme de Gantt des ressources montre le chargement de chaque tâche sur chaque ressource du système, et le diagramme de Gantt des tâches montre le flux de chaque tâche sur les ressources qu'elle utilise pendant le traitement. La figure suivante montre un simple diagramme de Gantt des ressources généré par le planificateur basé sur la simulation Simio. Ce diagramme de Gantt est interactif et permet au planificateur de faire glisser et de déposer des commandes à l'intérieur et entre les machines sur le diagramme de Gantt. Cela permet au planificateur d'apporter des ajustements au calendrier généré par le modèle de simulation.
En plus des diagrammes de Gantt interactifs, Simio peut également fournir des rapports détaillés et des tableaux de bord interactifs qui résument le flux de travail programmé dans l'installation. Il peut s'agir de rapports et de tableaux de bord standard sur les ressources, les matériaux et les contraintes du système, ainsi que de rapports et de tableaux de bord personnalisés pour des applications spécifiques. Les résultats de la planification peuvent être diffusés à plusieurs utilisateurs sur des appareils mobiles à l'aide du portail Simio basé sur le cloud. L'illustration suivante montre un exemple de tableau de bord interactif décrivant l'état des machines et la liste des travaux à effectuer pour les machines de l'installation.
Dans Simio, le flux de travail à travers le système pour générer le planning peut également être visualisé dans une animation 3D haute fidélité (voir ci-dessous). Cela rend le processus de génération de planning très transparent. Ce qui suit est un instantané de la génération de planning animée pour le planificateur Simio basé sur la simulation.
L'optimisation du planning se fait en appliquant des règles de planification heuristiques aux décisions prises pendant l'exécution du modèle. Par exemple, lorsqu'une machine est inactive, elle peut avoir le choix de la tâche suivante à traiter. Les outils de planification basés sur la simulation fournissent généralement un ensemble riche de règles pour effectuer cette sélection.Par exemple, dans une industrie de transformation, une règle peut être spécifiée pour minimiser les temps/coûts de préparation dépendant de la séquence à un poste de travail spécifique. D'autres règles sont disponibles pour se concentrer sur d'autres mesures de performance clés telles que la minimisation des retards, la maximisation du débit ou la minimisation du temps d'inactivité sur une machine goulot d'étranglement. Il est également facile de créer des règles personnalisées pour des mesures de performance spécifiques à l'application.
L'un des principaux avantages de l'approche de la planification basée sur la simulation est que lorsqu'un événement perturbateur se produit (par exemple, une panne de machine), une nouvelle planification peut être générée en quelques secondes ou minutes (contre plusieurs heures pour un outil basé sur l'optimisation). La vitesse nettement plus rapide des outils de planification basés sur la simulation en fait le meilleur choix dans les environnements très dynamiques où la nécessité d'une nouvelle planification se fait fréquemment sentir.
Un autre avantage clé de l'approche basée sur la simulation est la capacité de capturer les contraintes détaillées du système dans un modèle d'installation de haute fidélité. Il en résulte des planifications réalistes et exécutables qui peuvent être mises en œuvre "telles quelles" dans l'atelier sans ajustement par les opérateurs de l'atelier. Lorsqu'un outil de planification génère des planifications infaisables qui nécessitent des changements dans l'atelier, les opérateurs peuvent prendre des décisions "locales" qui produisent une planification non-optimale.
L'approche de l'ordonnancement basée sur l'optimisation pose un problème critique : elle exige que toutes les données soient parfaitement connues et déterministes. Par exemple, tous les temps de traitement doivent être fixes et il ne peut y avoir d'événements inattendus ou de retards. Malheureusement, il s'agit là d'un "chemin heureux" à travers le système et la programmation qui en résulte est par nature optimiste et généralement très différente de ce qui se passe dans l'installation réelle. Il est fréquent que ce qui est au départ un programme réalisable devienne infaisable au fil du temps, à mesure que les variations et les événements imprévus dégradent les performances. Il est normal qu'il y ait des écarts importants entre les plannings prévus et les performances réelles. La planification et l'ordonnancement basés sur les risques (RPS) de Simio, basés sur la simulation, étendent l'ordonnancement traditionnel pour prendre en compte les variations présentes dans presque tous les systèmes de production, et fournissent les informations nécessaires au planificateur pour permettre la réduction des risques et de l'incertitude.
Télécharger la version PDF