Does Size Generalization Imply Disruption Robustness? A Pre-Registered Study of GNN–PPO Scheduling Policies for the Dynamic Flexible Job-Shop Problem

ملخص تقني: هل تعني القدرة على التعميم عبر الأحجام متانة مواجهة الاضطرابات؟

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

المنهجية
استخدم الباحثون بروتوكولاً مسجلاً مسبقاً ومنضبطاً إحصائياً لتقييم مشفر شبكة التماثل الرسومي (GIN) العلاقاتي المقترن بوكيل تحسين السياسة القريبة (PPO).

• البنية: تستخدم السياسة مشفراً علاقياً من نوع (GIN) يميز بين ثلاثة أنواع من الحواف (أسبقية الوظيفة الداخلية، التنافس على الآلة، وأهلية العملية للآلة) عبر تحويلات خطية منفصلة قبل التجميع. تقع هذه البنية بين التمثيل الرسومي المتجانس تماماً وغير المتجانس تماماً. وتنتج رأس الممثل (actor head) قيم اللوجيت (logits) للعمليات المرشحة بغض النظر عن حجم النموذج، مما يضمن استقلال عدد المعلمات عن عدد العمليات.
• التدريب والمكافأة: تم تدريب الوكيل باستخدام (MaskablePPO). ولاختبار المتانة، قيمت الدراسة هيكلين للمكافأة: مكافأة أساسية قائمة على الإمكانات تقلل من زمن الإنجاز (makespan)، ونسخة موسعة تتضمن "عقوبة عدم الاستقرار" ($\kappa \cdot \Delta_{inst}$) لمعاقبة الانحرافات عن أوقات البدء المخطط لها بعد الاضطرابات.
• التصميم التجريبي: سجلت الدراسة مسبقاً خمس فرضيات (H1–H5) مع قواعد قرار مجمدة لتجنب التحييد بعد معرفة النتائج (HARKing).
  • النماذج المرجعية (Baselines): تمت مقارنة السياسة بتسع قواعد لتحديد الأولويات (PDRs)، وخوارزمية جينية (GA) مضبوطة، ومحلل برمجة قيود (CP-SAT) دقيق.
  • المعايير (Benchmarks): شمل التقييم 43 نموذجاً من عائلتي (Fisher–Thompson) و(Lawrence) لـ (JSSP)، وسبعة نماذج من عائلة (Brandimarte) لـ (FJSP)، بالإضافة إلى نماذج اصطناعية ممتدة.
  • البروتوكول الإحصائي: استخدمت المقارنات اختبارات "ويلكوكسون" للرتب الموقعة للتحليل الزوجي، واختبارات "فريدمان-نيميني" مع مخططات الفرق الحرجة لترتيب الطرق المتعددة. كما تم الإبلاغ عن أحجام التأثير طوال الدراسة.

النتائج الرئيسية
رُفضت أربع من أصل خمس فرضيات مسجلة مسبقاً، بينما قُبلت واحدة فقط. وتلخص النتائج أدناه:

1. التنافسية الساكنة (H1 - مرفوضة): لم تتفوق سياسة (GNN-PPO) على أفضل قاعدة تحديد أولويات في النماذج الساكنة. بلغ متوسط نسبة الانحراف المئوية النسبية (RPD) للسياسة 24.82%، مقارنة بـ 18.96% لأفضل قاعدة (FIFO). وقد خسرت السياسة في جميع نماذج (FJSP) وفازت فقط في 18.6% من نماذج (JSSP).
2. التعميم عبر الأحجام (H2 - مقبولة): نجحت السياسة في التعميم على أحجام نماذج أكبر بمقدار 1.5 إلى 3.0 أضعاف حجم مجموعة التدريب. ورغم أن قيمة (RPD) المطلقة ظلت غير تنافسية مقارنة بأفضل قاعدة (PDR)، إلا أن ترتيبها بين عشر طرق لم يكن أسوأ بشكل ملحوظ من ترتيب أفضل قاعدة (PDR) في أي فئة حجم. يشير هذا إلى انتقال التنافسية النسبية بدلاً من جودة الحل المطلقة.
3. المتانة تجاه الاضطرابات المتعددة (H3 - مرفوضة): فشلت السياسة في أن تكون متينة تحت تسعة أنظمة اضطراب متميزة (مزيج من الأعطال، والأوقات العشوائية، والوصول الديناميكي). وفي جميع الأنظمة، كان مؤشر المتانة (RI) للسياسة أسوأ بكرياً من أفضل قواعد (PDRs). وكان محور "الوصول الديناميكي" ضاراً بشكل خاص، حيث مثل تحولاً في التوزيع (إدراج وظائف في منتصف الحلقة) لم يسبق رؤيته أثناء التدريب.
4. المكافأة المدركة للاضطراب (H4 - مرفوضة): لم يؤدِ تعزيز المكافأة بعقوبة عدم الاستقرار ($\kappa > 0$) إلى تحسين المتانة. بدلاً من ذلك، تسبب ذلك في انهيار الأداء الاسمي (غير المضطرب)، مما أدى لزيادة (RPD) بمقدار 46.6 إلى 106.0 نقطة مئوية. تشخص الدراسة هذا الفشل بأنه نتيجة للتدريب حصرياً على حلقات الاضطراب ذات العشوائية النطاقية دون تعريض الوكيل أبداً للحلقات غير المضطربة (الاسمية).
5. زمن استجابة القرار (H5 - مرفوضة بموجب عتبة صارمة): بينما كان زمن استجابة القرار للسياسة (4-11 مللي ثانية) أسرع بعدة مراتب من (CP-SAT) في النماذج الكبيرة والصعبة، إلا أنها فشلت في اجتياز العتبة الصارمة المسجلة مسبقاً (أن تكون أقل من 1% من وقت CP-SAT) في 42 من أصل 43 نموذجاً. نتج هذا الفشل بشكل أساسي عن النماذج الصغيرة حيث قام (CP-SAT) بحل المشكلة فورياً تقريباً، مما خلق أثراً رياضياً في النسبة.

الأهمية والادعاءات
إن المساهمة المركزية للورقة ليست نتيجة إيجابية فيما يتعلق بجودة الحل، بل هي توصيف دقيق إحصائياً لحدود سياسات الجدولة (GNN-PPO). يجادل المؤلفون بأن التعميم عبر الأحجام والمتانة تجاه الاضطرابات المتعددة هما خاصيتان منفصلتان، وليسا "حزمة واحدة" تظهر تلقائياً من نفس البنية.

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

يخلص المؤلفون إلى أنه لا ينبغي للممارسين استنتاج متانة مواجهة الاضطرابات من ادعاءات التعميم عبر الأحجام وحدها. بدلاً من ذلك، يجب معاملة هذه القدرات كمحاور تصميم مستقلة تتطلب تقييماً وهندسة منفصلين. وتقترح الدراسة استراتيجية نشر هجينة محتملة حيث تعمل سياسة (GNN) سريعة وتفاعلية كحل احتياطي فوري أثناء الاضطرابات، بينما تعمل برامج حلول أعلى جودة وأبطأ (مثل GA أو CP-SAT) بالتوازي لإنشاء جداول محسنة.