Contribution à l’ordonnancement dynamique : proposition d’une approche guidée par effet de Simulation/Datamining

Abstract

Dans un environnement ouvert et mondialisé où la satisfaction des attentes des clients est à la base d’une concurrence extrême, l’amélioration de la compétitivité des entreprises devient une question de survie. Cette compétitivité implique la nécessité d’améliorer continuellement la productivité et de réduire encore et toujours les coûts de production. Parmi les réponses les plus immédiates on trouve l’ordonnancement dans les ateliers de fabrication. L’ordonnancement, étape de planification et d’organisation du fonctionnement des ateliers de production, optimise l’affection des ressources humaines et matérielles aux tâches et opérations de production. Il améliore l’utilisation des ressources et réduit de ce fait les temps de production et diminue les coûts de production. Pour les besoins de cette optimisation, il est possible de faire appel à une panoplie de méthodes et techniques présentées dans la littérature, chacune ayant ses points forts et ses points faibles et pouvant s’adapter à tel ou tel problème d’ordonnancement en fonction de ses particularités. Parmi les techniques qui ont fait leurs preuves pour la résolution de problèmes d’ordonnancement on peut citer les règles de priorité. Les règles de priorité sont capables d’affecter des priorités aux tâches en temps-réel, permettant ainsi de résoudre des problèmes d’ordonnancement fortement complexes mais aussi de renforcer la réactivité du système en cas de perturbation. Cependant, elles présentent certaines faiblesses liées au fait qu’aucune règle de priorité n’est à priori meilleure que les autres dans des environnements de production différents, poussant ainsi les opérateurs humains à recourir à la simulation, à leur expérience, ou aux données issues de productions antérieures. En pratique, les systèmes de production génèrent de gros volumes de données, qui ne sont souvent pas exploitées en dépit de leur fort potentiel et l’hypothèse est de mettre à profit ces données et d’y découvrir des connaissances implicites afin d’améliorer les pratiques d’ordonnancement actuelles. La solution serait de recourir à la fouille des données pour l’extraction de cette connaissance. Dans cette thèse nous proposons une nouvelle approche combinant simulation et fouille de données pour automatiser la sélection et l’identification des règles de priorité, et leur affectation, en temps-réel, aux machines d’un atelier Job Shop en vue d’en optimiser l’ordonnancement. Cette méthodologie repose sur l’hypothèse selon laquelle l’allocation de règles de priorité différentes pour chacune des machines de l’atelier permet de trouver de meilleures solutions. Mise à part l’automatisation de la sélection des règles de priorité, la fouille de données peut aussi être utilisée pour l’extraction de nouvelles règles en s’inspirant d’autres méthodes de résolution plus efficaces. Dans cette perspective nous proposons l'utilisation de la fouille de données pour la génération de nouvelles règles de priorité à partir de solutions obtenues par un algorithme génétique. Nous nous focalisons aussi sur l’utilisation de ces nouvelles règles dans les problèmes d’ordonnancement Single Machine. Dans chacune des approches proposées dans cette thèse, des expérimentations intensives ont été menées afin de montrer l’efficacité et l’intérêt à intégrer la fouille de données pour l’amélioration et l’optimisation des problèmes d’ordonnancement, leur résolution en temps-réel, ainsi que son utilisation comme outil d’aide à la décision dans la sélection des règles de priorité. ************************************************************************************************** في البيئة المفتوحة والعالمية الحالية أين إرضاء الزبائن هو أساس لتنافس شرس، أصبح تحسين قدرات الشركات التنافسية مسألة ضمان للبقاء في هذه البيئة. وترجع هذه القدرة التنافسية إلى ضرورة مواصلة تحسين القدرة الإنتاجية و كذلك تخفيض تكاليفها. من بين الحلول الممكنة في هذا المجال الجدولة في ورشات التصنيع. إن الجدولة، وهي مرحلة تخطيط وتنظيم في ورشات التصنيع، تحسن عملية تخصيص الموارد البشرية والمادية للاشغال و العمليات. مما يؤدي إلى تثمين استخدام الموارد، وبالتالي تقليل أوقات الإنتاج و تكاليفها. لحل هذه المشاكل، نجد مجموعة واسعة من الأساليب والتقنيات المقترحة من قبل الباحثين في هذا المجال، ولكل منها نقاط قوة وضعف خاصة بها، حيث من الممكن تكييفها لجدولة الأعمال لحالات معينة وفقا للخصائص التي تميزها عن غيرها. ومن بين التقنيات التي أثبتت جدارتها في حل مشاكل الجدولة نجد قواعد الأولوية. إن قواعد الأولوية قادرة على تحديد الأولويات للإشغال في الوقت الأني، مما يسمح لحل مشاكل جدولة صعبة وتعزيز استجابية النظام في حالة حدوث اضطرابات. ومع ذلك، هذه التقنيات لديها بعض نقاط الضعف التي ترجع إلى عدم وجود أي قاعدة أولوية أفضل من غيرها في بيئات إنتاج مختلفة، مما يدفع المسؤولين للجوء إلى تقنية المحاكاة، أو إلى خبراتهم المكتسبة، أو إلى البيانات المجمعة من عمليات الإنتاج السابقة. ومن الناحية العملية، تولد نظم الإنتاج كميات كبيرة من البيانات، التي غالبا لا تستغل رغم فائدتها المحتملة والفرص التي تتيحها لاكتشاف معارف مفيدة من هذه البيانات لغرض أجل تحسين عمليات الجدولة الحالية. الحل سيكون باستخدام تقنيات استخراج البيانات للتحصل على هذه المعرفة. في هذه الأطروحة، نقترح منهجية جديدة تجمع بين المحاكاة و تقنيات إستخراج البيانات بهدف التشغيل الآلي لعمليات الاختيار، التحديد، و التخصيص في الوقت الأني لقواعد الأولوية لكل الآلات ضمن ورشة العمل متعددة التوجيهات. تستند هذه المنهجية على افتراض أن تخصيص قاعدة أولوية مختلفة لكل آلة في ورشة العمل يسمح بإيجاد حلول جيدة. وبصرف النظر عن الإختيار الآلي لقواعد الأولوية، من الممكن أيضا إستعمال تقنيات إستخراج البيانات للحصول على قواعد جديدة من خلال تقليد أساليب حل أخرى أكثر كفاءة. وبالتالي نقترح استخدام تقنيات إستخراج البيانات لتشكيل قواعد أولوية جديدة من خلال الحلول المتحصل عليها اعتمادا على خوارزمية وراثية. و نركز كذلك على كيفية إستخدام هذه القواعد الجديدة من أجل حل مشاكل جدولة ذات آلة واحدة. في كل المناهج المقترحة في هاته الأطروحة، أجريت عدة تجارب واسعة النطاق لإثبات فعالية وفائدة هاته المناهج، وللتأكيد على ضرورة دمج تقنيات استخراج البيانات لتحسين حلول مشاكل جدولة الأعمال، حلها في الوقت الأني، وكذلك كأداة لدعم القرارات عند إختيار قواعد الأولوية. ******************************************************************************************** In an open and globalized environment where customer satisfaction is at the root of extreme competition, the competitiveness of companies becomes a matter of survival. This competitiveness implies the need to continuously improve productivity and to reduce production costs. Among the most immediate answers is scheduling in manufacturing workshops. Scheduling, a stage in planning and organizing the operation of workshops, optimizes the allocation of human and material resources to jobs and operations, improving the use of resources and thereby reducing production times as well as costs. To solve this optimization problem, a wide variety of well-established methods and techniques presented in literature is available, each with its own strengths and weaknesses, all of which can be adapted to a specific scheduling problem and its peculiarities. Examples of proven techniques for solving scheduling problems include dispatching rules; Dispatching rules are capable of assigning priorities to jobs in real time, thus allowing to solve highly complex scheduling problems and enhancing the system’s responsiveness in the event of a disruption. However, they have certain weaknesses related to the fact that no dispatching rule is a priori better than the others in different manufacturing environments, forcing human operators to resort to simulation, their experience, or data from earlier productions. In practice, manufacturing systems generate large volumes of data, which are often not exploited despite their potential usefulness and a good chance of discovering useful knowledge from this data to improve the current scheduling practices. The solution would be to use data mining to extract this knowledge. In this thesis, we propose a new methodology combining simulation and data mining for the automation of the selection, identification, and real-time allocation of dispatching rules to the machines of a Job Shop to optimize the scheduling performance measures. This methodology is based on the assumption that the allocation of a different dispatching rule for each machine in the workshop allows to reach better solutions. Aside from automating the selection of dispatching rules, data mining can also be used to extract new rules by mimicking other, more efficient solving methods. Given this we propose the use of data mining for the generation of new dispatching rules from solutions obtained by a genetic algorithm. We also focus on the use these new rules in order to solve Single Machine scheduling problems. For each approach presented below, intensive experiments were conducted to highlight their efficiency and emphasize, should data mining be integrated in the process, the improvements made in the optimization of scheduling problems, their resolution in real time, as well as a decision-making tool for the selection of dispatching rules.