📋 İçindekiler
Çizelgeleme Nedir
Çizelgeleme (scheduling), kısıtlı kaynaklar üzerinde işlerin zaman içinde sıralanmasıdır. Endüstri mühendisliğinde üretim çizelgeleme, makine atama, insan gücü planlaması ve proje kontrol için kritik öneme sahiptir.
Elimde n adet iş var. Her iş p_j işleme süresine ve d_j teslim tarihine sahip.
Bu işleri makinelere nasıl atayalım ki —
• Toplam akış süresi (makespan) minimize olsun
• Müşteri siparişleri gecikmesin
• Makine boşta kalma süresi minimize olsun
Graham Notasyonu: α | β | γ
| Bileşen | Anlam | Örnekler |
|---|---|---|
| α — Makine ortamı | Kaç makine, nasıl düzenlenmiş | 1 (tek), Pm (paralel), F (flow shop), J (job shop), O (açık shop) |
| β — İş kısıtları | Özel gereksinimler | r_j (hazır olma zamanı), d_j (teslim tarihi), prec (öncelik kısıtları), pmtn (kesilebilirlik) |
| γ — Optimizasyon hedefi | Minimize/maximize ne | C_max (makespan), ΣC_j (toplam akış), ΣT_j (toplam gecikme), L_max (max gecikme), ΣwjCj |
→ 1 makine | hazır olma zamanı ve teslim tarihi kısıtları var | toplam gecikmeyi minimize et
Tek Makine Öncelik Kuralları
| Kural | Açıklama | Optimize Ettiği | Ne Zaman |
|---|---|---|---|
| SPT Shortest Processing Time | En kısa işlemli iş önce | ΣC_j, Ȳ (ortalama akış) — Optimaldır! | Müşteri bekleme süresi kritik |
| LPT Longest Processing Time | En uzun işlemli iş önce | Makespan (paralel makinelerde yaklaşık) | Paralel makinede dengeleme |
| EDD Earliest Due Date | En erken teslim tarihli önce | L_max (maksimum gecikme) — Optimaldır! | Teslim tarihi aşımı asıl sorun |
| CR Critical Ratio | CR = (d_j − t) / p_j → en küçük önce | Dengeleyici kural | Dinamik ortam, öncelik sırası değişiyor |
| WSPT Weighted SPT | p_j/w_j → en küçük önce | ΣwjCj — Optimaldır! | İşlerin ağırlığı/önemi farklı |
| FIFO First In First Out | Geliş sırasıyla | Haksızlık önleme | Müşteri algısı |
| SLACK En Az Bolluk | d_j − p_j − t → en küçük önce | Gecikme sayısını azaltma | Gerçekçi gecikme yönetimi |
5 İş — Tam Karşılaştırma Tablosu
| İş | p_j (işleme süresi, gün) | d_j (teslim tarihi, gün) | w_j (ağırlık/öncelik) |
|---|---|---|---|
| İş 1 | 4 | 7 | 2 |
| İş 2 | 2 | 12 | 5 |
| İş 3 | 6 | 9 | 1 |
| İş 4 | 1 | 5 | 4 |
| İş 5 | 3 | 14 | 3 |
SPT Sırası: 4→2→5→1→3 (p=1,2,3,4,6)
ΣC_j = 1+3+6+10+16 = 36 ← Minimum ortalama akış süresi!
Ortalama akış = 36/5 = 7.2 gün
Gecikmeler: T_4=max(1-5,0)=0, T_2=max(3-12,0)=0, T_5=max(6-14,0)=0, T_1=max(10-7,0)=3, T_3=max(16-9,0)=7
ΣT_j = 10, L_max = 7
EDD Sırası: 4→1→3→2→5 (d=5,7,9,12,14)
ΣC_j = 1+5+11+13+16 = 46
Gecikmeler: T_4=0, T_1=max(5-7,0)=0, T_3=max(11-9,0)=2, T_2=max(13-12,0)=1, T_5=max(16-14,0)=2
ΣT_j = 5, L_max = max(1-5, 5-7, 11-9, 13-12, 16-14) = 2 ← Minimum L_max!
WSPT Sırası: 4→2→5→1→3 (p/w = 0.25, 0.40, 1.0, 2.0, 6.0)
Sıra: 4→2→5→1→3
wjCj: 4×1=4, 5×3=15, 3×6=18, 2×10=20, 1×16=16
ΣwjCj = 4+15+18+20+16 = 73 ← Minimum ağırlıklı akış!
| Kural | Sıra | ΣC_j | ΣT_j | L_max | ΣwjCj |
|---|---|---|---|---|---|
| SPT | 4,2,5,1,3 | 36 ★ | 10 | 7 | 73 |
| EDD | 4,1,3,2,5 | 46 | 5 | 2 ★ | 123 |
| WSPT | 4,2,5,1,3 | 36 | 10 | 7 | 73 ★ |
| FIFO | 1,2,3,4,5 | 56 | 16 | 9 | 110 |
| LPT | 3,1,5,2,4 | 62 | 24 | 16 | 120 |
Müşteri beklemesi kritik → SPT (ΣC_j minimum = 36)
Teslim tarihi kaçırma kabul edilemez → EDD (L_max minimum = 2)
Önemli müşterileri önce yetiştir → WSPT (ΣwjCj minimum = 73)
2 Makine Johnson Algoritması (F2||Cmax)
2 makine flow shop'ta (tüm işler M1→M2 sırasında işlenir), makespan'i minimize eden optimal sıralamayı verir. S.M. Johnson (1954).
Adım 1: Tüm p_{j1} ve p_{j2} değerlerini listele
Adım 2: En küçük süreyi bul:
Eğer minimum M1'de ise → o işi BAŞA koy
Eğer minimum M2'de ise → o işi SONA koy
Adım 3: Atanan işi listeden çıkar; kalan işler için tekrarla
| İş | M1 (hazırlık, dk) | M2 (boyama, dk) |
|---|---|---|
| A | 5 | 2 |
| B | 3 | 6 |
| C | 8 | 4 |
| D | 2 | 7 |
| E | 6 | 1 |
| F | 4 | 5 |
İterasyon 1: Min süre = 1 (E, M2) → E'yi SONA koy → Sıra: [_, _, _, _, _, E]
İterasyon 2: Min süre = 2 (D, M1 ve A, M2) → D'yi BAŞA, A'yı sondan önce → [D, _, _, _, A, E]
İterasyon 3: Min süre = 3 (B, M1) → B'yi BAŞA → [D, B, _, _, A, E]
İterasyon 4: Min süre = 4 (C, M2 ve F, M1) → F'yi BAŞA, C'yi iç boşluğa → [D, B, F, C, A, E]
İterasyon 5: Geriye C kalır → [D, B, F, C, A, E]
Optimal Sıra: D → B → F → C → A → E
Makespan Hesabı:
M1: D[0-2] B[2-5] F[5-9] C[9-17] A[17-22] E[22-28]
M2: D[2-9] B[9-15] F[15-20] C[20-24] A[24-26] E[26-27]
Cmax = 27 dakika
Gantt Şeması — Gerçekçi Görselleştirme
Optimal sıra D→B→F→C→A→E için iki makine Gantt şeması:
★ M2 sadece başta 2 dakika boş kalıyor (D'nin hazırlığını bekliyor). Toplam makespan: 27 dk.
Flow Shop vs Job Shop
🔄 Flow Shop
Tüm işler makineleri aynı sırada ziyaret eder. M1→M2→...→Mk. Otomotiv boya hattı, baskı makineleri gibi. Johnson algoritması 2 makine için optimaldır. 3+ makine için heuristikler (Nawaz-Enscore-Ham) kullanılır.
🔀 Job Shop
Her işin makine sırası farklıdır. 3×3 bile optimal çözümü NP-zor. Tabu arama, GA tercih edilir. Gerçek üretimde daha yaygın (özel siparişler). Gantt üretmek için simülasyon gerekir.
Ağırlıklı Gecikme — WEDD/WSPT Kombinasyonu
Bu problem NP-zor! Kesin çözüm için branch & bound.
Sezgisel: Wilkerson-Irwin (WI) kuralı:
Mod_SPT = p_j/w_j (WSPT) — ağırlıklı işleme süresi
Geç kalmak üzere olan işlere öncelik ver (dinamik CR)
Basit sezgisel: En büyük w_j/p_j oranına göre (WSPT)
Örneğimizde (İş4=4, İş2=2.5, İş5=1, İş1=0.5, İş3=0.17)
Sıra: 4→2→5→1→3 → ΣwjTj = 4×0+5×0+3×0+2×3+1×7 = 0+0+0+6+7 = 13
Türkiye Endüstri Uygulamaları
büyük bir otomotiv şirketi Kocaeli fabrikasında boyahane (paint shop) çizelgelemesi, flow shop yaklaşımıyla optimize edilmektedir. Renk değişimlerinde setup sürelerini minimize etmek için sipariş gruplandırması (batching) ve genetik algoritma tabanlı çizelgeleme uygulanmakta; günlük boya kaynaklı israf %15 azaltılmıştır.
dev bir elektronik üreticisi Manisa fabrikasında 200+ CNC tezgahının job-shop çizelgelemesi, WSPT ve tabu arama hibrit modeliyle yapılmaktadır. Her işin müşteri önem derecesine (ağırlık w_j) göre dinamik önceliklendirme uygulanmakta; teslim zamanında gerçekleşme oranı %94'ten %98'e çıkmıştır.