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

Abstract

Résumé Dans le contexte de la globalisation et de la mondialisation, les entreprises sont mises à rude épreuve en raison des demandes et attentes des clients, de la guerre féroce entre concurrents, et de la nécessité de réduire encore et toujours les coûts de production. L’entreprise se retrouve donc dans l’obligation d’améliorer sa compétitivité et garantir sa survie dans cet environnement ultra compétitif. Parmi les pistes possibles pouvant répondre aux besoins des clients et au problème de réduction des coûts, figure l’ordonnancement. L’ordonnancement permet d’optimiser l’affectation des ressources aux tâches en tentant de réduire les temps de production, de maximiser l’utilisation des ressources, de réduire les coûts, etc. Pour se faire, il est possible de faire appel à une panoplie de méthodes et techniques présentées dans la littérature, chacune présentant des points forts et des faiblesses, et pouvant s’adapter à tel ou tel problème d’ordonnancement en fonction de ses particularités. 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. Le problème est de savoir s’il est possible de mettre à profit ces données et y découvrir des connaissances implicites afin d’améliorer les pratiques d’ordonnancement actuelles. Une des techniques qui a fait ses preuves dans l’extraction des connaissances est la fouille des données, ou data mining. Dans cette thèse nous proposons une nouvelle méthodologie combinant fouille de données et simulation pour l’automatisation de la sélection, de l’identification, et de l’allocation en temps-réel de règles de priorité aux machines d’un atelier Job Shop en vue d’optimiser l’ordonnancement. Cette méthodologie repose sur l’hypothèse selon laquelle l’allocation d’une règle de priorité différente pour chacune des machines de l’atelier permet de trouver de bonnes solutions. Dans une autre approche, nous utilisons la fouille de données pour l’extraction 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 systèmes de production pour la résolution de problèmes d’ordonnancement Single Machine. Dans chacune des approches de cette thèse, des expérimentations intensives ont été menées afin démontrer l’efficacité et l’intérêt à intégrer la fouille de données pour l’amélioration et l’optimisation des solutions des problèmes d’ordonnancement, leur résolution en temps-réel, ainsi que l’aide à la décision.**//**مُلَخَّ صٌ في السياق الحاضر للعولمة والتدويل، أضحت الشركات تحت ضغط مستمر وهذا راجع إلى مطالب وتوقعات الزبائن، المنافسة الشرسة في السوق، وكذلك الحاجة الدائمة إلى خفض تكاليف الإنتاج . في ظل هذا الوضع، تجد الشركات نفسها مضطرة لتحسين قدراتها لضمان بقائها في هذه البيئة التنافسية . من بين السبل الممكنة لتلبية احتياجات الزبائن وكذا خفض تكاليف الإنتاج، نجد تقنية جدولة الأعمال . جدولة الأعمال تحسن عملية تخصيص موارد النظام لكل شغل من خلال الحد من وقت الإنتاج، رفع مستوى الاستفادة من الموارد، وخفض التكاليف . للقيام بذلك، يمكن الإستعانة بالأساليب والتقنيات المقترحة من قبل الباحثين في هذا المجال، لكل من هذه التقنيات مواطن قوة ومواطن ضعف، حيث يمكن تكييفها لجدولة الأعمال لحالات معينة وفقا للخصائص التي تميزها عن غيرها . أنظمة الإنتاج لدى الشركات تولد كميات كبيرة من البيانات، والتي غالبا ما تكون غير مستغلة على الرغم من أهميتها و إمكاناتها . هدفنا هو معرفة ما إذا كان من الممكن استخدام هذه البيانات لإستخلاص معارف ومعلومات جديدة من اجل تحسين الجدولة الحالية للأعمال . من بين التقنيات التي اثبتت جدارتها في استخراج هذه المعرفة نجد تقنية التنقيب واستخراج البيانات . في هذه الأطروحة، نقترح منهجية جديدة تجمع بين تقنيات استخراج البيانات والمحاكاة بهدف التشغيل الآلي لعمليات الاختيار، التحديد، و التخصيص في الوقت الأني لقواعد الأولوية لكل الآلات ضمن ورشة العمل متعددة التوجيهات . تستند هذه المنهجية على افتراض أن تخصيص قاعدة أولوية مختلفة لكل آلة في ورشة العمل يسمح بإيجاد حلول جيدة . وفي نفس السياق، نقترح منهجية أخرى تعتمد على استخدام تقنيات استخراج البيانات للعثور على قواعد أولوية جديدة باستعمال حلول تم الحصول عليها بواسطة الخوارزمية الوراثية . نركز أيضا في بحثنا على كيفية استخدام هذه القواعد الجديدة في أنظمة الإنتاج الحالية من أجل حل مشاكل جدولة الأعمال لآلة واحدة . في كل المناهج المقترحة في هاته الأطروحة، أجريت عدة تجارب واسعة النطاق لإثبات فعالية وفائدة دمج تقنيات استخراج البيانات لتحسين حلول مشاكل جدولة الأعمال، حلها في الوقت الأني، وكذلك تحسين عملية إتخاذ القرار .//**//Abstract In today’s context of globalization and internationalization, companies face new challenges related to the customer demands and expectations, the fierce competition between companies, and the need to further reduce the costs of production. The company is therefore obliged to improve its competitiveness and ensure its survival in this ultra-competitive environment. Possible solutions to meet costumers’ needs and to reduce production costs include the scheduling. Scheduling optimizes the allocation of resources to jobs by reducing the production time, maximizing resource utilization, reducing costs, and so on. In order to do this, it is possible to use a variety of methods and techniques suggested in the literature, each one presenting strengths and weaknesses, and able to adapt to a specific scheduling problem according to its nature and particularities. Manufacturing systems generate large volumes of data, which are often not exploited despite their high potential. The problem is whether it is possible to use this data and discover implicit knowledge in order to improve the current scheduling practices. One of the proven techniques in knowledge extraction is data mining. In this thesis, we propose a new methodology combining data mining and simulation 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. In another approach, we use data mining to extract new dispatching rules from solutions obtained by a genetic algorithm. We also focus on using these new rules in manufacturing systems for solving Single Machine scheduling problems. In each of the approaches of this thesis, intensive experiments have been carried out to demonstrate the efficiency and the interest to integrate data mining for the improvement and optimization of the solutions of scheduling problems, their resolution in real-time, and the decision support.//