المسرد · approach
مسألة التخصيص
مطابقة واحد لواحد لمجموعة موارد (أشخاص، مركبات، آلات) بمجموعة مهام بأقل تكلفة أو أعلى منفعة.
Assignment Problemالخوارزمية المجريةHungarian Algorithm
مسألة التخصيص (assignment problem) هي مسألة مطابقة n من الموارد (مثل عمال، فنيين، مركبات) إلى n من المهام واحد لواحد بحيث تكون التكلفة الإجمالية أدنى ما يمكن أو المنفعة الإجمالية أعلى ما يمكن. حُلَّت صيغتها الكلاسيكية في زمن متعدد الحدود على يد Kuhn عام 1955 بـ«الخوارزمية المجرية» — أحد أقدم الحلول الأنيقة في بحوث العمليات. مسألة التخصيص المعمَّمة (GAP) تسمح بعدة مهام لكل مورد وهي NP-صعبة. الهيكل الرياضي لكثير من المسائل يستند إلى مسألة التخصيص: تخصيص فنيي الخدمة الميدانية، جدولة الورديات، الجداول المدرسية، توزيع العطاءات، تعيين الروبوت للمهمة.
Örnek
مطابقة 5 فنيين بـ 5 عملاء حيث يختلف زمن التنقل لكل ثنائي. تجد الخوارزمية المجرية في ثوانٍ المطابقة التي تقلّل زمن التنقل الإجمالي.