Assignment Models

Assignment Problemini Anlamak

Operations Research alanında, Assignment Problem (Atama Problemi), belirli sayıda görevin, belirli sayıda varlığa veya kişiye en uygun şekilde atanmasını ele alır. Amacımız, toplam maliyeti veya süreyi minimize ederek her bir görevi en uygun kişiye atamaktır.

Örnek: Sandalye Yapımı Senaryosu

Bir sandalye üretim sürecini düşünelim. Bu süreçte üç ana görev bulunmaktadır:

1. Cutting (Kesme): Tahtaların istenilen boyutlarda kesilmesi.
2. Merging (Birleştirme): Kesilen tahtaların birleştirilmesi.
3. Painting (Boyama): Birleştirilen sandalyenin boyanması.

Elimizde bu görevleri yapabilecek üç işçi var: Alice, Bob ve Charlie. Her bir işçinin, her bir görevi tamamlama süreleri farklıdır:

• Alice:
  • Cutting: $5$ dakika
  • Merging: $6$ dakika
  • Painting: $7$ dakika
• Bob:
  • Cutting: $6$ dakika
  • Merging: $4$ dakika
  • Painting: $9$ dakika
• Charlie:
  • Cutting: $3$ dakika
  • Merging: $6$ dakika
  • Painting: $8$ dakika

Amacımız, toplam üretim süresini minimize etmek için her bir görevi farklı bir işçiye atamaktır. Görevler sıralı olarak yapılmalıdır; önce kesme, sonra birleştirme ve son olarak boyama işlemi gerçekleştirilir.

Problemin Ağ Modeli ile Gösterimi

Bu problemi Transportation Problem (Taşıma Problemi) gibi bir ağ modeliyle temsil edebiliriz. İşçiler ve görevler arasında bağlantılar kurarak süreleri maliyet olarak belirleriz.

Ağ Yapısı

• Kaynaklar (İşçiler):

  • Alice
  • Bob
  • Charlie

• Hedefler (Görevler):

  • Cutting
  • Merging
  • Painting

Her işçiden her göreve bir yön çizilir ve bu yönlerin üzerine ilgili süreler yazılır.

Matematiksel Modelleme

Karar Değişkenleri

Her işçinin her göreve atanıp atanmayacağını belirten ikili (binary) karar değişkenleri tanımlarız:

$$x_{ij} = \begin{cases} 1, & \text{eğer işçi } i \text{ göreve } j \text{ atanırsa} \\ 0, & \text{aksi halde} \end{cases}$$

Burada:

• $i$: İşçiyi temsil eder (Alice, Bob, Charlie).
• $j$: Görevi temsil eder (Cutting, Merging, Painting).

Amaç Fonksiyonu

Toplam üretim süresini minimize etmek isteriz:

$$\min \sum_{i} \sum_{j} c_{ij} x_{ij}$$

Burada $c_{ij}$, işçi $i$'nin görevi $j$ tamamlama süresidir.

Kısıtlar

1. Her İşçi Tek Bir Göreve Atanır:

$$\sum_{j} x_{ij} = 1, \quad \forall i$$

Anlamı: Her işçi sadece bir görevi yapar.

2. Her Görev Tek Bir İşçiye Atanır:

$$\sum_{i} x_{ij} = 1, \quad \forall j$$

Anlamı: Her görev sadece bir işçi tarafından yapılır.

3. Değişkenlerin İkili Olması:

$$x_{ij} \in \{0, 1\}, \quad \forall i, j$$

Anlamı: Atama ya yapılır ($1$) ya da yapılmaz ($0$).

Assignment ve Transportation Problemleri Arasındaki İlişki

Assignment Problem, yapısal olarak Transportation Problem'e benzerlik gösterir. Ancak önemli farklar vardır:

• Transportation Problem'de taşınan miktarlar sürekli olabilir ve arz-talep değerleri herhangi bir pozitif sayı olabilir.
• Assignment Problem'de karar değişkenleri ikilidir ($0$ veya $1$) ve her kaynağın arzı ile her hedefin talebi $1$'dir.

Bu nedenle, Assignment Problem, Transportation Problem'in özel bir durumu olarak düşünülebilir.

Problemin Çözümü

Örnek Çözüm Adımları

1. Verilerin Hazırlanması:

   İşçi ve görev sürelerini tablo halinde düzenleriz.

2. Matematiksel Modelin Kurulması:

   Amaç fonksiyonu ve kısıtlar belirlenir.

3. Çözüm Yönteminin Seçimi:

   • Hungarian Algorithm: Assignment Problem'ler için özel olarak geliştirilmiştir.
   • Linear Programming (LP): Modeli LP olarak kurup bir optimizasyon yazılımı ile çözülebilir.

Örnek Uygulama

Amaç fonksiyonu:

$$\min Z = 5x_{A1} + 6x_{A2} + 7x_{A3} + 6x_{B1} + 4x_{B2} + 9x_{B3} + 3x_{C1} + 6x_{C2} + 8x_{C3}$$

Kısıtlar:

• Alice için:

  $$x_{A1} + x_{A2} + x_{A3} = 1$$

• Bob için:

  $$x_{B1} + x_{B2} + x_{B3} = 1$$

• Charlie için:

  $$x_{C1} + x_{C2} + x_{C3} = 1$$

• Cutting görevi için:

  $$x_{A1} + x_{B1} + x_{C1} = 1$$

• Merging görevi için:

  $$x_{A2} + x_{B2} + x_{C2} = 1$$

• Painting görevi için:

  $$x_{A3} + x_{B3} + x_{C3} = 1$$

• Değişkenlerin ikili olması:

  $$x_{ij} \in \{0,1\}$$

Optimal Çözüm

Problemi çözdüğümüzde en düşük toplam süreyi elde etmek için aşağıdaki atamaları yaparız:

• Cutting: Charlie (Süre: $3$ dakika)
• Merging: Bob (Süre: $4$ dakika)
• Painting: Alice (Süre: $7$ dakika)

Toplam süre:

$$Z = 3 + 4 + 7 = 14 \text{ dakika}$$

Daha Karmaşık Durumlar ve Kısıtlar

Eğer işçi sayısı görev sayısından fazlaysa veya bazı işçiler belirli görevleri yapamıyorsa, modele ek kısıtlar eklenmelidir:

• İşçi Sayısı Görev Sayısından Fazlaysa:

  Bazı işçiler hiçbir göreve atanmayabilir.

• Görev Yapamama Durumu:

  Eğer işçi $i$, görevi $j$ yapamıyorsa, $x_{ij} = 0$ olarak tanımlanır.

Sonuç

Assignment Problem, kaynakların görevlere en verimli şekilde atanmasını sağlar. Doğru modelleme ve uygun çözüm yöntemleriyle toplam maliyet veya süre minimize edilir. Bu tür problemler, üretimden lojistiğe birçok alanda verimliliği artırmak için kritik öneme sahiptir.