Atama Problemi

• Macar Yöntemi
• Dal-Sınır Yöntemi

Macar Yöntemi

Hangi elemanı hangi işe atayacağımız sorusunun çözümünü arıyoruz.

1. Her sütundaki en küçük elemanı o sütündaki tüm elemanlardan çıkar.
2. Her satırdaki en küçük elemanı o satırdaki tüm elemanlardan çıkar.
3. Tüm sıfır değerlerinden geçen minimum sayıda doğru çiz.
4. Eğer çizilen doğru sayısı satır veya sütun sayısına eşitse atamalar yapılabilir.
5. Eğer çizilen doğru sayısı satır veya sütun sayısından azsa
   • Doğruların dışında kalan hücrelerin en küçük değerini, doğruların dışında kalan hücrelerden çıkar. Doğurların kesişim noktalarına ekle.

Örnek 1:

Birinci adımda her sütünunun en küçük elemanını bulunduğu sütünunun tüm elemanlarından çıkartıyoruz.

Oluşan tabloya Fırsat Maliyetleri Tablosu denir.

Aynı işlemi satır bazında tekrarlıyoruz.

Bu tablonun adı Toplam Fırsat Maliyetleri Tablosu’dur.

Tüm 0 değerlerinden geçen minimum sayıda doğru çiziyoruz. Çözümün birebir olması için bu doğru sayısın satır veya sütun sayısına eşit olması gerekli.

Bu tabloda 2 tane doğru oluştu. Böyle bir durumda doğruların taradığı alan dışındaki alanı alıyoruz.

Bu alandaki/tablodaki en küçük değeri, tüm değerlerden çıkartıyoruz(bu örnek için 1). Aynı değeri doğruların keşisim noktasına (CX) ekliyoruz.

Sonuç olarak aşağıdaki gibi yeni bir tablo elde ettik

Elde ettiğimiz tabloda dikey veya yatay şekilde sıfırlardan geçen doğruları çizdiğimizde 3 adet doğrumuz olacaktır. Bu durumda artık elemanların iş ataması yapabiliriz. Tablomuzdaki 0 olan hücrelere atama yapabiliriz.

A elemanı X işine B elemanı X veya Y işine C elemanı Y veya Z işine atanabilir.

A elemanını X işine atadık. B elemanı için sadece Y işi kaldı. B elemanını Y işine atadık. C elemanı için sadece Z işi kaldı. C elemanını Z işine atadık.

Elde edilen atama tablosu aşağıdaki gibidir

Maliyetleri hesaplamak için atama yapılan hücrelerin en baştaki değerlerini topluyoruz.

 toplam~maliyet=20+15+12=47 

Örnek 2:

Fırsat Maliyetleri tablosu:

Toplam Fırsat Maliyetleri tablosu:

\begin{align*}
A &\rightarrow II\\
B &\rightarrow I\\
C &\rightarrow IV\\
D &\rightarrow III
\end{align*}

 toplam~maliyet=14+12+12+15=53 

Dal-Sınır Yöntemi

I. işe A elemanını atıyoruz (maliyet 9) bundan sonraki atamalarda en az maliyeti seçiyoruz. II. işe C elemanını atıyoruz (maliyet 3) III. işe D elemanın atıyoruz (maliyet 8) IV. işe B elemanını atıyoruz (maliyet 11). Normalde A veya D elemanı bu işi daha az maliyetle yapabilir. Lakin o elemanları zaten başka bir işe atamış bulunduğumuz için kullanamayız. Toplam maliyet=9+3+8+11=31

Şimdi A elemanın I. işe atarsak nasıl bir maliyet çıkacağını hesapladık. Aynı durumu B, C, D için de hesaplıyoruz.

I. işe B elemanını atıyoruz (maliyet 14) II. işe C elemanını atıyoruz (maliyet 3) III. işe D elemanın atıyoruz (maliyet 8) IV. işe A elemanını atıyoruz (maliyet 8) toplam maliyet 14+3+8+8=33

Diğer işlemleri de yaptığımızda elimizde aşağıdaki gibi sonuç olacaktır.

 \begin{align*} &A\rightarrow I:9+3+8+11=31\\ &B\rightarrow I:14+3+8+8=33\\ &C\rightarrow I:11+5+8+8=32\\ &D\rightarrow I:15+3+10+8=36 \end{align*} 

En düşük maliyet A elemanının I. işe atanmasında gerçekleşmektedir. Bu durumda A elemanın I. işe atadık. Şimdi I. işle ve A elemanıyla işimiz bitti. Tablonun geri kalanı için diğer elemanları aynı işlemleri tekrar ederek atayacağız.

 \begin{align*} &A\rightarrow I:\\ &B\rightarrow II:9+(5+8+12)=34\\ &C\rightarrow II:9+(3+8+11)=31\\ &D\rightarrow II:9+(10+10+12)=41 \end{align*} 

II. işe C elemanını atadık.

 \begin{align*} &A\rightarrow I:\\ &C\rightarrow II:\\ &B\rightarrow III:9+3+(10+9)=31\\ &D\rightarrow III:9+3+(8+11)=31 \end{align*}

III. işe B veyahut D atanması durumunda maliyetler eşit çıkmaktadır.

Sonuç olarak en düşük maliyet için aşağıdaki atamaları yapabilirim

 A\rightarrow I;C\rightarrow II;B\rightarrow III;D\rightarrow IV;\\ A\rightarrow I;C\rightarrow II;D\rightarrow III;B\rightarrow IV; 

Proje Yönetimi

• PERT (Project Evaluation and Review Technique)
• CPM (Critical Path Method

PERT/CPM proje planlaması aşamları şöyledir:

• Planlama: Projeyi oluştur an faaliyetler belirlenir. Bunların süre tahminleri yapılıp, şebeke diyagramı ile proje temsil edilir.
• Programlama: Her faaliyet için en erken ve en geç başlama ve bitiş zamanları hesaplanır. Kritik faaliyetler belirlenir.
• Kontrol: Proje ilerlerken süre ve maliyetler bakımından planlara uygunluk kontrol edilir. Gerek varsa hızlandırma işlemleri yapılır.

Faaliyet: Bir başlangıç ve bitiş düğümü arasında okla gösterilir. Düğümlere birbirini izleyen numaralar verilir. Örneğin 15 birim zaman süren bir A faaliyeti şöyle gösterilir:

Faaliyetler arası öncelik ilişkisi ve bağımlılıkları temsil eder.

• Her bir faaliyet tek bir ok ile temsil edilir.
• Bir faaliyet kendisinden önceki faaliyet bitmeden başlayamaz.
• Bir şebekede, tek bir başlangıç ve tek bir bitiş düğümü bulunabilir.
• Her düğümünü numarası olmalıdır. Faaliyetlerin başlangıç ve bitiş düğümlerinin numaraları artan sırada verilmelidir.

Boş faaliyet: İki farklı faaliyetin başlangıç ve bitiş düğümleri aynı olamaz. Bu nedenle değeri sıfır olan bir boş faaliyet eklenmelidir.

En erken ve en geç başlama ve bitiş zamanları: PERT/CPM de bazı faaliyetler geciktirilebilir. Bu faaliyetler en erken belirli bir sürede başlayabileceği gibi en geç farklı bir zamanda da başlatılabilir ve bitirilebilir.

• İleriye doğru hesap:

EF_{ij}=maks(ES_{ij}+t_{ij})

• Geriye doğru hesap:

 LS_{ij}=min(LF_{ij}-t_{ij}) 

Kritik yol: En erken başlama ve en geç bitiş süreleri birbbirine eşit olan yani geciktirilemeyen faaliyetler kritik faaliyetlerdir. Kritik faaliyetlerden oluşan yol da kritik yoldur. Kritik yol, şebeke üzerindeki en uzun yoldur.

PERT

PERT yönteminde 3 çeşit süre kullanılmaktadır

• İyimser süre – a
• Muhtemel süre – m
• Kötümsel süre – b

Beklenen tamamlanma süresi:

 t=\frac{a+4m+b}{6} 

Beklenen süreye ait varyans:

 \sigma^2=(\frac{b-a}{6})^2 

Örnek: Aşağıda iyimser, muhtemel ve kötümser süre tahminleri verilen şebekeye ait faaliyetlerin süre ve varyanslarını hesaplayarak, projenin tamamlanma süresini ve varyansını hesaplayın.

Süre: 29 birim zaman
Kritik faaliyetlerin sürelerinin toplamı

Varyans=1+3+5.444=11.5444
Toplam varyans, kritik faaliyetlerin varyanslarının toplamıdır.