On the quadratic assignment problem and its extensions
No Thumbnail Available
Date
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Saudi Digital Library
Abstract
إن مسألة التخصيص التربيعية أكثر مسائل إيجاد الحلول المثلى التوافقية رواجاً ، ولها العديد من التطبيقات في علوم الحاسب الآلي وبحوث العمليات . في هذه الأطروحة ، تتطرق لعدة جوانب من مسألة التخصيص التربيعية وامتداداتها . فيما يخص مسألة التخصيص التربيعية ، نبدأ أولاً باستقصاء خصائص أدنى النقاط النجمية وانطلاقاً من هذه الخصائص والهيكل الشبكي الأساسي للمسألة نقترح خوارزمية أساسها النقاط الطرفية للمسألة . ثم نعيد صياغة المسألة كنموذج تخصيص خطي مقيدة ونبحث إمكانية استعمال هذه الصيغة في تطوير خوارزميات لمسألة التخصيص التربيعية . بعدها نقوم بتعميم مسألة التخصيص التربيعية حيث أن الصيغة الحالية لا تغطي جميع مسائل تحديد المواقع . ثم ندرس خصائص المسألة المقترحة ونبرهن أن مسألة التخصيص التربيعية وتعميماتها المعروفة هي حالة خاصة من مسألة التي اقترحناها . تركز الأطروحة على حل حالة خاصة من المسألة الجديدة . نرمز لهذه الحالة الخاصة بمسألة شبه التخصيص التربيعية العامة . ثم نطور عدة خوارزميات تفريع وتحديد بتكييف حد جيلمور المعروف وباستعمال طريقة الاسترخاء الخطي للشر على وأدمس وذلك لحلى مسألة شبه التخصيص التربيعية العامة . نولد مسائل اختبار معيارية بتعديل بعض مسائل الاختبار المعيارية المستخدمة في مسألة التخصيص التربيعية . توضح النتائج أن الحد المحرز بطريقة الاسترخاء الخطي أفضل بكثير من باقي الحدود ويستلزم أقل عدد من الفروع . غير أنه يحتاج إلى وقت طويل لحسابه مقارنتا بحد جيلمور ، لذلك فإن أداء الخوارزميات المؤسسة على حد جيلمور كان أفضل من حيث وقت التنفيذ . وقد تم حل مسائل بحجم 22 مرفق . وختمت الأطروحة ، باقتراح اتجاهات لمواصلة البحث في هذه المسألة .