استخدام خوارزميات كفوءة لحل مسألة جدولة الماكنة ثلاثية المعايير

الملخص

في هذا البحث سنتناول نموذج ماكنة منفردة متعددة المعايير. فليكن لدينا مسالة جدولة ماكنة (MSP) مكونة من n الاعمال لماكنة واحدة لتصغير دالة ثلاثية المعايير وهي: وقت الاتمام الكلي ( ), مدى التاخير( ) و اعظم تاخير غير سلبي ( ) وهي مسالة تعد من المسائل الصعبة (NP-hard) . اكثر من مسالة ثانوية تم اشتقاقها من مسالتنا الاصلية لغرض المناقشة والحل.في الجزء النظري من هذا البحث، تم اثبات ان قاعدة (SPT) تعطي حل كفوء لمسالتنا وتم تطبيق بعض قواعد الهيمنة عليها. اما في الجانب العملي، تم تطبيق واحدة من اهم طرق الحصول على حل تام وهي خوارزمية التفرع والتقيد على لمسالتنا حيث تم ايجاد حلول كفوءة للمسالة لـ n=18 وكذلك تم تنفيذ نفس الخوارزمية ولكن مع (DR) لـ n=39 لإيجاد حلول كفؤة تامة وحلول كفؤة تقريبية للمسالة في وقت مقبول.