جدولة ورش العمل
- قدّمه
- Pinedo, M. L.
- السنة
- 2016
- النوع
- Combinatorial scheduling problem
- العائلة
- Optimization
هذا النص ترجمة آلية ولم تتم مراجعته بعد. اقرأ النص الأصلي بالإنجليزية
ماذا تفعل؟
جدولة ورش العمل هي مشكلة تخصيص مجموعة من المهام (الوظائف) لمجموعة من الآلات (الموارد) على مدار الوقت، مع مراعاة قيود الأسبقية والقدرة، بهدف تحسين مقاييس الأداء مثل زمن الإنجاز الكلي (makespan)، أو التأخير، أو التكلفة. تُعد مشكلة ورشة العمل مشكلة تحسين توافقي كلاسيكية في بحوث العمليات، وتُعالَج من خلال الاستدلالات (قواعد الإرسال الجشعة، التلدين المحاكي، الخوارزميات الجينية) والخوارزميات الدقيقة (الفرع والحد، البرمجة بالقيود). وهي أساسية للتصنيع وإدارة المشاريع والجدولة الحاسوبية.
الفكرة الحدسية وراء الطريقة
تخيل ورشة ميكانيكية صغيرة بها 10 آلات. يتكون طلب العميل (الوظيفة) من 5 أجزاء، يتطلب كل منها سلسلة من العمليات على آلات مختلفة: الجزء 1 يحتاج إلى تشغيل على الآلة A، ثم حفر على الآلة C. الجزء 2 يحتاج إلى حفر على الآلة B، ثم لحام على الآلة D. تتجمع جميع الأجزاء للتجميع النهائي. التحدي: جدولة جميع العمليات لتقليل إجمالي وقت الإنجاز، دون تجاوز سعة الآلة، مع احترام تسلسل العمليات لكل جزء. إذا قمت بتعيين الجزء 1 للآلة A متأخرًا جدًا، فإن الآلة C تظل خاملة. إذا قمت بتحميل الآلة C بشكل زائد، يتأخر كل شيء. تلتقط مشكلة ورشة العمل هذا التعقيد: مع 100 وظيفة و 20 آلة، فإن عدد الجداول الممكنة فلكي، مما يجعل الحل الدقيق غير عملي. بدلاً من ذلك، تستخدم الاستدلالات للعثور على جدول جيد (ليس بالضرورة الأمثل) بسرعة.
التاريخ
ظهرت مشكلة جدولة ورش العمل في الخمسينيات كمشكلة بحثية في بحوث العمليات. قدم عمل جونسون (Johnson) الرائد (1954) حلاً أمثل لمشكلة الآلتين؛ وأنشأ فيشر وثومبسون (Fisher and Thompson) (1963) مشكلات معيارية لا تزال تستخدم حتى اليوم. المشكلة هي NP-hard (أثبتت في السبعينيات)، مما حفز تطوير الاستدلالات والميتادليل. تشمل الأساليب الحديثة البرمجة بالقيود (التسعينيات-العقد الأول من القرن الحادي والعشرين)، والخوارزميات الجينية، والأساليب الهجينة. أصبحت جدولة ورش العمل الآن مجالًا ناضجًا مع تطبيقات تتجاوز التصنيع لتشمل الحوسبة السحابية، والاتصالات، والنقل.
متى تُستخدم
تنطبق جدولة ورش العمل على أي بيئة تصنيع أو خدمة تحتوي على آلات/موارد متعددة ووظائف ذات تسلسلات تشغيل مميزة. تشمل التطبيقات النموذجية ورش الآلات، ومصانع الطباعة، وتصنيع رقائق أشباه الموصلات، والمستشفيات (جدولة غرف العمليات)، وجدولة المشاريع. استخدمها عندما يكون تعقيد الوظيفة مرتفعًا (عمليات متعددة لكل وظيفة)، أو عندما يكون استخدام الآلة حاسمًا، أو عندما تكون تواريخ الاستحقاق ضيقة. تكون أقل أهمية في بيئات خطوط التجميع (التدفق الخطي) أو العمليات البسيطة ذات الآلة الواحدة.
الحدود والاعتبارات
- التعقيد التوافقي: إيجاد الحلول المثلى هو مشكلة NP-hard؛ تتطلب الحلول العملية استدلالات قد لا تكون مثلى عالميًا.
- الحلول الاستدلالية تعتمد على السياق؛ قد تؤدي القاعدة التي تعمل جيدًا لورشة عمل واحدة بشكل سيء في أخرى، مما يتطلب الضبط والتحقق.
- تفترض مدخلات ثابتة (وظائف وآلات ثابتة)؛ تشهد الورش الحقيقية وصولات ديناميكية، وإلغاءات، وأعطال في المعدات، مما يتطلب إعادة جدولة متكررة.
- استقرار الجدول: التغييرات المتكررة في الجداول (بسبب وظائف جديدة أو اضطرابات) يمكن أن تزيد التكاليف وتزيد من تعقيد التنسيق مع العمال والعملاء.
لا تغني شروط المصدر عن المراجعة العلمية المستقلة أو التحقق بواسطة محرك تحليل.
نقاط القوة
- تستوعب قيودًا معقدة وواقعية (الأسبقية، قدرات الآلة، تواريخ الاستحقاق) لا تستطيع قواعد الجدولة البسيطة التعامل معها.
- تحسين مقاييس الأعمال ذات الصلة (زمن الإنجاز الكلي، التأخير، استخدام الآلة) بدلاً من القواعد المخصصة.
- تتيح الاستجابة السريعة للاضطرابات؛ يمكن لخوارزميات إعادة الجدولة إنشاء خطط منقحة عند تعطل آلة أو وصول وظيفة عاجلة.
- تسمح الصياغة الرياضية بتحليل الحساسية واستكشاف المقايضات (على سبيل المثال، التأخير مقابل زمن الإنجاز الكلي).
- مدعومة بأدوات برمجية فعالة وخوارزميات ميتاهيوريستية ناضجة.
التطبيقات
- تستخدم ورشة ميكانيكية دقيقة جدولة ورش العمل مع التلدين المحاكي لجدولة أكثر من 200 قطعة مخصصة عبر 15 آلة CNC، مما يقلل من زمن الإنجاز الكلي بنسبة 15 بالمائة ويحسن التسليم في الوقت المحدد من 85 بالمائة إلى 95 بالمائة.
- تطبق منشأة تصنيع أشباه الموصلات جدولة قائمة على القيود لإدارة أكثر من 500 خطوة عملية عبر 50 أداة، مما يقلل من وقت دورة الرقاقة ويقلل المخزون قيد المعالجة بنسبة 20 بالمائة.
- تستخدم شركة طباعة جدولة ديناميكية لورش العمل لتعيين مهام الطباعة لـ 8 مطابع ذات قدرات مختلفة، مع التحسين لمزيج الوظائف (الحجم الكبير مقابل التخصص) وتقليل وقت التغيير.
- يطبق فريق جدولة المستشفى خوارزميات جدولة ورش العمل لجدولة غرف العمليات، وتنسيق الجراحين، والفرق الجراحية، والمعدات، مما يحسن استخدام غرفة العمليات من 65 بالمائة إلى 82 بالمائة.
كيف يعمل
كيف يعمل
تحديد الوظائف (الطلبات، المهام) مع تسلسل العمليات، ومتطلبات الآلة، وأوقات المعالجة، وتواريخ الاستحقاق. تحديد الآلات المتاحة ونوافذ توفرها.
تحديد القيود: أسبقية العملية (يجب أن ينهي الجزء 1 العملية A قبل بدء العملية B)، والقدرة (يمكن لكل آلة معالجة وظيفة واحدة في كل مرة)، واختياريًا، أوقات الإصدار وتواريخ الاستحقاق.
تطبيق قاعدة إرسال (مثل، أقصر وقت معالجة، أقرب تاريخ استحقاق، النسبة الحرجة) لتسلسل الوظائف في كل آلة، مما يولد جدولاً مبدئيًا.
استخدام الميتاهيوريستكس (التلدين المحاكي، البحث التابو، الخوارزميات الجينية، تحسين مستعمرة النمل) لتحسين الجدول من خلال البحث المحلي أو الأساليب القائمة على السكان.
تقييم جودة الجدول (زمن الإنجاز الكلي، التأخير، وقت الخمول، وقت المخزن المؤقت). إذا كان مقبولاً، يتم التنفيذ؛ وإلا، يتم تعديل المعلمات وإعادة التحسين.
الأخطاء الشائعة
- التحسين لمقياس خاطئ؛ قد يؤدي تعظيم استخدام الآلة إلى زيادة تأخير الوظائف، بينما قد يتطلب الوفاء بجميع تواريخ الاستحقاق وقت خمول كبيرًا.
- تجاهل أوقات الإعداد والتغيير؛ قد يكون الجدول الذي يقلل من وقت الخمول ولكنه يتطلب إعدادات متكررة ومستهلكة للوقت غير أمثل في الممارسة.
- الإفراط في الثقة في الجداول الاستدلالية دون التحقق من سلوك الورشة الحقيقي؛ غالبًا ما تكون القيود أكثر تعقيدًا مما يغطيه النموذج.
الأسئلة الشائعة
ما هو زمن الإنجاز الكلي، ولماذا هو مهم؟
زمن الإنجاز الكلي هو الوقت الإجمالي من بداية العملية الأولى إلى اكتمال العملية الأخيرة. يرتبط ارتباطًا مباشرًا باستخدام المعدات، والتدفق النقدي (الانتهاء الأسرع = الدفع الأسرع)، ورضا العملاء. يعد تقليل زمن الإنجاز الكلي هدفًا أساسيًا شائعًا في جدولة ورش العمل.
ما الفرق بين جدولة ورش العمل الثابتة والديناميكية؟
تفترض الجدولة الثابتة أن جميع الوظائف معروفة مسبقًا؛ تقوم بتحسين مجموعة ثابتة. تتعامل الجدولة الديناميكية مع الوظائف التي تصل بمرور الوقت؛ يتم مراجعة الجداول عند وصول وظائف جديدة أو حدوث اضطرابات. معظم الورش الحقيقية ديناميكية، وتتطلب خوارزميات إعادة تحسين سريعة.
ما هي قاعدة الإرسال التي يجب أن نستخدمها؟
لا توجد قاعدة واحدة مهيمنة. أقصر وقت معالجة (SPT) يقلل من زمن الإنجاز الكلي؛ أقرب تاريخ استحقاق (EDD) يقلل من التأخير؛ النسبة الحرجة توازن بين الاثنين. اختبر القواعد باستخدام البيانات التاريخية أو المحاكاة للعثور على الأنسب لأولويات ورشة عملك وقيودها.
هل يمكن لجدولة ورش العمل التعامل مع مهارات العمال والتدريب المتبادل؟
نعم، عن طريق توسيع نموذج الموارد: بدلاً من مجرد 'الآلة A'، حدد 'الآلة A مع العامل 1' أو 'الآلة A مع العامل 2'. ومع ذلك، هذا يزيد من تعقيد المشكلة؛ تأكد من أن برنامج الجدولة الخاص بك يدعم قيود الموارد المتعددة.
طرق ذات صلة
المصادر
Pinedo, M. L. (2016). Scheduling: Theory, algorithms, and systems (5th ed.). Cham: Springer.
افتح مرجع DOIتم النسخ.Taillard, E. (1993). Benchmarks for basic scheduling problems. European Journal of Operational Research, 64(2), 278-285.
افتح مرجع DOIتم النسخ.