مسائل الجدولة الانسيابية باستخدام الطرائق المضبوطة وطرائق البحث المحلية == Flow shop scheduling problems Using Exact and Local search methods
Author name:
حسين جميل مطشر
Supervisor name:
طارق صالح عبد الرزاق
General topic:
Mathematics
Specific topic:
Mathematics
Degree:
Master
University:
Mustansiriyah University - College Of Science
Language:
English
University location:
Baghdad
First pages:
27T975 - p.pdf
Abstract:
تناولنا في هذا البحث مسالة جدولة (n)من النتاجات على ثلاث مكائن بوجود زمن للنقل بين تلك المكائن لتقليل اكبر وقت اتمام. نظريا ، تمكنا من اشتقاق اثنان من النتائج للامثلية كحالات خاصة للمسالة. هذه المسالة معروفة على انها من النوع المعقد (NP - hard) واقترحنا خوارزميات للتفرع والتقيد مع اثنان من القيود الدنيا المقترحة في هذا البحث ( LB - I, LB - II ) والتي قورنت مع قيد ادنى اخر (LB - N) والمقدم من قبل (المرعشي)، حصلنا عمليا على ان القيد (LB - II) هو القيد الافضل، بعد اختبار هذه القيود على مجموعة من المسائل المولدة عشوائيا، والتي وجدت الحل الامثل لغاية (15) نتاج. ان استخدام خوارزميات الامثلية تبدو بانها غير ضامنة ولذلك قمنا بمعالجة المسالة بطرائق البحث المحلية. كذلك قمنا بتطوير ومقارنة واختبار مختلف طرائق البحث المحلية : (Descent Method, Simulation Annealing, Threshold Accepting, Tabu Search, Genetic Algorithm, Ant colony algorithm). للمسالة وتحرينا عن تاثير تغاير المعلمات لهذه الطرائق. وتحليل حلولها الاولية حسابيا، عمليا ومن خلال الخبرة الحسابية وجد، بان خوارزميات البحث المحلي تستطيع حل المسالة الى (7000) نتاج بوقت معقول، كذلك وجدنا ان (Genetic Algorithm ) هو الافضل للمسالة عندما يكون الحجم اقل او مساوي لـ(400) نتاج، اما للمسائل من حجم اكبر كانتDescent) (Method هي الافضل. كل الطرائق المستخدمة في هذا البحث ( خوارزمية التفرع والتقيد وكذلك خوارزميات البحث المحلية)، برمجت باستخدام لغة البرمجة (Matlab language). | This thesis considers the problem of scheduling 'n' jobs on three machines with transportation times between the machines to minimize the maximum completion time. Theoretically, we drive two results concerning the optimality for two special cases of the problem. As this problem is known as NP - hard (Non deterministic polynomial bounded), we propose branch and bound algorithms with two new lower bounds (LB - I, LB - II) that introduced in this thesis and compared with other lower bound (LB - N) which introduced by Al - Maraashi, we conclude that the lower bound (LB - II) is the best one from the introduced lower bounds after tested them on a set of randomly generated problems, which obtain optimal solution with up to (15) jobs. The implementation of optimizing algorithms does not seem to be promising, thus we decided to tackle the problem with local search algorithms. Different local search methods : (Descent Method, Simulation Annealing, Threshold Accepting, Tabu Search, Genetic Algorithm, Ant Colony Optimization algorithm) are developed, compared and tested for the problem. We investigate the influence of the parameters variance for these local search methods, and empirically analyze their starting solutions. Computational experience is found that these local search algorithms can solve the problem up to (7000) jobs with reasonable time, also found that : the Genetic algorithm is the best local search heuristic algorithm for our problem, when the size is less than or equal to (400) jobs, and for problems of large size the Descent algorithm was recommended. All methods (branch and bound and the local search heuristic algorithms) are programming (coding) in Matlab technical language
