الطرائق المضبوطة والتقريبية والميتاهيوريستكية لحل مسائل الأمثلية التوافقية
Exact, Approximation and Meta-Heuristic Methods for Solving Combinatorial Optimization Problems
- الباحث
- عادل هاشم نوري جاسم
- المشرف
- كريمة عبد الكاظم - حسام عبد علي محمد
- الجامعة
- جامعة بابل
- الكلية / القسم
- كلية التربية للعلوم الصرفة / الرياضيات
- الشهادة
- دكتوراه
- السنة
- 2023
- لغة الرسالة
- انكليزي
- الكلمات المفتاحية
- Combinatorial optimization; Exact methods; Approximation methods; Meta-heuristics
الملخص
تتضمن مشاكل التحسين التوافقي (COPs)، التي لها عدد محدود من الحلول الممكنة (FS)، آلات الجدولة وهبوط الطائرات. يعد التحقق من جميع FSs في منطقة البحث هو أفضل أسلوب لحل مشكلة COP. ليس من العملي دائمًا التحقق من كل FS، خاصة إذا كانت منطقة البحث واسعة النطاق. ولمعالجة هذه المشكلات، تم تطوير وتحسين خوارزميات البحث المحلية أو الاستدلال الفوقي. تعد مشكلة جدولة الآلة (MSP) ومشكلة هبوط الطائرة (ALP) مسألتين للتحسين تمت دراستهما في هذه الأطروحة، إلى جانب استخدام كل من استراتيجيات التحسين الدقيقة والإرشادية لحلهما. تمت دراسة متجر التدفق التناسبي (PFS) والآلات المتوازية المتطابقة (IPM) في مشكلة جدولة الآلة (MSP) وتقليل كلفة التبكير والتاخير في هبوط الطائرات (ALP) في هذه الاطروحة. تم إجراء كل هذه الحسابات باستخدام طرق دقيقة مثل طريقة التعداد الكامل (CEM) والفرع والحدود (BAB). كما تم استخدام الأساليب الفوقية الإرشادية، مثل الخوارزمية الجينية (GA)، والخوارزمية الميميتية (MA) وغيرها. في مسائل هبوط الطائرات (ALP)، نصف العديد من الخوارزميات متعددة الأهداف لـ BOALP التي تحسب كلاً من أوقات الهبوط الإجمالية المجدولة (SLTs) لجميع الطائرات وإجمالي تكلفة عقوبة الاختلاف بين SLT لكل طائرة ووقت الهبوط المستهدف (TLT) ).
Abstract
Combinatorial Optimization Problems (COPs), which have a finite number of Feasible Solutions (FS), include scheduling machines and landing aircraft. Checking all of the FSs in the search area is the best technique to solve a COP. It is not always practicable to check every FS, especially if the search region is extensive. To address these issues, local search algorithms, or meta- heuristics, have been developed and improved. The Machine Scheduling Problem (MSP) and the Aircraft Landing Problem (ALP) are two optimization problems that are studied in this dissertation, along with the use of both exact and heuristic optimization strategies to solve them. The Proportional Flow Shop (PFS) and Identical Parallel Machines (IPM) in Machine Scheduling Problem (MSP) and multi-runaway in Aircraft Landing Problem (ALP) are studied in this work. All of these calculations were carried out using exact methods such as Complete Enumeration Method (CEM) and Branch and Bound (BAB). Meta- heuristic methods have also been used, such as Genetic Algorithm (GA) , Memetic Algorithm and other. In Aircraft Landing Problem (ALP) ,we describe several multi-objective algorithms for the BOALP that calculate both the overall scheduling landing times (SLTs) for all aircraft and the total penalty cost of divergence between each aircraft's SLT and its Target Landing Time (TLT).
طلب نسخة من الملف
الملفات غير منشورة على الموقع. اترك بياناتك وسيتواصل معك موظفو قسم الشؤون الثقافية والفنون لإرسال النسخة مجاناً.