n×n maliyet matrisi verildiğinde n işçi/kaynağı n göreve bire-bir atayarak toplam maliyeti veya süreyi minimum yapma problemi; OR'un en temel kombinatoryel problemlerinden biri (literatürde Assignment Problem, çözümü Kuhn-Munkres Hungarian Method, polinom-zaman O(n³)).
Kısaca
Tanıdık geliyor mu?
- 5-30 mühendis + 10-50 proje görevli mühendislik bürosuyuz; her hafta hangi mühendisin hangi göreve atanacağı kararı sezgisel olarak yapılıyor, planlamacı + spreadsheet ile teyit ediliyor.
- Haftalık 20-80 yeni dosya dağıtan hukuk bürosuyuz; her avukatın her dosya tipinde maliyeti (uzmanlık + saat ücreti + müvekkille mevcut ilişki) farklı, dağıtım kıdem sırasına veya 'kim müsait' kuralına göre yapılıyor.
- Şehir-içi 10-50 servis aracı + personel havuzu olan tesis-yönetimi firmasıyız; her gün gelen 10-50 saha çağrısını personele atıyoruz, transfer mesafesi + personel yetkinliği + iş süresi farklı.
- 5-30 cerrah + 10-50 vaka planlayan hastane planlamacısıyız; her cerrahın her vaka tipinde süre + kalite skoru farklı, atama 'en deneyimli cerraha en karmaşık vaka' sezgisi ile yapılıyor.
- Eğitim kurumuyuz; 20-80 öğretmen + 20-80 sınıf/ders eşleştirmesi var, öğretmenin ders tercihi + uzmanlık alanı + sınıf seviyesine uygunluğu farklı, atama yarı-manuel.
- Atama matrisimiz 'rectangular' (7 personel + 12 görev, ya da 15 personel + 9 görev gibi) — kare olmadığı için Hungarian Method ile nasıl çözüleceği belli değil, dummy genişletme yapıyor muyuz onu da bilmiyoruz.
- Atama kararının optimum olmadığını biliyoruz ama ne kadar uzakta optimum olduğunu ölçemiyoruz — referans 'optimum maliyet' rakamımız yok.
- Tek-tedarikçi iş gücü yönetimi yazılımına bağımlıyız; içinde 'atama optimizasyonu' modülü olduğu söyleniyor ama hangi algoritma (Hungarian, LAP, sezgisel) kullandığı şeffaf değil.
Niye önemli?
Nasıl çözülür?
Teknik derinlik
Nasıl çözülür?
Teknik derinlikTek cümlede: Personel-görev çifti için maliyet matrisi C[i,j] (saatlik ücret × tahmini süre + yetkinlik uyumsuzluğu cezası + transfer mesafesi) verildiğinde Macar yöntemi (Hungarian Method) O(n³) zamanda bire-bir optimum eşleştirmeyi bulur — her personel tam bir göreve, her görev tam bir personele, toplam maliyet en az olacak şekilde.
Bu problem yöneylem araştırması (matematik ve bilgisayar kullanarak işletme kararı çözen disiplin) ve kombinatoryel optimizasyon literatüründe Assignment Problem olarak çalışılır. Klasik çözümü 1955’te ortaya konan Macar Yöntemi (Hungarian Method)‘dur; 1957’de algoritma tam-formel bir polinom-zaman O(n³) prosedüre dönüştürüldü; bu nedenle modern literatürde Kuhn-Munkres algoritması da denir. Adı, temelini Macar matematikçilerin attığı çift-yönlü çizge eşleştirme teoremlerinden gelir. Çözüm üç aşamalı:
1. Modelleme — n×n maliyet matrisi + bire-bir atama. Veri girdileri: (a) n adet kaynak (örn. personel, araç, makina) — her birinin yetkinlik profili, saatlik maliyeti, mevcut konumu/uygunluğu, (b) n adet görev — her birinin tipi, beklenen süresi, lokasyonu, son teslim tarihi, kalite gereksinimi, (c) n×n maliyet matrisi C[i,j] — i’inci kaynağın j’inci göreve atandığında doğacak maliyet (ya da süre, ya da olumsuz fayda); maliyet bileşenleri: yetkinlik uyumsuzluğu cezası + saatlik ücret × beklenen süre + transfer mesafesi maliyeti + tercih/uyum cezası. Karar değişkenleri: x[i,j] ∈ {0,1} — i. kaynak j. göreve atandı mı. Kısıtlar: her kaynak tam bir göreve (∑_j x[i,j] = 1, ∀i), her görev tam bir kaynağa (∑i x[i,j] = 1, ∀j). Hedef: minimize ∑{i,j} C[i,j] × x[i,j]. Modeli kare ve dengeli olmalı; rectangular durum (m≠n) için dummy genişletme: m=7 personel + n=12 görev ise, 5 adet dummy personel ekle; her dummy personelin her göreve maliyeti 0 (görev atanmadan kalsa kabul edilebilirse) ya da çok yüksek M (her görev mutlaka atanmalı zorlanırsa). m>n durumunda dummy görev eklenir. Maksimizasyon varyantı (toplam fayda maksimum) için maliyeti -fayda ile değiştir; aynı algoritma çalışır.
2. Çözüm — Hungarian Method ve modern alternatifleri. Hungarian Method’un özü matris-üzerinde sıra/sütun azaltma + atama-grafiği üzerinde örtme (covering) + boş hücrelerde ilerleme: (a) her satırdan minimumu çıkar (her satırda en az bir sıfır kalır), (b) her sütundan minimumu çıkar (her sütunda en az bir sıfır kalır), (c) sıfırlardan oluşan atama-grafiğinde maksimum eşleştirmeyi bul, (d) eşleştirme tam-bir-tam (n çift) değilse, atanmamış satır/sütunları minimum sayıda çizgi ile örtmek için sıralı emin-örtme prosedürü uygula, örtülmeyen hücrelerin minimumunu örtülmemiş satırlardan çıkar + örtü kesişimlerine ekle, sıfır kümesini güncelle, (e) tam eşleştirme bulunana kadar tekrarla. Karmaşıklık O(n³), polinom-zaman, optimum garantili. Modern alternatifler: LAP — Linear Assignment Problem çözümü için shortest-augmenting-path algoritmaları, pratikte Hungarian’dan 5-20 kat daha hızlı; auction algorithm — paralelleştirme uyumlu, büyük ölçekte pratik. LP-tabanlı alternatif: assignment problem’in LP relaxation’ı total unimodular (tam-tek-modüllü) kısıt matrisi nedeniyle integer optimum verir — generic LP solver de garantili optimum verir, sadece daha yavaş. Bottleneck Assignment varyantı: hedef maliyet toplamı değil, atanan en-yüksek-maliyet (max-min adillik) — farklı algoritma, threshold-binary search. Quadratic Assignment Problem (QAP): birbirine bağlı atama maliyeti (kişi-kişi etkileşimi var) — NP-zor, ayrı problem; bizim klasik linear assignment ile karıştırılmamalı.
3. Saha entegrasyonu. Çıktı üç-katmanlı: (a) atama listesi — her kaynak-görev çifti, beklenen başlangıç-bitiş, maliyet katkısı; planlamacı bu listeyi yayımlar, (b) alternatif atama karşılaştırması — optimum atama yanında 2-3 ‘yakın optimum’ seçenek (örn. transfer mesafesi öncelikli, yetkinlik öncelikli, müvekkille-süreklilik öncelikli) sunulur, yönetici bağlamsal karar verir, (c) maliyet-matrisi geri-besleme — atama uygulandıktan sonra gerçek süre/kalite ölçülür, maliyet matrisi tahminleri güncellenir (örn. ‘X personel Y tipi görevde tahmin edilenden %25 yavaş çıktı’). Yukarı entegrasyon: HR sistemi (yetkinlik profili, ücret tablosu, uygunluk takvimi), CRM/proje yönetimi (görev havuzu, müvekkil-süreklilik kaydı), GIS (lokasyon + transfer mesafesi). Aylık atama-komitesi: gerçek vs optimum sapma analizi, maliyet-matrisi kalibrasyon, personel iş yükü dengesi, müvekkil-süreklilik oranı, atama-sonrası iş tatmini sinyalleri.
Alternatifler
Manuel + spreadsheet atama
ÜcretsizSıfır lisans
Kim için: Küçük havuz (kaynak <10, görev <10), tek-aşamalı atama
- + Sıfır yazılım maliyeti
- + Planlamacının saha bilgisi öne çıkar
- + 5x5 ya da 7x7 matrisler için manuel olarak yakın-optimum bulunabilir
- − 10x10 üstü ölçekte manuel optimum imkânsız — sezgi %15-30 sapar
- − Maliyet matrisi tahmin sapması ölçülmez
- − Rectangular durum (m≠n) sezgisel olarak yönetilir, dummy ile genişletme yapılmaz
- − Atama gerekçesi yazılı kalmaz — şeffaflık şikayetlerinde geri dönülemez
Açık-kaynak Hungarian / LAP modülü + özel entegrasyon
Açık KaynakLisans ücretsiz; iç geliştirme 8-16 hafta veya 300K-1M TRY danışmanlık
Kim için: Teknoloji ekibi olan orta hizmet işletmesi, HR/CRM ile entegre
- + Hungarian Method + LAP açık-kaynak kütüphanelerde olgun (her yaygın dilde mevcut)
- + Polinom-zaman O(n³) — saniyeler içinde 100x100 çözüm
- + Optimum garantili; sezgisel sapma riski yok
- + Rectangular + maksimizasyon + bottleneck varyantları açık-kaynakta mevcut
- + Kod açık — şeffaflık denetlenebilir
- − İçeride OR bilgisi + yazılım ekibi şart
- − Maliyet matrisi tahmini için ayrı veri-modeli kurulmalı — algoritma çözer ama girdiyi sen üretirsin
- − Çoklu-dönem dinamik atama için ek modülleme
- − Bakım sorumluluğu işletmede
İş gücü yönetimi (WFM) yazılımı — atama modüllü
Kurumsal200K-1.2M TRY lisans + 80K-400K TRY/yıl bakım (TR pazar gözlemi)
Kim için: Orta-büyük hizmet işletmesi (kaynak 30-200), CRM/HR/operasyon entegre ihtiyaç
- + Atama modülü hazır (Hungarian veya LAP kütüphanesi içeride)
- + HR + CRM + planlama entegre
- + Çoklu-dönem dinamik atama destekli
- + Operasyonel destek + eğitim
- − Algoritmanın hangi varyantı kullanıldığı şeffaf olmayabilir
- − Yüksek lisans + uzun (9-15 ay) kurulum
- − Maliyet matrisi tahmin modeli paket içinde 'kara kutu' — pazarlık edilmeli
- − Tek-tedarikçi lock-in riski
Enterprise OR platformu + özel atama modeli
KurumsalYıllık 600K-3M TRY (büyük OR platformları)
Kim için: Büyük hizmet işletmesi, çoklu-bölge + çoklu-dönem + stokastik gereksinimli
- + Hungarian + LAP + auction + stokastik varyantlar entegre
- + Generalized Assignment Problem (GAP — bir kaynağa birden çok görev) ek modül
- + Çoklu-hedef optimizasyon (maliyet + adillik + süreklilik)
- + Şeffaf metodoloji — sonuçlar bağımsız bir uzman tarafından denetlenebilir
- − Yüksek lisans + uzun (12-24 ay) kurulum
- − Geniş kapsam — küçük-orta ölçek aşırı olabilir
- − OR uzman ekibi + saha entegrasyon ekibi şart
- − TR mevzuatına ve süreçlerine özelleştirme proje süresi ekler
Tavsiye
Çözüm görüşmesinde sor
- Atama altyapısı hangi yaklaşımı kullanıyor — sistematik bir eşleştirme algoritması (Macar yöntemi / kısa-yol artırma / açık artırma tabanlı, akademik adıyla Hungarian / LAP / auction), bir doğrusal programlama çözücüsü, yoksa sezgisel kural mı? Hangi varyantın seçildiği ve sonucun garantili optimum olup olmadığı belgede yazılı mı?
- Rectangular durum (m≠n personel-görev) nasıl yönetiliyor — dummy satır/sütun otomatik mi ekleniyor, kullanıcı manuel mi yapıyor? Dummy maliyeti (0 ya da yüksek M) nasıl seçiliyor?
- Maksimizasyon varyantı (toplam fayda max) destekleniyor mu — maliyet ile fayda arasında otomatik dönüşüm yapılıyor mu?
- Bottleneck assignment (maliyet toplamı yerine max-min adillik) destekleniyor mu? Hangi senaryoda öneriliyor?
- Maliyet matrisi C[i,j] nasıl tahmin ediliyor — kullanıcı manuel mi giriyor, sistem geçmiş veriden mi türetiyor, hibrit mi? Tahmin sapması raporu var mı?
- Çoklu-hedef atama (maliyet + adillik + süreklilik) destekleniyor mu, yoksa tek-hedef mi? Ağırlıklı toplam + Pareto-cephe seçenekleri var mı?
- Pilot dönemde gerçek operasyonel veri ile (6-10 hafta) önceki manuel atamaya kıyasla nasıl bir tasarruf raporu sunulabilir — toplam maliyet, atama süresi, personel iş yükü dengesi?
- Sözleşme biterse maliyet matrisi geçmişi, atama sonuçları arşivi, personel-müvekkil-süreklilik kaydı ve algoritma seçim parametrelerini hangi standart formatta dışa aktarabiliriz?
Teknik detay
Editör notu
Bu problem halk dilinde “iş dağıtımı”, “personel atama”, “görev paylaşımı” veya “kaynak tahsisi” diye anılır. Akademik literatürde adı Assignment Problem; klasik çözümü Hungarian Method veya Kuhn-Munkres algoritması olarak bilinen O(n³) polinom-zaman kombinatoryel algoritma. Algoritmanın adı Macar matematikçiler Dénes König ve Jenő Egerváry’nin 1900’lerin başında geliştirdiği bipartite-matching teoremlerinden gelir; Harold Kuhn 1955 makalesinde bu temele dayanan algoritmayı kurar, James Munkres 1957’de formel polinom-zaman prosedüre çevirir. #072 (Stable Matching) ile karıştırma: stable matching iki-taraflı tercih listeleri (preferences) ile çalışır — aday A kurumu X’i tercih, kurum X adayı A’yı tercih, hiçbir blocking pair olmayacak şekilde eşleşme. Assignment’ta sadece tek-yön maliyet matrisi vardır — kişinin görevde maliyeti var, görev tercih sıralaması yok; ödeme yok ama maliyet var, optimizasyon hedefi toplam maliyet (sosyal optimum) — stratejik manipülasyon analizi farklı. #094 (Transportation Problem) ile karıştırma: transportation’da m kaynak n hedef olabilir (m≠n), her kaynak birden çok hedefe miktar gönderebilir (ki bölünebilir), arz/talep eşitliği farklı kısıtlanır. Assignment’ta her kaynak tek hedefe, her hedef tek kaynaktan — kare 0/1 atama. Transportation’ın bir özel hali assignment.
Sektörde en sık atlanan nokta: rectangular durum (m≠n) için dummy genişletme. Kuhn’un orijinal Hungarian Method’u n×n kare matris ister; pratikte saha 7 personel + 12 görev, ya da 15 personel + 9 görev gibi unbalanced gelir. Çözüm basit ama pratisyen bilmez: matrisi dummy satır/sütun ile kare‘ye genişlet. (a) m<n (personel az, görev fazla): (n-m) dummy personel ekle, dummy personelin her göreve maliyeti M (çok yüksek) — bu, ‘görev mutlaka atanmalı’ zorlanıyorsa kullanılır; eğer ‘fazla görev atanmadan kalsın’ kabul edilebilirse maliyet 0 yapılır ve atanmamış görevler dummy personele ‘gider’ (gerçekte atanmaz). (b) m>n (personel fazla, görev az): tersine dummy görev ekle, dummy göreve atanan personel ‘bu hafta görev almadı’ anlamına gelir. Pratisyen bu prosedürü bilmez, ’ekstra personel artığı’ veya ‘atanmamış görev artığı’ manuel kalır — optimum kaybı %10-25 olur. İkinci atlanan nokta: maksimizasyon ↔ minimizasyon dönüşümü. Bazı problemler ’toplam fayda maksimum’ formundadır (örn. yetenek + müvekkil uyumu); Hungarian Method minimizasyon algoritması ama her maliyeti -fayda ile değiştirip ya da (max_fayda - fayda) transformasyonu ile minimizasyona çevrilir; aynı algoritma çalışır. Üçüncü atlanan nokta: maliyet matrisi tahmin sapması. Algoritmanın optimum verebilmesi için C[i,j] doğru tahmin edilmiş olmalı; kötü tahmin atamayı yanlış yapar. Matrisin nasıl tahmin edildiği (geçmiş süre verisi, yetkinlik formülü, transfer mesafesi tarifesi) algoritmadan önce gelen modelleme sorunu — pratisyenler bunu genelde sezgisel yapar, sistemin çıktı kalitesi tahmin kalitesi ile sınırlıdır. Dördüncü atlanan nokta: Quadratic Assignment (QAP) ile karışıklık. Klasik linear assignment’ın maliyeti her hücre bağımsızdır (C[i,j] sadece i ve j’ye bağlı); QAP’da iki atama birbirini etkiler (kişi i ile kişi i’ aynı bölgeye atanırsa transfer maliyeti var gibi) — NP-zor, ayrı algoritma sınıfı (Koopmans-Beckmann 1957). Lineer atama ile QAP’nin karıştırılması ‘algoritma neden bu kadar uzun sürüyor’ şaşkınlığına yol açar.
Adım adım yol — KOBİ için
Aşama 1 — Önce maliyet matrisini ölç ve yazılı hale getir. En az 6-12 ay geçmiş veri: her personel-görev çifti için gerçekleşen süre, kalite skoru, transfer mesafesi, müvekkil/proje uyumu. Maliyet formülü yazılı: C[i,j] = α × tahmini_süre[i,j] × saatlik_ücret[i] + β × transfer_mesafesi[i,j] + γ × yetkinlik_uyumsuzluğu[i,j] + δ × müvekkil_süreklilik_cezası[i,j]. Ağırlıklar (α, β, γ, δ) yönetim kararı; en azından başlangıç için α=1, β=0.5, γ=2 (ağır), δ=0.3 örnek başlangıç. Her atama-sonrası gerçekleşen vs tahmin sapması kayıtlı.
Aşama 2 — Bilgi sermayesini çıkar. Personel yetkinlik haritası (yetkinlik × seviye matrisi), görev tipi taksonomisi (görev sınıfları + her sınıfın gerektirdiği yetkinlik + ortalama süre), transfer mesafesi tarifesi (bölge×bölge matrisi), müvekkil-süreklilik kuralları (hangi müvekkil için aynı personel zorunluluğu, hangi için tercihi). Bu veri seti maliyet matrisi tahmin modelinin girdisi.
Aşama 3 — Pilot. 6-10 hafta. Bir sub-set (örn. tek-bölge, tek-iş-tipi) için Hungarian Method ile optimum atama hesapla, mevcut manuel atama ile paralel sun. Planlamacı kararı verir; algoritma öneri rolünde. Rectangular durum için dummy prosedürü test et. Başarı kriterleri önceden belirlenmiş: toplam maliyet -%10 minimum, planlamacı atama süresi -%50 minimum, personel iş yükü dengesizliği -%20 minimum.
Aşama 4 — Yaygınlaştırma. 9-15 ay sürede tam hizmet kapsamı + çoklu-hedef (maliyet + adillik + süreklilik) optimizasyona geçiş. Aylık atama-komitesi: gerçek vs optimum sapma analizi, maliyet matrisi kalibrasyon güncellemesi (her 3 ayda bir), personel iş yükü dengesi raporu, müvekkil-süreklilik oranı.
Riskler — ne yanlış gidebilir
Maliyet matrisi tahmin sapması. C[i,j] yanlış tahmin edilmişse algoritma yanlış optimum bulur. Örn. X personelinin Y tipi görevde tahmin edilen 4 saat, gerçekleşen 10 saat — atama ‘optimum’ çıkmış ama saha çöker. Çözüm: maliyet matrisi her atama-sonrası geri-besleme ile güncellenir; en az 3 aylık bir kalibrasyon döngüsü; sapma >25% olan hücreler için ek-analiz tetiklenir.
Yetkinlik birden çok seviyeli — tek skalar maliyet yetersiz. Bir personelin bir görevde yetkinliği ’temel + spesifik müvekkil bilgisi + dil yeterliliği’ gibi birden çok boyutta olabilir; bunu tek bir C[i,j] sayısına çökertmek karar bilgisini kaybeder. Çözüm: çoklu-hedef formülasyonu (toplam maliyet + adillik + süreklilik ayrı hedefler) veya maliyet bileşenlerini ayrı raporla — atama sonrası yöneticinin alternatif seçimi yapabilmesi için.
Çatışan tercihler (sosyal boyut). Optimum atama maliyet matrisini takip eder ama personel-tercih boyutu (kim hangi görevde çalışmak ister, kim hangi müvekkili tekrar görmek ister) maliyet matrisine girmediyse, optimum atama personel memnuniyetinde puan kaybı verir. Çözüm: tercih bilgisi maliyet matrisine tercih-cezası bileşeni olarak eklensin (γ × tercih_uyumsuzluğu[i,j]); ya da Pareto-cepheden alternatif sun.
Tek-tedarikçi iş gücü yönetimi (WFM) lock-in. Sözleşmede “maliyet matrisi geçmişi, atama sonuçları arşivi, personel-yetkinlik kaydı, müvekkil-süreklilik kayıtları ve algoritma parametreleri açık formatta yıllık ihraç” maddesi olmazsa, çözüm sağlayıcıyı değiştirmek hizmet işletmesinin operasyonel hafızasını kaybetmek demektir. Atama sistemleri 5-15 yıl çalışır — tek-tedarikçi bağımlılığı uzun-vadeli risktir.
Çözüm yöntemine teknik bakış
| Yaklaşım | Tipik ölçek | Çözüm süresi | Garantili optimum? |
|---|---|---|---|
| Sezgisel atama (planlamacı + kural) | Küçük (n<10) | anında | Hayır, %70-85 optimum |
| Manuel + spreadsheet (yarı-sistematik) | Küçük (n<10) | dakika | Hayır, yakın-optimum |
| Hungarian Method (Kuhn 1955 / Munkres 1957) | Orta (n<200) | saniye | Evet, O(n³) polinom |
| LAP — shortest augmenting path (Jonker-Volgenant 1987) | Orta-büyük (n<2000) | saniye | Evet, pratikte 5-20x hızlı |
| Auction algorithm (Bertsekas 1988) | Büyük + paralel | saniye-dakika | Evet (ε-yakınsama) |
| Generic LP solver (total-unimodular) | Tüm ölçek | dakika | Evet (LP relaxation integer) |
| Bottleneck Assignment (max-min adillik) | Adillik-odaklı | saniye | Evet (threshold binary search) |
| QAP (Quadratic Assignment) | Etkileşimli atama | saatler | Hayır, NP-zor, metaheuristik |
| GAP (Generalized Assignment) | Bir kaynağa çoklu görev | saatler | NP-zor, MIP veya metaheuristik |
Hedef fonksiyonu seçimi:
- Hedef 1 — Toplam maliyet minimum: Klasik linear assignment; maliyet bileşenleri ağırlıklı toplam.
- Hedef 2 — Toplam süre minimum: Süre-odaklı; saatlik ücret eşit olduğunda maliyet ile aynı.
- Hedef 3 — Bottleneck (max-min adillik): En kötü atamanın maliyeti minimum; adillik-odaklı.
- Hedef 4 — Çoklu-hedef (maliyet + adillik + süreklilik): Pareto-cephe veya ağırlıklı toplam.
Assignment varyantları — sahaya göre seç:
- Klasik Linear Assignment (kare + balanced): n×n maliyet matrisi, bire-bir atama, Hungarian Method O(n³).
- Rectangular Assignment (m≠n): Dummy ile genişletme + Hungarian; ya da LAPJV doğrudan rectangular destekler.
- Maksimizasyon varyantı: Maliyeti -fayda ile değiştir, aynı algoritma.
- Bottleneck Assignment: Threshold binary search + Hungarian; max-min adillik.
- Generalized Assignment (GAP): Her kaynağa kapasite, her göreve kaynak gereksinimi — NP-zor, MIP/metaheuristik.
- Quadratic Assignment (QAP): Kişi-kişi etkileşim maliyeti — NP-zor, Koopmans-Beckmann 1957.
- Dinamik Atama: Çoklu-dönem, görev havuzu dinamik gelir — rolling-horizon.
- Stokastik Atama: Maliyet matrisi belirsiz, beklenen-değer veya CVaR optimizasyon.
Akademik kaynaklar
Sayfanın frontmatter’ında sources alanında listelidir.
Kaynaklar
- Kuhn, H. W. (1955). The Hungarian method for the assignment problem. Naval Research Logistics Quarterly, 2(1-2), 83-97. Atama probleminin polinom-zaman çözümünün temel kaynağı; adı König ve Egerváry’nin Macar matematik geleneğine atfen.
- Munkres, J. (1957). Algorithms for the assignment and transportation problems. Journal of the Society for Industrial and Applied Mathematics, 5(1), 32-38. Kuhn’un yönteminin formel polinom-zaman O(n³) prosedüre dönüştürülmesi.
- Burkard, R., Dell’Amico, M. ve Martello, S. (2009). Assignment Problems. SIAM. Atama problemlerinin kanonik referans kitabı (linear, bottleneck, quadratic, generalized varyantlar).
- Jonker, R. ve Volgenant, A. (1987). A shortest augmenting path algorithm for dense and sparse linear assignment problems. Computing, 38(4), 325-340. LAP algoritması — pratikte Hungarian’dan 5-20 kat hızlı.
- Pentico, D. W. (2007). Assignment problems: A golden anniversary survey. European Journal of Operational Research, 176(2), 774-793. 50 yıllık atama problemi literatür taraması.
- Bertsekas, D. P. (1988). The auction algorithm: A distributed relaxation method for the assignment problem. Annals of Operations Research, 14(1), 105-123. Paralelleştirme-uyumlu auction algorithm.
- YÖK Tez Merkezi — anahtar kelime: ‘atama problemi’, ‘Macar algoritması’ veya ‘Hungarian’ — TR akademisinden 25+ tez. tez.yok.gov.tr
Sözlük
- 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.
- Macar Algoritması
- Atama problemini (n×n maliyet matrisi, bire-bir minimum-maliyet eşleştirme) polinom-zamanda O(n³) çözen kombinatoryel algoritma; Kuhn (1955) ve Munkres (1957).
- Ağırlıklı İki Parçalı Eşleştirme
- İki ayrık düğüm kümesi arasında, kenarların ağırlıklı olduğu iki parçalı bir grafte, maksimum (veya minimum) toplam ağırlığa sahip eşleştirmeyi bulma OR problemi.
Benzer problemler
Haftalık Çalışan Örüntülerini Nasıl Kursam — Talep Karşılansın, Dinlenme + Mesai + Adillik Birlikte Tutsun?
7 gün 24 saat hizmet veren bir operasyonun (perakende zinciri çağrı merkezi, otel resepsiyon, güvenlik, hastane temizliği) İK veya operasyon müdürü, 100-500 çalışan için tek tek vardiya değil **haftalık örüntü** atar: kim hangi günlerde, hangi vardiyada (sabah/öğle/gece), hangi izin dağılımıyla çalışır — talep tepe saatlerde karşılansın, hafta-sonu ve gece yükü kimseye fazla binmesin. Sezgisel plan iki uçtan birinden kazıyor: tepe saatte eksik personel (kasa kuyruğu, kayıp satış, terkedilme oranı) veya ölü saatte fazla personel (saatlik 80-200 TRY işçilik, 100 kişilik operasyonda aylık 30-60K TRY israf). Üstüne sözleşme aşımı (haftalık 45 saat tavanı, 5 ardışık gün, aylık 7-10 gece sınırı) bordro cezası ve iş hukuku riski doğurur; adillik metriği yazılı olmadığında turnover %40-80'e çıkar ve her yeni işe alımın eğitim maliyeti 8-30K TRY. 200 çalışanlık operasyonda yıllık işçilik 30-80M TRY mertebesinde; %10 iyileşme 3-8M TRY/yıl tasarruf demektir.
Hangi Teknisyeni Hangi Müşteriye, Hangi Saatte Yollasam?
5-50 saha teknisyeni çalıştıran bir klima servisi, asansör bakım firması, beyaz eşya servisi, internet teknisyeni sağlayıcısı veya tarımsal makine servisinde — her sabah günlük talep listesi ile karşılaşılır: 30-150 müşteri ya planlı periyodik bakım, ya arıza tamiri, ya kurulum istiyor. Karar verilmesi gereken: hangi teknisyen, hangi müşteriye, hangi sırada, hangi saatte gidecek. Eş zamanlı tutulması gereken kısıtlar: müşteri zaman penceresi (sabah / öğlen / belirli saat aralığı), teknisyen yeteneği (klima A markası, asansör tipi, internet altyapısı), seyahat süresi (şehir içi 20-90 dakika), yedek parça araçtaki stok, acil iş önceliği. Manuel atama 10-15 teknisyen için makul; üzerinde dispatch ekibi günde 2-4 saat telefon zinciriyle ayarlama yapıyor — randevu kayması, müşteri memnuniyetsizliği ve teknisyen boş bekleme yaygın.