ملخص تقني: PyCSP3-Scheduling

بيان المشكلة

بينما توفر PyCSP3 بيئة منتجة لنمذجة المسائل التوافقية وتصديرها إلى معيار XCSP3، إلا أنها تفتقر إلى الدعم الأصلي لتجريدات الجدولة عالية المستوى. حالياً، يتعين على النمذجين استخدام متغيرات صحيحة منخفضة المستوى (أوقات البدء، المدد) وبناء قيود الأسبقية الحسابية والنزاعات (disjunctions) يدوياً للتعامل مع تعارضات الموارد. ورغم أن PyCSP3 توفر قيوداً عالمية مثل NoOverlap و Cumulative على مصفوفات الأعداد الصحيحة، إلا أنه يجب على النمذج إدارة مصفوفات أوقات البدء، وقوائم المدد، وارتفاعات الموارد بشكل صريح. هذا النهج يحجب الهيكل الجوهري للجدولة، ويعقد إضافة ميزات مثل الاختيارية (مهام قد تحدث أو لا تحدث) أو أوقات الإعداد المعتمدة على التسلسل، ويتطلب إعادة بناء الترميزات من الصفر لنماذج جديدة. توفر الأدوات الصناعية الموجودة (مثل CP Optimizer) كائنات جدولة، لكنها غالباً ما تربط النماذج بمحللات محددة، وهي أحياناً تجارية، بينما تفتقر لغات مثل MiniZinc إلى أنواع متغيرات الفترات (interval variable types) كعناصر أساسية.

المنهجية

تقدم الورقة البحثية PyCSP3-Scheduling، وهي مكتبة توسع PyCSP3 بطبقة جدولة مخصصة. تتضمن المنهجية الأساسية ما يلي:

1. طبقة التجريد: تقدم المكتبة نوعين رئيسيين من المتغيرات:
   • IntervalVar: يمثل مهمة ذات سمات للبدء، والنهاية، والحجم (المدة)، والوجود. وهو يدعم خمسة أنواع: ثابت (Fixed)، مرن (Flexible)، اختياري (Optional)، محدود (Bounded)، ومقياس (Scaled) (يربط المدة بملفات الكثافة).
   • SequenceVar: يجمع قائمة من متغيرات الفترات في تسلسل مرتب، يمثل عادةً مورداً تنافرياً (مثل آلة)، ويدعم أوقات الانتقال المعتمدة على النوع.
2. مخطط التجميع (Compilation Scheme): لا تقدم المكتبة خلفية محلل (solver backend) جديدة، بل تقوم بتجميع هذه التجريدات عالية المستوى إلى متغيرات وقيود PyCSP3 قياسية، والتي يتم تصديرها بعد ذلك كحالات XCSP3 قياسية.
   • الرسم المباشر (Direct Mapping): عندما تتطابق الأنماط مع القيود العالمية الموجودة (مثل الفترات الإلزامية بدون انتقالات)، تصدر المكتبة قيود XCSP3 عالمية قياسية مثل noOverlap و Cumulative.
   • التفكيك (Decomposition): في الحالات المعقدة (مثل الفترات الاختيارية مع حراس الوجود أو الإعدادات المعتمدة على التسلسل)، تقوم المكتبة بتفكيك التجريدات إلى قيود أولية. على سبيل المثال، فإن SeqNoOverlap مع الفترات الاختيارية يعود إلى قيود التنافر الثنائية $O(n^2)$ المحروسة بمتغيرات وجود (presence literals)، لأن معيار XCSP3 الحالي لا يدعم الفترات الاختيارية في القيود العالمية.
   • النمذجة الهجينة: طبقة التجريد مدمجة داخل PyCSP3، مما يسمح للنمذجين بالخلط بين إنشاءات الجدولة عالية المستوى وقيود PyCSP3 الخام (على سبيل المثال، استخدام presence_of لتفعيل منطق عد مخصص).
3. نظام التعبيرات: توفر المكتبة أدوات وصول (start_of، end_of، presence_of، إلخ) التي ترجع تعبيرات PyCSP3، مما يتيح عمليات حسابية ومنطقية معقدة مباشرة على سمات الفترة.

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

تقدم الورقة ثلاث مساهمات محددة:

1. واجهة برمجة تطبيقات للجدولة (Scheduling API): واجهة شاملة لـ PyCSP3 تتمحور حول تجريدات الفترة والتسلسل، وتدعم الاختيارية، ودوال الكثافة، والتسلسل المدرك للانتقال.
2. مخطط تجميع (Compilation Scheme): آلية تقوم بخفض هذه التجريدات إلى قيود PyCSP3/XCSP3 مستقلة عن المحلل مع الحفاظ على القابلية للإرضاء والتحسين.
3. التقييم التجريبي: مقارنة صارمة لـ 261 حالة مزدوجة (صياغة PyCSP3 الكلاسيكية مقابل صياغة الجدولة) عبر 17 عائلة من المسائل.

النتائج

أُجري التقييم على 261 حالة مزدوجة باستخدام محلل ACE مع مهلة زمنية قدرها 1200 ثانية. وتشمل النتائج الرئيسية ما يلي:

• الصحة الدلالية: في الـ 72 حالة التي أثبتت فيها الصياغتان المثالية، تطابقت قيم الهدف تماماً (100%)، مما يؤكد أن التجميع لا يسبب أي تباعد دلالي.
• الاتفاق على حالة المحلل: اتفقت الصياغتان على حالة المحلل (مثالي، مرضٍ، غير مرضٍ، انتهاء المهلة) في 80.8% من الأزواج. وكانت الخلافات ناتجة أساساً عن اختلافات التقدم في البحث المرتبطة بالمهلة الزمنية بدلاً من الأخطاء المنطقية.
• تباين الأداء: تباين أداء وقت التشغيل بشكل كبير عبر العائلات:
  • المكاسب: أظهرت ثلاث عائلات تسارعاً واضحاً: MSPSP (5.82×)، و AircraftLanding (3.47×)، و Rehearsal (3.31×). عُزي المكسب في MSPSP إلى آثار ترتيب المتغيرات في إعلان متغير PyCSP3 بدلاً من التجريدات نفسها، بينما استفادت AircraftLanding و Rehearsal من تقليل حجم النموذج والالتقاط الهيكلي الأفضل.
  • التراجعات: تراجعت ثلاث عائلات: LotSizing (0.29×)، و MRCPSP (0.61×)، و FlexibleJobshopScen (0.89×).
    • تتبع التراجع في MRCPSP إلى تجميع الفترات الاختيارية الذي عاد إلى التنافر الثنائي بدلاً من إصدار قيد noOverlap عالمي، مما منع الانتشار الفعال.
    • رُبط التراجع في LotSizing بمشاكل التشفير على مستوى القيد وقوة الانتشار تحت المهلة الزمنية.
    • عانت FlexibleJobshopScen من تضخم هيكلي كبير (انفجار في المتغيرات والقيود) بسبب تكرار القرارات الاختيارية عبر السيناريوهات.
• الأثر الهيكلي: أظهرت 8 من أصل 17 عائلة تضخماً هيكلياً ضئيلاً (أقل من 1%). أما بالنسبة للبقية، فقد أدت صياغة الجدولة أحياناً إلى تقليل حجم النموذج (مثل BACP، Rehearsal) وأحياناً إلى زيادته بشكل كبير (مثل FlexibleJobshopScen بنسبة +383.7% في القيود).

الأهمية والادعاءات

تضع الورقة PyCSP3-Scheduling كأول طبقة جدولة توفر تجريدات IntervalVar و SequenceVar كعناصر أساسية مع دعم الاختيارية والتسلسل المدرك للانتقال مع التجميع إلى معيار مستقل عن المحلل (XCSP3).

يؤكد المؤلفون أن المكتبة تحافظ على الفصل الكامل بين النمذجة والحل، وهو مبدأ أساسي في منظومة PyCSP3. وهذا يسمح للنماذج بالبقاء قابلة للاستخدام مع مجموعة واسعة من المحللات (ACE، Choco، CoSoCo، OR-Tools، CP Optimizer، إلخ) دون تعديل.

تتسم الورقة بالتواضع فيما يتعلق بادعاءات الأداء، مشيرة إلى أن مكاسب وقت التشغيل ليست عالمية وغالباً ما ترتبط بهياكل مسائل محددة أو خوارزميات البحث (مثل ترتيب المتغيرات). ويذكر المؤلفون صراحة أن التسارع الكبير في MSPSP هو على الأرجرج نتاج أنماط إعلان المتغيرات وليس التجريدات الخاصة بالجدولة. القيمة الأساسية هي القدرة التعبيرية وسهولة الصيانة لصياغة الجدولة، والتي تقلل من تعقيد الكود (على سبيل المثال، تقليل بنسبة 31% في عدد الأسطر لنموذج Job-shop مرن)، وتبسط إضافة ميزات مثل الاختيارية، حتى لو تسبب ذلك أحياناً في عبء تجميع يؤثر على أداء وقت التشغيل في عائلات مسائل معينة.

تم تحديد العمل المستقبلي في توسيع التجميع لإصدار قيود XCSP3 عالمية تدعم الاختيارية (لتجنب التفكيك الثنائي) وتحسين قواعد التجميع لتقليل العبء الهيكلي في العائلات الشاذة.