Sözlük · approach
Atama Problemi
Bir kaynak kümesini (kişi, araç, makine) bir görev kümesine en az maliyet veya en yüksek fayda ile eşleştirme problemi.
Assignment ProblemMacar AlgoritmasıHungarian Algorithm
Atama problemi (assignment problem), n adet kaynağı (örnek işçi, teknisyen, araç) n adet göreve birebir eşleştirirken toplam maliyeti en aza indirme veya toplam faydayı en yüksek yapma problemidir. Klasik formu 1955'te Kuhn tarafından 'Macar algoritması' ile polinom zamanda çözüldü — bu, OR'nin en eski ve şık çözümlerinden biri. Genelleştirilmiş atama problemi (GAP) bir kaynağa birden çok görev atanmasına izin verir ve NP-zor sınıfa girer. Saha servis teknisyeni atama, vardiya çizelgeleme, ders programı, ihale tahsisi, robot-iş atama gibi pek çok problemin matematiksel iskeleti atama problemidir.
Örnek
5 teknisyen × 5 müşteri eşleştirmesinde her teknisyenin her müşteriye gidiş süresi farklı. Toplam seyahat süresini en aza indiren eşleştirmeyi Macar algoritması saniyeler içinde verir.