مقارنة بين خوارزميات البحث المحلي لمسائل الجدولة متعددة الاهداف == A Comparison of Local Search Algorithms for Multicriteria Scheduling Problems
Author name:
سالي عدنان علي
Supervisor name:
طارق صالح عبد الرزاق
General topic:
Mathematics
Specific topic:
Mathematics
Degree:
Master
University:
Mustansiriyah University - College Of Science - Department Of Mathematics
Language:
English
University location:
Baghdad
First pages:
27T1149 - p.pdf
Abstract:
في هذه الرسالة درست مسالة جدولة n من الاعمال على ماكنة واحدة ولتصغير الدالة لمجموع اوقات الاتمام∑Ci) (مع مدى التاخير(RL).في المسالة الرئيسية 1//(∑Ci,RL) اقترحنا وطبقنا العديد من الخوارزميات (المثلى والتقريبية) التي تعطي المجموعة التقريبية للحلول الكفوءة لاول مرة لهذه المسالة. بعض النتائج التجريبية عرضت تطبيق الخوارزميات المثلى والبحث المحلي وخلال فترة زمنية معقوله ، خوارزميات البحث المحلي يمكن ان تحل المسالة حتى 900 عمل. يتم تحسين اثنين من متعددة اهداف خوارزميات البحث المحلية MOVNS2 وMOVNS3 وتعطي نتائج افضل من Geiger خوارزمية .MOVNS1 وكذلك وضعنا وبرهنا بعض المقترحات لايجاد الحلول الكفوءة .وفي المسالة الخاصة 1//Lex(∑Ci,RL) اقترحنا خوارزمية ((AP1 التي تعطي الحل الافضل للمسالة. اما في المسالة الخاصة 1//Lex(RL , ∑Ci) اقترحنا خوارزمية (MLH) وهي تطوير لخوارزمية (LH) لايجاد افضل نتائج للمسالة .وفي المسالة الخاصة 1// (∑Ci+RL) فقد وجدنا الحل الامثل او حل قريبا من الحل الامثل للمسالة بدون استخدام طريقة التفرع والتقيد (BAB) ، حصلنا على هذه الحلول من مجموعة الحلول الكفوءة للمسالة الرئيسية . | In this thesis, the problem of scheduling n jobs on a single machine with objective to minimize a function of total completion times (∑Ci) and range of lateness (RL) is examined. For the main problem 1//(∑Ci , RL), we propose and apply several (exact and approximate) algorithms, which give approximate set of efficient solutions, for the first time for this problem. Some experimental results are presented to show the applicability of the exact and local search algorithms. With a reasonable time, local search algorithms can solve the problem up to (900) jobs. Two multi - objective local search algorithms MOVNS2 and MOVNS3 are modified and give better results than that of Geiger algorithm MOVNS1. As well as we state and prove some propositions for finding efficient solutions. For the problem 1//Lex(∑Ci , RL), we propose an algorithm (AP1), which gives the best solution for it. For the problem 1//Lex(RL , ∑Ci), we propose an algorithm (MLH) which is a modification of the algorithm (LH) to find the best result for it. For the problem 1//(∑Ci + RL), we find the optimal or near optimal solution for it, without using branch and bound (BAB) method, we get these solutions from the set of efficient solutions of the main problem
