Low-Cost Labels, Reliable Choices: Rollout-Calibrated Hyper-Heuristics for Job Shop Scheduling

ملخص تقني: ملصقات منخفضة التكلفة، خيارات موثوقة

بيان المشكلة
تتناول الورقة مشكلة جدولة ورش العمل (JSSP) من منظور الاستدلالات الفائقة للاختيار (selection hyper-heuristics). وبينما توفر الاستدلالات الفائقة المعززة بالتعلم حلاً وسطاً بين قواعد التوزيع الثابتة وبُناة النماذج المكتسبة من البداية إلى النهاية (end-to-end learned constructors) عبر الحفاظ على القابلية للتفسير والجدوى، إلا أنها تواجه عقبتين رئيسيتين:

1. تكلفة توليد الملصقات: يتطلب التعلم الخاضع للإشراف ملصقات يتم توليدها عبر "تشغيل" (rollout) قواعد توزيع مرشحة من جدول زمني جزئي وصولاً إلى حالة نهائية. إن التشغيل الكامل لكل قاعدة مرشحة عند كل نقطة قرار يكلف حسابياً $O(|H|T)$، حيث $|H|$ هو عدد القواعد و $T$ هو عدد القرارات المتبقية.
2. موثوقية الاختيار: قد يتنبأ المختار المتعلم عن طريق الخطأ بتحسن طفيف فوق قاعدة افتراضية قوية بسبب الضجيج أو الإفراط في التخصيص (overfitting). إن اتباع أدنى درجة متوقعة بشكل أعمى قد يؤدي إلى تدهور الأداء مقارنة بقاعدة ثابتة قوية.

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

المنهجية
يعتمد النهج المقترح، والذي يسمى الاستدلالات الفائقة المعايرة بالتشغيل (Rollout-Calibrated Hyper-Heuristics)، على دمج ثلاثة مكونات أساسية:

1. ملصقات التشغيل المعايرة بالندم (Regret-Normalized Rollout Labels):
   بدلاً من استخدام إجمالي زمن الإنجاز (makespan) الخام أو زمن الإنجاز المعاير بالحد الأدنى، يعرّف المؤلفون ملصق ندم لكل حالة:
   $$r(s, h) = \frac{m(s, h) - \min_{h' \in H_s} m(s, h')}{\min_{h' \in H_s} m(s, h')}$$
   حيث $m(s, h)$ هو زمن الإنجاز الناتج عن تطبيق القاعدة $h$ عند الحالة $s$. هذا يحول الهدف إلى إشارة ترتيب محلية حيث تكون أفضل قاعدة في حالة معينة ذات ندم يساوي 0، مما يعزل الأداء النسبي للقواعد ضمن ذلك السياق المحدد.

2. الاختيار المحكوم بعدم اليقين (Uncertainty-Gated Selection):
   يستخدم النظام مُنظم الجيران الأقرب السياقي (contextual K-Nearest Neighbors - KNN) للتنبؤ بالندم لكل قاعدة مرشحة. ولضمان الموثوقية، تم إدخال آلية تحكم (gating mechanism). لا يقوم المختار بالتبديل من القاعدة الافتراضية الثابتة ($h_0$، المختارة كأفضل قاعدة ثابتة في مجموعة التدريب) إلى القاعدة الأفضل المتوقعة ($h^*$) إلا إذا تجاوز التحسن المتوقع هامشاً معدلاً بعدم اليقين:
   $$\pi_{gated}(s) = \begin{cases} h^* & \text{if } \hat{r}(s, h_0) - \hat{r}(s, h^*) > \lambda \hat{\sigma}(s, h^*) \\ h_0 & \text{otherwise} \end{cases}$$
   هنا، $\hat{\sigma}$ هو الانحراف المعياري للجيران الأقرب $k$ (باعتباره تقديراً لعدم اليقين)، و $\lambda$ هو معلم فائق (hyperparameter) يتحكم في عدوانية التبديل.

3. مقايضة ميزانية التشغيل (Rollout Budget Trade-off):
   يقوم المؤلفون بتغيير عرض التشغيل ($b$، عدد القواعد المرشحة التي يتم تقييمها) وعمق التشغيل ($\kappa$، عدد الخطوات التي تتبع فيها قاعدة مرشحة قبل العودة إلى القاعدة الافتراضية) بشكل صريح لرسم جبهة باريتو (Pareto frontier) بين تكلفة توليد الملصقات (خطوات المحاكاة/وقت الجدار) والأداء النهائي في الاختبار (الانحراف بالنسبة المئوية النسبية، RPD).

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

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

النتائج التجريبية
أُجريت التجارب على حالات JSSP اصطناعية بأحجام $6\times6$ و $10\times10$ و $15\times10$.

• الأداء: حقق المختار المحكوم بالندم (Regret-Gated) أدنى متوسط RPD بين جميع الطرق المتعلمة عبر جميع المقاييس. وقد ظل قريباً جداً من أفضل قاعدة توزيع ثابتة (عادةً FIFO أو MOPNR في هذه الإعدادات الاصطناعية)، مع فجوات متوسط RPD بلغت 0.70 و 0.67 و 0.06 على التوالي.
• المتانة: قلل النهج المحكوم من متوسط RPD لنموذج Random-HH المرجعي بأكثر من مرتبة عشرية واحدة (من ~36–54% إلى ~0.8–2.8%).
• الدراسة الاستقصائية (Ablation): أكدت الدراسة أن آلية التحكم أكثر استقراراً من التبديل الدائم (argmin selection). تم الحصول على أفضل النتائج باستخدام ملصقات الندم وعتبة ثقة $\lambda=1.0$. أدت متغيرات الحد الأدنى للثقة (LCB) إلى نتائج أسوأ، مما يشير إلى أن عدم اليقين يُستخدم بشكل أفضل كاختبار للتبديل بدلاً من كونه مكافأة مباشرة للدرجة.
• تحليل التكلفة: حقق التشغيل الكامل ($\kappa=\infty, b=|H|$) أفضل جودة ولكن بأعلى تكلفة. أما التشغيل الضحل ($\kappa=1$) فقد أدى إلى RPD أعلى بكثير. وقدمت الأعماق المتوسطة مقايضة مجدية، حيث قللت خطوات المحاكاة بشكل كبير مع الحفاظ على جودة مقبولة.

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

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

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