💻 علوم الحاسوب

A Block-Guided Artificial Bee Colony Algorithm for Distributed Assembly Flowshop Scheduling with Sequence-Dependent Setup Times

تقترح هذه الورقة خوارزمية مستعمرة النحل الاصطناعية الموجهة بالكتل (BG-ABC) التي تدمج آلية ضغط الكتل المدركة للتعطل، واختيار المشغل التكيفي بحد الثقة العلوي المنزلق 1 (SW-UCB1)، والبحث المحلي المرتكز على الوظائف الحرجة لتقليل زمن الإنجاز (makespan) بفعالية لمسألة جدولة تدفق ورش العمل المتسلسلة ذات أوقات الإعداد المعتمدة على التسلسل في بيئة التجميع الموزعة (DAPFSP-SDST).

المؤلفون الأصليون: Ji-Feng Xu, Hong-Bo Song

نُشر 2026-10-30

📖 3 دقيقة قراءة☕ قراءة في استراحة قهوة

CC BY 4.0

المؤلفون الأصليون: Ji-Feng Xu, Hong-Bo Song

البحث الأصلي مرخَّص بموجب CC BY 4.0 (https://creativecommons.org/licenses/by/4.0/). ✨ هذا شرح مولَّده بالذكاء الاصطناعي للبحث أدناه. لم يكتبه المؤلفون ولم يصادقوا عليه. وللتحقق من الدقة التقنية، يرجى الرجوع إلى البحث الأصلي. اقرأ إخلاء المسؤولية الكامل

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

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

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

اختبر الفريق طريقتهم الجديدة، التي أطلقوا عليها اسم "خوارزمية مستعمرة النحل الاصطناعية الموجهة بالكتل" (Block-Guided Artificial Bee Colony)، مقابل مجموعة واسعة من المشكلات المعيارية التي يستخدمها الباحثون في هذا المجال. تضمنت هذه الاختبارات آلاف السيناريوهات المختلفة مع أعداد متفاوتة من المصانع والآلات والمنتجات. وأظهرت النتائج أن طريقتهم تفوقت باستمرار على الخوارزميات الحالية المتطورة، حيث وجدت جداول زمنية أقصر بكثير في مدتها. ومن خلال الجمع بين كفاءة تجميع أزواج المنتجات المثالية وقدرة البحث المستوحى من النحل على التكيف، أثبت الباحثون وجود طريقة قوية للتعامل مع التنسيق المعقد المطلوب في سلاسل التوريد الحديثة. ويشير عملهم إلى أنه من خلال فهم الأنماط الهيكلية المحددة لمشكلات الجدولة هذه، من الممكن تصميم أدوات ذكية تجعل شبكات التصنيع العالمية المعقدة تعمل بسلاسة وكفاءة أكبر.

ملخص تقني: خوارزمية مستعمرة النحل الاصطناعية الموجهة بالكتل لجدولة تدفق التجميع الموزع مع أوقات إعداد متغيرة حسب التسلسل

تعريف المشكلة
تتناول هذه الورقة مشكلة جدولة تدفق التجميع الموزع مع أوقات إعداد متغيرة حسب التسلسل (DAPFSP-SDST). ينمذج هذا النموذج سلسلة توريد متعددة المراحل حيث يتم معالجة $n$ من الوظائف عبر $f$ من المصانع المتماثلة، حيث يحتوي كل مصنع على $m$ من الآلات بتكوين تدفق ورشة (flowshop). عند الاكتمال، تُنقل الوظائف إلى مرفق مركزي ليتم تجميعها في $d$ من المنتجات على آلة تجميع واحدة. والهدف هو تقليل زمن الإنجاز الكلي ( $C_{max}$ ).

وتكمن الصعوبة الحرجة لهذه المشكلة في إدراج أوقات الإعداد المتغيرة حسب التسلسل (SDST) في كل من مرحلتي التصنيع والتجميع. ففي مرحلة التصنيع، تعتمد أوقات الإعداد على الوظائف المتتالية داخل المصنع؛ وفي مرحلة التجميع، تعتمد على المنتجات المتتالية. وقد تم تحديد المشكلة على أنها مسألة NP-hard قوية، تتطلب التحسين المتزامن لتخصيص الوظائف للمصانع، وتسلسل الوظائف داخل المصانع، وتسلسل تجميع المنتجات.

المنهجية: خوارزمية BG-ABC
يقترح المؤلفون خوارزمية مستعمرة النحل الاصطناعية الموجهة بالكتل (BG-ABC). وتستند فلسفة التصميم إلى ملاحظة أن تقليل زمن الإنجال الكلي يكافئ تقليل مجموع إجمالي أوقات إعداد التجميع (TSTA) وإجمالي أوقات تعطل التجميع (TITA). وتظهر الحلول عالية الجودة غالباً أزواج منتجات متجاورة تحقق في آن واحد حداً أدنى من الـ SDST وزمن تعطل تجميع صفري.

تدمج الخوارزمية أربع آليات محددة في إطار عمل ABC القياسي:

الضغط الكتلي الواعي للتعطل (Idle-Aware Block Compression):
تحدد الخوارزمية "الكتل القابلة للضغط"، وهي أزواج المنتجات المتتالية $(\pi_l, \pi_{l+1})$ حيث يكون $\pi_{l+1}$ هو التابع الأدنى من حيث الـ SDST للمنتج $\pi_l$ ويكون زمن التعطل بينهما صفراً. يتم قفل هذه الأزواج في كتل ذرية. ويؤدي ذلك إلى تقليص فضاء البحث من تبديلات المنتجات الفردية إلى تبديلات هذه الكتل، مما يقلص أبعاد فضاء البحث بشكل كبير مع الحل الحفاظ على الأنماط الهيكلية الواعدة.
الاختيار التكيفي للمشغل (SW-UCB1):
في مرحلة النحل العامل، تعمل الخوارزمية على تسلسل الكتل المضغوطة باستخدام ثلاثة مشغلات للجوار: التبديل (Swap)، والإدراج (Insertion)، والانعكاس (Inversion). وللاختيار الديناميكي للمشغل الأكثر فعالية مع تقدم عملية البحث، يتم استخدام مخطط النافذة المنزلقة للحد الأعلى للثقة 1 (SW-UCB1). يتتبع هذا الآلية المكافآت الأخيرة لكل مشغل ضمن نافذة منزلقة، مما يسمح للخوارزمية بتكييف استراتيجية البحث الخاصة بها دون الحاجة إلى الضبط المعقد للمعلمات المطلوب في تعلم تعزيزي (Q-learning).
البحث المحلي لتسلسل الوظائف الحرجة (CJS):
يتم تقييد البحث المحلي في مرحلة النحل المطلع (onlooker bee) بـ "تسلسل الوظائف الحرجة" (CJS). وبناءً على ملاحظة أن أوقات التعطل للمنتجات التي تظهر بعد آخر وقت تعطل إيجابي لا يمكن تقليلها أكثر من ذلك، تركز الخوارمة جهودها الحسابية فقط على البادئة (prefix) لتسلسل المنتجات (تسلسل المنتج الحرج) التي تحتوي على أوقات تعطل إيجابية. وتُستخدم استراتيجية تقييم ثنائية المستوى: تقييم جزئي سريع لأول $K$ من المنتجات لتصفية المرشحين قبل تفعيل التقييم الكامل لزمن الإنجاز، مما يقلل من العبء الحسابي.
التهذيب وإعادة البناء (مرحلة النحل الكشاف):
لمواجهة خطر التقارب المبكر الناتج عن ضغط الكتل، يتم تنفيذ آلية نحلة كشافة. إذا ركد فرد ما تجاوز عتبة $\theta$ ، تحاول الخوارزمية أولاً إجراء تهذيب مستهدف باستخدام الهبوط الجواري على المنتجات غير الحرجة والـ CJS. وإذا لم يتم العثور على تحسن، تقوم الخوارما بإجراء إعادة ضبط هيكلية: حيث تقوم بتفكيك الكتل المقفلة، وتبديل المنتجات المتبقية عشوائياً، وإعادة خلط ترتيب الوظائف داخل المنتجات، مما يعيد التنوع الهيكلي ويساعد على الهروب من الحلول المحلية المثلى.

المساهمات الرئيسية
تدعي الورقة وجود أربع مساهمات رئيسية:

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

النتائج التجريبية
تم تقييم الخوارمة على 540 حالة اختبار مستمدة من مجموعة بيانات DAPFSP-SDST الخاصة بـ Hatami et al. [7]، تغطي مقاييس مختلفة للمشكلة ( $n \in \{100, 200\}$ , $m \in \{5, 10, 20\}$ , $f \in \{4, 6, 8\}$ , $d \in \{30, 40, 50\}$ ).

المقارنة: تمت مقارنة BG-ABC مع أربع خوارزميات من أحدث التقنيات: الخوارزمية الجشعة المتكررة (IG)، والتحليل الاستدلالي فائق التوليد (GP-HH)، وتحسين التوزيع الحيوي الجديد (NBBO)، وخوارزمية المرحلتين (TSHA).
الأداء: حققت BG-ABC أدنى متوسط انحراف نسبي مئوي (ARPD) قدره -1.95%، متفوقة بشكل كبير على TSHA (-1.28%)، وNBBO (-1.32%)، وGP-HH (-0.49%)، وIG (0.81%). وأكد التحليل الإحصائي باستخدام اختبار Friedman واختبار Bonferroni-Dunn البعدي أن تفوق BG-ABC ذو دلالة إحصائية عند مستويات ثقة 95% و99%.
دراسة الاستئصال (Ablation Study): تم اختبار متغيرات من BG-ABC تفتقر إلى مكونات محددة (ضغط الكتل، الاختيار التكيفي، بحث CJS، أو إعادة البناء الموجه)، وأظهرت النسخة الكاملة من BG-ABC تفوقاً ملحوظاً على جميع المتغيرات، مما يؤكد أن كل مكون غير زائد عن الحاجة ويساهم في الأداء العام.

الأهمية والادعاءات
تؤكد الورقة أن خوارزمية BG-ABC توفر أداة تحسين ذكية وعملية وقوية لبيئات سلسلة التوريد متعددة المراحل. وتكمن أهميتها في النجاح في دمج الرؤى الهيكلية الخاصة بالمشكلة (تحديداً العلاقة بين الـ SDST، وزمن التعطل، وتكوين الكتل) في خوارزمية ميتا-هيورستية قائمة على الجمهرة. ومن خلال موازنة عمق البحث والتكلفة الحسابية عبر ضغط الكتل والبحث المحلي المركز، تتغلب الخوارزمية على قيود الخوارزميات أحادية الهبوط (مثل TSHA) والخوارزميات الميتا-هورستية العامة التي تفشل في استغلال الخصائص المحددة لـ DAPFSP-SDST بشكل كامل. ويخلص المؤلفون إلى أن الطريقة المقترحة تحسن بفعالية الكفاءة التشغيلية واتخاذ القرار في أنظمة التجميع الموزعة.

أبحاث مشابهة