A Genetic Algorithm with Critical‑Path‑Driven Dual‑Neighborhood Search for Flexible Job Shop Scheduling

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

تعريف المشكلة
تتناول الورقة البحثية مشكلة جدولة ورش العمل المرنة (FJSP)، وهي تحدٍ من نوع التحسين الصعب للغاية (NP-hard) المنتشر في التصنيع الحديث. وخلافًا لمشكلة جدولة ورش العمل الكلاسيكية (JSP)، حيث تكون عمليات التعيين الآلي ثابتة، تسمح مشكلة (FJSP) لكل عملية بأن تتم معالجتها على أي آلة من بين مجموعة من المرشحين البدلاء، وغالبًا بأوقات معالجة متفاوتة. الهدف الأساسي هو تقليل زمن الإنجاز الكلي ($C_{max}$)، والذي يُعرف بأنه أقصى وقت لإكمال جميع الوظائف. تتضمن المشكلة تحديد كل من اختيار الآلة لكل عملية وتسلسل المعالجة على كل آلة مع تلبية قيود الأسبقية وتوافر الآلات.

المنهجية: HGVNSA
يقترح المؤلفون خوارزمية البحث في الجوار المتغير الهجين الجينية (HGVNSA) التي تدمج الخوارزمية الجينية (GA) للاستكشاف العالمي مع البحث في الجوار المتغير (VNS) المدفوع بالمسار الحرج للاستغلال المحلي.

1. الترميز وفك الترميز: يتم تمثيل الحل باستخدام ترميز ثنائي الطبقات: متجه تسلسل العمليات (OS) ومتجه اختيار الآلة (MS). ويتم استخدام استراتيجية فك ترميز نشطة لتوليد جداول زمنية قابلة للتنفيذ.
2. تهيئه الجمهرة: لموازنة الجودة والتنوع، يتم توليد الجمهرة الأولية باستخدام استراتيجية هجينة: الاختيار العالمي (60%، لتقليل زيادة الحمل العالمي)، والاختيار المحلي (30%، لموازنة الحمل داخل الوظائف)، والاختيار العشوائي (10%).
3. العمليات الجينية:
   • العبور (Crossover): تم تقديم عامل عبور يعتمد على إعادة الربط بالمسار (PR). وبدلاً من تبادل الجينات العشوائي، يقوم هذا العامل بتحويل حل الأب بشكل منهجي إلى حل آخر، مع تسجيل وتقييم الحلول الوسيطة لاستغلال مساحة البحث بين الآباء.
   • الطفرة (Mutation): تعمل آلية الطفرة التكيفية على ضبط الاحتمالات بناءً على لياقة الفرد وعدد الأجيال. تُستخدم نوعان من الطفرات: طفرة تسلسل العمليات (إعادة ترتيب ترتيب العمليات) وطفرة اختيار الآلة (تغيير تعيينات الآلات).
   • الحفاظ على التنوع: تُستخدم استراتيجية قائمة على مسافة هامينج (Hamming distance) للحفاظ على تنوع الجمهرة ومنع التقارب المبكر.
4. البحث في الجوار المزدوج المدفوع بالمسار الحرج VNS: يركز البحث المحلي المدمج ضمن إطار الخوارزمية الجينية على العمليات الواقعة على المسار الحرج (أطول مسار في الرسم البياني المتقطع). وهو يستخدم بنيتين متكاملتين للجوار:
   • جوار N8: يحسن تسلسل العمليات على نفس الآلة. وهو يوسع حركات N5-N7 التقليدية من خلال السماح بنقل العمليات الحرجة خارج الكتل الحرجة إلى نهايات الكتل أو مواضع ما قبل/ما بعد الكتلة.
   • جوار k-insertion: يعيد تخصيص العمليات الحرجة إلى آلات مختلفة. يتضمن ذلك التنقل عبر الآلات البديلة وإدراج العملية في مواضع قابلة للتنفيذ، مع التحقق من وجود تبعيات حلقية.
   • استراتيجية البحث: تعطي عملية VNS الأولوية لجوار N8 (تكلفة حوسبة أقل) وتنتقل إلى k-insertion (تكلفة أعلى، بحث أوسع) فقط في حالة عدم العثور على تحسن، مما يضمن التوازن بين الكفاءة وعمق الاستكشاف.

المساهمات الرئيسية
تحدد الورقة خمس مساهمات رئيسية:

1. الإطار الهجين: تؤسس لإطار عمل تآزري يتبع مبدأ "الاستكشاف العالمي أولاً، ثم الاستغلال المحلي لاحقاً"، مما يوازن بفعالية بين دقة الحل والكفاءة الحسابية.
2. تكامل الجوار المزدوج: تعد هذه هي المرة الأولى التي يتم فيها دمج جيران N8 و k-insertion ضمن إطار عمل VNS موحد لمشكلة FJSP. هذا الجمع يعالج كلاً من التسلسل داخل الآلة وإعادة التخصيص بين الآلات، مما يعزز قدرة البحث المحلي بشكل كبير.
3. العمليات الجينية المحسنة: إن إدخال عبور إعادة الربط بالمسار واحتمالات الطفرة التكيفية يعزز قدرة الخوارزمية على استكشاف مساحة الحل والحفاظ على استقرار التقارب.
4. أداء الاختبار المعياري: في مجموعة اختبار Brandimarte MK، وصلت HGVNSA باستمرار إلى الحلول المثلى المعروفة في 6 من أصل 10 حالات (MK01-MK04, MK08-MK09) وحققت أدنى متوسط انحراف مئوي نسبي (RPD) قدره 0.06% بين الخوارزميات المقارنة (HGWO, HLO-PSO, HA, SLGA, ISLGA).
5. التطبيق في العالم الحقيقي: تم تطبيق الخوارزمية على سيناريو معالجة عمود التروس في الشركة (أ). مقارنة بالخوارزمية الجينية التقليدية، حسنت HGVNSA كفاءة الإنتاج بنسبة 8.81%، مما أظهر عمليتها الهندسية.

النتائج والتحقق

• اختبار المعايير: أظهرت التجارب المكثفة على حالات MK01-MK10 أن HGVNSA تفوقت على الخوارزميات المقارنة من حيث جودة الحل والاستقرار. وأكدت دراسات الاستئصال (Ablation studies) أن إزالة مكون VNS، أو بنية الجوار المزدوج، أو الآليات التكيفية أدى إلى تدهور كبير في الأداء (على سبيل المثال، أدت إزالة VNS إلى زيادة متوسط زمن الإنجال في MK02 من 26 إلى 30.4).
• دراسة الحالة: في دراسة حالة الشركة (أ) التي تضمنت 10 وظائف و59 عملية عبر 15 آلة، قللت الخوارزمية زمن الإنجال من 522 (الخوارزمية الجينية التقليدية) إلى 476.
• التقارب: أشار تحليل التقارب إلى أنه بينما استقرت الخوارزميات الأخرى بعد التقارب السريع الأولي، استمرت HGVNSA في تحسين الحلول من خلال آليات البحث المحلي الخاصة بها، محطمة الحواجز للوصول إلى الأمثل المحلي في التكرارات اللاحقة.

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