Solving Distributed Flexible Job Shop Scheduling Problems in the Wool Textile Industry with Quantum Annealing

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

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

المنهجية
صاغ المؤلفون مشكلة (DFJSP) الموسعة كمسألة تحسين ثنائية غير مقيدة تربيعية (QUBO) ليتم حلها باستخدام نظام التلدين الكمي (D-Wave Advantage System 4.1) (QPU).

1. صياغة QUBO: يتم إسقاط المشكلة على متغيرات ثنائية $x_{i,o,m,t}$، والتي تمثل ما إذا كانت العملية $o$ للوظيفة $i$ تبدأ على الآلة $m$ في الوقت $t$. يتم بناء دالة التكلفة $H(x)$ كمجموع مرجح لدوال الجزاء (penalty functions) للقيود (الأسبقية، تنفيذ العملية مرة واحدة، عدم التداخل) ودالة هدف لتقليل زمن الإنجاز الكلي.
2. تقليم المتغيرات (Variable Pruning): لإدارة حجم المشكلة ضمن الحدود الفيزيائية لوحدة المعالجة الكمية (QPU)، استخدم المؤلفون تقنية تقليم المتغيرات. يتضمن ذلك حساب الحدود الدنيا والعليا لأوقات بدء العمليات بناءً على أدنى أوقات السوابق والحد الأقصى لزمن الإنجاز، مما يؤدي إلى استبعاد المتغيرات الثنائية التي تقابل جداول زمنية غير صالحة.
3. تحديد المعلمات: تتضمن الخطوة المنهجية الحرجة حساب معاملات لاغرانج ($\alpha, \beta, \gamma$) لدوال الجزاء بشكل منهجي. وبدلاً من الاعتماد على التجربة والخطأ، اشتق المؤلفون هذه الأوزان رياضيًا بناءً على أقصى زمن إنجاز ممكن ($t_{max}$) لنموذج المشكلة المحدد. يضمن ذلك أن طاقة أي حل صالح تكون أقل من طاقة أي حل غير صالح.
4. التضمين والتهيئة (Embedding and Configuration): يتم تضمين متغيرات (QUBO) المنطقية على طوبولوجيا (QPU) الفيزيائية باستخدام سلاسل من الكيوبتات (qubits). بحث المؤلفون في تأثير "قوة السلسلة" (قوة الاقتران بين الكيوبتات في السلسلة) على جودة الحل، وتحديد القيم المثلى من خلال تحليل المقايضة بين طاقة النظام ونسبة السلاسل المكسورة.
5. المقارنة: تمت مقارنة نتائج التلدين الكمي (QA) مع التلدين المحاكي (SA) باستخدام (D-Wave Ocean SDK). تم اختبار كلتا الطريقتين على نماذج مشكلات تتراوح من 50 إلى 250 متغيرًا (الحد الأقصى للحجم القابل للتضمين في (QPU) المختبر)، كما تم اختبار (SA) أيضًا على نماذج أكبر (تصل إلى 400 متغير) لتحديد خط الأساس للقياس الحسابي.

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

1. نموذج DFJSP الموسع مع التلدين الكمي (QA): قدم المؤلفون أول تطبيق معروف للتلدين الكمي على مشكلة (DFJSP) موسعة حيث يتم توزيع أوامر الإنتاج والعمليات الفردية عبر المصانع، مع نمذجة أوقات الشحن بين المواقع بشكل صريح.
2. الحساب المنهجي للمعلمات: تفصل الورقة طريقة لتحديد معاملات لاغرانج وإعدادات تهيئة (QPU) (تحديدًا قوة السلسلة) بناءً على الصياغة الرياضية للمشكلة، بعيدًا عن نهج التجربة والخطأ الحدسي.
3. التقييم الاقتصادي والأداء: تقيم الدراسة إمكانية الحصول على ميزة السرعة باستخدام (QA) للجدولة الموزعة الخاصة بالصناعة، من خلال مقارنة جودة الحل ووقت الحساب مع التلدين المحاكي (SA) الكلاسيكي.

النتائج

• جودة الحل: بالنسبة لنماذج المشكلات التي تصل إلى 150 متغيرًا، أنتج (QA) حلولاً متسقة وصحيحة (بدون قيود مكسورة)، رغم أن التلدين المحاكي (SA) قدم عمومًا حلولًا ذات طاقة أقل قليلاً (أفضل من حيث الأمثلية). ومع زيادة حجم المشكلة إلى 200 و250 متغيرًا، بدأت حلول (QA) تظهر قيودًا مكسورة (انتهاك واحد و2 على التوالي)، مما أدى إلى قيم طاقة أعلى. يُعزى هذا التدهور إلى الصعوبة المتزايدة لتضمين المشكلات المنطقية الأكبر في رسم (QPU) البياني الفيزيائي، مما يؤدي إلى سلاسل أطول ومعدل أعلى لكسر السلاسل.
• زمن الإنجاز (Makespan): وقعت حلول (QA) لمعظم أحجام المشكلات ضمن النصف الأدنى من نطاق زمن الإنجاز الممكن، مما يشير إلى جداول إنتاج قابلة للتطبيق. ومع ذلك، بالنسبة لنموذج الـ 250 متغيرًا، كان زمن الإنجاز في النصف الأعلى من النطاق.
• وقت الحساب: أظهر (SA) أوقات حساب أسرع لنماذج المشكلات الصغيرة. ومع ذلك، نما وقت وحدة المعالجة المركزية (CPU time) لـ (SA) بشكل أسي مع زيادة حجم المشكلة. في المقابل، زاد وقت الوصول إلى (QPU) الخاص بـ (QA) بمعدل متناقص (لوغاريتمي). وبينما تقتصر قيود الأجهزة الحالية على (QA) لتضمين مشكلات تصل إلى 250 متغيرًا، فإن الاتجاه يشير إلى أنه بالنسبة للنماذج الأكبر (خارج نطاق 300 متغير عند الاستقراء)، يمكن لـ (QA) أن يوفر ميزة سرعة كبيرة مقارنة بـ (SA).

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