Chawki A. Fedjki2022-05-182022-05-185467https://drepo.sdl.edu.sa/handle/20.500.14154/1230إن مسألة التخصيص التربيعية أكثر مسائل إيجاد الحلول المثلى التوافقية رواجاً ، ولها العديد من التطبيقات في علوم الحاسب الآلي وبحوث العمليات . في هذه الأطروحة ، تتطرق لعدة جوانب من مسألة التخصيص التربيعية وامتداداتها . فيما يخص مسألة التخصيص التربيعية ، نبدأ أولاً باستقصاء خصائص أدنى النقاط النجمية وانطلاقاً من هذه الخصائص والهيكل الشبكي الأساسي للمسألة نقترح خوارزمية أساسها النقاط الطرفية للمسألة . ثم نعيد صياغة المسألة كنموذج تخصيص خطي مقيدة ونبحث إمكانية استعمال هذه الصيغة في تطوير خوارزميات لمسألة التخصيص التربيعية . بعدها نقوم بتعميم مسألة التخصيص التربيعية حيث أن الصيغة الحالية لا تغطي جميع مسائل تحديد المواقع . ثم ندرس خصائص المسألة المقترحة ونبرهن أن مسألة التخصيص التربيعية وتعميماتها المعروفة هي حالة خاصة من مسألة التي اقترحناها . تركز الأطروحة على حل حالة خاصة من المسألة الجديدة . نرمز لهذه الحالة الخاصة بمسألة شبه التخصيص التربيعية العامة . ثم نطور عدة خوارزميات تفريع وتحديد بتكييف حد جيلمور المعروف وباستعمال طريقة الاسترخاء الخطي للشر على وأدمس وذلك لحلى مسألة شبه التخصيص التربيعية العامة . نولد مسائل اختبار معيارية بتعديل بعض مسائل الاختبار المعيارية المستخدمة في مسألة التخصيص التربيعية . توضح النتائج أن الحد المحرز بطريقة الاسترخاء الخطي أفضل بكثير من باقي الحدود ويستلزم أقل عدد من الفروع . غير أنه يحتاج إلى وقت طويل لحسابه مقارنتا بحد جيلمور ، لذلك فإن أداء الخوارزميات المؤسسة على حد جيلمور كان أفضل من حيث وقت التنفيذ . وقد تم حل مسائل بحجم 22 مرفق . وختمت الأطروحة ، باقتراح اتجاهات لمواصلة البحث في هذه المسألة .enThesis