On the quadratic assignment problem and its extensions
| dc.contributor.author | Chawki A. Fedjki | |
| dc.date | 2000 | |
| dc.date.accessioned | 2022-05-18T04:29:25Z | |
| dc.date.available | 2022-05-18T04:29:25Z | |
| dc.degree.department | College of Computer Science and Engineering | |
| dc.degree.grantor | King Fahad for Petrolem University | |
| dc.description.abstract | إن مسألة التخصيص التربيعية أكثر مسائل إيجاد الحلول المثلى التوافقية رواجاً ، ولها العديد من التطبيقات في علوم الحاسب الآلي وبحوث العمليات . في هذه الأطروحة ، تتطرق لعدة جوانب من مسألة التخصيص التربيعية وامتداداتها . فيما يخص مسألة التخصيص التربيعية ، نبدأ أولاً باستقصاء خصائص أدنى النقاط النجمية وانطلاقاً من هذه الخصائص والهيكل الشبكي الأساسي للمسألة نقترح خوارزمية أساسها النقاط الطرفية للمسألة . ثم نعيد صياغة المسألة كنموذج تخصيص خطي مقيدة ونبحث إمكانية استعمال هذه الصيغة في تطوير خوارزميات لمسألة التخصيص التربيعية . بعدها نقوم بتعميم مسألة التخصيص التربيعية حيث أن الصيغة الحالية لا تغطي جميع مسائل تحديد المواقع . ثم ندرس خصائص المسألة المقترحة ونبرهن أن مسألة التخصيص التربيعية وتعميماتها المعروفة هي حالة خاصة من مسألة التي اقترحناها . تركز الأطروحة على حل حالة خاصة من المسألة الجديدة . نرمز لهذه الحالة الخاصة بمسألة شبه التخصيص التربيعية العامة . ثم نطور عدة خوارزميات تفريع وتحديد بتكييف حد جيلمور المعروف وباستعمال طريقة الاسترخاء الخطي للشر على وأدمس وذلك لحلى مسألة شبه التخصيص التربيعية العامة . نولد مسائل اختبار معيارية بتعديل بعض مسائل الاختبار المعيارية المستخدمة في مسألة التخصيص التربيعية . توضح النتائج أن الحد المحرز بطريقة الاسترخاء الخطي أفضل بكثير من باقي الحدود ويستلزم أقل عدد من الفروع . غير أنه يحتاج إلى وقت طويل لحسابه مقارنتا بحد جيلمور ، لذلك فإن أداء الخوارزميات المؤسسة على حد جيلمور كان أفضل من حيث وقت التنفيذ . وقد تم حل مسائل بحجم 22 مرفق . وختمت الأطروحة ، باقتراح اتجاهات لمواصلة البحث في هذه المسألة . | |
| dc.identifier.other | 5467 | |
| dc.identifier.uri | https://drepo.sdl.edu.sa/handle/20.500.14154/1230 | |
| dc.language.iso | en | |
| dc.publisher | Saudi Digital Library | |
| dc.thesis.level | Doctoral | |
| dc.thesis.source | King Fahad for Petrolem University | |
| dc.title | On the quadratic assignment problem and its extensions | |
| dc.type | Thesis |