L’ordonnancement d’un système « flexible flow shop »

La fonction d’ordonnancement dans un système de production représente la dernière phase de prise de décision avant l’exécution des plans de production. Si l’on considère toutes les étapes et activités de planification et de contrôle de la production (PPC) qui se succèdent (voir Fig. 1), les problèmes d’ordonnancement concernent l’allocation de ressources limitées à des activités dans le temps afin de répondre aux exigences issues de la phase de planification [1].

La problématique d’ordonnancement dans les ateliers organisés en Flexible Flow-Shop

Les problèmes d’ordonnancement sont fortement influencés par l’agencement de l’atelier où se déroulent les opérations. Dans cet article, nous analyserons le problème Hybrid Flow-Shop (HFS), également appelé Flexible Flow-Shop (FFS), qui résulte de la combinaison de deux problèmes élémentaires d’ordonnancement [2] 

• Le problème de Flow-Shop où des machines, chacune réalisant une opération particulière, sont disposées en série. Chaque tâche est décomposée en autant d’opérations qu’il y a de machines. Toutes les opérations, quel que soit la tâche, sont réalisées dans un même ordre prédéfini.

• Le problème de machines parallèles où des machines réalisant le même type d’opération sont disposées en parallèle à la même étape du processus de production.

Sur la base de ces considérations, un problème d’ordonnancement FFS correspond à une série de machines parallèles (voir Fig. 2). Chaque tâche, ou job, ne doit pas nécessairement passer par toutes les étapes ; certaines tâches peuvent ignorer une ou plusieurs étapes. Dans le cas général, une machine ne peut traiter qu’une seule opération à la fois.

Il existe de nombreuses variantes du problème, que l’on peut principalement classer en fonction de trois facteurs :

a. Configuration de l’atelier

Cet axe distingue les problèmes selon le nombre d’étapes dans l’atelier, le nombre de machines parallèles à chaque étape, et la présence ou non d’écarts de performances ou de disponibilités entre les machines parallèles.

b. Contraintes et hypothèse

Cet axe définit, entre autres, les règles d’affectation des opérations aux machines. Pour des raisons le plus souvent techniques, il arrive en effet que certaines opérations ne puissent être traitées que par certaines machines. D’autres contraintes/hypothèses relatives à la préemptivité des tâches, la précédence des tâches, les capacités de stockage intermédiaires ou encore les dates de début au plus tôt/au plus tard peuvent être décrites et donner lieu à des variantes plus ou moins complexes du problème FFS.

c. Les fonctions objectives considérées

L’objectif est généralement de minimiser la durée d’exécution, ce qui revient implicitement à maximiser l’utilisation des ressources. Il peut cependant exister d’autres objectifs comme par exemple minimiser le stock d’en-cours ou encore se rapprocher d’un niveau de stock cible. Les modèles théoriques existants se concentrent en général sur un objectif unique. Sur le terrain, plusieurs objectifs sont à prendre en considération avec une importance relative qui peut varier selon le contexte.

Les systèmes flexible flow shop dans l’industrie

Le FFS correspond à une organisation d’atelier très répondue dans l’industrie notamment dans les secteurs de la cosmétique, de l’agroalimentaire ou encore de la pharmaceutique. Dans ces industries, le processus générique correspond à une série d’opérations qui se succèdent dans un ordre précis (préparation, fabrication et conditionnement) avec, à chaque étape, des ressources disposées en parallèle

Dans ce type de système, les ateliers sont organisés et dimensionnés de manière à assurer un flux régulier. La matière première est introduite au début de la chaîne et passe d’une opération à l’autre avec un minimum de stockage intermédiaire.

En outre, les ateliers doivent être dimensionnés pour faire face aux pics saisonniers sans engendre de retard et, dans de nombreux cas, doivent être suffisamment flexibles pour gérer différents types de matières premières et/ou de produits finis. Dans cette perspective, le FFS s’adapte parfaitement aux variations des volumes de production, grâce à sa conception qui permet d’augmenter ou de diminuer la capacité du système de production par l’ouverture ou la fermeture de ressources parallèles à certaines étapes du processus. 

L’organisation en FFS est particulièrement adaptée à une production de masse de produits standardisés ou modérément diversifié. Sans remettre en question la séquence des étapes de production, la diversité s’obtient le plus souvent en faisant varier les recettes et/ou les formats. Des opérations de nettoyage et de changement de format doivent de ce fait être gérées conjointement avec les opérations de production.

Résolution du problème d’ordonnancement FFS

Résoudre un problème d’ordonnancement revient à décrire, dans le respect des contraintes, ce qu’il convient de produire (quoi), en utilisant quelle ressource (où) et à quel moment (quand) dans le but de satisfaire un objectif prédéfini. Compte tenu de sa complexité et de son importance dans les applications réelles, le problème FFS a fait l’objet d’études intensives et de nombreuses techniques de résolution ont été mises au point pour traiter ce type de configuration.

Les approches de résolution exactes fournissent les meilleurs résultats, mais ne sont applicables qu’à des problèmes de taille relativement modeste. Les heuristiques ne sont pas toujours efficaces car elles procèdent le plus souvent par construction itérative d’une solution (c-à-d en affectant une à une les tâches à des ressources selon des règles simples définies a priori) sans remettre en question les choix initiaux. Les nouvelles approches basées sur l’intelligence artificielle trouvent de bonnes solutions qui échappant au piège de l’optimum local, mais elles sont difficiles à construire et la plupart des algorithmes sont spécifiques à une variante particulière du problème FFS

Les récentes innovations introduites par le nouveau paradigme de l’Industrie 4.0 favorisent le développement de deux pratiques intéressantes [1] qui peuvent s’avérer utiles pour traiter autrement les problématiques d’ordonnancement complexes :

• L'exploitation en temps réel de l'information

• La décentralisation du processus de décision  

La possibilité de trouver des solutions efficaces et réalisables dépend de plus en plus de la capacité à capturer et à utiliser la grande quantité de données générées par le système de production. La conception de l’ensemble du système d’acquisition et de traitement des données est essentielle pour tenir compte des perturbations fréquentes qui se manifestent à un niveau opérationnel. L’objectif est de pouvoir réagir rapidement à des événements inattendus susceptibles de compromettre, voire d’invalider, la solution trouvée.

Perspectives

Les méthodes de résolution issues de la recherche théorique se sont avérées utiles dans le développement d’un cadre algorithmique applicable à un grand nombre de systèmes d’ordonnancement issus du monde réel. L’aspect le plus critique reste néanmoins la fréquence à laquelle des événements inattendus entraînent des modifications de l’ordonnancement au cours d’exécution. Cela relativise de plus en plus l’intérêt de consacrer un temps de calcul long à la recherche d’une solution optimale qui peut être compromise au bout de quelques minutes

Il est donc important de développer des modèles et des méthodes qui fournissent non seulement des solutions efficaces, mais aussi des ordonnancements robustes capables de résister aux événements imprévus (c-à-d un ordonnancement qui demeure valide malgré les aléas opérationnels). Une piste intéressante consiste à combiner des techniques d’ordonnancement prédictives (hors ligne) et dynamiques (en ligne)

• En l’absence de méthodes de résolution totalement satisfaisantes, des efforts importants devraient être déployés pour exploiter les possibilités offertes par les nouvelles technologies de l’Industrie 4.0, telles que les systèmes cyber-physiques

La capacité à contrôler, calculer et communiquer de grandes quantités de données issus des systèmes de production est le défi que les systèmes cyber-physiques tentent de relever. Grâce à une combinaison de calcul numérique et de contrôle physique, les systèmes cyber-physiques sont conçus pour soutenir des applications en temps réel et promouvoir la décentralisation du processus de prise de décision, permettant une réactivité basée sur les informations disponibles localement

• Développer des solutions ergonomiques d’aide à la planification avec des capacités de simulation et de travail collaboratif

Développer des outils d’aide à la décision pour simplifier l’environnement de travail des ordonnanceurs est primordial. Les fonctionnalités de simulation et de travail collaboratif sont essentielles pour travailler sur plusieurs scénarios, évaluer rapidement l’impact d’une décision avant de la mettre en œuvre et trouver des solutions consensuelles

Pour résumer, un ordonnancement efficace des systèmes de production en général et des configuration FFS en particulier repose davantage sur la réactivité et l’anticipation que sur la résolution exacte du problème mathématique sous-jacent. Le développement des systèmes cyber-physiques combiné à l’émergence de nouvelles solutions logicielles d’ordonnancement contribue à renforcer la capacité d'anticipation et de réactivité des ordonnanceurs et à converger vers des compromis validité/performance efficaces.

BIBLIOGRAPHY

[1] M. L. Pinedo, Scheduling. Cham: Springer International Publishing, 2016. [2] H. Wang, ‘Flexible flow shop scheduling: optimum, heuristics and artificial intelligence solutions’, Expert Syst., vol. 22, no. 2, pp. 78–85, May 2005.

[3] R. Ruiz and J. A. Vázquez-Rodríguez, ‘The hybrid flow shop scheduling problem’,Eur. J. Oper. Res., vol. 205, no. 1, pp. 1–18, Aug. 2010.

[4] D. A. Rossit, F. Tohmé, and M. Frutos, ‘Production planning and scheduling in Cyber-Physical Production Systems: a review’, Int. J. Comput. Integr. Manuf., vol. 32, no. 4–5, pp. 385–395, May 2019.