An Analysis of the Coordination Gap between Joint and Modular Learning for Job Shop Scheduling with Transportation Resources

إليك ملخص تقني مفصل لورقة البحث بعنوان: "تحليل فجوة التنسيق بين التعلم المشترك والتعلم المجزأ لجدولة ورش العمل مع موارد النقل."

1. تعريف المشكلة

تتناول الورقة مشكلة جدولة ورش العمل مع موارد النقل (JSSPT)، وهي نسخة معقدة من مشكلة جدولة ورش العمل الكلاسيكية (JSSP).

• السياق: في "المصانع اللامركزية" الحديثة، يجب تنسيق عمليات الإنتاج مع مناولة المواد باستخدام المركبات الموجهة آلياً (AGVs).
• الهدف: تقليل زمن الإنجاز الكلي ($C_{max}$)، والذي يُعرف بأنه وقت اكتمال آخر وظيفة عند آلة التفريغ.
• القيود:
  • الإنتاج: تتبع الوظائف تسلسلات مسارات ثابتة؛ وتُعالج الآلات عملية واحدة في كل مرة دون إمكانية المقاطعة.
  • النقل: تمتلك المركبات الموجهة آلياً (AGVs) سعة وحدة واحدة (وظيفة واحدة في كل مرة) ولا يمكن مقاطعتها. لا يمكن بدء العملية إلا بعد اكتمال نقلها، ولا يمكن بدء النقل إلا بعد انتهاء العملية السابقة.
  • المخازن المؤقتة: مخازن المدخلات غير محدودة (نظام الوارد أولاً يخرج أولاً FIFO)؛ ومخازن المخرات غير محدودة ولا توجد قيود على الترتيب.
• التحدي الجوهري: تواجه الطرق التقليدية (قواعد التوزيع، الخوارزميات الجينية) صعوبة في التكيف في الوقت الفعلي أو التكلفة الحسابية العالية. وبينما تقدم التعلم التعزيزي متعدد الوكلاء (MARL) حلاً، فإنه من غير الواضح متى يكون التدريب المشترك (التدريب المتزامن لوكلاء الوظائف ووكلاء الـ AGV) ضرورياً مقابل متى يكفي التدريب المجزأ (التدريب المستقل متبوعاً بالتكامل).

2. المنهجية

أ. إطار التعلم التعزيزي متعدد الوكلاء

صاغ المؤلفون المشكلة كعملية ماركوف لاتخاذ القرار (MDP) مع وكيلين متميزين:

1. وكيل جدولة الوظائف: يقرر أي عملية سيتم جدولتها تالياً.
2. وكيل جدولة الـ AGV: يقرر أي مركبة (AGV) سيتم تخصيصها للعملية المختارة.

تمثيل الحالة:

• حالة الوظيفة ($S^o_t$): ممثلة بـ رسم بياني متقطع ($G=\{V, E\}$).
  • الرؤوس: العمليات والآلات.
  • الميزات: مؤشرات ثنائية لحالة الجدولة، نوع الآلة، والحد الأدنى (LB) وهو قيمة عددية تمثل الحد الأدنى للوقت المتبقي للوظيفة. تتضمن رؤوس الآلات نسبة العمليات المجدولة.
  • البنية: يتم ترميزها باستخدام شبكة تماثل الرسم البياني (GIN) لالتقاط طوبولوجيا الرسم البياني وتمرير الرسائل.
• حالة الـ AGV ($S^{agv}_t$): متجه من ست قيم عددية لكل مركبة، تشمل أبكر وقت للاستلام، أوقات السفر، وتوافر الآلة.
  • البنية: يتم ترميزها باستخدام مدرك متعدد الطبقات (MLP).

فضاء الإجراءات:

• الإجراء المشترك: زوج $(a_o, a_{agv})$ حيث $a_o$ هي العملية المختارة و $a_{agv}$ هي الـ AGV المخصص.
• السياسة: سياسة الـ AGV مشروطة بإجراء سياسة الوظيفة ($\pi(a_{agv}|S^{agv}_t, a_o)$).

دالة المكافأة:

• مكافأة متفرقة تعتمد على سالب زمن الإنجاز الكلي ($-C_{max}$) مع تطبيعها بواسطة حد أدنى. هذا يجبر الوكلاء على تحسين الهدف العالمي بدلاً من الكفاءة المحلية.

ب. أنماط التدريب

تقارن الدراسة بين استراتيجيتين للتدريب:

1. التدريب المشترك: يتم تدريب كلا الوكيلين كمعلمات قابلة للتعلم في آن واحد باستخدام MAPPO (تحسين السياسة التقريبية متعدد الوكلاء). يتعلمان السلوكيات التعاونية بشكل متكامل (end-to-end).
2. التدريب المجزأ: يتم تدريب الوكلاء بشكل مستقل. يكون أحد الوكلاء سياسة قابلة للتعلم (GNN أو MLP)، بينما يكون الآخر قاعدة توزيع (DR) ثابتة (مثل: أقصر وقت معالجة، أو أول من يأتي أول من يخدم). يتم تحديد أفضل التوليفات المجزأة لاحقاً.

ج. التصميم التجريبي

• المقارنات المرجعية: 10 قواعد اختيار عمليات $\times$ 4 قواعد اختيار AGV = 40 توليفة من قواعد التوزيع.
• تحليل الحساسية: قدم المؤلفون مقياسين رئيسيين لتحليل "فجوة التنسيق" (الفرق في الأداء بين المشترك والمجزأ):
  • ندرة الموارد ($\rho$): نسبة الـ AGVs إلى الوظائف ($k/n$).
  • الهيمنة الزمنية ($\tau^*$): مؤشر معياري يمثل التوازن بين وقت المعالجة ووقت النقل.
• التقييم: يتم قياس الأداء باستخدام الزيادة المئوية النسبية (RPI) مقابل أفضل قاعدة توزيع مرجعية، ومعدل الفوز (WR).

3. المساهمات الرئيسية

1. إطار تدريب مبتكر: بنية مرنة تسمح بتعلم الوكلاء بشكل مستقل مع الحفاظ على التوافق للتقييم المشترك، مما يتيح مقارنة مباشرة لأنماط التدريب.
2. تحليل حساسية منهجي: أول كمّ دقيق لـ "فجوة التنسيق" في JSSPT، وتحديد الظروف البيئية المحددة التي يكون فيها التدريب المشترك ضرورياً.
3. توصيف الاعتماد المتبادل: توصيف رياضي لكيفية تأثير ندرة الموارد والهيمنة الزمنية بشكل غير خطي على فعالية التعلم المشترك مقابل المجزأ.
4. إرشادات عملية: أدلة تجريبية توجه صناع القرار حول متى ينبغي الاستثمار في التدريب المشترك المعقد مقابل النهج المجزأ الأبسط.

4. النتائج

أ. الأداء العام

• تفوق النظام المشترك: يتفوق الحل المشترك ($J_0 A_0$) باستمرار على جميع الحلول المجزأة وقواعد التوزيع المرجعية.
• متوسط الربح: يحقق الحل المشترك متوسط تحسن قدره 4.2% في زمن الإنجاز الكلي مقارنة بأفضل توليفة لقواعد التوزيع.
• تباين الحلول المجزأة: تظهر الحلول المجزأة تبايناً عالياً؛ حيث يعتمد نجاحها بشدة على نوع التوليفة من القواعد الاستدلالية المستخدمة أثناء التدريب المستقل.

ب. فجوة التنسيق والعوامل البيئية

تحدد الدراسة علاقة غير خطية بين الظروف البيئية وفائدة التدريب المشترك:

• البيئات المتوازنة (فجوة تنسيق عالية): في الأنظمة التي لا تكون فيها الموارد نادرة ولا وفيرة، وتكون أوقات المعالجة والنقل متوازنة، يحقق التدريب المشترك أعلى المكاسب (تصل إلى 8.5%) RPI. هنا، يعتمد النظام على الترابط بين جدولة الوظائف وتخصيص الـ AGV.
• بيئات الاختناق (فجوة تنسيق منخفضة):
  • مقيدة بالنقل: ندرة شديدة في الـ AGVs ($\rho < 0.4$).
  • مقيدة بالعمليات: هيمنة أوقات المعالجة مع وفرة في الـ AGVs ($\rho > 0.8$).
  • النتيجة: في هذه الأنظمة، تتقلص فجوة الأداء بشكل كبير (لتصل إلى 0.6% - 1.5%). عندما يهيمن عائق واحد على النظام، فإن الفائدة الهامشية للتنسيق الشامل تتضاءل لأن النظام يظل مقيداً بذلك العامل الواحد بغض النظر عن تعاون الوكلاء.

ج. التحقق الإحصائي

• تحليل الانحدار: يؤكد نموذج المربعات الصغرى العادية (OLS) أن هيمنة الاختناق (قيد المهمة الواحدة) وتوازن المهام يتنبآن بشكل كبير بفجوة التنسيق ($R^2 = 0.67$).
• رؤية رئيسية: تشير المعاملات السالبة لمتغيرات الاختناق إلى أنه مع هيمنة مهمة واحدة، تنخفض ميزة التدريب المشترك. وتشير المعاملات الموجبة لمقياس التوازن إلى أن الأنظمة المتوازنة تستفيد أكثر من التعلم المشترك.

5. الأهمية والآثار المترتبة

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

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