Assignment Problem

Assignment Problem'ine Giriş

Assignment Problem, Operations Research alanında sıklıkla karşılaştığımız ve belirli sayıda işin belirli sayıda kaynağa en etkin şekilde atanması gerekliliğini ele alan bir problemdir. Bu kaynaklar genellikle çalışanlar, makineler veya araçlar olabilir ve her bir işin her bir kaynak tarafından yapılmasının farklı bir maliyeti vardır. Amacımız, toplam maliyeti veya süreyi en aza indirerek işleri kaynaklara atamaktır.

Örnek: Alice, Bob ve Charlie'nin Görevleri

Elimizde üç çalışanımız olsun: Alice, Bob ve Charlie. Aynı zamanda yapılması gereken üç görevimiz var:

1. Cutting (Kesme)
2. Merging (Birleştirme)
3. Painting (Boyama)

Her bir çalışan, bu görevleri farklı sürelerde tamamlayabiliyor:

| Çalışan | Cutting (dakika) | Merging (dakika) | Painting (dakika) | |----------|------------------|------------------|-------------------| | Alice | $5$ | $6$ | $7$ | | Bob | $6$ | $4$ | $9$ | | Charlie| $3$ | $6$ | $8$ |

Amacımız, her bir görevi farklı bir çalışana atayarak toplam tamamlanma süresini en aza indirmek. Görevler birbirini takip eden süreçler olduğundan, örneğin önce kesme, sonra birleştirme ve en son boyama işlemi yapılmalıdır.

Problemin Ağ Yapısı ile Gösterimi

Assignment Problem'ini daha iyi anlamak için bunu bir network problem (ağ problemi) şeklinde gösterebiliriz:

• Kaynaklar (Supply Nodes): Alice, Bob, Charlie
• Görevler (Demand Nodes): Cutting, Merging, Painting
• Edge Costs: Her bir çalışanın her bir görevi tamamlama süresi

Her bir kaynağın kapasitesi (supply) $1$, her bir görevin talebi (demand) ise $1$'dir. Bu, her çalışanın en fazla bir görev alabileceği ve her görevin tam olarak bir çalışana atanması gerektiği anlamına gelir.

Lineer Programlama (LP) Formülasyonu

Assignment Problem'i, Linear Programming (Doğrusal Programlama) kullanarak çözebiliriz. Burada karar değişkenlerimiz ve kısıtlarımız aşağıdaki gibi tanımlanır:

Karar Değişkenleri

$$x_{ij} = \begin{cases} 1 & \text{Eğer çalışan } i \text{ görevi } j \text{ yaparsa} \\ 0 & \text{Aksi halde} \end{cases}$$

Amaç Fonksiyonu

Toplam süreyi en aza indirmek istiyoruz:

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

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

Kısıtlar

1. Her Görev İçin Tek Çalışan:

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

Her bir görev, tam olarak bir çalışana atanmalıdır.

2. Her Çalışan İçin Tek Görev:

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

Her bir çalışan, en fazla bir görev almalıdır.

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

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

Karar değişkenlerimiz binary'dir; bir çalışan ya bir görevi alır ya da almaz.

Transportation Problem ile Karşılaştırma

Assignment Problem, yapısal olarak Transportation Problem'e benzer. Ancak aralarındaki temel farklar şunlardır:

• Kapasiteler ve Talepler: Transportation Problem'de kaynakların kapasiteleri ve talepler farklı değerler alabilirken, Assignment Problem'de genellikle hepsi $1$'dir.
• Karar Değişkenleri: Transportation Problem'de karar değişkenleri sürekli olabilirken, Assignment Problem'de karar değişkenleri binary'dir ($0$ veya $1$).
• Miktarlar: Transportation Problem'de miktarlar (örn. taşıma hacmi) dikkate alınırken, Assignment Problem'de bir işin bir kaynağa atanıp atanmadığı önemlidir.

Özel Durumlar

Bazen kaynak ve görev sayıları eşit olmayabilir. Örneğin, $5$ çalışan ve $3$ görev varsa, tüm çalışanlar bir göreve atanamaz. Bu durumda LP modelimizde aşağıdaki düzenlemeleri yaparız:

• Her Görev İçin Tek Çalışan:

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

• Her Çalışan En Fazla Bir Görev Alabilir:

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

Bu yaklaşım, fazla olan kaynakların (veya görevlerin) sistemde yer almasını sağlar ancak onlar için ek bir maliyet oluşmaz.

Sonuç

Assignment Problem, belirli işlerin belirli kaynaklara en etkin şekilde atanmasını amaçlayan ve birçok gerçek dünya uygulaması bulunan önemli bir optimizasyon problemidir. Problemin doğru bir şekilde modellenmesi ve uygun çözüm yöntemleriyle toplam maliyet veya süre en aza indirilebilir.

Not: Bu problemde kullanılan yöntemler ve prensipler, kaynakların ve işlerin sayısına bağlı olarak daha karmaşık durumlara da uygulanabilir. Bu nedenle, Assignment Problem'ini anlamak ve çözüm tekniklerini öğrenmek, operasyon araştırmaları ve optimizasyon alanında önemli bir beceridir.