özdeş paralel makineli bir üretim sisteminin karınca koloni

Transkript

T. C.
İSTANBUL ÜNİVERSİTESİ
SOSYAL BİLİMLER ENSTİTÜSÜ
İŞLETME ANABİLİM DALI
ÜRETİM YÖNETİMİ BİLİM DALI
DOKTORA TEZİ
ÖZDEŞ PARALEL MAKİNELİ BİR ÜRETİM
SİSTEMİNİN KARINCA KOLONİ
ALGORİTMASI İLE ÇİZELGELENMESİ
BİRGÜL KÜÇÜK
2502040158
TEZ DANIŞMANI:
DOÇ. DR. NECDET ÖZÇAKAR
İSTANBUL, 2010
T. C.
İSTANBUL ÜNİVERSİTESİ
SOSYAL BİLİMLER ENSTİTÜSÜ
İŞLETME ANABİLİM DALI
ÜRETİM YÖNETİMİ BİLİM DALI
DOKTORA TEZİ
BİRGÜL KÜÇÜK
2502040158
TEZ DANIŞMANI:
DOÇ. DR. NECDET ÖZÇAKAR
İSTANBUL, 2010
Bu Doktora Tezi, İstanbul Üniversitesi Bilimsel Araştırmalar Proje Birimi (BAP)
tarafından desteklenmiştir. Proje No:2697
ii
ÖZ
Üretim çizelgeleme, üretim ve servis işletmelerinde kullanılan önemli bir karar
verme prensibidir. Çizelgeleme sistemin etkinlik ve verimliliğini etkileye önemli bir
unsurdur. Makine çizelgeleme problemi, amaç fonksiyonuna uygun biçimde, verilen
zaman periyodu içinde işleri makinelere atamayı amaçlar. İşler makinelere
paylaştırılırken bir ya da birden çok amaç optimize edilmeye çalışılır.
Paralel makine çizelgelemede n sayıda işin m sayıda makineye atanması söz
konusudur. Bu tez çalışmasında ele alınan paralel makine sistemi özdeş yani aynı
işlemleri yapabilen makinelerden oluşmaktadır. Makinelere atanacak işlerin atama
sırasına göre hazırlık süreleri mevcuttur. İşlerin özdeş makinelere atanması esnasında
iki amaç fonksiyonunun optimize edilmesi söz konusudur. Teslim süresinden erken
ve geç tamamlanmaların ceza maliyetlerine sebep olduğu problemde birinci amaç
erken/geç tamamlanma maliyetinin minimize edilmesi iken, diğer amaç ise
maksimum tamamlanma süresinin minimize edilmesidir. Kullanılan veriler sert PVC
takviyeli spiral hortumlar üreten Plahosan fabrikasından alınmıştır. Uygulamada ele
alınan çizelgeleme probleminin çözümüne yönelik olarak Karınca koloni
optimizasyonu yöntemi kullanılmış, elde edilen sonuçlar temel atama problemlerine
göre yapılan çizelgeleme sonuçları ile karşılaştırılarak sonuçlar yorumlanmıştır.
iii
IDENTICAL PARALLEL MACHINE
SCHEDULING USING AN ANT COLONY
ALGORITHM
ABSTRACT
Production scheduling is an important form of decision making used in
manufacturing and service industries. The production scheduling is an important
function determining the efficiency and productivity of a manufacturing system.
Machine scheduling problem aims to assign jobs to machines depending on the
objective functions and time limit. In this problem assignment is made by optimizing
one or more objectives.
In paralel machine scheduling N jobs are assigned to M machines. Parallel machine
systems analyzed in this research are consisted of identical machines which can
perform same jobs. Each machine has a set-up time and set-up times are sequence
dependent. While assigning the jobs to identical machines, two objectives should be
optimized. The objectives are to minimize the total completion of all jobs and the
total earliness-tardiness cost. The data used in this research is taken from the Phocan
company which produces PVC hoses with spirals. The scheduling problem is solved
using Ant Colony Optimization and results are compared with the results found by
using basic assignment methods. The results are recommended in this perspective.
iv
ÖNSÖZ
Bu çalışmanın amacı; tek ve paralel makine çizelgeleme konularını genel hatları ile
incelemek, özdeş paralel makine çizelgelemeyi detaylı olarak ele almak ve gerçek bir
işletmede yer alan çizelgeleme problemini farklı çözüm yöntemleri ile ele alarak
teorik bilgilerin gerçek hayattaki uygulama sonuçlarını değerlendirebilmektir.
Gerçek bir üretim sisteminde yapılan uygulama ile, alınan sipariş örneklerine göre
üretimi daha verimli kılacak çizelgenin elde edilmesi amaçlanmıştır. Aynı zamanda
son yıllarda çizelgeleme problemlerinin çözümü amacı ile kullanılan karınca koloni
algoritması yönteminin ortaya çıkardığı sonuçların temel atama kurallarına göre
üstünlüklerinin irdelenmesi amaçlanmıştır. Ele alınan problem sıra bağımlı hazırlık
zamanlı işler içermekte ve hem toplam erken-geç tamamlanma maliyetini hem de
maksimum tamamlanma zamanını minimize etmeye yöneliktir.
Yaptığım bu çalışma için sayın hocalarım; Doç. Dr. Necdet Özçakar’ a, Yrd. Doç.
Dr. Faik Başaran’ a ve Doç. Dr. Ş. Alp Baray’ a, başta Dr. Timur Keskintürk ve Dr.
Şebnem Er olmak üzere emeği geçen tüm dostlarıma teşekkür ederim.
Ayrıca, uygulama çalışmamdaki verileri sağlayan Sayın Abdullah Er’ e
teşekkürlerimi sunarım.
Ve son olarak, beni büyütüp bu günlere getiren, kişiliğimin oluşmasında büyük
katkıları olan sevgili anne ve babama verdikleri emek ve sevgi için, kardeşlerime ve
eşime sağladıkları manevi destek ve sevgi için, ayrıca neşe kaynağım olduğu için
sevgili yeğenim Efe’ ye teşekkürlerimi ve sevgimi sunarım.
v
İÇİNDEKİLER
ÖZ ............................................................................................................................... iii
ABSTRACT ................................................................................................................ iv
ÖNSÖZ ........................................................................................................................ v
İÇİNDEKİLER ........................................................................................................... vi
TABLOLAR LİSTESİ .............................................................................................. viii
ŞEKİLLER LİSTESİ .................................................................................................. xi
KISALTMALAR LİSTESİ........................................................................................ xii
GİRİŞ ........................................................................................................................... 1
BÖLÜM 1.
ÜRETİM ÇİZELGELEME ................................................................ 5
1.1.
Makine Çizelgeleme .................................................................................... 10
1.2.
Tek Makine Çizelgeleme ............................................................................. 14
1.2.1.
Toplam Ağırlıklı Tamamlanma Süresi................................................. 15
1.2.2.
Maksimum Gecikme ............................................................................ 16
1.2.3.
Geciken İşlerin Sayısı .......................................................................... 18
1.2.4.
Toplam Erken Tamamlanma ve Gecikme............................................ 20
1.3.
Paralel Makine Çizelgeleme ........................................................................ 22
1.3.1.
Paralel Makine Çizelgeleme Problemi ................................................. 27
1.3.2.
Paralel Makine Çeşitleri ....................................................................... 27
1.3.3.
Hazırlık zamanına bağlı sıralama ......................................................... 29
1.3.4.
Ortak Teslim Süresi’ ne Sahip Olan Paralel Makine Ortamının
Çizelgelenmesi ................................................................................................... 33
1.3.4.1.
BÖLÜM 2.
Özdeş Paralel Makinelerde Ortak Teslim Tarihi .......................... 38
KLASİK ÇİZELGELEME YÖNTEMLERİ .................................... 44
vi
2.1.
En Uzun İşlem Süresine Öncelik Tanıma ................................................... 44
2.2.
En Kısa İşlem Süresine Öncelik Tanıma ..................................................... 45
2.3.
İlk Gelene İlk Hizmet .................................................................................. 46
2.4.
Teslim Süresi Yakın Olana Öncelik Tanıma ............................................... 46
2.5.
Klasik Çizelgeleme Yöntemleri İle Çizelgeleme Problemleri .................... 46
BÖLÜM 3.
3.1.
KARINCA KOLONİ OPTİMİZASYONU ...................................... 57
Karınca Koloni Optimizasyonu Yöntemi İle Çizelgeleme Problemleri ...... 61
BÖLÜM 4.
UYGULAMA ................................................................................... 67
4.1.
İncelenen Üretim Sistemi İle İlgili Genel Bilgiler ...................................... 67
4.2.
Çizelgeleme Probleminin Yapısı ................................................................. 69
SONUÇ ...................................................................................................................... 80
KAYNAKLAR .......................................................................................................... 82
ÖZGEÇMİŞ ............................................................................................................... 97
vii
TABLOLAR LİSTESİ
Tablo 1 Amaç fonksiyonuna göre geçmiş çalışmalar ................................................ 26
Tablo 2 Sıra bağımsız hazırlık süreli paralel makine problemleri ............................. 31
Tablo 3 Sıra bağımlı hazırlık süreli paralel makine problemleri ............................... 32
Tablo 5 Makinelere göre iş sıraları ............................................................................ 41
Tablo 6 Makinelere göre optimum iş sıraları ............................................................. 43
Tablo 7 İşlerin proses süreleri .................................................................................... 47
Tablo 8 İşler arası hazırlık süreleri............................................................................. 47
Tablo 9 Makine sayısına göre teslim süreleri ............................................................ 47
Tablo 10 Uzun işlem süresine göre işlerin makinelere atanması ............................... 48
Tablo 11 Kısa işlem süresine göre işlerin makinelere atanması ................................ 48
Tablo 12 İlk gelen işe ilk hizmet kuralına göre işlerin makinelere atanması............. 49
Tablo 19 Problem 2 İki Makine U.İ.S. Çözüm .......................................................... 51
Tablo 20 Problem 2 İki Makine K.İ.S. Çözüm .......................................................... 52
Tablo 21 Problem 2 İki Makine İ.G.İ.H. Çözüm ....................................................... 52
Tablo 22 Problem 2 Üç Makine U.İ.S. Çözüm .......................................................... 53
Tablo 23 Problem 2 Üç Makine K.İ.S. Çözüm .......................................................... 53
viii
Tablo 24 Problem 2 Üç Makine İ.G.İ.H. Çözüm ....................................................... 54
Tablo 25 Problem 2 Dört Makine U.İ.S. Çözüm ....................................................... 54
Tablo 26 Problem 2 Dört Makine K.İ.S. Çözüm ....................................................... 55
Tablo 27 Problem 2 Dört Makine İ.G.İ.H. Çözüm .................................................... 55
Tablo 28 Problem 3 Yöntemlere Göre Çözüm Sonuçları .......................................... 56
Tablo 29 Karınca Koloni Algoritması ile 2 Makine Çizelgeleme ............................. 62
Tablo 30 Karınca Karınca Koloni Algoritması ile 3 Makine Çizelgeleme ................ 62
Tablo 31 Karınca Koloni Algoritması ile 4 Makine Çizelgeleme ............................. 63
Tablo 32 Problem 1 Yöntemlere Göre Karşılaştırmalı Sonuçlar ............................... 63
Tablo 33 Karınca koloni algoritması yöntemine göre işlerin makinelere atanması... 64
Tablo 34 Problem 2 KKO Sonuçları .......................................................................... 65
Tablo 36 Problem 3 KKO Sonuçları .......................................................................... 66
Tablo 38 Hortum çeşit ve detayları ............................................................................ 68
Tablo 39 Uygulama Problem-1 iş süreleri ................................................................. 72
Tablo 40 Uygulama Problem-1 hazırlık süreleri ........................................................ 72
Tablo 41 Uygulama Problem-1 KKO çözüm ........................................................... 73
Tablo 42 Uygulama Problem-2 U.İ.S çözüm ............................................................. 74
Tablo 43 Uygulama Problem-2 K.İ.S çözüm ............................................................. 74
Tablo 44 Uygulama Problem-2 İ.G.İ.H çözüm .......................................................... 75
Tablo 45 Uygulama Problem 1 Yöntemlere Göre Karşılaştırmalı Sonuç.................. 75
Tablo 46 Uygulama Problem-2 iş süreleri ................................................................. 76
Tablo 47 Uygulama Problem-2 hazırlık süreleri ........................................................ 76
ix
Tablo 48 Uygulama Problem-2 KKO çözüm ........................................................... 77
Tablo 49 Uygulama Problem-2 U.İ.S çözüm ............................................................. 77
Tablo 50 Uygulama Problem-2 K.İ.S çözüm ............................................................. 78
Tablo 51 Uygulama Problem-2 İ.G.İ.H çözüm .......................................................... 78
Tablo 52 Uygulama Problem 2 Yöntemlere Göre Karşılaştırmalı Sonuç.................. 78
x
ŞEKİLLER LİSTESİ
Şekil 1 Gant diyagramı................................................................................................. 7
Şekil 2 Öncelik diyagramı ............................................................................................ 9
Şekil 3 İşlerin yer değiştirmesi durumu ..................................................................... 15
Şekil 4 Paralel makine ortamı .................................................................................... 28
Şekil 5 Çizelgelenmiş iş sırası.................................................................................... 38
Şekil 6 Optimal çizelge .............................................................................................. 43
Şekil 7 SPT kuralına göre iş sırası ............................................................................. 45
Şekil 8 Gerçek Karıncaların En Kısa Yolu Bulma Aşamaları ................................... 58
Şekil 9 Matlab’ de karınca koloni optimizasyonu ile çözüm görüntüsü .................... 73
xi
KISALTMALAR LİSTESİ
İ.S: İş süresi
H.S: Hazırlık sürei
T.S: Tamamlanma süresi
K.T: kümülatif toplam süre
E/G: Erken/Geç tamamlanma süresi
C.M: Erken/Geç tamamlanma ceza maliyeti
LPT: En uzun işe öncelik tanıma
SPT: En kısa işe öncelik tanıma
FIFO: İlk gelene ilk hizmet
PVC: Polivinil Klorür
U.İ.S.: Uzun işlem süresine öncelik tanıma
K.İ.S.: Kısa işlem süresine öncelik tanıma
İ.G.İ.H.: İlk gelene ilk hizmet
K.K.O.: Karınca koloni optimizasyonu
n: iş sayısı
m: makine sayısı
(i,j) : j işinin i makinesinde işlem göreceğini belirtir.
xii
pij: proses süresi, yani j işinin i makinesinde işlem gördüğü süre
rj: release date, j işinin prosese başlayacağı en erken süre
dj: due date, tamamlanma süresi, teslim süresi.
wj: j işinin sistemdeki diğer işlere göre önem derecesini gösterir
Pm: m sayıda paralel makine
Qm: m sayıdaki paralel makinenin farklı hızlara sahip olduğunu gösterir
Sjk: sıraya bağımlı hazırlık zamanı, j den k işine geçerken gerekli olan hazırlık
zamanı
Cmax: maksimum üretim süresi
Lmax: Maksimum gecikme
Ej: Erken Tamamlanma
xiii
GİRİŞ
Makine çizelgeleme; bir ya da birden fazla amacı gerçekleştirmeyi hedefleyen,
işlerin uygun biçimde makinelere atanmasını ele alan bir karar verme sürecidir.
Çizelgeleme problemi üretim süresi, kaynak kullanım oranı, stok miktarı, ve teslim
tarihi arasındaki dengeleri içerir. Çizelgelemenin aynı anda bütün amaçları tam
olarak
gerçekleştirmesi
beklenilemez.
Amaçların
birbiri
ile
çatışabileceği
çizelgeleme problemlerinde esas hedef problemde ele alınan amaçların mümkün
olduğunca optimuma yakın olarak karşılanmasıdır.
Literatüre bakıldığında yapılan çalışmaların toplam tamamlanma zamanı, toplam
gecikme, geciken iş sayısı, toplam erken-geç tamamlanma maliyetinin minimize
dilmesini amaçladığı görülmektedir. Ele alınan problemin yapısına göre işlerin
öncelikleri, teslim süreleri ya da işler arasında hazırlık süreleri söz konusu
olabilmektedir. Tamamlanma süresinin azaltılması ya da çeşitli maliyetlere sebep
olacak erken bitirmelerin en aza indirilmesi üretim birimi tarafından tercih edilen
amaçlar olmakla birlikte, gecikme, geciken iş sayısı gibi amaçlar da müşteriler
tarafından arzu edilen amaçlardır. İster üretim birimi tarafından isterse müşteriler
tarafından tercih edilen bir amaç olsun elbette ki amaçların karşılanması üretim
yapan işletmenin yükümlülüğüdür.
İşletmelerin günümüz ekonomisinde rekabet edebilmeleri için müşteri taleplerine
hızla cevap verebilmeleri bir zorunluluktur. Sipariş gecikmelerinden kaynaklanan
müşteri kayıpları işletmeler açısından istenmeyen ve önlenmesi gereken önemli bir
konudur. Çizelgeleme yapılır iken belirlenen amaçlar da bu doğrultuda pek çok faklı
şekilde olabilirler. Bir amaç son işin tamamlanma süresinin en küçüklenmesi
olabilirken, bir başkası ise teslim süresinden sonra tamamlanan yani geciken işlerin
sayısının minimize edilmesi olabilir. Tüm amaçların yanında iş yükü dengesinin
sağlanması da önemlidir.
Üretim çizelgeleme probleminde hangi işin önce yapılması ve hangi işin hangi
makine tarafından yapılması gerektiği kararları cevap bulunması gereken iki temel
1
sorudur. Bunların yanında hangi işin ne zaman başlaması gerektiği, ne zaman
tamamlanması gerektiği de önemlidir. Tüm bu sorulara verilecek en uygun cevap
amaç fonksiyonunu en uygun biçimde karşılayan çözümde yatmaktadır. Bu çözümü
ortaya çıkaracak yöntemler ise analitik yöntemler ya da sezgisel yöntemler
olabilmektedir.
Belirli bir prosedürün izlenmesi ile problemlerin çözümüne ilişkin yaklaşık sonuçlar
veren sezgisel yöntemlere karşın analitik yöntemler kısıt ve amaç fonksiyonları
kullanarak en uygun sonucu veren yöntemlerdir. Ancak analitik yöntemler ile,
özellikle büyük problemlerde, çözüm bulmak zordur. Çizelgeleme problemlerinde
optimal çözümün bulunması zordur ve bu sebeple genelde sezgisel yöntemler ile
çözüme gidilmeye çalışılır.
Analitik
yöntemler;
tamsayılı
programlama,
dinamik
programlama,
lineer
programlama gibi pek çok yöntem içermektedir. Analitik yöntemler kesin çözümler
üretmekle birlikte büyük hacimli çizelgeleme problemlerinde etkin çözümler
yaratmada zayıf kalmaktadır.
Sezgisel yöntemlerin en basit olanları temel sıralama kurallarıdır. En sık kullanılan
temel sıralama kuralları; Kısa İşlem Süresi (KİS), Uzun İşlem Süresi (UİS), İlk
Gelene İlk Hizmet (İGİH) ve Erken Teslim Süresi (ETS)’ dir. Sezgisel algoritmalar
basit sıralama kuralları yanında , Genetik Algoritma, Karınca Koloni Algoritması,
Tabu Araştırma Yöntemi gibi çeşitli yöntemlerden oluşmaktadır.
Tüm işler için mümkün olan en az toplam maliyeti ortaya çıkaracak çizelgenin
bulunması olarak ifade edilen makine çizelgeleme problemi  /  /  olarak ifade
edilmektedir.  makine ortamını,  prosesin özelliğini ve kısıtları,  ise minimize
edilecek amacı göstermektedir.
Makine ortamı tek ya da birden çok makineyi ihtiva edebilir. Tek makine
problemlerinde bir makine üzerinde işlem görecek işlerin amaç fonksiyonu
doğrultusunda sıralanması söz konusudur. Genel görüşe göre paralel makine
2
problemleri tek makine problemlerine göre oldukça zordur. Çünkü her bir
makinedeki işlerin kendi aralarında sıralanması yanında işlerin birden fazla makineye
paylaştırılması da söz konusudur. Yani verilmesi gereken iki karar vardır. Birincisi;
işlerin hangi makineye atanacağının saptanması, ikincisi ise her bir makinede
yapılacak işlerin sırasının belirlenmesidir.
Paralel makineli bir üretim sisteminde özdeş, benzer ve birbirinden bağımsız
makinelerden söz edilebilir. Üretim sisteminde yer alan makineler aynı işi yapan,
aynı hıza sahip makinelerden oluştuğunda özdeş makine çizelgeleme probleminden
bahsedilir. İşlemlerden her biri, sistemde yer alan herhangi bir makinede işlem
görebilir ve işlem süresi değişmez. Yani bir işlem m adet özdeş makineden
hangisinde işlem görürse görsün aynı işlem süresine sahip olur. Birbirinden farklı
hızlara sahip makineler Benzer makineler olarak adlandırılırken, makine hızlarının
işlere bağlı olarak değiştiği makineler ise birbirinden bağımsız paralel makineler
adını almaktadır.
Bu çalışmada özdeş paralel makinelerden oluşan bir üretim sistemi ele alınmış, işe
bağımlı hazırlık zamanı gerektiren üretim sisteminin toplam tamamlanma zamanı ve
toplam erken-geç tamamlanma maliyeti amaçlarına uygun şekilde çizelgelenmesi
amaçlanmıştır.
Birinci bölümde üretim çizelgeleme kavramı ele alınmış, tek ve paralel makine
çizelgeleme konuları detaylı bir biçimde incelenmiştir. Problemden probleme
farklılık gösteren amaç fonksiyonları ve kısıtlar açıklanmıştır.
Çalışmanın ikinci bölümünde çizelgelemeye yönelik basit atama kuralları
açıklanmış, literatürden alınan test problemleri bu yöntemler ile çözülerek ortaya
çıkardıkları sonuçlar değerlendirilmiştir.
Karınca koloni optimizasyon yönteminin ele alındığı üçüncü bölümde söz konusu
yöntemin ortaya çıkışı, esasları, işleyiş biçimi ile ilgili bilgiler verilmiş ve karınca
koloni optimizasyon yöntemi ile çözülen çalışmalara değinilmiştir. İkinci bölümde
3
yararlanılan test problemleri karınca koloni algoritması ile yeniden çözülmüş ve
sonuçlar
basit
atama
kuralları
ile
bulunan
sonuçlar
ile
karşılaştırılarak
yorumlanmıştır.
Dördüncü ve son bölümde sert Polivinil Klorür (PVC) takviyeli spiral hortumlar
üreten fabrikadan alınan veriler ışığında özdeş paralel makine çizelgeleme
yapılmıştır. Çizelgeleme problemi karınca koloni optimizasyonu ile çözülmüştür.
Ayrıca ikinci bölümdeki problemlerde en başarılı sonucu ortaya çıkaran basit atama
kuralı ile de çizelgeleme yapılmış ve sonuçlar Karınca algoritması ile karşılaştırılarak
yorumlanmıştır.
Ele alınan tüm problemlerde amaç; toplam erken-geç tamamlanma maliyetini
minimize etmenin yanında, maksimum tamamlanma süresini de minimize etmeye
yöneliktir. Erken-geç tamamlanma çeşitli maliyetlerin oluşmasına yol açmaktadır.
Bunun yanında makinelerdeki iş yükünün dengelenmesi de işletmeler açısından
önemlidir.
Müşteri taleplerinin zamanında karşılanamaması sonucunda oluşan gecikme maliyeti
yanında teslim tarihinden önce, erken tamamlanan ürünlerin de bir maliyete sebep
olduğu unutulmamalıdır. Gecikme maliyeti; sözleşmede belirtilen parasal cezalar,
müşteri kaybı, müşteri memnuniyetsizliği gibi durumları kapsarken işlerin erken
tamamlanması ise depolama maliyeti, oluşabilecek bozulma maliyeti ve kaçırılan
fırsat maliyeti vb. olabilir. Bu sebeplerle işletmelerde asıl istenen işlerin teslim
sürelerine
yakın
zamanlarda
tamamlanmasıdır.
İşlerin
erken
veya
geç
tamamlanmasının amaç fonksiyonunu olarak değerlendirilmesi “Tam zamanında
üretim” in yaygınlaşması ile birlikte her geçen gün daha da önem kazanmaktadır.
Problemin yapısı gereği işlerin makinelerde işlem görmeleri arasında hazırlık zamanı
söz konusudur. Ele alınan problem hazırlık ve teslim zamanları gerektirmesi ve aynı
anda maksimum tamamlanma ve erken-geç tamamlanma amaçlarını ele almaktadır
ve bu yönleri ile çizelgeleme literatürüne katkı yapması hedeflenmektedir.
4
BÖLÜM 1. ÜRETİM ÇİZELGELEME
Çizelgeleme, bir çok üretim ve servis endüstrisinde kullanılan temel bir karar verme
prensibidir. Verilen zaman süresi (periyodu) içinde kaynakları işlere paylaştırır ve bir
ya da daha fazla amacı optimize etmeyi amaçlar (Pinedo, 2008: 1). Üretim
çizelgeleme, imalat işletmelerinin üretim planlamasının önemli bir bölümünü
oluşturur ve prosesler açısından önemli bir karar verme problemidir.
İşletmelerin günümüz ekonomisinde rekabet edebilmeleri hatta hayatta kalabilmeleri
için müşteri taleplerine hızla cevap verebilmeleri bir zorunluluktur. Sipariş
gecikmelerinden kaynaklanan müşteri kayıpları işletmeler açısından istenmeyen ve
önlenmesi gereken önemli bir konudur. Çizelgeleme yapılır iken işletmeler
tarafından belirlenen amaçlar da bu doğrultuda pek çok faklı şekilde olabilirler. Bir
amaç son işin tamamlanma süresinin en küçüklenmesi olabilirken, bir başkası ise
teslim süresinden sonra tamamlanan yani geciken işlerin sayısının minimize edilmesi
olabilir. Aynı şekilde iş yükü dengesinin sağlanması da bir başka amaçtır. İşlerin
makinelere mümkün olduğunca dengeli bir şekilde dağıtılması ile darboğazlar
elimine edilebilir, çıktı miktarı maksimize edilebilir ve bitmiş ürün stoklarının ve
üretim maliyetlerinin de azaltılması sağlanabilir. (Rajakumar, Arunachalam,
Selladurai, 2004: 366).
Çizelgeleme; üretim çevrim süresi, kaynak kullanım oranı, stok miktarı, ve teslim
tarihi arasındaki dengeleri içerir. Bu dengenin sağlanması amacıyla yapılan
çizelgeleme elbetteki bütün unsurları aynı anda iyileştiremez. Çünkü amaçlar çoğu
zaman birbirleri ile çatışırlar (Küçük, Keskintürk, Yıldırım: 2008, 54).
Bir üretim sisteminde, tamamlanma süresinin minimuma indirilmesi üretim kontrolü
açısından arzulanan bir durum iken, maksimum gecikmenin minimize edilmesi ise
müşteriler tarafından talep edilir (Mohri, Masuda, Ishii, 1999: 530). Üretim birimi ve
müşteri tarafından gelen bu iki talebin de karşılanması üretimi yapan işletmenin
sorumluluğudur.
5
Wight (1984)’ e göre; Üretim çizelgelemenin iki temel problemi “öncelikler” ve
“kapasite” dir. (Diğer bir ifade ile hangi işi önce yapmalıyım ve söz konusu iş hangi
kaynak tarafından yapılmalı, hangi operasyon ne zaman başlamalı ve ne zaman
tamamlanmalı sorularına cevap aranmaktadır.
Bir işletmede sahip olunan kaynaklar; bir fabrikadaki makineler, bir santral
inşaatında çalışan işçiler, hava alanındaki pistler gibi çok faklı şekillerde olabilir.
İşler ise, üretim prosesindeki operasyonlar, santral inşaatının aşamaları ya da hava
alanındaki uçakların iniş ve kalkışları vs. olabilir. Her bir iş belirli bir öncelik
düzeyi, mümkün olan en erken başlama zamanı ve teslim süresine sahip olabilir.
Üretim
Çizelgeleme
hikayesi,
Hennry
Gantt
tarafından
geliştirilen
ilk
çizelgelemelerden, gelişmiş/kompleks algoritmalara içeren gelişmiş çizelgelere kadar
uzanır (Herrmann, 2006: 2).
Henry L. Gantt, üretim kontrolü için şemalar geliştirmiştir. Cox ve arkadaşlarına
göre (1992) Gantt şeması; planlanan performans ile gerçekleşen performans
arasındaki ilişkiyi grafik olarak göstermek üzere dizayn edilen ilk ve en çok bilinen
kontrol şemasıdır (Herrmann, 2006: 5).
Gantt (1919) şemalarına iki esas amaç yüklemişti:
1- Aktivitelerin tamamlanması için gerekli olan toplam zamanı ölçmek,
2- Şema üzerinde yer alan mesafeleri ve aktivitelerin tamamlanacağı süreleri
göstermek.
İyi bilinen üç çeşit Gantt Şeması; Yükleme, Yerleşim ve Proje Gantt şemalarıdır.
Esasen Gantt Şeması bir Bar Şemasıdır. Şemada yatay eksen süreyi, dikey eksen ise
ilgili aktiviteler, makineler, çalışanlar ya da diğer kaynakları gösterir. Barlar yani
çubuk diyagramlar, yükleme süreleri veya aktivitelerin başlama ve bitiş sürelerini
göstermek için kullanılır.Gant Şeması kompleks çizelgelemeyi açıklayan görsel bir
özettir. (Nahmias, 2001: 324)
6
Üç çeşit Gant Şeması da temelde benzerdir, uygulamada bazı farklılıklar gösterirler.
En popüler Gant Şeması Proje şemasıdır ve projenin içerdiği aktivitelerin başlama ve
bitiş sürelerini göstermek için kullanılır. Projede meydana gelebilecek gecikmeleri
takip etmek için kullanılabilir. Ancak Gant şeması işlemlerin başlangıç ve bitiş
sürelerini göstermekle birlikte işlemlerin öncelik ilişkilerini göstermez. Daha
sonraları geliştirilen Kritik Yol Metodu (CPM) ve Proje Değerlendirme ve Gözden
Geçirme Tekniği (PERT) öncelik ilişkilerini göstererek bu eksikliği gidermiştir.
Şekil 1 Gant diyagramı
Kritik Yol Metodu (CPM) ve Proje Değerlendirme ve Gözden Geçirme Tekniği
(PERT) 1950’ lerin sonunda geliştirilmiş iki metotdur. CPM , Dupont ve UNIVAC
tarafından geliştirilmiştir. CPM’ in geliştirilme amacı, başlangıçta, kimya
fabrikalarında bakım için oluşacak durmaların programlanmasıdır (Shtub, Bard,
Globerson, 1994: 305).
PERT tekniği ise bilim adamları tarafından ABD Deniz Kuvvetleri’ nin Polaris füze
programında uygulanmak üzere geliştirilmiştir (Tütek, Gümüşoğlu, 2000: 285).
Her iki teknik de geliştirildikleri günden bu yana geniş bir kullanıma sahiptirler. Söz
konusu metotlar öncelik ilişkilerini içeren diyagramlar kullanarak işlemler arası
koordinasyonun planlanması ve uygulanmasına yardımcı olmaktadırlar (Hillier,
7
Lieberman, 2001: 468). İşlemler arasındaki ilişkileri göstermek için ok diyagramlar
kullanılmaktadır.
Kritik Yol Metodu’ nda işlem süreleri kesin olarak verilirken, PERT’ te ise süreler
olasılık içermektedir. İyimser, kötümser ve en olası süre olmak üzere üç farklı süre
söz konusudur. Verilen bu üç süre ile yapılan hesaplamalar ile işlemlere ait beklenen
süreler elde edilir. Bu yöntemlerde kullanılan çeşitli kavramlar vardır:
 Diyagram: Faaliyetlerin birbiri ile olan öncelik ilişkilerini göstermek için
kullanılan gösterim şeklidir.
 Faaliyet: İşi oluşturan işlemlerin her biri faaliyet olarak isimlendirilir.
Gösterim şekline göre ok ya da düğüm noktaları faaliyetleri ifade eder.
 Öncül faaliyet: Bir faaliyetin yapılmaya başlanabilmesi için kendisinden önce
tamamlanması gereken faaliyet öncül faaliyettir.
 İyimser süre: Faaliyetin sorunsuz şekilde ve en iyi şartlar altında
bitirilebileceği süreyi ifade eder.
 Kötümser süre: Oluşabilecek en kötü koşullar düşünüldüğünde faaliyetin
tamamlanabileceği süreyi anlatır.
 En olası süre: Uygun şartlar altında bir faaliyetin bitirilebileceği muhtemel
süredir.
 Beklenen süre: İyimser, Kötümser ve En olası süreler diKKOte alınarak
yapılan hesaplamalar sonucu elde edilen, gerçekleşmesi beklenen faaliyet
süresini ifade eder.
Her iki metotda da işlemlerin tamamının bitirilmiş olduğu süre hesaplanır ve bu süre
kritik faaliyetlerin süreleri toplamına eşittir. Kritik faaliyetlerin işlem süreleri toplamı
projenin toplam süresine eşit olduğundan bu faaliyetlerin herhangi birinde meydana
gelebilecek bir gecikme bütün projenin tamamlanma süresinin gecikmesine sebep
olacaktır. Projede yer alıp kritik faaliyetler arasında yer almayan işlemlerin ise bir
miktar gecikmeleri (projenin tamamlama süresini geçmeyecek şekilde) mümkündür
ve gecikebilecekleri bu süreler bolluk olarak adlandırılmaktadır.
8
CPM ve PERT’ in sağladığı asıl avantaj ise; çizelgeyi yani tamamlanma zamanını
kısaltacak şekilde paralel bir biçimde yapılabilecek işlerin saptanabilmesidir (Lewis,
2001: 256).
Her iki yöntemde de işlem süreleri ve öncelik ilişkilerine göre oluşturulan
diyagramlar yardımı ile çizelgeleme yapılır. Günümüzde kullanılan yazılım paketleri
genelde CPM ve PERT’ in önemli özelliklerini içermektedir.
2
9
3
1
7
9
4
5
8
Şekil 2 Öncelik diyagramı
Çizelgeleme problemlerinin çözümüne ilişkin olarak pek çok yöntem geliştirilmiştir.
Geliştirilen yöntemleri Sezgisel ve Analitik yöntemler olarak iki gruba ayırabiliriz.

Sezgisel Yöntemler: Bu yöntemler, belirli bir yordamın (prosedürün)
izlenmesi ve belirli varsayımların yapılması yoluyla, problemin çözümüne
yönelik yaklaşık sonuçlar verir.

Analitik Yöntemler: “Matematiksel Programlama Yöntemleri” olarak da
adlandırılırlar. En uygun sonucu verirler. Bu yöntemlerde kısıt ve amaç
denklemleri bulunur, özellikle işlem sayılarının arttığı durumlarda, çözüm
bulmak zorlaşmaktadır.
Çizelgeleme problemlerinde optimal çözümün bulunması zordur ve bu sebeple
genelde Sezgisel yöntemler ile çözüme gidilmeye çalışılır. Nispeten büyük hacimli
9
problemlerde optimale yakın çözümleri uygun sürede üretebilen çeşitli sezgisel
algoritmalar kullanılabilmektedir. Sezgisel algoritmalar basit sıralama kuralları
yanında , Genetik Algoritma, Karınca Koloni Algoritması, Tabu Araştırma Yöntemi
gibi çeşitli yöntemlerden oluşmaktadır.
Analitik yöntemler ise; dinamik programlama, lineer programlama, dal-sınır
algoritması gibi pek çok yöntem içermektedir. Analitik yöntemler kesin çözümler
üretir. Ancak bu yöntemler, büyük hacimli çizelgeleme problemlerinde etkin
çözümler yaratmada zayıf kalmaktadır.
Sezgisel yöntemlerin en basit olanları sıralama kurallarıdır. En sık kullanılan öncelik
belirlemeye yönelik yöntemler; En Kısa İşlem Süresi (SPT), En Uzun İşlem Süresi
(LPT), İlk Gelene İlk Hizmet (FCFS) ve En Erken Teslim Süresi (EDD)’ dir (Heizer,
Reinder, 2008: 612). Tüm bu yöntemler tamamlanma zamanını ve gecikmeleri
minimize etmeyi amaçlar. En erken teslim süresi’ ne göre yapılan sıralamada teslim
süresi erken olan işin ilk önce yapılması söz konusudur. En Uzun İşlem Süresi
yönteminde en uzun süreye sahip olan işin ilk olarak atanması söz konusu iken En
Kısa Süreli İşlem yönteminde ise kısa süreli işe öncelik tanınmaktadır. İlk gelene ilk
hizmet verme benimsenmiş ise işler üretim merkezine geliş sırasına göre makinelere
atanacaktır.
1.1. Makine Çizelgeleme
Makine çizelgeleme probleminin amacı, tüm işler için mümkün olan en az toplam
maliyeti ortaya çıkaracak çizelgenin bulunmasıdır (Ting, 2000: 1). Problemin
çözümünde, amaç fonksiyonuna uygun şekilde işlerin makinelere atanması
hedeflenmektedir. Makine çizelgeleme probleminin çözümüne yönelik pek çok farklı
yaklaşım mevcuttur (Rajakumar, Arunachalam, Selladurai, 2006: 240).
Çizelgeleme problemi  /  /  olarak ifade edilmektedir.  makine ortamını, 
prosesin özelliğini ve kısıtları,  ise minimize edilecek amacı ihtiva eder.
10
: iş sayısını,
n
m
: makine sayısını,
i , j  :
j
işinin
p 
İşlem süresi
;
ij
gereken süredir.
j
i
makinesinde işlem göreceğini belirtir.
j
işinin
i
makinesinde göreceği işlemlerin tamamlanması
işinin işlem süresi
i
makinesinden bağımsız olabileceği gibi,
işinin yalnızca belirli bir makinede işlem görme zorunluluğu da olabilir.
j
Hazır olma süresi
r  ; j
işinin sisteme gelip prosese girebileceği en erken süredir.
j
Bu süre öncesinde söz konusu iş işlem görmeye başlayamaz.
Tamamlanma süresi
d  ; j
j
işinin tamamlanması taahhüt edilen süredir.
Tamamlanma süresinin aşılması durumunda ceza oluşur.
C
ij
,
işinin
j
i
makinesinde işlem gördüğü süreyi ifade etmek üzere,
sistemden çıkış süresi
L C d
j
Ağırlık
j
j
C
j
dir.
j
j
işinin
işinin gecikmesi durumu;
olur.
w  ; j
j
işinin sistemdeki diğer işlere göre önem derecesini, önceliğini
gösterir. İşin ağırlığı ihtiva ettiği elde bulundurma ya da stok maliyeti vs.’ den
kaynaklanabilir.
Problemi genel olarak tanımlayacak notasyon ve varsayımlara bakar isek;
11
N
sayıda iş vardır ve her bir iş prosese girmek üzere 0 anında hazır beklemektedir.
Makine ortamında bir ya da birden çok makine yer alabilir. Tek makineli bir problem
söz konusu ise tek bir makine var iken paralel makineler için birden çok sayıda
makine vardır. Makinelerin de işler gibi 0 anında iş görmeye hazır olduğu, tüm
makinelerin uygun olduğu varsayılır.
Rastlanılabilecek makine çeşit ve özelliklerine   bakıldığında çok sayıda kavramla
karşılaşırız. Tek makine, özdeş paralel makineler, benzer paralel makineler,
birbirinden bağımsız paralel makineler şeklinde pek çok farklı sistem mevcuttur.
Tek makine 1 : Tek makineli bir üretim sistemi söz konusudur. Tek makine ortamı
diğerlerine göre çok basit ve kendine özgüdür.
Özdeş paralel makineler
 P  : Sistemde m
m
sayıda paralel makine mevcuttur.
Sisteme gelen işlerin uymaları gereken bir öncelik kuralı, tamamlanmasını
beklemeleri gereken herhangi bir iş yok ise işler paralel makinelerden herhangi
birinde işlem görebilirler.
Benzer paralel makineler
Q  : Birbirinden farklı hızlara sahip paralel makineler
m
işlem yapmaktadır. Her bir makinenin hızı
işlem gördüğü
p
ij
süresi
p
v
j
v
i
ile gösterilir.
j
işi
i
makinesinde
’ te eşit olur ve bu durumda benzer makineler söz
i
konusudur. Tüm makinelerin aynı hıza eşit olması durumunda
v
i
değeri 1’ e eşit
olacaktır ve bu durumda özdeş paralel makinelerden söz edilir.
Birbirinden bağımsız paralel makineler
birbirinden farklı makine vardır.
j
işi
i
R  :
m
makinesinde
Paralel şekilde
v
ij
m
sayıda
hızı ile işlem görebilir ve
12
işlem süresi
p
v
j
olarak gerçekleşir. Makine hızlarının tüm işlerden bağımsız olması
ij
durumunda makine hızı
v
ij
yerine
v
i
olarak ifade edilir.
Prosesin özelliğini ve kısıtlarının ifade edildiği  ortamına ait parametrelerin
bazıları şu şekildedir:
Öncelik sırası kısıtı
 prec  : Hem tek hem de paralel makinelerde görülebilen bu
kısıt, bir işin prosese girebilmesi için kendisinden önce tamamlanması gereken iş ya
da işleri ifade eder. Kendisinden önce tamamlanması gereken ya da kendisini takip
etmesi gereken yalnızca bir iş olabileceği gibi birden çok iş de olabilir ve birden çok
iş olması durumunda zincir ifadesi kullanılır.
İşlemin yarıda kesilebilmesi
 prmp  : İşin işlem görmeye başladığı makinede
tamamlanma zorunluluğu yoktur. Makine operatörü farklı önceliklere göre işlemi
yarıda kesebilir. Yarıda kalan işlem aynı makinede işlem görmeyi bekleyebileceği
gibi diğer makinelerden birinde de işlem görmeye devam edebilir. İşin yarıda
kesilebilmesi kısıtı konulabileceği gibi işler yarıda kesilemez kısıtı da konulabilir.
Hazırlık zamanına bağlı sıralama
s 
jk
: Bir işlem bitirilip diğer işlemin
yapılmaya başlaması arasında bir hazırlık süresi söz konusu olabilir.
işi arasındaki hazırlık süresini gösterirken,
s
0k
s
jk
j işi ile k
ise sisteme ilk iş olarak girecek olan
k işinin hazırlık süresi gerektirmediğini gösterir. İki işlem arasındaki hazırlık zamanı
makineye bağlı ise notasyon
Arızalar
brkdwn  :
s
ijk
şeklini alır.
Makine arızası meydana gelip o makinenin sürekli
kullanımının mümkün olmaması durumudur.
13
Makine uygunluk şartı
M
j
: Paralel makineler söz konusu olduğunda makine
uygunluk şartı gündeme gelir.
m
adet paralel makinenin tamamı
yapılması için uygun değil ise,
j
işinin işlem görebileceği makineler
gösterilir.  alanında
M
j
yer almıyor ise
işlem görebilir yani tüm makineler
Üretim süresi
j
j
M
j
ile
işini yapmaya uygundur.
max
Maksimum Gecikme
işinin
işi o anda boş olan tüm makinelerde
C : Tüm işlerin tamamlanarak,
süredir. max C ,..., C olarak ifade edilir.
1
j
son işin sistemden ayrıldığı
n
 L  : max  L ,..., L  şeklinde gösterilir.
max
Toplam Ağırlıklı Tamamlanma Süresi
1
n
  w c  : Toplam elde bulundurma veya
j
j
stok maliyetlerinin hesaplanmasına olanak verir.
1.2. Tek Makine Çizelgeleme
Tek makine çizelgelemede işler bir tek makine tarafından yapılır. Tek makineli bir
üretim ortamı diğerlerine göre çok basit ve kendine özgüdür. Uygulamada
çizelgeleme problemleri oldukça karmaşık makine ortamlarını ele alır ve sık sık tek
makinelerden oluşacak şekilde bileşenlerine, alt problemlere ayrılırlar (Pinedo, 2008:
35). Örneğin seri halde çalışan makinelerden oluşan bir üretim sisteminde tek bir
makine darboğaz yaratıyor ise söz konusu makinenin tek makine çizelgeleme
problemi olarak ele alınması gerekebilir.
Literatüre bakıldığında tek makine çizelgelemenin farklı amaç fonksiyonlarına göre
yapıldığı görülmektedir. Toplam ağırlıklı tamamlanma süresi, maksimum gecikme,
toplam gecikme, geciken işlerin sayısının minimize edilmesini amaçlandığı pek çok
çalışma vardır.
14
1.2.1. Toplam Ağırlıklı Tamamlanma Süresi
W
j
; j işinin sistemdeki diğer işlere göre önem derecesini göstermek üzere, toplam
ağırlıklı tamamlanma süresi
w C
j
j
olarak ifade edilir. Tek makine çizelgelemede
toplam ağırlıklı tamamlanma süresine göre çizelgeleme yaptığımızda amaç
fonksiyonumuz;
1║  w jC j
1: tek makine
w
j
: j işinin diğer işlere göre önemi
w C
j
j
: toplam ağırlıklı tamamlanma zamanı
Varsayımlar:

j işi t anında işlem görmeye başlıyor

j ve k işlerinin sırası birbirleri ile değiştirilebilir

Diğer bütün işler mevcut sıralarını koruyacak
Sıralama j-k şeklinde ise çizelge S , sıralama k-j ise çizelge
S
|
olarak
adlandırılsın. Çizelgelere ait şekil aşağıda gösterilmiştir (Pinedo, 2008: 37).
çizelgesi
S
J
k
t
t
|
S çizelgesi
k
p p
j
k
j
Şekil 3 İşlerin yer değiştirmesi durumu
15
için toplam ağırlıklandırılmış tamamlanma zamanı;
S
t  p  w  t  p  p  w ,
j
j
j
k
k
|
S için toplam ağırlıklandırılmış tamamlanma zamanı;
t  p  w  t  p
k
k
w w
p p
i
k
j
k
k

p w
j
j
dir.
ise ağırlıklı tamamlanma süreleri toplamı
S
|
için
S
’ den küçük
olacaktır.
1.2.2. Maksimum Gecikme
Maksimum gecikme modeli teslim süresi ile ilişkili amaçlardan biridir. Problem;
1 | prec|h
h
max
 max
h,j
j
max
şeklinde ifade edilir.
 h C  ,..., h C 
1
1
n
n
 1,..., n maliyet fonksiyonunu gösterir.
Taahhüt edilen tamamlama ya da teslim süresine uyulmadığı durumda ceza maliyeti
söz konusu olacaktır. Teslim süresine bağlı olarak geliştirilen üç temel ceza
fonsiyonu; Gecikme, Pozitif gecikme ve Birim ceza maliyeti’ dir.
 d  j işinin tamamlanma taahhütü verilen süredir. Bir işin teslim
süresini aşması durumunda  c  d  ceza maliyeti oluşur.
Teslim süresi
j
j
J
j
işinin;
16

Gecikme miktarı; L j  C j  d j pozitif ise j işi gecikmiş, negatif ise erken
tamamlanmıştır.

Pozitif gecikme’ yi;
T
j
 max
C  d , 0  max  L , 0 dır. T negatif
j
j
j
değer alamaz.

Birim ceza maliyeti ;
U

 C j  d j ise;1


j

 değil ise 0





Belirtilen öncelik kısıtıne uygun olarak ya da rastgele bir biçimde işler sıralanıp
işlem görmeleri durumunda son işin tamamlanma durumu;
C
max
  p ile ifade
j
edilir.


Çizelgelenmiş işler; C max   p , C max  zaman aralığında işlem görmüş demektir.
j

J
; tamamlanmış işleri,
bileşeni olup

jJ
J
c
çizelgelenecek işleri gösterir.
J
|
ise
J
c
’ nün alt
iş setinden sonra çizelgelenmesi gereken işleri içerir. Yani
J
|
J,
tamamlanmış işler göz önüne alınarak, çizelgelenmesi mümkün olan, öncül işleri
tamamlanmış olan işlerden oluşur.
Algoritma adımları: (Maksimum maliyeti minimize etme)
1. Adım:
J
2. Adım:
j
 , J  1,..., n
c


h j   c
 k J


j

yi işleme sok
p
 

  min  h j  
k
| 

c
jJ

  k J
yi yapılmış işlere yani
p


k 

J
listesine ekle,
17

j

J

c
yi yapılacak işlerden ( J setinden) sil,
|
nü çizelgelenebilecek işler setini gösterecek şekilde yeniden
düzenle.
3. Adım:
J
c
  ise atama işlemini durdur, değil ise 2. Adıma git
Yapılan çizelgelemede
tamamlanma
j
maliyetini

işi
j

işinden önce yapılmış ve bu çizelge minimum
sağlayamamış
ise
j

işinin
j

işinden
sonra
çizelgelenmesi sağlanarak maksimum tamamlanma maliyeti düşürülür.
1 || L
problemi,
max
1 | prec|h
max
probleminin
en bilinen özel durumudur.
(Pinedo; 2008)
h
j
fonksiyonu
C d
j
j
olarak ifade edilir ve algoritma işlerin teslim sürelerine göre
küçükten büyüğe doğru sıralanmalarını sağlar. En erken teslim süresine (EDD) sahip
olan iş ilk önce yapılır .
1.2.3. Geciken İşlerin Sayısı
Teslim süresi ile ilgili bir diğer amaç
1|| U
j
U
j
’ dir.
olarak tanımlanan problem için optimal çizelgenin oluşturulması için
önerilen yöntem; teslim süresini karşılayan işler önce çizelgelenir, teslim süresini
karşılayamayan işler ise en son çizelgelenir mantığına dayanır.
İşler teslim süresine göre
d d
göre atamalar yaparak
iterasyon boyunca devam eder.
n
1
2
...d n şeklinde düzenlenir ve algoritma bu sıraya
18
J
c
: teslim tarihinden önce tamamlanması mümkün olan işleri,
J
d
: teslim tarihine kadar tamamlanamayacak işleri gösterir.
Algoritma adımları:
1. Adım:
2. Adım:
3. Adım:
J
 , J  1,..., n , ve
k
1
k
işini
J
k
işini
J
c
 p d
Değil ise;
d

setine ekle
c
setinden sil
ise 4. Adıma git
k
j
jJ
J
o ana kadar çizelgelenen tüm işleri göstermek üzere,

p  max  p  ise

j
j J

işini

işini
J
J
setinden sil
d
setine ekle
4. Adım:
J J
k  n ise DUR
değil ise k  k 1 yapıp 2. adıma git
k
19
Algoritmayı sözlü olarak ifade edecek olu isek:
 İşler teslim süreleri küçükten büyüğe doğru olacak şekilde sıralanır
 Sıraya göre birinci, ikinci işler çizelgelenir ve teslim süresi içinde tamamlanıp
tamamlanmadıkları kontrol edilir. Teslim süresi içinde tamamlandıklarında
üçüncü işe geçilir.
 Üçüncü iş de çizelgelendiğinde o ana kadar çizelgelenen her iş için toplam
proses süreleri hesaplanarak üçüncü işin de teslim süresine yetişip
yetişmediğine bakılır. Yetişmiş ise dördüncü işlemin çizelgelenmesine devam
edilir.
 Üçüncü iş teslim süresine kadar tamamlanamıyor ise o ana kadar
çizelgelenmiş olan üç iş arasında proses süresi büyük olan seçilir ve
çizelgeden silinir ve sona bırakılır.
 Aynı şekilde dördüncü işin dahil olduğu ve proses süresi büyük olan işin
silindiği yeni çizelgenin toplam proses süresi hesaplanır ve dördüncü iş teslim
tarihinden önce tamamlanabiliyor ise işleme devam edilir tamamlanamıyor
ise yine en büyük süreye sahip olan iş listeden silinir.
 Tüm işler bu işlemlere tabi tutulup liste sonuna gelindiğinde ve listeden
silinmiş olan işler de çizelgenin sonuna eklenir.
 Çizelgeden silinip en son tekrar çizelgeye eklenen işler geciken işlerdir ve bu
işlerin sayısı
U
j
’ yi gösterir.
1.2.4. Toplam Erken Tamamlanma ve Gecikme
Üretim yapan firmalar müşteri taleplerini zamanında karşılayamama sonucu oluşan
gecikme maliyetine önem verirler. Ancak unutulmamalıdır ki teslim tarihinden önce,
erken tamamlanan ürünler de bir maliyete sebep olurlar. Gecikme maliyeti;
sözleşmede belirtilen parasal cezalar, müşteri kaybı, müşteri memnuniyetsizliği gibi
durumları kapsarken işlerin erken tamamlanması ise depolama maliyeti, oluşabilecek
bozulma maliyeti ve kaçırılan fırsat maliyeti vb. olabilir. Bu sebeplerle işletmelerde
asıl istenen işlerin teslim sürelerine yakın zamanlarda tamamlanmasıdır. İşlerin erken
20
veya
geç
tamamlanmasının
cezalandırıldığı
çizelgeleme
modeli
Erken
Tamamlanma/Gecikme (E/G) çizelgeleme problemi olarak tanımlanır (Toksarı,
2008: 1).
j
işinin erken bitirilmesi;
E  max  d  C , 0  dır.
j
j
j
Amaç fonksiyonu;
n

j 1
Ej
n
T
j 1
j
E/G problemlerinin bir kısmında teslim süreleri aynı, bir kısmında ise farklı teslim
süreleri söz konusudur. Burada tüm işlerin teslim sürelerinin aynı olduğu problem
yapısını ele alınmaktadır. Yani tüm
C d
j
j
işleri için
d
j
 d ’ dir.
’ yi sağlayan işler teslim süresinden önce tamamlanan işleri ifade eder iken,
bunun dışında kalan işler ise vaktinde tamamlanamayan işlerdir.
Algoritma:
1. Adım:
T d
k1
1
veT 2  
p d
j
2. Adım:
T T
1
T
1
’i
2
ise, k işini çizelgede dolu olmayan pozisyonlardan ilkine yerleştir ve
p
k
kadar azalt,
21
T T
1
2
ise, k işini boş pozisyonlardan sona yerleştir ve
T
2
’ yi
p
k
kadar
azalt.
3. Adım:
k n ise, k
’ yı 1 arttır ve 2. Adıma git,
k  n ise, DUR
1.3. Paralel Makine Çizelgeleme
Paralel makine çizelgeleme geçen on yıl boyunca araştırmacılar tarafından yoğun
biçimde çalışılmıştır. Birden fazla makinenin çizelgelenmesi yalnızca sıralamayı
değil, kaynakların paylaştırılmasını ve sıralamasını içerir (Rajakumar, Arunachalam,
Selladurai, 2004: 367). İşlerin makinelere paylaştırılması; öncelik, makinenin
uygunluğu, dengeli iş yükü gibi çok sayıda faktöre bağlıdır.
Genel görüşe göre paralel makine problemleri tek makine problemlerine göre
oldukça zordur. Çünkü hem her bir makinedeki işlerin kendi aralarında sıralanması
gerekir hem de işlerin birden fazla makineye paylaştırılması söz konusudur (Biskup,
Herrmann, Gupta, 2008: 134).
Paralel makine çizelgelemede temelde ele alınan üç amaç; üretim süresinin, toplam
tamamlanma süresinin ve maksimum gecikmenin minimize edilmesidir. Tek makine
çizelgelemede üretim süresinin minimize edilmesi amacı genellikle yalnızca hazırlık
zamanlarına bağlı bir sıralama oluşturulması ile sağlanıyordu. Diğer taraftan üretim
süresi işlem sürelerinin toplamına eşitti ve sıralamadan bağımsız idi. Paralel makine
çizelgeleme ile birlikte üretim süresi kayda değer bir amaç haline geldi (Pinedo,
2008: 112).
22
Paralel makine çizelgeleme problemlerinde genel olarak verilmesi gereken iki karar
vardır. Birincisi; işlerin makinelere atanması, ikincisi ise her bir makinede yapılacak
işlerin sıralamasının belirlenmesidir (Shim, Kim, 2007: 135 ).
Rajakumar ve arkadaşları (2004) yaptıkları çalışmada, paralel makine çizelgelemede
iş sırasının belirlenmesi için üç farklı öncelik stratejisini kıyaslamışlardır. Rastgele,
En kısa işlem süresine öncelik tanıma ve En uzun işlem süresine öncelik tanıma
yöntemlerini kullanarak,
n  50
iş ve
m  2,3,4,5,6 makine sayıları için ayrı ayrı
çizelgeleme yapmış lardır. C++ ile ele aldıkları problemlerde En uzun işlem süresine
öncelik tanıma yöntemine göre yapılan çizelgelemenin diğer yöntemlere göre daha
iyi sonuç verdiğini, iş yükü dengesini sağlamada daha başarılı olduğunu tespit
etmişlerdir.
Shim ve Kim (2007) Dal Sınır algoritmasını kullanarak özdeş paralel makineleri
çizelgelemiştir. Toplam gecikmeyi minimize etmeyi amaçladıkları çalışmada rastgele
yaratılan test problemlerini kullanmışlardır. Yapılan hesaplamalar sonucunda,
önerilen algoritmanın 30 iş ve 5 makineye kadar olan problemlerde optimuma yakın
sonuçlar yaratacağı saptanmıştır.
Paralel makineli bir üretim ortamında sıra bağımlı ve bağımsız işlerden oluşan farklı
örnekler için toplam tamamlanma zamanını minimize etmeye çalışan Silva ve
arkadaşları (2002) önerdikleri Karınca algoritmasının ele aldıkları örneklerde
oldukça başarılı sonuçlar yarattığını söylemişlerdir.
Sankar ve arkadaşları 2005 yılında yaptıkları çalışmada Silva ve arkadaşlarının
çalışmasında yer alan problemi ele almışlardır. Silva va arkadaşlarından farklı olarak
Lokal arama içeren karınca koloni optimizasyon algoritmasını kullanmışlar ve daha
başarılı sonuçlar elde etmişlerdir.
Min ve Cheng
1999 yılında yaptıkları çalışmada paralel makinelerde toplam
tamamlanma zamanını genetik algoritma ile ele almışlardır. Genetik algoritma ile
23
elde ettikleri sonuçları benzetilmiş tavlama yöntemi ile elde ettikleri sonuçlar ile
karşılaştırmışlar ve genetik algoritmanın daha iyi sonuçlar yarattığını saptamışlardır.
Azizoğlu ve Kırca 1998 yılında yayınlanan çalışmalarında
m
adet özdeş paralel
makine için toplam gecikmeyi minimize etme amacı ile Dal Sınır algoritması
kullanmış, 15 işe kadar olan problemlerde optimal sonuçlar elde etmişlerdir. Farklı
hızlardaki paralel makinelerin yer aldığı sistemlerin özelliklerine de yer verdikleri
çalışmada önerdikleri algoritmanın sözkonusu makinelerin yer aldığı sistemler için
de geliştirilebileceğini öne sürmüşlerdir.
Zouba ve arkadaşları (2009) literatürde az sayıda rastlanan bir problem olan insan ve
makine kaynağının eş zamanlı olarak çizelgelenmesi konusunu ele almışlardır.
Makine operatörü sayısının makine sayısından az olduğu sistemde toplam
tamamlanma zamanını minimize etmeye çalışmışlardır.
Toplam akış süresini minimize etmeye çalışırken işlerin ortak bir teslim süresine
göre erken ve geç bitirmelerini de ceza maliyeti olarak değerlendiren Su (2009) her
iki ceza maliyetini eşit kabul ederek toplam maliyeti de en aza indirmeye çalışmıştır.
Erken geç tamamlanma çizelgeleme problemleri ilk olarak Baker ve Scudder (1990)
tarafından çalışılmıştır. Erken ve geç bitirme maliyetleri ile çalışılan çizelgeleme
problemlerine bakıldığında söz konusu maliyetlerin dört farklı şekilde ele alındığı
görülmektedir. Bunlar; işe bağlı olarak değişen erken ve geç tamamlanma
maliyetinin olduğu, erken ve geç tamamlanma durumuna göre faklı ceza
maliyetlerinin gerektiği, her iki maliyetin de eşit olduğu ve işin ağırlığı ile orantılı
ceza maliyetinin olduğu problemlerdir. Baker ve Scudder (1990), Zhu ve Heady
(2000), Bank ve Werner (2001) erken ve geç tamamlanma maliyetlerini işe bağlı
olarak ele almışlardır. Arkin ve Roundy (1991), Sun ve Wang (2003)’ ün
çalışmalarında ise işin ağırlığı ile orantılı ceza maliyetleri kullanılmıştır.
Paralel makinelerde erken ve geç tamamlanma problemini ele alan Toksarı ve Güner
(2009) öğrenme ve bozulma etkileri altında yaptıkları çizelgeleme ile 1000 adet iş ve
4 adet makine yer alan bir problemi çözmüşlerdir.
24
Hazırlık zamanı ve teslim süresine bağlı olarak birbirinden bağımsız paralel
makinelerin yer aldığı bir üretim sistemine ait problemi Benzetilmiş tavlama yöntemi
ile çizelgeleyen Chen (2009) toplam gecikmeyi minimize etmiş ve olumlu sonuçlar
elde etmiştir.
Heady ve Zhu 1998 yılında özdeş paralel makine çizelgelemeyi sıraya bağımlı
hazırlık zamanı kısıtı ile birlikte ele almış, tamsayılı programlama ile erken-geç
tamamlanma zamanı toplamını minimize etme amacı ile küçük problemlerde
algoritmanın performansını ölçmüşlerdir.
İşin yarıda kesilmesine izin verilmeyen, özdeş paralel makinelerden oluşan bir üretim
ortamının konu edildiği problemde toplam gecikmeyi minimize etmek amacı ile Dal
Sınır algoritmasını kullanan Yalaoui ve Chu (2002) rastgele oluşturdukları test
problemleri ile algoritmayı test etmişlerdir.
Tabu arama, benzetilmiş tavlama ve komşuluk arama yöntemlerinin pek çok
özelliklerini bir araya getirerek yeni bir melez metasezgisel yöntem geliştiren
Anghinolfi ve Paolucci (2007) paralel makinelerde toplam gecikmeyi minimize
etmeyi amaçlamışlardır.
Emmons 1987 yılındaki çalışmasında özdeş paralel makine problemini ele almış,
konumsal ağırlık algoritmasını uyguladığı çalışmada işlerin ortak teslim süresine
sahip olduğunu varsaymıştır.
Li ve Cheng (1994) birbirinden bağımsız paralel makine problemine maksimum
mutlak gecikmeyi minimize etme amacına yönelik olarak çözüm getirmişlerdir.
Ting 2000 yılında yaptığı çalışma ile Baker ve Scudder’ ın 1990 yılındaki
çalışmasına benzer şekilde paralel makine problemlerini, farklı problemler için
geliştirilmiş farklı amaç fonksiyonlarını gösterir şekilde Tablo 1’ deki gibi
özetlemiştir.
25
Tablo 1 Amaç fonksiyonuna göre geçmiş çalışmalar
Amaç
n
C
j
j 1
d
   d  C


j

j

n
j 1
   d  C
n
j 1
n
w
j 1

 d
Cj
j

 
j

C
d
j
  C

j
j
  C



j 1 


n



d 



d


j
j



d 

Kaynak
Kanet (1981), Emmons (1987)
Kolay
( d büyük
ise)
Kolay
Bagchi, Chang ve Sullvan
(1987, Emmons (1987)
NP-zor
Hall ve Posner (1991)
Hall, Kubiak ve Sethi (1991),
Hoogeveen and van de Valde
(1991),
Hoogeveen,
Oosterhout ve van de Valde
(1994), Swarz (1989)
Panwalkar,
Smith
ve
Seidmann (1982), Bagchi,
Julien ve Magazine (1994)
Kolay
Ahmed ve Sundararaghavan
Alidaee ve Dragan
w j / p j  r (1990),
(1997)
ise
NP-zor
Dileepan
(1993),
Szwarc
(1996), van den Aker,
Hoogeveen ve van de Velde
(1997), Chai, Lum ve Chan
(1997)



d
j

NP-zor
Gupta ve Sen (1983), Fry,
Amstrong
ve
Blackstone
(1986), Garey, Tarjan ve
Wilfong (1988), Yano ve Kim
(1991), Davis ve Kanet (1993),
Szwarc (1993)



NP-zor
Bagchi, Sullivan ve Chang
(1987), De, Ghosh ve Wells
(1990), Hall ve Kubiak (1991),
Kubiak (1993), Weng ve
Ventura (1996), Chai (1996),
Manna ve Prasad (1997)




d
;

C j C 
Cj


2




d
j

 d  C    C
 d

Cj

j 1 
n

C

n
j 1

Açıklama
Kolay
( d büyük
ise)
NP-zor ( d
küçük ise)
2
26
1.3.1. Paralel Makine Çizelgeleme Problemi
Paralel makine çizelgeleme problemi Pm║Cmax olarak ele alınır. Makinelerin iş
yükü dengesini etkileyeceği için üretim süresinin minimizasyonu ile ilgilenir.
P || C
2
max
problemleri
ve P 2 ||  wC
i
i
NP _ hard
olarak nitelendirilir (Brucker,
2007: 106).
Paralel makine ortamını birbirinden bağımsız ve aralarında öncelik ilişkileri olan
işler olarak iki grup halinde inceleyebiliriz. Ele alınan işler birbirinden bağımsız
olabileceği gibi, aralarında öncelik ilişkisi olan işler de olabilir.
 Birbirinden bağımsız işler
Birbirinden bağımsız olan yani aralarında herhangi bir öncelik ilişkisi olmayan
işlerin yer aldığı paralel makine problemleridir. Birbirinden bağımsız işler farklı
paralel makine türleri için o sistemlere ait unsurlar, özellikler diKKOte alınarak
çizelgeleme işlemi yapılır.
 Öncelik kısıtı olan işler
Aralarında öncelik ilişkisi bulunan
j
 1,..., n olmak üzere
n
sayıda iş mevcuttur.
Çizelgelenecek ilk iş önceliği olmayan işlerden biri olmalıdır. Daha sonra
çizelgelenecek işler ise kendisinden önce tamamlanması gereken iş yani öncülü
tamamlanmış olan işlerdir. Öncelik kısıtı olan işler öncelik ilişkilerine riayet edilerek
paralel makinelere atanır.
1.3.2. Paralel Makine Çeşitleri
Paralel makineli ortamlarda özdeş, benzer ve birbirinden bağımsız paralel
makinelerden söz edilebilir.
27
 Özdeş makineler  P m 
Üretim sisteminde yer alan makineler aynı
işi yapan, aynı hıza sahip özdeş
makinelerden oluştuğunda Özdeş makine çizelgeleme probleminden bahsedilir.
p i
i
 1,..., n  işlem sürelerine sahip
n
sayıda işlemden her biri, sistemde yer alan
herhangi bir makinede işlem gördüğünde işlem süresi değişmez sabittir. Yani bir
işlem m adet özdeş makineden hangisinde işlem görürse görsün aynı işlem süresine
sahip olur.
Şekil 4 Paralel makine ortamını göstermektedir (Keskintürk, Küçük, 2008; 54).
Şekil 4 Paralel makine ortamı
 Benzer paralel makineler
n
Q 
sayıda işlem, birbirinden farklı
işlem görmektedir.
j
işi
m
m
v
i
hızlarına sahip
m
sayıda paralel makinede
makinesinde işlem gördüğünde
p / v ’ lik bir süre
i
j
gereklidir.
 Birbirinden bağımsız paralel makineler
Paralel şekilde
v
ij
m
R 
m
sayıda birbirinden farklı makine vardır.
hızı ile işlem görebilir ve işlem süresi
p
v
j
j
işi
i
makinesinde
olarak gerçekleşir. Makine hızları
ij
28
işlere bağlı olarak değişir. Bu sebeple farklı hızlara sahip paralel makinelerden
farklıdırlar. Makine hızlarının tüm işlerden bağımsız olması durumunda makine hızı
v
ij
yerine
v
i
olarak ifade edilir.
1.3.3. Hazırlık zamanına bağlı sıralama
Hazırlık zamanına bağlı sıralamanın söz konusu olduğu problemlerde sıralama
s 
jk
ile ifade edilir. Hazırlık zamanı makinede ard arda yapılan işlerin özelliklerine göre
bir işten diğerine geçerken yapılması gereken ayarlamalardan kaynaklanabileceği
gibi makinenin temizlenmesi, bakımı gibi sebeplerden de kaynaklanabilir. Ele alınan
çizelgeleme problemlerine bakıldığında pek çoğunda hazırlık zamanının ihmal
edildiği ya da hazırlık zamanlarının işlem sürelerine eklendiği görülmektedir. Ancak
bazı problemlerde hazırlık süreleri ihmal edilemeyecek kadar önemlidir va işlem
sürelerinden ayrı olarak değerlendirilmeleri gerekir. Hazırlık süreleri sıralamadan
bağımsız olabileceği gibi işlerin sırasına bağlı da olabilir. Kim ve Bobrowski (1994),
Behnamian, Zandieh ve Ghomi (2009) sıraya bağlı hazırlık sürelerinin olduğu
problemleri ele almış ve çizelgeleme yapmışlardır.
Bir işlem bitirilip ardından gelen işlemin yapılabilmesi için bir hazırlık süresi söz
konusu ise bu süre
s
jk
j işi ile gösterilir.
s
jk
k işi arasındaki hazırlık süresini ,
s
0k
ise sisteme girecek olan ilk k işinin hazırlık süresi gerektirmediğini gösterir. İki
işlem arasındaki hazırlık zamanı makineye bağlı ise gösterge
s
ijk
şeklini alır.
Hazırlık zamanı gerektiren tek makine problemlerine çeşitli sezgisel yöntemler, dalsınır algoritması, dinamik programlama, tamsayılı programlama gibi pek çok yöntem
ile çözüm getirilmiştir. Gascon ve Leachman (1998) çalışmalarında tek makine
çizelgelemeyi dinamik programlama ile çözmüşlerdir. Williams ve Wirth (1996) ise
sıra bağımsız hazırlık zamanlı tek makine problemi için yeni bir sezgisel yöntem
geliştirmişlerdir. Nazif ve Lee 2009 yılında yaptıkları çalışmada tek makineli
çizelgeleme problemini sıra bağımsız hazırlık zamanları ile birlikte ele almış, toplam
29
ağırlıklı tamamlanma zamanını minimize etmek amacı ile genetik algoritma
kullanmışladır.
Paralel makineli sistemleri ele alan çizelgeleme problemlerinde de hazırlık zamanına
bağlı olarak yapılan çalışmalar mevcuttur. Silva ve diğerlerinin 2002 yılında
yaptıkları çalışmada, hazırlık zamanı gerektiren paralel makineli bir problem toplam
tamamlanma zamanını minimize etme amacı ile ele alınmış ve Karınca kolonileri
optimizasyon algoritması ile probleme çözüm getirilmiştir. Sankar ve diğerleri(2005)
ise aynı çalışma verilerini kullanarak, yerel arama içeren karınca koloni algoritması
ile Silva ve diğerlerinin elde ettiği sonuçlardan daha iyi sonuçlar elde etmişlerdir.
Hazılık zamanı gerektiren özdeş paralel makine problemini ele alan Lee ve Pinedo
1997 yılında yaptıkları çalışmada toplam ağırlıklı gecikmeyi minimize etmek için üç
aşamalı sezgisel yöntem kullanmışlardır.
Hazırlık zamanı gerektiren problemleri Allahverdi ve diğerlerinin (2008)
çalışmalarında yaptıkları özet literatür tablosunu genişleterek Tablo 2 ve Tablo 3’ de
verebiliriz.
30
Tablo 2 Sıra bağımsız hazırlık süreli paralel makine problemleri
Amaç
Yaklaşım
Makine atıl zamanlarını minimize Demet
araması
etmek
yöntemi
Lee ve Pinedo (1997)
Benzetilmiş tavlama,
 w jT j
Sezgisel yöntemler
Kravchenko
ve Tamamlanma zamanını minimize Sezgisel yöntemler
Verner (1997)
etmek
Kravchenko
ve
Sahte-polinom
C max
Verner (1998)
algoritması
Schuurman
ve
Algortima
(önceliğe bağlı)
C
max
Woeginger (1999)
Glass ve diğerleri
Algoritmalar
C
max
(2000)
Hall ve diğerleri
,
,
,
C j, T j, Sahte-polinom-zaman
C
max L max  C j  w j
(2000)
algoritması
Kaynak
Koulamas (1996)
 w jT , U ,  w jU
j
j
Xing ve Zhang (2000)
Kravchenko
ve
Werner (2001)
Wang
ve
Cheng
(2001)
Abdekhodaee
ve
wirth (2002)
Brucker ve diğerleri
(2002)
C
C
Sezgisel yöntem
max
Sezgisel yöntem
j
 w jC
C
C
max
, L max,  C j,  w jC , T j,
j
 w jT , U ,  w jU
ve
C
max
ve
C
max
j
C
j
, L max,  C j,  w jC , T j,
max
Karmaşık sonuçlar
j
 w jT , U ,  w jU
ve
Yaklaştırma
algoritması
Tamsayılı
programlama,
sezgiseller
Spesifik vakalar için
yeni
karmaşık
sonuçlar
Sezgiseller
j
Abdekhodaee
diğerleri (2006)
Eren (2009)
j
max
j
Abdekhodaee
diğerleri (2004)
Guirchoun
diğerleri (2005)
j
j
j
Genetik algoritma
Toplam ağırlıklı tamamlanma Matematik
zamanı ve toplam gecikme
programlama modeli
Sıra bağımlı hazırlık süreli paralel makine problemleri Tablo 3’ de gösterilmiştir.
31
Tablo 3 Sıra bağımlı hazırlık süreli paralel makine problemleri
Kaynak
Tamimi
(1997)
Amaç
ve
Rajan
Yaklaşım
Genetik algoritma
 wT  Q 
j
i
Heady ve Zhu (1998)
Toplam Erken ve
tamamlanma maliyeti
Balakrishnan
diğerleri (1999)
w E  w T
ve
j
j
j
j
geç Sezgisel yöntem
Q, r 
Karışık
programlama
j
Sivrikaya, Şerifoğlu
ve Ulusoy (1999)
w  E  w T
Vignier ve diğerleri
Hazırlık maliyetlerini de Sezgiseller,
dahil
tüm
maliyetlerin algoritma,
minimizasyonu
algoritması
Park ve
(2000)
 wT
diğerleri
Radhakrishnan
Ventura (2000)
ve
j
E
i
Genetik algoritma
j
T
tamsayılı
genetik
dal-sınır
Sinir ağı ve sezgisel
yöntem
j
 E  T
j
Karışık
tamsayılı
programlama,
Benzetilmiş tavlama
j
w E  w T R 
Karışık
programlama
Gendreau ve diğerleri
(2001)
C
Sezgisel yöntem
Kurz ve Aşkın (2001)
C r
Silva ve
(2002)
diğerleri
C
max
Mendes ve diğerleri
(2002)
C
max
Fowler ve diğerleri
(2003)
C  w T   w C r
Kim ve Shin (2003)
L
Zhu ve Heady (2000)
j
j
j
j
max
max
max
max
tamsayılı
Tamsayılı programlama,
Gezgin satısı, Genetik
algoritma
j
Karınca
algoritması
koloni
Tabu arama algoritması
j
j
j
j
j
Genetik algoritma
32
Tablo 3 Sıra bağımlı hazırlık süreli paralel makine problemleri (devam)
Kaynak
Bilge ve
(2004)
Amaç
diğerleri
T Q , r
j
j

Anglani ve diğerleri Toplam hazırlık
(2005)
minimizasyonu
Sankar ve diğerleri
(2005)
C
max
Tahar ve
(2006)
C
max
Toksarı
(2008)
ve
diğerleri
Güner
Behnamian, Zandieh
ve Ghomi (2009)
Sezgisel yöntem
j
max
maliyeti Karışık tamsayılı lineer
programlama
Yerel aramalı karınca
koloni algoritması
T ,  E
C
Yaklaşım
j
Doğrusal
karışık
programlama
olmayan
tamsayılı
Karınca
koloni
optimizasyonu,
Benzetilmiş
tavlama,
Melez algoritma
1.3.4. Ortak Teslim Süresi’ ne Sahip Olan Paralel Makine Ortamının
Çizelgelenmesi
Hoogeveen ve Van de Velde (1991) in çalışmalarında yer verdikleri sınırlandırılmış
teslim süreli problemi ile bu tür problemlerin NP-zor yapıda problemler olduğunu
göstermişlerdir.
Bu tür problemler tam zamanında (JIT) üretimin ortaya çıkışı ile birlikte
araştırmacıların diKKOtini çekmeye başlamıştır (Lee, Lin ve Ying, 2008: 91). Tam
zamanında üretimin gereği olarak işlerin tam zamanında tamamlanması istenir iken
erken ya da geç tamamlanan işler maliyete sebep olur. Erken-geç tamamlanma
sebebi ile oluşan maliyetler problemin çözümünde ceza maliyetleri olarak
adlandırılır.
33
Ortak teslim süresine sahip işlerden oluşan makine çizelgeleme problemlerinde
erken-geç tamamlanma minimizasyonu problemini ele alalım.
n :birbirinden bağımsız işlerin sayısı
p :işlem süreleri, j 1,..., n
d : ortak tesli m süresi
j
Erkentamamlanma ; E  max d  C , 0 
Geçtamamlanma ;T  max C  d , 0 
j 1,..., n
j
j
j
j
Varsayım: İşlem görmeye başlayan işlem yarıda kesilemez
Amaç; x.x.’ in minimize edilmesi
Amaç Fonksiyonu;
  i max 0,d C i  imax 0,C i d 
n
i 1


j

j
j
: erken tamamlanma birim maliyeti
: geç tamamlanma birim maliyeti
:1,..., n
j
ve  birbirine eşit ceza maliyetlerine sahip ise ;
j
Problem; Toplam ağırlıklandırılmış erken-geç tamamlanma problemi (TWET)
adını alır.
Ortak teslim süresine sahip işlerin yer aldığı, toplam tamamlanma süresinin
minimize edilmesinin amaçlandığı çizelgeleme problemi ilk olarak Kanet (1981)
34
tarafından tek makineli sistemler için ele alınmıştır. Kanet’ in ele aldığı sisteme
göre,
1. İşlerin yarıda kesilmesine izin verilmez,
2. Her bir makinede ilk iş prosese girdikten sonra o makinenin işler arasında
boş beklemesi söz konusu değil. Makineler yalnızca ilk iş başlamadan önce
atıl kalabilir.
C
j 1
C j
p
j 1
3. Optimal çizelge V-şeklindedir.
Baker ve Scudder (1990)’ a göre; V şeklinde olması, teslim süresinden önce
tamamlananların En uzun işlem süresine (LPT) öncelik tanıyarak, teslim
süresinden sonra tamamlananların ise En kısa işlem süresine öncelik tanıma
(SPT) yöntemine göre sıralanacağını ifade eder.
4.
C  d iseişler proses sürelerine göre azalan sırada,
C  d iseişler prosessürelerine göre ar tan sırada çize lg elenir.
j
j
5. Optimal çizelgede bir iş tam olarak teslim süresinde tamamlanmalıdır.
E
setindeki işler teslim süresinden önce ya da teslim süresinde
tamamlanan işlerden,
T
setindeki işler ise teslim süresinden sonra tamamlanan işlerden
oluşmaktadır.
İlk işlemin prosese başlama süresini;
35
d   jE p j
formülü ile hesaplayabiliriz.
p Ej ; E setinde yer alan j. işin proses süresi,
pTj ;T
n
n
j. işin proses süresi.
setinde yer alan
E;
E setinde yer alan iş sayısı,
T;
T setinde yer alan iş sayısı olmak üzere,
Toplam erken tamamlanma;
 d
jE
n E1
nE
   p
C j 

j 1 k  j 1
E
k
 n E 1  p n   n  2 p
E
E
E
E
2
E
E
2
1
 ...  1 p  0 p
Toplam geç tamamlanma;

jT

C jd
j
n T 1
  p

j 1 k 1
T
k
 n T p   n T  1
T
1
p
T
2
 ...  1 p
T
nT
Amaç fonksiyonu;
n
C
j 1
 d  0 p 1 p 1 p  ...   n E  1 p
j
E
E
T
E
1
2
nT
nE
 nT p
T
1
36
6. Optimal bir çizelgede teslim süresinden önce çizelgelenen işlerin sayısı,
n
E
 n /2 
Kanet’ in algortiması:
J
c
: çize lg elenecek iş seti
1. E   ve T  
2. p  max
k
 p  olmak üzere k işini J
j
c
setinden al
3. k işini E sıralamasında ilk pozisyona yerleştir
4. J   ise
c
p
k
 max
 p  olmak üzere k işini J
j
c
setinden al
5. k işini T sıralamasında en son pozisyona yerleştir
6. J   ise 2. adıma git
c
7. E ve T sıralamalrınıbirleştir.
Ör:
p
1
n
 6 işten oluşan bir problemde yer alan işlerin süreleri;
 3, p  8, p  5, p  7, p  14, p  9 ve
2
Teslim süresi
3
d
4
5
6
 60 olmak üzere Kanet’ in algoritmasını kullanarak çizelgeleme
yapar isek;
E   5, 2,3
T   3, 4, 6  ve
çize lg enin başlama zamanı;
60  (14  8  5)  60  27  33 olur.
37
5
2
3
1
33
4
6
60
79
t
Şekil 5 Çizelgelenmiş iş sırası
Özdeş Paralel Makinelerde Ortak Teslim Tarihi
1.3.4.1.
Sundararaghavan ve Ahmet (1984) ve Hall (1986) çalışmalarında özdeş paralel
makinelere yönelik sisteme göre optimal çizelge;
1. Makinelerde işler arasında boş bekleme söz konusu değildir. Makineler
yalnızca ilk iş başlamadan önce atıl kalabilir.
C
j 1
C j
p
j 1
2.
C  d iseişler proses sürelerine göre azalan sırada,
C  d iseişler prosessürelerine göre ar tan sırada çize lg elenir.
j
j
3. Optimal çizelgede bir iş tam olarak teslim süresinde tamamlanmalıdır.
4.
m
sayıda makinenin her birine atanan işlerin sayısı n / m ya da n / m dir.
n ,i
j
i
makinesine atanan işleri göstermek üzere
makinesinde teslim süresinde
d
n /2
j
sayıda iş
tamamlanır.
Varsayım: İşler en uzun süresli işleme öncelik tanıma (LPT) kuralı gereğince proses
süresine göre büyükten küçüğe doğru sıralanır.
38
pp
1
2
 ... 
p
n
Sundararaghavan ve Ahmet’ in çalışmasında yer alan algoritmaya göre;
Algoritma:
1.
m
sayıda makine,
n
sayıda iş var. İşleri her bir makineye bir iş gelecek
şekilde ata. Atanacak iş sayısı
2m  n ise
n  n m
olur.
2.
sıradaki
2m sayıda işi ikişer ikişer
Atanacak yeni iş sayısı nn2m olur. 3. Adıma git.
3.
m n 2m ise
sıradaki
m
sayıdaki işi her bir makineye birer tane
olacak şekilde ata. Atanacak iş sayısı;
4.
0nm
makinelere ata.
n  n m
.
ise işleri makinelere ata. Bu durumda her bir makineye en fazla
bir iş yüklenmiş olur.
5. Amaç fonksiyonuna göre her bir makine için optimal sonucu bul.
  i max 0,d C i  imax 0,C i d 
n
i 1
Örnek: (Jozefowska, 2007: 65)
14 adet iş ve 3 adet makineden oluşan özdeş paralel makineli bir problemde işlerin
ortak teslim süresi 100’ dür. 14 işe ait proses süreleri aşağıda verildiği gibidir.
39
Sundararaghavan ve Ahmet’ in geliştirdiği algoritmaya göre optimal çizelgeyi
bulalım.
n14, m3, d 100
p  37, p  35, p  32, p  31, p
p  16, p  12, p  11, p  7, p
 27, p  23, p  21, p  19,
1
2
3
4
5
9
10
11
12
13
M :i
i
6
 5,
p
14
7
8
3
makinesine atanan işler seti.
1. Adım
İşleri her bir makineye birer tane gelecek şekilde sırası ile ata
Makine137 , Makine 235 , Makine 32
nnm n14311
2. Adım
2m n 2.3 n 6 n (n  11idi)
 2m sayıda işi makinelere ata
2m  2.3 6 iş
Mak1 31, 27
Mak 2 23, 21
Mak 319,16
n  n  2m n 11 6 5 iş
40
3. Adım
m n 2m ' euygun mu ?
35 6 mı ?  evet
 sıradaki m sayıda (3) işi her bir makineyebir iş gelecek şekilde ata
Makine1  12
Makine2  11
Makine3  7
4. Adım
Kalan iki adet işi makinelere birer birer ata
Makine1  5
Makine2  3
Tablo 4 Makinelere göre iş sıraları
n
n
n
 5iş
 5iş
 4iş
Makine1
Makine 2
Makine 3
İşler

1
4
5
10
13

2
6
7
11
14

3
8
9
12
5. Adım
İlk dört adımda hangi işlerin hangi makinelere atanacağını belirledik. Bu
aşamada ise makinelerdeki iş sıraları belirlenir.
Aşağıdaki amaç fonksiyonuna göre her bir makine için optimal sonucu buluruz.
  i max 0,d C i  imax 0,C i d 
n
i 1
41
Teslim süresi
d
100 olmak üzere Kanet’ in algoritmasını kullanarak çizelgeleme
yapar isek;
Makine1 için;
E  1,5,13
T  10, 4  ve
100  (37  27  5) 100  69  31 olur.
Makine 2
için;
E   2, 7,14 
T  11, 6  ve
100  (35  21  3) 100  59  41 olur.
Makine 3
için;
E   3,9 
T  12,8 ve
100  (32  16) 100  48  52 olur.
42
Tablo 5 Makinelere göre optimum iş sıraları
Makine1
Makine 2
Makine 3
M1
M2
M3

1
5
İşler
13
10
4

2
7
14
11
6

3
9
12
8
1
5
2
7
3
52
9
13
10
14 11
12
100
4
6
8
126
134
t
Şekil 6 Optimal çizelge
43
BÖLÜM 2. KLASİK ÇİZELGELEME YÖNTEMLERİ
Çizelgeleme problemlerinde, işlerin iş merkezlerine-makinelere atanması için temel
öncelik kuralları kullanılmaktadır. Öncelik kuralları üretim sisteminde yer alan
işlerin tamamlanma süresini ve gecikme miktarlarını minimize etmeyi ve etkinliği
maksimize etmeyi amaçlamaktadır (Heizer, Reinder; 2008: 612).
En çok kullanılan öncelik kurallarının bazıları:
 En uzun işlem süresine öncelik tanıma,
 En kısa işlem süresine öncelik tanıma,
 İlk gelene ilk hizmet,
 Teslim süresi yakın olana öncelik tanıma kurallarıdır.
2.1. En Uzun İşlem Süresine Öncelik Tanıma
En uzun işlem süresine öncelik tanıma yöntemi kısaca LPT olarak ifade edilirç Bu
atama kuralına göre; işler proses sürelerine göre büyükten küçüğe sıralanır ve
t
0
anında en uzun süreye sahip iş ilk olarak makinelerden birine atanır. Ardından, henüz
işlem görmeye başlamamış olan işlerden en uzun süreli olanı o anda işlem görmeyen
boş makinelerden birine atanır. Kısa süreli işler ise en sona bırakılır. Bu şekilde
makineler arasındaki iş yükü dengelenmeye çalışılarak maksimum tamamlanma
süresi de minimize edilmeye çalışılır.
LPT kuralına göre yapılan atamalarda en kısa süreli işlem en sona kalacaktır. En kısa
süreli işlemin prosese başlama zamanı:
C  LPT   p
max
n
olacaktır. Çünkü bu ana kadar tüm makineler meşgul
olacaktır.Yani,
44
 p
LPT




p
C
m
n 1
j 1
max
n
j
’ dir.
Formülün sağ tarafı, en kısa süreli işin prosese gireceği üst sınırı vermektedir. Üst
sınıra erişilmesi için, en kısa süreli işten önceki tüm işlerin
 n 1
LPT kuralına
göre makinelere atanmaları durumunda tüm makinelerin toplam proses sürelerinin
eşit olması gerekir.
Bu yöntem, her bir makineye atanan iş sayısının en çok iki olduğu küçük boyutlu
örneklerde optimal bir çizelge ortaya çıkarabilir ancak büyük örneklerde optimumu
yakalayamamaktadır ( Pinedo, 2008: 114).
2.2. En Kısa İşlem Süresine Öncelik Tanıma
SPT olarak ifade edilen bu atama kuralı en uzun işlem süresi kuralının tersi bir
yapıya sahiptir. Yani öncelikle kısa süreye sahip işler makinelere atanmaktadır. İşler
sürelerine göre küçükten büyüğe doğru sıralanır ve en kısa süreye sahip iş ilk olarak
makinelerden birine atanır. İlk işin atanmasından sonra yapılan atamalar da küçükten
büyüğe sıralanmış liste sırasına göre yapılır. Böylece uzun süreli işler en sona
bırakılmış olur.
en kısa süreli iş
en uzun süreli iş
Şekil 7 SPT kuralına göre iş sırası
Çizelgeleme problemleri için yapılan çalışmalar 1950’ lere dayanmaktadır. Toplam
tamamlanma zamanını minimize etmeye yönelik olarak yapılan çalışmalarda ilk
kullanılan atama kuralı en kısa süreli işe öncelik tanımadır. Smith 1956 yılındaki
çalışmasında SPT kuralını kullanmıştır (Baker, 2008:15).
SPT kuralı basit sıralama problemleri için uygun olabilir. Ancak uygulamada, uzun
işlerden birinin öncelikli olması gibi komplike durumlar söz konusu olabilir. Bu
durumda problemin yapısı ve kısıtlarına göre uygun çözüm yöntemi araştırılır.
45
2.3. İlk Gelene İlk Hizmet
Sisteme gelen işler geliş sıralarına göre ilk gelenden son gelen işe doğru sıralanır ve
işler geliş sıralarına göre sırası ile makinelerde işlem görmeye başlar. Bu kural tüm
müşteriler için uygun gözükmektedir ve bu sebeple çoğunlukla servis işletmelerinde
kullanılmaktadır (Weng ve Ren, 2006: 790).
2.4. Teslim Süresi Yakın Olana Öncelik Tanıma
Makinelere ilk atanan iş teslim süresi en erken olan iştir. Bu defa işler teslim süresi
en erken olandan en geç olana doğru sıralanır ve işler bu sıraya riayet edilerek
makinelere atanır.
2.5. Klasik Çizelgeleme Yöntemleri İle Çizelgeleme Problemleri
Uygulama bölümünde ele alacağımız çizelgeleme problemi öncesinde literatürden
aldığımız Sankar ve diğerlerinin 2005 yılı çalışmasındaki problemlerden üçü basit
atama kurallarına göre aşağıda çözülmüştür. Uygulama problemimizde işlerin teslim
süreleri aynı olduğu için “Teslim süresi yakın olana öncelik tanıma” kuralına göre
çözüm yapılmamıştır.
Sankar ve diğerlerinin çalışmasında yer alan test problemlerinden ilk 10 adetine ait
proses süreleri ve işlemler arası hazırlık süreleri Tablo 6 ve Tablo 7’ de
gösterilmiştir. Sankar’ ın probleminde teslim süresi yer almadığı için her bir problem
için teslim süreleri oluşturulmuş ve söz konusu değerler Tablo 9’ da ifade edilmiştir.
46
Tablo 6 İşlerin proses süreleri
Problem
no
1
2
3
1
7
7
8
2
7
5
5
3
6
3
3
4
6
8
2
İş Numarası
5
5
6
9
6
5
6
8
7
4
8
7
8
4
9
9
9
4
4
7
Tablo 7 İşler arası hazırlık süreleri
İş no
1
2
3
4
5
6
7
8
9
1
0
1
2
2
2
2
2
2
2
2
1
0
2
2
2
2
2
2
2
3
2
2
0
1
2
2
2
2
2
4
2
2
1
0
2
2
2
2
2
5
2
2
2
2
0
1
2
2
2
6
2
2
2
2
1
0
2
2
2
7
2
2
2
2
2
2
0
1
1
8
2
2
2
2
2
2
1
0
1
9
2
2
2
2
2
2
1
1
0
Tablo 8 Makine sayısına göre teslim süreleri
Problem No
1
2
3
2 Makine
22
26
27
Makine Sayısı
3 Makine
14
16
17
4 Makine
10
12
12
Problem çözümünde yer alan tablolar üzerinde yer alan kısaltmalar ve açıklamaları
şu şekildedir:
İ.N: İş no
İ.S: İş süresi
H.S: Hazırlık sürei
T.S: Tamamlanma süresi
47
K.T: kümülatif toplam süre
E/G: Erken/Geç tamamlanma süresi
C.M: Erken/Geç tamamlanma ceza maliyeti
Problem 1.
Makine sayısı= 2, Teslim süresi= 22
Tablo 9 Uzun işlem süresine göre işlerin makinelere atanması
Makine 1
Makine 2
İ.N
İ.S
H.S
T.S
K.T.
E/G
C.M
İ.N
İ.S
H.S
T.S
K.T
E/G
C.M
1
7
-
7
7
-15
30
2
7
-
7
7
-15
30
3
6
2
8
15
-7
14
4
6
2
8
15
-7
14
5
5
2
7
22
0
0
6
5
2
7
22
0
0
7
4
2
6
28
6
24
8
4
2
6
28
6
24
9
4
1
5
33
11
44
-
-
-
-
-
-
-
Toplam Erken/Geç tamamlanma= 180
Cmax= 33
Tablo 10 Kısa işlem süresine göre işlerin makinelere atanması
Makine 1
Makine 2
İ.N
İ.S
H.S
T.S
K.T.
E/G
C.M
İ.N
İ.S
H.S
T.S
K.T
E/G
C.M
7
4
-
4
4
-18
36
8
4
-
4
4
-18
36
9
4
1
5
9
-13
26
5
5
2
7
11
-11
22
6
5
2
7
16
-6
24
3
6
2
7
18
-4
16
4
6
2
6
22
0
0
1
7
2
9
27
5
20
2
7
2
9
31
9
36
-
-
-
-
-
-
-
48
Cmax= 31
Tablo 11 İlk gelen işe ilk hizmet kuralına göre işlerin makinelere atanması
Makine 1
Makine 2
İ.N
İ.S
H.S
T.S
K.T.
E/G
C.M
İ.N
İ.S
H.S
T.S
K.T
E/G
C.M
1
7
-
7
7
-15
30
2
7
-
7
7
-15
30
3
6
2
8
15
-7
14
4
6
2
8
15
-7
14
5
5
2
7
22
0
0
6
5
2
7
22
0
0
7
4
2
6
28
6
24
8
4
2
6
28
6
24
9
4
1
5
33
11
44
-
-
-
-
-
-
-
Cmax= 33
Makine 1
İ.N
1
5
8
İ.S
7
5
4
H.S
2
2
Makine 2
C.M
18
4
16
İ.N
2
6
9
İ.S
7
5
4
H.S
2
2
Makine 3
C.M
18
4
16
İ.N
3
4
7
İ.S
6
6
4
H.S
1
2
C.M
20
6
12
Cmax= 20
Makine 1
İ.N
7
5
4
İ.S
4
5
6
H.S
2
2
Makine 2
C.M
24
10
12
İ.N
8
6
1
İ.S
4
5
7
H.S
2
2
Makine 3
C.M
24
10
16
İ.N
9
3
2
İ.S
4
6
7
H.S
2
2
C.M
24
8
20
49
Cmax= 21
Makine 1
İ.N
1
5
8
İ.S
7
5
4
H.S
2
2
Makine 2
C.M
18
4
16
İ.N
2
6
9
İ.S
7
5
4
H.S
2
2
Makine 3
C.M
18
4
16
İ.N
3
4
7
İ.S
6
6
4
H.S
1
2
C.M
20
6
12
Cmax= 20
Makine 1
İ.N
İ.S C.M
1
7
6
7
4
12
9
4
24
Makine 2
İ.N
İ.S C.M
2
7
6
8
4
12
-
Makine 3
İ.N
İ.S C.M
3
6
8
5
5
12
-
Makine 4
İ.N
İ.S C.M
4
6
8
6
5
12
-
Cmax= 18
Makine 1
İ.N
İ.S C.M
7
4
12
6
5
4
2
7
40
Makine 2
İ.N
İ.S C.M
8
4
12
3
6
8
-
Makine 3
İ.N
İ.S C.M
9
4
12
4
6
8
-
Makine 4
İ.N
İ.S C.M
5
5
10
1
7
16
-
Cmax= 20
50
Makine 1
İ.N
İ.S C.M
1
7
6
7
4
12
9
4
24
Makine 2
İ.N
İ.S C.M
2
7
6
8
4
12
-
Makine 3
İ.N
İ.S C.M
3
6
8
5
5
12
-
Makine 4
İ.N
İ.S C.M
4
6
8
6
5
12
-
Cmax= 18
Toplam Erken/Geç tamamlanma maliyeti= 100
Problem 2
Tablo 18 Problem 2 İki Makine U.İ.S. Çözüm
Makine 1
Makine 2
İ.N
İ.S
C.M
İ.N
İ.S
C.M
8
9
34
4
8
34
1
7
16
7
8
16
5
6
0
6
6
0
2
5
28
9
4
24
-
-
-
3
3
44
Toplam E/G Tamamlanma= 196
Cmax= 37
51
Tablo 19 Problem 2 İki Makine K.İ.S. Çözüm
Makine 1
Makine 2
İ.N
İ.S
C.M
İ.N
İ.S
C.M
3
3
46
9
4
44
2
5
32
5
6
28
6
6
16
1
7
10
4
8
8
7
8
20
8
9
52
-
-
-
Cmax=39
Tablo 20 Problem 2 İki Makine İ.G.İ.H. Çözüm
Makine 1
Makine 2
İ.N
İ.S
C.M
İ.N
İ.S
C.M
1
7
38
2
5
42
4
8
18
3
3
32
6
6
2
5
6
16
8
9
40
7
8
8
-
-
9
4
28
-
Cmax=36
52
Tablo 21 Problem 2 Üç Makine U.İ.S. Çözüm
Makine 1
Makine 2
Makine 3
İ.N
İ.S
C.M
İ.N
İ.S
C.M
İ.N
İ.S
C.M
8
9
14
4
8
16
7
8
16
6
6
4
1
7
4
5
6
0
9
4
28
3
3
24
2
5
28
Cmax=23
Tablo 22 Problem 2 Üç Makine K.İ.S. Çözüm
Makine 1
Makine 2
Makine 3
İ.N
İ.S
C.M
İ.N
İ.S
C.M
İ.N
İ.S
C.M
3
3
26
9
4
24
2
5
22
5
6
10
6
6
8
1
7
6
4
8
20
7
8
24
8
9
32
Cmax=24
53
Tablo 23 Problem 2 Üç Makine İ.G.İ.H. Çözüm
Makine 1
Makine 2
Makine 3
İ.N
İ.S
C.M
İ.N
İ.S
C.M
İ.N
İ.S
C.M
1
7
18
2
5
22
3
3
26
6
6
2
5
6
6
4
8
8
9
4
20
8
9
32
7
8
24
Cmax=24
Tablo 24 Problem 2 Dört Makine U.İ.S. Çözüm
Makine 1
Makine 2
Makine 3
Makine 4
İ.N
İ.S
C.M
İ.N
İ.S
C.M
İ.N
İ.S
C.M
İ.N
İ.S
C.M
8
9
6
4
8
8
7
8
8
1
7
10
9
4
12
6
6
16
2
5
12
5
6
12
3
3
32
-
-
-
-
-
-
-
-
-
Cmax= 20
54
Tablo 25 Problem 2 Dört Makine K.İ.S. Çözüm
Makine 1
Makine 2
Makine 3
Makine 4
İ.N
İ.S
C.M
İ.N
İ.S
C.M
İ.N
İ.S
C.M
İ.N
İ.S
C.M
3
3
18
9
4
16
2
5
14
5
6
12
6
6
2
1
7
4
4
8
12
7
8
16
8
9
40
-
-
-
-
-
-
-
-
-
Cmax=22
Tablo 26 Problem 2 Dört Makine İ.G.İ.H. Çözüm
Makine 1
Makine 2
Makine 3
Makine 4
İ.N
İ.S
C.M
İ.N
İ.S
C.M
İ.N
İ.S
C.M
İ.N
İ.S
C.M
1
7
10
2
5
14
3
3
18
4
8
8
7
8
20
6
6
4
5
6
2
8
9
28
-
-
-
-
-
-
20
-
-
-
9
4
Cmax=19
55
Problem 3
Tablo 27 Problem 3 Yöntemlere Göre Çözüm Sonuçları
2 Makine
3 Makine
4 Makine
E/G
Cmax
E/G
Cmax
E/G
Cmax
U.İ.S
204
36
130
24
112
17
K.İ.S
268
39
182
25
134
21
İ.G.İ.H
248
38
164
27
144
22
56
BÖLÜM 3. KARINCA KOLONİ OPTİMİZASYONU
Karınca Algoritmasında çalışılan modeller gerçek karınca davranışlarından
türetilmişlerdir (Dorigo, Stützle; 2004, 25).
Goss ve arkadaşları (1989)’ nın laboratuarda yaptıkları deneylerde pek çok karınca
türünün neredeyse kör olduğu, geçtikleri yol üzerimde bıraktıkları kimyasal madde
sayesinde yollarını bularak yiyecek kaynağı ile yuvaları arasında gidip geldikleri
saptanmıştır.
Karıncalar tek başlarına birey olarak basit gibi görünen canlılar olsalar da koloni
halinde iken son derece karmaşık işler yapabilmektedirler. Nabiyev’ in (2005)
çalışmasında belirttiği gibi kendilerinden çok büyük cisimleri taşımak, köprüler
oluşturmak veya yuva ile yiyecek kaynağı arasındaki en kısa yolu bulmak gibi karmaşık
işlemlere karşı zeki çözümler üretirler. Karıncalardan yiyecek bulabilmek için ilk
olarak öncü karıncalar araştırma yaparlar. Öncü karıncalar yiyecek kaynağına
ulaştığında yuvalarına dönerler ve geçtikleri yerlerde Feromon denilen özel bir koku
izi bırakırlar. Diğer karıncalar feromonun kokusunu takip ederek yollarını bulurlar.
Yuva ile yiyecek kaynağı arasında gidip gelen karıncalar başlangıçta öncü
karıncaların gidip geldiği farklı yolları rastsal olarak tercih ederler. Ancak daha kısa
yolu tercih eden karıncalar daha çok sayıda gidiş-geliş yapacağı için kısa yol
üzerindeki Feromon miktarı diğer yollarda çok daha fazla olacaktır. Karıncalar
feromon maddesinin kokusunu alabilirler ve ayrım noktalarında yollarını seçerken
kokunun, başka bir deyişle iz miktarının yoğun olduğu tarafı daha yüksek bir
olasılıkla seçme eğilimi gösterirler (Yağmahan, Yenisey; 2006,17). Zamanla kısa
yolu seçen karınca sayısında artış olur. Sonuçta tüm karıncalar Şekil.8’ de
(Keskintürk, Söyler; 2006, 5) gösterildiği gibi kısa yolu tercih ederler.
57
YUVA
ENGEL
YİYECEK
YİYECEK
ENGEL
YUVA
YUVA
YİYECEK
Şekil 8 Gerçek Karıncaların En Kısa Yolu Bulma Aşamaları
Şekil 8’ de olduğu gibi karıncaların yuvası ile yiyecek arasındaki yol üzerinde bir
engel yer aldığında karıncalar engeli iki farklı yerden aşabilirler. Başlangıçta
karıncalar eşit olasılıkla yollardan birini tercih edecektir. Bir kısmı kısa bir kısmı ise
uzun olan yolu tercih edecektir. Kısa yolu tercih edenlerin geçtiği yol üzerinde
biriken feromon miktarı daha yoğun olacaktır ve dolayısı ile kısa bir süre sonra tüm
karıncalar kısa yolu tercih edecektir.
Karınca koloni optimizasyonu, popülasyon tabanlı rastsal arama prensibine dayanan
bir arama yöntemidir. Karınca kolonilerini doğal ortamlarında gözlemleyerek,
onların yiyecek toplama prensibini diKKOte alan biyoloji biliminden esinlenerek
geliştirilmiş bir meta sezgisel yöntemdir (Alaykıran, Engin, 2005: 69).
Karınca koloni optimizasyonu (ACO) algoritması ilk olarak 1991 yılında Dorigo
tarafından doktora tezi olarak gerçekleştirilmiş ve yayınlanmıştır. Bu algoritmaya ise
“Ant System” yani karınca sistemi (AS) adını vermiştir. Dorigo algoritmayı farklı
büyüklüklerdeki gezgin satıcı problemlerinin (TSP) çözümünde kullanmıştır.
Algoritma küçük ölçekli problemlerde başarılı sonuçlara ulaşmış ancak büyük
problemlerde başarılı olamamıştır.
58
1996 yılında Dorigo ve Gambardella tarafından bu defa Karınca koloni sistemi
(ACS) adlı algoritma geliştirilmiştir. İlk algoritmadan farklı olarak ACS’ de en iyi
sonucun komşularında arama yapılmaktadır.
Yapay karıncalardan oluşan karınca kolonisi algoritması, yapay feromon izlerinin
güncelleştirilmesiyle tekrarlanan bir yapıya sahiptir. Algoritmanın çalışma sürecinde,
karıncalar tarafından güncellenen feromon izleriyle iyi bir çözümün bulunması için
bilgi oluşturulmakta ve her iterasyonda bu bilgiler güncellenmektedir (Küçük,
Keskintürk, Yıldırım; 2008, 54).
Algortima adımları:
 Yapay karıncaların birer turu tamamladıklarında geçmiş oldukları yolların
feromon miktarlarının arttırılır. Herhangi iki nokta arasındaki feromon
miktarı yolun uzunluğu ile ters orantılı olarak gerçekleşir.
 Feromon buharlaşması gerçekleştirilir ve feromon miktarı güncel hale
getirilir. Buharlaştırma karıncaların daha iyi çözümler üzerinden yol
almalarını sağlar.
 Karıncalar yeni feromon miktarlarına göre yeni turlarını yapar. Karıncaların
yol tercihleri feromon miktarına göre olacaktır.
  i, j  :
görünürlük, seçilebilirlik parametresi olarak ifade edilir ve iki nokta
arasındaki uzaklığın tersidir
1/  i, j  .
 (i, j ) : iki nokta arasındaki feromon miktarı.
 ve  : ayarlanabilir parametrelerdir. Bu iki parametre feromon izi ile sezgisel
fonksiyonun etki oranını belirler. Örneğin  değeri 0 olur ise feromon izi
diKKOte alınmadan görünürlüğe göre seçim yapılması söz konusu olur.
Karınca koloni algoritmasında yol tercihi iki farklı şekilde gerçekleştirilir.
59
q
1.
i
0
olasılıkla feromon miktarının en çok olduğu yolun seçilmesi,
noktasında yer alan bir karıncanın gideceği nokta u aşağıdaki formüle göre seçilir.

j  max  (i, u )   (i, u )
uJ k ( i )
J i  :
k



eğer q  q0
ziyaret edilmemiş varış noktalarını yani
i
noktasındaki karıncanın
gidebileceği noktaları göstermektedir.
2.
1 q
0
olasılıkla feromon izleri ile orantılı bir biçimde gidilecek yolun
seçilmesidir.
Gidilebilecek tüm noktalar için seçilme olasılıkları aşağıdaki gibi hesaplanır.
  (i, j )    (i, j ) 




pk (i, j )     (i, u )    (i, u ) 
 uJ k (i )
0
eğer j  J k (i )
diğer durumda
Yukarıdaki formüle göre i noktasında yer alan bir karıncanın j noktasını seçip o
noktaya gitme olasılığı hesaplanmış olur.
Karınca koloni algoritmasında kullanılan bir diğer önemli parametre karınca
sayısıdır. Dorigo karınca sayısının ziyaret edilecek nokta sayısına eşit olması
gerektiğini belirtmektedir.
Stützle ve Hoss tarafından 1997’ de önerilen Min-Max karınca sistemine göre
feromon miktarları maksimum ve minimum aralıklar ile sınırlanmaktadır.
Karıncaların sürekli olarak aynı sonuçları bulmasını önlemek için, feromon
güncelleşmesinin alt ve üst sınırı belirlenmiştir. Min-max karınca sisteminin bir diğer
60
özelliği de her iterasyonda yalnızca en iyi sonucu yaratan karıncanın feromon
yenilemesine izin vermesidir. 1999 yılında Bullnheimer ve arkadaşları tarafından
geliştirilen sisteme göre ise, karıncalar tur uzunluklarına göre sıralanmakta,
sıralamada yer alan belli sayıdaki en iyi karıncalar seçilerek bu karıncaların belli bir
miktara göre feromon bırakmasına izin verilmektedir (Uğur, Aydın, 2006: 53).
Karınca algoritmaları pek çok problemin çözümünde kullanılmaktadır. Karınca
algoritması ile çözümü aranan problemlerden biri de Çizelgelemedir. Son yıllarda
Karınca koloni optimizasyonu algoritmasının çizelgeleme problemlerindeki etkinliği
çeşitli çalışmalarda ele alınmıştır. Besten ve arkadaşları 2000 yılında toplam ağırlıklı
geciken iş sayısı problemini, Bauer ve arkadaşları (2000) tek makineli bir üretim
sisteminde toplam gecikmeyi minimize etme problemini, Silva ve arkadaşları (2002)
paralel makine çizelgeleme problemini, Rajendran ve Ziegler (2004) akış tipi
çizelgeleme problemini vb. karınca algoritması kullanarak çözmüşlerdir.
Çizelgeleme problemlerinde makinelere işlerin paylaştırılmasında herhangi bir
mesafe değeri sözkonusu olmadığından, yenilenen turlarda bilgi olarak sadece
feromon miktarları kullanılmaktadır.
Karınca koloni optimizasyonu yöntemine ait kodlar MATLAB 7.0 programlama dili
ile yazılmıştır. Çalıştırma süreleri iş sayısına bağlı olarak değişmekte olup tüm
problemler için kabul edilir cpu sürelerine sahiptir.
3.1. Karınca Koloni Optimizasyonu Yöntemi İle Çizelgeleme
Problemleri
Literatürden aldığımız Sankar ve diğerlerinin 2005 yılı çalışmasındaki problemler bu
bölümde Karınca Koloni Optimizasyonu Yöntemi’ ne göre çözülmüştür.
61
Problem 1.
Tablo 28 Karınca Koloni Algoritması ile 2 Makine Çizelgeleme
Makine 1
Makine 2
İ.N
İ.S
H.S
T.S
K.T.
E/G
C.M
İ.N
İ.S
H.S
T.S
K.T
E/G
C.M
2
7
-
7
7
-15
30
1
7
-
7
7
-15
30
7
4
2
6
13
-9
18
4
6
2
8
15
-7
14
9
4
1
5
18
-4
8
5
5
2
7
22
0
0
8
4
1
5
23
1
4
6
5
1
6
28
6
24
3
6
2
8
31
9
36
-
-
-
-
-
-
-
Cmax= 31
Tablo 29 Karınca Karınca Koloni Algoritması ile 3 Makine Çizelgeleme
Makine 1
Makine 2
Makine 3
İ.N
İ.S
H.S
C.M
İ.N
İ.S
H.S
C.M
İ.N
İ.S
H.S
C.M
4
6
-
16
2
7
-
14
1
7
-
14
3
6
1
2
6
5
2
0
7
4
2
2
9
4
2
20
5
5
1
24
8
4
1
16
Cmax= 20
62
Tablo 30 Karınca Koloni Algoritması ile 4 Makine Çizelgeleme
Makine 1
Makine 2
Makine 3
Makine 4
İ.N
İ.S
C.M
İ.N
İ.S
C.M
İ.N
İ.S
C.M
İ.N
İ.S
C.M
4
6
8
8
4
12
5
5
10
2
7
6
3
6
12
9
4
2
6
5
4
1
7
20
-
-
-
7
4
16
-
-
-
-
-
-
Cmax= 15
Aşağıdaki tablolarda kullanılan kısaltmalar ve açıklamaları şu şekildedir:
U.İ.S.: Uzun işlem süresine öncelik tanıma
K.İ.S.: Kısa işlem süresine öncelik tanıma
İ.G.İ.H.: İlk gelene ilk hizmet
K.K.O.: Karınca koloni optimizasyonu
Tablo 31 Problem 1 Yöntemlere Göre Karşılaştırmalı Sonuçlar
U.İ.S
K.İ.S
İ.G.İ.H.
KKO
E/G
Cmax
E/G
Cmax
E/G
Cmax
E/G
Cmax
2 Makine
180
33
216
31
180
33
164
31
3 Makine
114
20
148
21
114
20
108
20
4 Makine
100
18
182
20
100
18
90
15
63
Problem 1’ in çözüm sonuçlarının özetlendiği Tablo 32’ ye bakıldığında, Karınca
Koloni Optimizasyonu (KKO), Uzun İşlem Süresi (UİS), Kısa İşlem Süresi (KİS) ve
İlk Gelene İlk Hizmet (İGİH) yöntemleri ile elde edilen sonuçlar arasında KKO ile
elde edilen sonuçların diğer yöntemlere göre daha iyi sonuçlar ortaya çıkardığı
görülmektedir. 2 makineli sistemde KKO, diğer yöntemler arasında en iyi maksimum
tamamlanma süresini elde eden KİS ile aynı maksimum tamamlanma süresine
ulaşmakla birlikte bu süreyi çok daha düşük bir toplam erken/geç tamamlanma ile
elde etmiştir. Üç makineli sistemde yine KKO elde edilen maksimum tamamlanma
süresini diğer yöntemlerden daha düşük toplam erken/geç tamamlanma miktarı ile
elde etmiştir. Dört makineli üretim yapısında ise KKO her iki amacı da diğer üç
yöntemden daha iyi sonuçlar ile sağlamıştır.
Yani Karınca Koloni Optimizasyonu ile işlerin makinelere, teslim süresine göre
toplam erken ve geç tamamlanma süresini minimize edecek ve maksimum
tamamlanma süresini de en az kılacak şekilde atandığı saptanmıştır.
Problem 2.
Makine sayısı= 2, Teslim süresi=26
Tablo 32 Karınca koloni algoritması yöntemine göre işlerin makinelere atanması
Makine 1
İ.N
İ.S
4
8
1
Makine 2
İ.N
İ.S
36
7
8
36
7
18
8
9
16
2
5
6
6
6
0
3
3
8
5
6
28
9
4
32
-
-
C.M
C.M
-
64
Cmax= 34
Tablo 33 Problem 2 KKO Sonuçları
3 Makine
KKO
4 Makine
E/G
Cmax
E/G
Cmax
126
23
96
19
U.İ.S
K.İ.S
İ.G.İ.H.
KKO
E/G
Cmax
E/G
Cmax
E/G
Cmax
E/G
Cmax
2 Makine
196
37
256
39
224
36
180
34
3 Makine
134
23
172
24
158
24
126
23
4 Makine
116
20
134
22
124
19
96
19
Problem 2’ nin çözüm sonuçlarının özetlendiği Tablo 35’ e bakıldığında, Karınca
Koloni Optimizasyonu yöntemi ile elde edilen sonuçların toplam erken/geç
tamamlanma süreleri açısından diğer yöntemlere göre çok daha iyi sonuçlar ortaya
çıkardığı görülmektedir. Aynı şekilde 2 makineli sistemde KKO, diğer yöntemler
arasında en iyi maksimum tamamlanma süresini elde etmiş, 3 ve 4 makineli
sistemlerde ise diğer yöntemler arasında en düşük sonucu ortaya çıkaran maksimum
tamamlanma süresi ile aynı sonuca ulaşmıştır.
Problem 3
65
Tablo 35 Problem 3 KKO Sonuçları
2 Makine
3 Makine
4 Makine
E/G
Cmax
E/G
Cmax
E/G
Cmax
176
35
124
23
100
17
KKO
U.İ.S
K.İ.S
İ.G.İ.H.
KKO
E/G
Cmax
E/G
Cmax
E/G
Cmax
E/G
Cmax
2 Makine
204
36
268
39
248
38
176
35
3 Makine
130
24
182
25
164
27
124
23
4 Makine
112
17
134
21
144
22
100
17
Tablo 37’ de görüleceği gibi, 2 ve 3 makineli sistemlerde Karınca Koloni
Optimizasyonu ile elde edilen sonuçlar hem toplam erken/geç tamamlanma hem de
maksimum tamamlanma süreleri açısından diğer yöntemlere göre çok daha iyi
sonuçlar ortaya çıkardığı görülmektedir. 4 makineli sistemde ise KKO en iyi toplam
erken/geç tamamlanma süresini elde etmiş, Cmax değerinde ise uzun işlem süresine
göre oluşan çizelge ile aynı sonucu yakalamıştır.
66
BÖLÜM 4. UYGULAMA
4.1. İncelenen Üretim Sistemi İle İlgili Genel Bilgiler
Plahosan A.Ş. otomotiv sanayinden inşaat sektörüne ve tarım sektörüne kadar pek
çok alanda kullanılan sert PVC takviyeli spiral hortumlar ve örgülü hortumlar üreten
bir işletmedir.
PETKİM’ den temin edilen PVC ve başka firmalardan satın alınan boya, kimyasal
madde, soya yağı gibi hammaddeler Mikser makinesinde karıştırılmaktadır.
Mikserden alınan karışım granül makinesinde işlemden geçirilerek yarı mamül yani
granül haline getirilmektedir. Üretilecek hortum çeşidine göre yumuşak ve sert
granül elde edilmesi mümkündür. Elde edilen granüller hortum imalat hattına
getirilerek işleme sokulmaktadır.
Hortum üretim hattında yer alan makineler Spiral ve Örgülü hortum üretmek üzere
iki farklı çeşittedir. Ayrıca her bir hortum çeşidinin işlevine göre farklı renklerde
üretilmesi söz konusudur.
Üretilen hortum çeşitlerinden bir kısmı özellik ve çapları ile birlikte Tablo 38’ de
özetlenmiştir.
Her bir hortum çeşidi ve çapı için makinelere farklı kalıplar takılmalıdır. Kalıpların
takılma süresi kalıp farklılıklarından dolayı farklılıklar göstermektedir. Hazırlık
zamanı olarak alacağımız kalıp değişim süreleri problemlerin ele alındığı bölümde
verilmiştir.
67
Tablo 37 Hortum çeşit ve detayları
Hortum çeşidi
E-Tipi Yeşil
V-Tipi Sarı
HV- Tipi Kırmızı
TE-Tipi Gri
LS ve LLS tipi
E-Tipi beyaz
Çapı
Özelliği
½" den 8" e kadar Yüksek basınç
çeşitli çaplarda
ve
vakuma
dayanma
1" den 4" e kadar Basınca
çeşitli çaplarda
mukavemet
1" den 8" e kadar Hafif ve çok
çeşitli çaplarda
bükülgen
1" den 8" e kadar Yumuşak
ve
çeşitli çaplarda
bükülgen
Kullanım yeri
Tarım
sanayi
inşaat sektörü
ve
Pompa çıkışları
Yüksek
basıncın
olmadığı sistemlerde
Maden
ocaklarında
havalandırma
sistemlerinde
½" den 2" e kadar Pislik tutmayan Klimalar
çeşitli çaplarda
iç yüzey
½" den 8" e kadar Çok yumuşak
Tekne ve yatlarda
çeşitli çaplarda
PVC Şeffaf
HJ-Tipi Beyaz
4’den 13 mm’ ye Milimetrik
kadar
1.1/4" den 2.1/2" e Çok yumuşak
kadar
Otomotiv sanayii
Havuz ve jakuziler
Tüm makineler üretime başlamadan önce belli bir ısıya ulaşana kadar ısıtılmalıdır.
Üretim başlamadan önce bir kez ısıtılan makineler üretim sonuna kadar sıcak
tutulmakta ve tekrar tekrar ısıtmaya gerek yoktur. Granüllerin makineye yerleştirilip
sıvı hale dönüşerek kalıba sarılmaya başlamasına kadar 10 ila 15 dakika süre
geçmesi gerekmektedir. Bu süre üretilecek ürün çeşidine göre değişmektedir ve işlem
sürelerine
dahil
edilmiştir.
Yani
proses
süresi
yarı-mamülün
makineye
konulmasından hortum haline gelmesine kadar geçen toplam süredir.
Tezde ele alınan çizelgeleme problemi Spiral hortum üreten özdeş paralel makineleri
içermektedir. Bu makinelerde ayrı çap, özellik ve renge sahip çok sayıda hortum
çeşidi üretilebilmektedir. Hortumlar 50 metrelik uzunluklar halinde üretilmekte ve
paketlenmektedir. Hortum çeşitlerine göre işlem süreleri yine problemlerde
özetlenmiştir.
Ürünlerin teslim süresi esas alınarak tam zamanında üretilmesi amaçlanmakta, erken
ve geç tamamlanma halinde ceza maliyetleri söz konusu olmaktadır. Problemin
68
çözümünde erken tamamlanma ceza maliyeti 2, geç tamamlanma ceza maliyeti 4
birim olarak alınmıştır.
4.2. Çizelgeleme Probleminin Yapısı
 Uygulama bölümde özdeş paralel makineli bir üretim ortamında erken-geç
tamamlanma (E/G) problemi ele alınmıştır. Burada tüm işlerin teslim
sürelerinin aynı olduğu problem yapısını söz konusudur. Yani tüm
j
işleri
için;
d d
j
j
Bir
’ dir.
işinin erken tamamlanması;
E
j
E  max d  C 
j
j
Aynı şekilde bir
j
işinin geç tamamlanması;
T
j
T  max C  d 
j
j
 Erken ve Geç Tamamlanma Maliyetleri söz konusudur.

j
; bir
j
işinin erken tamamlanma cezasını yani erken tamamlanma birim
maliyeti,

j
;
j
işinin geç tamamlanma cezasıdır.
 İşlem görmeye başlayan işlerin yarıda kesilmesine izin verilmez.
69
Bir makinede işlem görmeye başlayan işin tamamlanmadan, daha sonra işleme
devam etmek üzere yarıda kesilmesine izin verilmemektedir. Yani bir iş işlem
göremeye başladığı makinede işlemini tamamlayıp sistemden çıkmaktadır.
 Sıraya bağlı hazırlık süreleri söz konusudur.
Hazırlık zamanı makinede ard arda yapılan işlerin özelliklerine göre bir işten
diğerine geçerken
yapılması
gereken ayarlamalardan
ve kalıp değiştirme
işlemlerinden kaynaklanmaktadır. Hazırlık süreleri ihmal edilemeyecek kadar
önemlidir ve işlem süresine dahil edilmemiş, işlem sürelerinden ayrı olarak
değerlendirilmişlerdir. Hazırlık süreleri işlerin sırasına bağlı olarak değişmektedir.
Yani sıraya bağlı hazırlık süreleri söz konusudur.
 İşler arasında boş beklemeler söz konusu değildir.
Her bir makinede ilk iş prosese girdikten sonra o makinenin işler arasında boş
beklemesi söz konusu değildir. Makinede bir ürün tamamlandığında diğer ürününü
oluşturacak yarı mamül makineye girmiştir.

Her bir iş özdeş paralel makinelerin herhangi birinde işlem görebilir.

Bir makinede aynı anda yalnızca bir iş yapılabilir.

Makine arızaları göz ardı edilmiştir.
 Erken-Geç Tamamlanma Maliyeti ve Maksimum Tamamlanma Süresinin
Minimize edilmesi amaçlanmaktadır.
Amaç fonksiyonumuz şu şekilde ifade edilebilir;
Erken-Geç Tamamlanma Maliyeti amaç fonksiyonu:
  i max d C i  imax C i d 
n
i 1
 ,   0 
kısaca
70
  E
n
j 1
j
 T
j

Maksimum Tamamlanma amaç fonksiyonu:
C
max
Uygulama verileri firmadan alınan iki farklı sipariş verilerini içermektedir. Sipariş
miktarları, teslim süreleri ve iş süreleri firmadan ayrıntılı şekilde temin edilmiştir.
Alınan her iki sipariş de 10’ ar adet faklı ürünü içermekte ve ürünlerin 4 adet özdeş
makinede üretilmesi söz konusudur.
Problemlere ilişkin olarak sırası ile Karınca koloni optimizasyonu, uzun işlem süresi,
kısa işlem süresi ve ilk gelene ilk hizmet atama kurallarına göre çözümler
yapılmıştır. Elde edilen sonuçlar tablolarda özetlenmiş ve amaç fonksiyonlarına
ilişkin olarak elde edilen sonuçlar ayrıca verilmiştir. Her bir yöntem ile elde edilen
sonuçlar karşılaştırılmış ve yorumlanmıştır.
Problem 1:
Uygulama verilerinin temin edildiği üretim sisteminden alınan birinci siparişte yer
alan ürünlere ait işler, iş süreleri ve işler arası hazırlık süreleri aşağıdaki tablolarda
yer almaktadır. Söz konusu siparişe ilişkin teslim süresi firma tarafından 800 birim
süre olarak belirlenmiştir.
71
Tablo 38 Uygulama Problem-1 iş süreleri
İş Kodu
İş
Numarası
İşlem
süresi
İş Kodu
İş
Numarası
İşlem
süresi
H2"
1
500
L2"
6
250
H5"
2
500
LS1.3/4"
7
250
H8"
3
350
E1"
8
250
T3"
4
300
E3"
9
250
T5"
5
300
V1"
10
200
Tablo 39 Uygulama Problem-1 hazırlık süreleri
H2" H5" H8"
T3"
T5"
L2" LS1.3/4" E1"
E3"
V1"
H2"
0
25
25
25
30
30
25
25
30
30
H5"
25
0
25
25
30
30
25
25
30
30
H8"
25
25
0
25
30
30
25
25
30
30
T3"
25
25
25
0
30
30
25
25
30
30
T5"
30
30
30
30
0
30
25
25
30
30
L2"
30
30
30
30
30
0
25
25
30
30
LS1.3/4" 25
25
25
25
25
25
0
25
30
30
E1"
25
25
25
25
25
25
25
0
30
30
E3"
30
30
30
30
30
30
30
30
0
30
V1"
30
30
30
30
30
30
30
30
30
0
72
Tablo 40 Uygulama Problem-1 KKO çözüm
Makine 1
Makine 2
Makine 3
Makine 4
İ.N
İ.S
C.M
İ.N
İ.S
C.M
İ.N
İ.S
C.M
İ.N
İ.S
C.M
2
500
600
3
350
900
5
300
1000
1
500
600
9
250
40
7
250
350
8
250
450
4
300
100
-
-
-
10
200
220
6
250
200
-
-
-
Toplam E/G Tamamlanma=
4460
Cmax = 855
Şekil 9 Matlab’ de karınca koloni optimizasyonu ile çözüm görüntüsü
73
Tablo 41 Uygulama Problem-2 U.İ.S çözüm
Makine 1
Makine 2
Makine 3
Makine 4
İ.N
İ.S
C.M
İ.N
İ.S
C.M
İ.N
İ.S
C.M
İ.N
İ.S
C.M
1
500
600
2
500
600
3
350
900
4
300
1000
7
250
50
8
250
50
6
250
340
5
300
340
-
-
-
-
-
-
9
250
440
10
200
240
4560
Cmax = 910
Tablo 42 Uygulama Problem-2 K.İ.S çözüm
Makine 1
Makine 2
Makine 3
Makine 4
İ.N
İ.S
C.M
İ.N
İ.S
C.M
İ.N
İ.S
C.M
İ.N
İ.S
C.M
10
200
1200
6
250
1100
7
250
1100
8
250
1100
9
250
640
4
300
440
5
300
450
3
350
350
1
500
840
-
-
-
2
500
1220
-
-
-
Cmax = 1105
74
Tablo 43 Uygulama Problem-2 İ.G.İ.H çözüm
Makine 1
Makine 2
Makine 3
Makine 4
İ.N
İ.S
C.M
İ.N
İ.S
C.M
İ.N
İ.S
C.M
İ.N
İ.S
C.M
1
500
600
3
350
900
2
500
600
5
300
1000
6
250
40
7
250
350
8
250
50
4
300
350
-
-
-
9
250
420
-
-
-
10
200
220
Cmax = 905
Tablo 44 Uygulama Problem 1 Yöntemlere Göre Karşılaştırmalı Sonuç
U.İ.S
4 Makine
K.İ.S
İ.G.İ.H.
KKO
E/G
Cmax
E/G
Cmax
E/G
Cmax
E/G
Cmax
4560
910
8440
1105
4530
905
4460
855
En Uzun İşlem Süresi, En Kısa İşlem Süresi ve İlk Gelene İlk Hizmet yöntemleri ile
elde edilen sonuçlara bakıldığında İlk Gelene İlk Hizmet yönteminin her iki amaç
için de diğer yöntemlerden daha iyi sonuçlar ortaya çıkardığı görülmektedir. Karınca
Koloni Algoritması ile elde edilen sonuçlar ise İlk Gelene İlk Hizmet yönteminden
de çok daha iyi değerlere sahiptir.
Yani Karınca Koloni Algoritması ile işlerin makinelere çok daha etkin sonuçlar
yaratacak şekilde atandığı ve teslim süresi açısından da oldukça iyi sonuçlar
yarattığı saptanmıştır.
Problem 2:
10 adet faklı üründen oluşan siparişe ilişkin teslim süresi firma tarafından 220 birim
süre olarak belirlenmiştir.
75
Tablo 45 Uygulama Problem-2 iş süreleri
İş Kodu
İş
Numarası
H1"
1
H3"
2
T1"
3
T5"
4
L2"
5
İşlem
süresi
75
İş Kodu
İş
Numarası
LS1.3/4"
6
E1"
7
E3"
8
V1"
9
V3"
10
75
81
90
96
İşlem
süresi
105
75
90
96
96
Tablo 46 Uygulama Problem-2 hazırlık süreleri
H1" H3"
T1"
T5"
L2" LS1.3/4"
E1"
E3"
V1"
V3"
H1"
0
25
30
30
30
30
25
30
30
30
H3"
25
0
30
30
30
30
30
30
30
30
T1"
30
30
0
25
30
30
30
30
30
30
T5"
30
30
25
0
30
30
30
25
30
30
L2"
30
30
30
30
0
25
30
30
30
30
LS1.3/4" 30
30
30
30
30
0
30
30
30
30
E1"
25
30
30
30
30
30
0
25
25
30
E3"
30
30
30
25
30
30
25
0
25
30
V1"
30
30
30
30
30
30
25
25
0
30
V3"
30
30
30
30
30
30
30
30
30
0
76
Teslim süresi= 220 birim süre için;
Karınca Koloni Algoritması ile çözüm sonuçları aşağıdaki tablodaki gibidir.
Tablo 47 Uygulama Problem-2 KKO çözüm
Makine 1
Makine 2
Makine 3
Makine 4
İ.N
İ.S
C.M
İ.N
İ.S
C.M
İ.N
İ.S
C.M
İ.N
İ.S
C.M
5
96
248
9
96
248
6
105
230
4
90
260
10
96
8
1
75
38
3
81
8
8
90
30
-
-
-
2
75
324
-
-
-
7
75
340
1734
Cmax = 305
Tablo 48 Uygulama Problem-2 U.İ.S çözüm
Makine 1
Makine 2
Makine 3
Makine 4
İ.N
İ.S
C.M
İ.N
İ.S
C.M
İ.N
İ.S
C.M
İ.N
İ.S
C.M
6
105
230
5
96
248
9
96
248
10
96
248
1
75
20
4
90
8
8
90
18
3
81
26
7
75
360
-
-
-
-
-
-
2
75
348
Cmax = 310
77
Tablo 49 Uygulama Problem-2 K.İ.S çözüm
Makine 1
Makine 2
Makine 3
Makine 4
İ.N
İ.S
C.M
İ.N
İ.S
C.M
İ.N
İ.S
C.M
İ.N
İ.S
C.M
1
75
290
2
75
290
7
75
290
3
81
278
4
90
50
8
90
50
5
96
38
9
96
26
10
96
404
6
105
440
-
-
-
-
-
-
Cmax = 330
Tablo 50 Uygulama Problem-2 İ.G.İ.H çözüm
Makine 1
Makine 2
Makine 3
Makine 4
İ.N
İ.S
C.M
İ.N
İ.S
C.M
İ.N
İ.S
C.M
İ.N
İ.S
C.M
1
75
290
2
75
290
3
81
278
4
90
260
5
96
38
6
105
20
7
75
68
8
90
30
10
96
428
-
-
-
9
96
348
-
-
-
Cmax = 327
Tablo 51 Uygulama Problem 2 Yöntemlere Göre Karşılaştırmalı Sonuç
U.İ.S
4 Makine
K.İ.S
İ.G.İ.H.
KKO
E/G
Cmax
E/G
Cmax
E/G
Cmax
E/G
Cmax
1754
310
2156
330
2050
327
1734
305
78
Problemin çözümünde kullanılan yöntemler arasında Karınca Koloni Algoritması ile
elde edilen sonuçların her iki amaç açısından da en iyi sonuçları ortaya çıkardığı
görülmektedir. Problem 2’ de de Karınca Koloni Algoritması ile çizelgelenen işlerin
makinelere çok daha etkin sonuçlar yaratacak şekilde atandığı ve toplam erken/geç
tamamlanma süresi açısından da oldukça iyi sonuçlar ortaya çıkardığı saptanmıştır.
79
SONUÇ
Bu çalışmada ele alınan temel konu Özdeş Paralel Çizelgeleme problemidir. Bununla
birlikte makine çizelgeleme problemleri genel olarak ele alınmıştır. Tek ve paralel
makineler incelenmiş, Özdeş paralel makine çizelgeleme konusu ayrıca ele
alınmıştır.
Yapılan çalışmada sezgisel yöntemlerden biri olan Karınca Koloni Optimizasyonu
yönteminin yanı sıra eski temel atama kurallarına da yer verilmiştir. Çizelgelemenin
temel unsurlarını görmek ve anlayabilmek açısından analitik ve sezgisel yöntemlere
yer vermek gereklidir. Uygulama bölümünde ise MATLAB 7.0 programlama dili ile
yazılan kodlar içeren Karınca Koloni Optimizasyonu yöntemi ile ele alınan
çizelgeleme probleminin sonuçları Klasik atama yöntemleri ile elde edilen sonuçlar
ile karşılaştırılmıştır.
Uygulama yerinin tercih edilmesinde söz konusu işletmede yer alan üretim
sisteminin Özdeş paralel makine ortamı olması ve yeterli miktarda ürün çeşitliliğinin
üretilmesidir.
Uygulama yerinden alınan veriler özdeş makine gruplarının bir bölümüne aittir. Bu
bölümde yapılan işlemler, işlem süreleri ve hazırlık süreleri detaylı olarak temin
edilmiştir. İşlem süreleri, söz konusu ürünün tamamlanmış halde makineden çıkış
süresini ifade ederken, hazırlık süreleri işlem sürelerine dahil edilmemiştir. Hazırlık
süreleri işe bağımlıdır ve bu süreler ayrıca gösterilmiştir.
Uygulamanın ikinci kısmı olan, Klasik Çizelgeleme Yöntemleri bölümünde
literatürden alınan problemler en uzun işlem, en kısa işlem, ilk gelene ilk hizmet
kurallarına göre çizelgelenmiş ve sonuçlar tablolara aktarılarak yorumlanmıştır.
Karınca koloni optimizasyonunun anlatıldığı üçüncü bölümde ise yine literatürden
alınan problemler bu defa Karınca koloni optimizasyonu ile çözülmüştür. Elde edilen
sonuçlar bir önceki bölümde elde edilen sonuçlar ile karşılaştırılmış ve genel olarak
daha üstün sonuçlar yarattığı saptanmıştır.
80
Uygulama bölümünde ise gerçek bir makine ortamından alınan veriler ışığında çok
amaçlı çizelgeleme yapılmış ve sonuçlar değerlendirilmiştir. Sıraya bağımlı hazırlık
sürelerinin olduğu, işlerin bölünmesine izin verilmediği ve her iş için ortak bir teslim
süresinin olduğu sistem probleme konu edilmiştir. Söz konusu sistem hem ErkenGeç tamamlanma hem de Maksimum tamamlanma amaçlarının minimize edilmesini
hedeflemektedir.
Uygulama
sonuçları
değerlendirildiğinde
karınca
koloni
optimizasyonunun kayda değer sonuçlar ürettiği görülmektedir. Üretim çizelgesinin
geçmiş tecrübeler doğrultusunda oluşturulduğu firmada, hedeflenen amaçlara
ulaşmak açısından iyi sonuçlar ortaya çıkaracak çizelge önerisinin KKO sonuçları ile
getirilebileceği düşünülmektedir.
Günümüzün artan rekabet koşullarında şirketlerin hem kendilerini hem de
müşterilerini memnun edecek sonuçlara ulaşmak için birden çok sayıda amacı
optimize etmeye çalışmaları zorunluluktur. Bu sebeple çok amaçlı çizelgeleme
yöntemleri de giderek önem kazanmaktadır. Farklı amaçları bir arada ele alan farklı
çizelgeleme
problemleri
üzerinde
çalışılmaya
devam
edilmesi
gerektiği
düşünülmektedir.
Yapılan bu çalışma sezgisel yöntemlerden biri olan Karınca Koloni Optimizasyonu
yönteminin çok amaçlı çizelgeleme problemlerinde ortaya çıkardığı sonuçların
değerlendirilmesi açısından önemlidir.
81
KAYNAKLAR
Ahmed
M., : Minimizing the weighted sum of late and early completion
Sundararaghavan P.
penalties in a single machine, IIE Transactions, 22, 1990,
288-290.
Alidaee B., Dragan I.
: A note on minimizing the weighted sum of tardy and early
completion penalties in a single machine: A case of small
common due date , European Journal of Operational
Research, 96, 1997, 559-563.
Allahverdi
A.,
Ng : A survey of scheduling problems with setup time sor costs,
C.T., Cheng T.C.E.,
European Journal of Operational Research, 187, 2008,
Kovalyov M.Y.
985-1032.
Anghinolfi
D., : Parallel machine total tardiness scheduling with a new
Paolucci M.
hybrid metaheuristic approach, Computers & Operations
Research, 34, 2007, 3471-3490.
Arkin E.M., Roundy : Weighted-tardiness scheduling on parallel machines with
R.O.
proportional weights, Operations Researchs, 39 (1), 1991,
64-81.
Bagchi U., Chang Y., : Minimizing absolute and squared deviation of completion
Sullivan R.S.
times with different earliness and tardiness penalties and a
common due date, Naval Research Logistics, 34, 1987, 739751.
Bagchi
U.,
Julien : Note: Due-date assignment to multi-job customer orders,
F.M., Magazine M.J.
Baker K.R.
Management science, 40,1994,1389-1392.
: Sequencing:
International
The
Shortest
Series
in
Processing
Operations
Time
Rule,
Research
Management Science, 115, 2008, 1-17.
82
&
Baker K.R., Scudder : Sequencing with earliness and tardiness penalties: a review,
G.D.
Operations research 38(1), 1990, 22-36.
Bank J., Werner F.
: Heuristics algorithm
for unrelated parallel
machine
scheduling with common due date, release dates and linear
earliness and tardiness penalties, Mathematical and
Computer Modeling, 33, 2001, 363-383.
Behnamian
J., : Parallel-machine scheduling problems with sequence-
Zandieh M., Fatemi
dependent setup times using an ACO, SA and VNS hybrid
Ghomi S.M.T.
algorithm, Expert Systems with Applications, 36, 2009,
9637-9644.
Biskup D., Herrmann : Scheduling identical parallel machines to minimize total
J., Gupta J.N.D.
tardiness, International Journal of Production Economics;
2008, 115, 134-142
Cai X., Lum Y.S., : Scheduling about a common due date with job-dependent
Chan J.M.T.
asymmetric earliness and tardiness penalties, European
Journal of Operational Research, 98, 1997, 154-168.
Chen J.F.
: Scheduling on unrelated parallel machines with sequenceand
machine-dependent
constraints,
setup
times
and
due-date
The International Journal of Advanced
Manufacturing Technology, 44, 2009, 1204-1212.
Cox J.F., Blackstone : APICS Dictionary, Amerikan Production and Inventory
J.H., Spencer M.S.
Dileepan P.
Control Society, Falls Church, Virginia, 1992
: Common due date scheduling problem with separate
earliness
and
tardiness
penalties,
Computers
and
Operations Researchs, 20, 1993, 179-184.
83
Dorigo M.
: Ottimizzazino, aarendimento automatico, ed algoritmi
basati su metafora naturale (Optimization, Learning and
Natural Algorithms), Ph.D.Thesis, Politecnico di Milano,
Italy, Italyanca.
Dorigo M.,
Gambardella L.M.
: Solving symmetric and asymmetric TSPs by ant colonies, in
Proceedings of the 1996 IEEE International Conference on
Evolutionary Computation (ICEC’96), 1996.
Dorigo M., Stützle T.
: Ant Colony Optimization, A Bradford Book, The MIT
Press, Cambridge, Massachusetts, London, England, 2004
Emmons H.
: Scheduling to a common due date on paralel common
processors, Naval Research Logistics Quarterly, 34, 1987,
567-575.
Eren T.
: A bicriteria parallel machine scheduling with a learning
effect of setup and removal times, Applied Mathematical
Modelling, 33, 2009, 1141-1150
Gambardella L.M.,
Dorigo M.
: Ant-Q: A reinforcement learning approach to the travelling
salesman
problem,
Proceedings,
12th
International
Conference on Machine Learning; 1995, 252-260.
Gantt, H.L., 1919
: Organizing for Work, Harcourt, Brace, and Howe, New
York, Hive Publishing Company, Easton, Maryland, 1973
Gascon A., Leachman : A dynamic programming solution to the dynamic, multiR.C.
item, single machine scheduling problem, Operations
Research, 36(1), 1998, 50-56.
84
Hall N.G.
: Single and multiple processor models for minimizing
completion variance, Naval Research Logistics Quarterly,
33, 1986, 49-54.
Hall N.G., Kubiak W., : Earliness-Tardiness scheduling problems, II:Deviation of
Sethi S.P.
completion times about a restrictive common due date,
Operations Research, 39, 1991, 847-856.
Hall
N.G.,
Posner : Earliness-tardiness
M.E.
scheduling
problem
I:
weighted
deviation of completion times about a common due date,
Operations, research, 39, 1991, 836-846.
Heady R.B., Zhu Z.
: Minimizing the sum of job earliness and tardiness in a
multimachine system, International Journal of Production
Research, 36, 1998, 1619-1632.
Hillier
F.S., : Introduction To Operations Research, McGraw-Hill, 2001,
Lieberman G.J.
Hoogeveen
s.468
J.A., : New Lower and Upper Bounds for Scheduling Around a
Oosterhout H., van de
Small Common Due Date, Operations Research, 42, 1994,
Velde S.L.
102-110.
Hoogeveen J.A., van : Scheduling around a small common due date, European
de Velde S.L.
Jeffrey W. Herrmann
Journal of Operational Research, 55, 1991, 237-242.
: A History of Production Scheduling, Handbook of
ProductionSscheduling, , Ed. By. Jeffrey W. Herrmann,
University of Maryland, USA, 2006, 1-22
Jozefowska J.
: Just-İn-Time Scheduling: Models and algorithms for
computer and manufacturing systems, Springer Science,
New York, 2007
85
Kanet J.J.
: Minimizing the average deviation of job completion times
about a common due date, Naval Research Logistics
Quarterly, 28, 1981, 643-651.
Kim S.C., Bonrowski : Impact of sequence dependent setup time on job shop
P.M.
scheduling
performance,
International
Journal
of
Production Research, 32(7), 1994, 1503-1520.
Küçük B., Keskintürk : Paralel makineli bir üretim sisteminin karınca koloni
T., Yıldırım B.
Lee Y.H., Pinedo M.
optimizasyonu ile çizelgelenmesi, YAEM, 2008.
: Scheduling jobs on parallel machines with sequencedependent setup times, European Journal of Operational
Research, 100, 1997, 464-474.
Lee Z.J., Lin A.W., : “A dynamical ant colony optimization with heuristics for
Ying K.C.
scheduling jobs on a single machine with a common due
date”, Metaheuristics for Scheduling in Industrial and
Manufacturing Applications, Ed. By. Fatos Xhafa, Ajitth
Abraham, Springer-Verlag Berlin Heidelberg, Germany,
2008, s.91-103.
Lewis, J.P.
: Project Planning Scheduling and Control: A Hands-On
Guide to Bringing Projects in On Time and On Budget, 3rd
edition, Blacklick, OH, USA: McGraw-Hill, 2001, s. 256
Li C.L., Cheng T.C.E. : The paralel machine min-max weighted absolute lateness
scheduling problem, Naval Research Logistics, 41, 1994,
33-46.
Min L., Cheng W.
: A genetic algorithm for minimizing the makespan in the
case of scheduling identical parallel machines, Artificial
Intelligence in Engineering, 13, 1999, 399-403.
86
Mohri S., Masuda T., : Bi-criteria scheduling problem on three identical parallel
Ishii H.
machines, International Journal of Production Economics,
1999, 60-61: 529-536
Nabiyev, V. V.
: Yapay Zeka: Problemler, Yöntemler, Algoritma, Seçkin
Yayınevi, Ankara, 2005
Nazif H., Lee L.S.
: A genetic algorithm on single machine scheduling problem
to minimise total weighted completion time, European
Journal of Scientific Research, 35, 2009, 444-452.
Panwalkar S.S., Smith : Common due-date assignment to minimize total penalty for
M.L, Seidmann A.
the one machine. scheduling problem, Operations research,
30, 1982, 391-399.
Pinedo M.L
: Scheduling Theory, Algorithms, and Systems, Springer,
2008
Pinedo M.L, Chao X.
: Operations Scheduling with Applications in Manufacturing
and Services, McGraw-Hill, 1999
Rajakumar
Arunachalam
S., : Workflow
V.P.,
Salladurai V.
Rajakumar
Arunachalam
scheduling,
balancing
strategies
International
in
Journal
parallel
machine
of
advanced
Manufacturing Technology, 2004, 23, 366-374
S., : Workflow balancing in parallel machine scheduling with
V.P., precedence constraints using genetic algorithm, Journal of
Selladurai V
Manufacturing Technology Management; 2006, 17: 239254
Sankar
S.S., : Scheduling in parallel machine shop: An ant colony
Ponnambalam
S.G.,
Rathinavel
V.,
optimization
Approach,
Institute
of
Electrical
and
Electronics Engineers (IEEE), 2005, 276-280
Viveshvaren M.S.
87
Shim S., Kim Y.
: Scheduling on parallel identical machines to minimize total
tardiness, European Journal of Operation Research, 2007,
177: 135-146
Shtub A., Bard J.F., : Project
Globerson S..
Silva
C.A.,
Management:
Engineering,
Technology
and
Implementation, Prentice-Hall, New Jersey, USA, 1994
Sousa : Scheduling in manufacturing systems using the ant colonies
J.M., Runkler T.A.,
optimization algorithm, Proceedings of 5st Potuguese
Palm R., Sa da Costa
conference on automatic control (controlo 2002), sep 5-7,
J.M.
2002.
Smith, W.E.
: Various Optimizers for Single-Stage Production, Naval
Research Logistics, 3, 1956, 59-66.
Steven Nahmias
: Gantt Charts ( 2001, encylopedia of production research ,
324)
Stützle T., Hoos H.H.
: The MAX-MIN ant system and local search for the
traveling salesman problem, in Proceedings of the 1997
IEEE
International
Conference
on
Evolutionary
Computation (ICEC'97),1997.
Su L.H.
: Minimizing earliness and tardiness subject to total
completion time in an identical parallel machine system,
Computers&Operations Research, 36, 2009, 261-471
Sun H., Wang G.
: Parallel machine earliness and tardiness scheduling with
proportional weights, Computers and Operations Research,
30, 2003, 801-808.
Sundararaghavan P.S., : Minimizing the sum of absolute lateness in single-machine
Ahmed M.U.
and multimachine scheduling, Naval Research Logistics
Quarterly, 31, 1984, 325-333.
88
Szwarc W.
: Adjacent orderings in single-machine scheduling with
earliness and tardiness penalties, Naval Research Logistics,
40, 1993, 229-243.
Szwarc W.
: Single machine scheduling to minimize absolute deviation
of completion times from a common due date, Naval
Research Logistic, 36, 1989, 663-673.
Szwarc W.
: The weighted common due date single machine scheduling
problem revisited, Computers and Operations Research, 23,
Ting C.C.
1996, 255-262.
: The total earliness and tardiness problem for single machine
and identical machines, Doktora tezi, Auburn Alabama,
2000
Toksarı M.D., Güner : Parallel machine earliness/tardiness scheduling problem
E.
under the effects of position based learning and
linear/nonlinear
deterioration,
Computers&Operations
Research, 36, 2009, 2394-2417.
Toksarı M.D., Güner : Minimizing the earliness/tardiness costs on parallel machine
E.
with learning effects and deteriorating jobs: a mixed
nonlinear integer programming approach, The International
Journal
Toksarı, M.D.
of
Advanced
Manufacturing
Technology,38,
2008,801-808.
: Öğrenme ve bozulma etkileri altında hazırlık zamanlı
paralel makineli erken tamamlanma/gecikme çizelgeleme
problemi, doktora tezi, Gazi Ü. Fen bil. Ens. 2008
Tütek H.H.,
Gümüşoğlu Ş.
Weng M.X., Ren H.
: Sayısal Yöntemler: Yönetsel Yaklaşım, Yenilenmiş 3. Bası,
Beta Basım Yayım Dağıtım A.Ş., İstanbul, 2000
: An efficient priority rule for scheduling job shops to
minimize mean tardiness, IIE Transactions, 38, 2006, 789795.
89
Wight, O.W.
: Production and Inventory Management in the Compute
Age, Van Nostrand Reinhold Company, Inc., New York,
1984
Williams D., Wirth A. : A new heuristic for a single machine scheduling problem
with set-up times, Journal of Operational Research Society,
47, 1996, 175-180.
Yalaoui F., Chu C.
: Parallel machine scheduling to minimize total tardiness,
International Journal of Production Economics, 76, 2002,
265-279.
Zhu Z., Heady R.B.
: Minimizing the sum of earliness/tardiness in multi-machine
scheduling: a mixed integer programming approach,
Computers and Industrial Engineering, 38, 2000, 297-305.
Zouba M., Baptiste P., : Scheduling identical parallel machines and operators within
Rebaine D.
a period based changing mode,
Computers&Operations
Research, 36, 2009, 3231-3239.
90
EKLER
Ek 1 Sert PVC takviyeli spiral hortumlar üreten Plahosan A.Ş. üretim bölümünden
makine , yarı mamül ve mamül fotoğrafları
Fotoğraf 1 Hammaddelerin karıştırıldığı mikser
91
Fotoğraf 2 Yumuşak Granül makinesi
Fotoğraf 3 Sert Granül makinesi
92
Fotoğraf 4 Spiral hortum makinesi
Fotoğraf 5 Spiral hortum makinesi kalıp görüntüsü
93
Fotoğraf 6 Spiral hortumun makineden çıkış/üretime başlama anı
Fotoğraf 6 Örgülü hortum makinesi
94
Fotoğraf 7 Hortum çeşidi için çeşitli kalıplar
Fotoğraf 8 HV tipi kırmızı spiralli hortum
95
Fotoğraf 9 E tipi beyaz hortum
Fotoğraf 10 TE tipi gri ve şeffaf spiralli hortum
96
ÖZGEÇMİŞ
1978 yılında Trabzon’ da doğdu. İlk ve orta öğrenimini Sürmene’ de, Yüksek
öğrenimini ise 2000 yılında İstanbul Üniversitesi İşletme Fakültesi’ nde tamamladı.
Üniversite öğrencisi olduğu yıllarda yarı zamanlı olarak çalışmaya başladığı Vakko
Tekstil A.Ş.’ nde Üretim Planlama ve İş Geliştirme Uzmanı olarak görev yaptı. 2001
yılında İ.Ü. İşletme Fakültesi Üretim Anabilim Dalı’ nda yüksek lisans eğitimine
başladı ve Aralık 2001 tarihinde aynı bölümde Araştırma Görevlisi olarak göreve
başladı. 2004 yılında Toyota Montaj Fabrikası’ nda yaptığı “Karışık Modelli Montaj
Hattı Dengeleme ve Simülasyon Uygulaması” adlı tez ile yüksek lisansını
tamamladı. Aynı yıl İ.Ü. İşletme Fakültesi’ nde doktora programına başladı.
Halen İ.Ü. İşletme Fakültesi’ nde Araştırma Görevlisi olarak görevini sürdüren
Birgül KÜÇÜK evlidir.
97

özdeş paralel makineli bir üretim sisteminin karınca koloni

Transkript

Benzer belgeler

Makine Durumu

paletli eklemli platform

mayer panel ebatlamaların genel avantajları

Gaziantep... Makine Halısı`nın Başkenti

Mal Alımı İhaleleri İçin Teknik Şartname Standart Formu