EvoDR: تطوير قواعد الإرسال عبر نموذج لغوي كبير لجدولة تدفق التجميع الديناميكي المرن EvoDR: Evolving Dispatching Rules via Large Language Model for Dynamic Flexible Assembly Flow Shop Scheduling

شارك:
المجلة: IEEE Transactions on Evolutionary Computation
DOI: https://doi.org/10.1109/tevc.2026.3751778
تاريخ النشر: 2026-01-01
المؤلف: Junhao Qiu وآخرون
الموضوع الرئيسي: خوارزميات الجدولة والتحسين

نظرة عامة

تقدم ورقة البحث إطارًا جديدًا، يُطلق عليه EvoDR، لتصميم قواعد التوزيع ذات الأولوية (PDRs) تلقائيًا في جدولة ورش التجميع المرنة الديناميكية (FAFSP) مع تسليم متعدد المنتجات وقيود التجميع المزدوج. يدمج EvoDR قدرات نماذج اللغة الكبيرة (LLMs) لتعزيز توليد وتحليل قواعد الجدولة، معالجًا قيود طرق البرمجة الجينية التقليدية، التي غالبًا ما تعاني من مجموعات نهائية ثابتة ونقص في القابلية للتفسير. يستخدم الإطار آلية تطور مزدوجة الخبراء، حيث يقوم أحد نماذج اللغة الكبيرة بتوليد الشيفرة بينما يقوم الآخر بإجراء تحليل الجدولة، مما يسمح بالتطور المستمر للقواعد التكيفية التي تستجيب لميزات الجدولة الديناميكية. تشير النتائج التجريبية إلى أن EvoDR يقلل بشكل كبير من متوسط التأخير مقارنةً بكل من الأساليب المتطورة وطرق التصميم من قبل الخبراء عبر سيناريوهات متنوعة، مما يظهر قدرة قوية على التكيف تحت ظروف تشغيل متنوعة.

في الختام، تؤكد الدراسة فعالية EvoDR من خلال تجارب واسعة، بما في ذلك تحليل حساسية المعلمات ودراسات الإزالة، حيث تظهر تقليلاً في متوسط التأخير بنسبة 3.67-12.95% مقارنةً بالطرق الحالية وبنسبة 16.81% مقابل خط الأساس لأقرب موعد استحقاق (EDD). يتم إثبات متانة الإطار بشكل أكبر من خلال أدائه المتفوق عبر 480 حالة مع تكوينات موارد ومستويات اضطراب متنوعة. ستسعى الأبحاث المستقبلية إلى تقليل الاعتماد على المطالبات اليدوية وتوسيع قدرات EvoDR لمعالجة قيود واضطرابات أكثر تعقيدًا. بالإضافة إلى ذلك، تسلط الورقة الضوء على إمكانية تطبيق EvoDR خارج مجال التصنيع، مما يقترح قابليته للتكيف مع مجالات أخرى من خلال إعادة تعريف ميزات الحالة ومساحات العمل، وتؤكد على أهمية استكشاف التعاون بين الإنسان والذكاء الاصطناعي في أنظمة الجدولة الذكية.

مقدمة

تتناول مقدمة ورقة البحث هذه التحديات التي تطرحها أنماط الطلب المتقلبة ومتطلبات التجميع المعقدة في أنظمة التصنيع الحديثة، تحديدًا من خلال عدسة مشكلة جدولة ورشة التجميع المرنة (FAFSP). تعتبر هذه المشكلة حاسمة في صناعات متنوعة، بما في ذلك الأجهزة المنزلية والطيران، حيث إنها تُنمذج العلاقات المعقدة بين معالجة الأجزاء وتجميع المنتجات. تفشل طرق الجدولة الثابتة التقليدية، على الرغم من فعاليتها في الظروف المستقرة، في البيئات الديناميكية حيث تتطلب عدم اليقين في الوقت الحقيقي، مثل وصول الطلبات المتقلبة، إعادة جدولة فورية وتعديلات في الأولويات.

لمعالجة هذه التحديات، تسلط الورقة الضوء على قيود الأساليب الحالية للجدولة الديناميكية، والتي تُصنف إلى طرق استباقية وتفاعلية. تهدف الجدولة الاستباقية إلى تحقيق المتانة ولكن قد تؤثر على الأداء، بينما تقدم الجدولة التفاعلية مرونة من خلال اتخاذ قرارات في الوقت الحقيقي باستخدام قواعد التوزيع ذات الأولوية (PDRs). يقترح المؤلفون إطارًا مبتكرًا، EvoDR، الذي يستفيد من نماذج اللغة الكبيرة (LLMs) لتصميم هيروسي تلقائي. يدمج هذا الإطار آلية مزدوجة الخبراء لتوليد وتحليل قواعد التوزيع، مما يعزز التكيف مع ظروف التصنيع الديناميكية. توضح الورقة صياغة عملية قرار ماركوف القائمة على الرسم البياني غير المتجانس لمشكلة FAFSP المقيدة بالتجميع المزدوج وتقدم نتائج تجريبية تُظهر أن EvoDR يتفوق بشكل كبير على الأساليب الحالية، بما في ذلك PDRs المصممة يدويًا، عبر سيناريوهات متنوعة.

الطرق

توضح القسم المعنون “الطرق” الإجراءات التجريبية والتقنيات التحليلية المستخدمة في الدراسة. يتناول تفاصيل المنهجيات المحددة المستخدمة لجمع البيانات، بما في ذلك تصميم التجارب، واختيار المواد، والبروتوكولات المتبعة لضمان قابلية التكرار وموثوقية النتائج. يؤكد القسم على أهمية التحكم في المتغيرات والأساليب الإحصائية المطبقة لتحليل البيانات.

علاوة على ذلك، يسلط قسم الطرق الضوء على الأدوات والتقنيات المستخدمة في التجارب، مثل الأدوات المحددة للقياس والبرامج لمعالجة البيانات. يتم مناقشة الأسباب وراء المنهجيات المختارة، مما يوفر نظرة ثاقبة حول كيفية توافقها مع أهداف البحث وتساهم في صحة النتائج. بشكل عام، يعمل هذا القسم كأساس لفهم الإطار التجريبي الذي يدعم النتائج والتحليل اللاحقين المقدمين في الورقة.

المناقشة

تتناول قسم المناقشة في ورقة البحث تعقيدات مشكلة ورشة التجميع المرنة متعددة المنتجات الديناميكية (FAFSP) تحت متطلبات التسليم في الوقت الحقيقي. تختلف هذه المشكلة عن FAFSP التقليدية من خلال ضرورة مزامنة منتجات غير متجانسة متعددة ضمن طلب واحد، مما يقدم قيود تجميع مزدوجة هرمية. التحدي الرئيسي يكمن في تحقيق اكتمال التجميع، حيث يتم تحديد تأخير الطلب من خلال إكمال أحدث مكون له. يهدف النموذج الرياضي إلى تقليل إجمالي تأخير الطلب، مع دمج قيود متنوعة تتعلق بأهلية الآلات، وتسلسل الوظائف، وأوقات المعالجة. يتم تقييم فعالية النموذج من خلال إطار عملية قرار ماركوف (MDP)، الذي يلتقط ميزات الحالة الديناميكية ويسمح باتخاذ قرارات في الوقت الحقيقي بناءً على توفر الوظائف والآلات.

يعزز إطار EvoDR المقترح عملية الجدولة من خلال دمج استراتيجيات تطورية لقواعد التوزيع (PDRs) التي تتكيف مع الطبيعة الديناميكية للبيئة. يستخدم آلية مزدوجة الخبراء، مستفيدًا من نموذجين مختلفين من نماذج اللغة الكبيرة (LLMs) لتوليد وتقييم PDRs. يركز الإطار على التطور المشترك للمعرفة التصميمية وقواعد الجدولة، مما يضمن أن القواعد المولدة لا تؤدي بشكل جيد فحسب، بل تتكيف أيضًا مع ظروف التشغيل المتغيرة. تُظهر النتائج التجريبية تفوق نهج EvoDR على الطرق التقليدية، مما يبرز قدرته على تقليل التأخير بشكل فعال مع الحفاظ على الاستجابة في الوقت الحقيقي. تؤكد دراسات الإزالة أيضًا على مساهمات كل مكون داخل إطار EvoDR، مؤكدة على أهمية بدء المعرفة النخبوية، ودمج الميزات الديناميكية، والأدوار التكميلية للمشغلين التطوريين في تعزيز أداء الجدولة.

Journal: IEEE Transactions on Evolutionary Computation
DOI: https://doi.org/10.1109/tevc.2026.3751778
Publication Date: 2026-01-01
Author(s): Junhao Qiu et al.
Primary Topic: Scheduling and Optimization Algorithms

Overview

The research paper presents a novel framework, termed EvoDR, for the automatic design of priority dispatching rules (PDRs) in dynamic flexible assembly flow shop scheduling (FAFSP) with multi-product delivery and dual kitting constraints. EvoDR integrates the capabilities of large language models (LLMs) to enhance the generation and analysis of scheduling rules, addressing the limitations of traditional genetic programming methods, which often suffer from fixed terminal sets and lack interpretability. The framework employs a dual-expert co-evolution mechanism, where one LLM generates code while another conducts scheduling analysis, allowing for continuous evolution of adaptive rules that respond to dynamic scheduling features. Experimental results indicate that EvoDR significantly reduces average tardiness compared to both state-of-the-art approaches and expert-designed methods across various scenarios, demonstrating robust adaptability under diverse operating conditions.

In conclusion, the study validates the effectiveness of EvoDR through extensive experiments, including parameter sensitivity analysis and ablation studies, showing a reduction in average tardiness by 3.67-12.95% compared to existing methods and by 16.81% against the earliest due date (EDD) baseline. The framework’s robustness is further evidenced by its superior performance across 480 instances with varying resource configurations and disturbance levels. Future research will aim to minimize the reliance on manual prompts and extend EvoDR’s capabilities to address more complex constraints and disturbances. Additionally, the paper highlights the potential for EvoDR’s application beyond manufacturing, suggesting its adaptability to other domains by redefining state features and action spaces, and emphasizes the importance of exploring human-AI collaboration in intelligent scheduling systems.

Introduction

The introduction of this research paper addresses the challenges posed by volatile order patterns and complex kitting demands in modern manufacturing systems, specifically through the lens of the flexible assembly flow shop scheduling problem (FAFSP). This problem is critical in various industries, including home appliances and aerospace, as it models the intricate supply relationships between part processing and product assembly. Traditional static scheduling methods, while effective under stable conditions, fall short in dynamic environments where real-time uncertainties, such as fluctuating order arrivals, necessitate immediate rescheduling and prioritization adjustments.

To tackle these challenges, the paper highlights the limitations of existing dynamic scheduling approaches, which are categorized into proactive and reactive methods. Proactive scheduling aims for robustness but may compromise performance, while reactive scheduling offers flexibility through real-time decision-making using priority dispatching rules (PDRs). The authors propose an innovative framework, EvoDR, which leverages large language models (LLMs) for automated heuristic design. This framework integrates a dual-expert mechanism for generating and analyzing dispatching rules, enhancing adaptability to dynamic manufacturing conditions. The paper outlines the formulation of a heterogeneous graph-based Markov decision process for the dual kitting constrained FAFSP and presents experimental results demonstrating that EvoDR significantly outperforms existing methods, including manually designed PDRs, across various scenarios.

Methods

The section titled “Methods” outlines the experimental procedures and analytical techniques employed in the study. It details the specific methodologies used to gather data, including the design of experiments, selection of materials, and the protocols followed to ensure reproducibility and reliability of results. The section emphasizes the importance of controlling variables and the statistical methods applied for data analysis.

Furthermore, the methods section highlights the tools and technologies utilized in the experiments, such as specific instruments for measurement and software for data processing. The rationale behind the chosen methodologies is discussed, providing insight into how they align with the research objectives and contribute to the validity of the findings. Overall, this section serves as a foundation for understanding the experimental framework that supports the subsequent results and analysis presented in the paper.

Discussion

The discussion section of the research paper addresses the complexities of the dynamic multi-product Flexible Assembly Flow Shop Problem (FAFSP) under real-time delivery requirements. This problem diverges from traditional FAFSP by necessitating the synchronization of multiple heterogeneous products within a single order, which introduces hierarchical dual kitting constraints. The primary challenge lies in achieving kit-completeness, where the tardiness of an order is dictated by the completion of its latest component. The mathematical model aims to minimize total order tardiness, incorporating various constraints related to machine eligibility, job sequencing, and processing times. The model’s effectiveness is evaluated through a Markov Decision Process (MDP) framework, which captures the dynamic state features and allows for real-time decision-making based on job and machine availability.

The proposed EvoDR framework enhances the scheduling process by integrating evolutionary strategies for dispatching rules (PDRs) that adapt to the dynamic nature of the environment. It employs a dual-expert mechanism, utilizing two distinct large language models (LLMs) for generating and evaluating PDRs. The framework emphasizes the co-evolution of design knowledge and scheduling rules, ensuring that the generated rules not only perform well but also adapt to varying operational conditions. Experimental results demonstrate the superiority of the EvoDR approach over traditional methods, highlighting its ability to minimize tardiness effectively while maintaining real-time responsiveness. The ablation studies further validate the contributions of each component within the EvoDR framework, confirming the importance of elite knowledge initialization, dynamic feature integration, and the complementary roles of evolutionary operators in enhancing scheduling performance.