حل مشكلة جدولة الآلة باستخدام طريقة تحسين سرب الجسيمات

الملخص

في هذه الورقة، تم النظر في مشكلة جدولة n وظيفة في جهاز واحد لتقليل التكلفة الإجمالية لمجموع وقت الإنجاز المرجح، والحد الأقصى للتأخير المرجح والحد الأقصى للتأخير الجزائي (أي لتقليل وظائف الهدف المتعددة . يتم تطبيق طرق تحسين سرب الجسيمات (PSO) كطريقة بحث محلية جديدة على مجموعة من المشكلات المولدة عشوائيًا لحل مشكلة جدولة الجهاز مع وظائف هدف متعددة. يتم إجراء دراسات مقارنة بين PSO والخوارزمية الوراثية (GA) لإظهار أيهما أفضل في التطبيقات. بالإضافة إلى ذلك، تم اقتراح ضبط معلمات كل طريقة من أجل تحسين تطبيق كل طريقة. تم اقتراح أسلوب جديد لخطوات التطوير لتحقيق تقارب جيد في التطبيق. نظرًا لأن مشكلتنا هي NP-hard، فإننا نقترح طريقة استدلالية جديدة مثل تحسين سرب الجسيمات لإيجاد حلول شبه مثالية خاصة عندما يتجاوز عدد الوظائف قدرة بعض الطرق الدقيقة مثل طرق الفروع والحدود (BAB) في حل مثل هذه المشاكل.
أخيرًا، تمت مقارنة نتائج طريقتي البحث المحليتين المقترحتين بطريقة البحث الكامل في حل مشكلة مثل مشكلة جدولة الآلات. وجدت التجربة الحسابية أن خوارزميات البحث المحلي هذه تحل مشكلة 2000 وظيفة في وقت معقول.