özdeş paralel makineli bir üretim sisteminin karınca koloni
Transkript
özdeş paralel makineli bir üretim sisteminin karınca koloni
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İ Ö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 Bu Doktora Tezi, İstanbul Üniversitesi Bilimsel Araştırmalar Proje Birimi (BAP) tarafından desteklenmiştir. Proje No:2697 ii ÖZDEŞ PARALEL MAKİNELİ BİR ÜRETİM SİSTEMİNİN KARINCA KOLONİ ALGORİTMASI İLE ÇİZELGELENMESİ Ö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 13 Uzun işlem süresine göre işlerin makinelere atanması ............................... 49 Tablo 14 Kısa işlem süresine göre işlerin makinelere atanması ................................ 49 Tablo 15 İlk gelen işe ilk hizmet kuralına göre işlerin makinelere atanması............. 50 Tablo 16 Uzun işlem süresine göre işlerin makinelere atanması ............................... 50 Tablo 17 Kısa işlem süresine göre işlerin makinelere atanması ................................ 50 Tablo 18 İlk gelen işe ilk hizmet kuralına göre işlerin makinelere atanması............. 51 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 35 Problem 2 Yöntemlere Göre Karşılaştırmalı Sonuçlar ............................... 65 Tablo 36 Problem 3 KKO Sonuçları .......................................................................... 66 Tablo 37 Problem 3 Yöntemlere Göre Karşılaştırmalı 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 jJ 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 jJ 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 jJ 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 k1 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 Tabu arama algoritması 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 Tabu arama algoritması 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 jE 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 jE n E1 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; jT C jd 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 pp 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ı nn2m 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. 0nm 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. n14, m3, 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 Makine137 , Makine 235 , Makine 32 nnm n14311 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 319,16 n n 2m n 11 6 5 iş 40 3. Adım m n 2m ' euygun mu ? 35 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 çize lg enin başlama zamanı; 100 (37 27 5) 100 69 31 olur. Makine 2 için; E 2, 7,14 T 11, 6 ve çize lg enin başlama zamanı; 100 (35 21 3) 100 59 41 olur. Makine 3 için; E 3,9 T 12,8 ve çize lg enin başlama zamanı; 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 Toplam Erken/Geç tamamlanma= 216 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 - - - - - - - Toplam Erken/Geç tamamlanma= 180 Cmax= 33 Makine sayısı= 3, Teslim süresi= 14 Tablo 12 Uzun işlem süresine göre işlerin makinelere atanması 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 Toplam Erken/Geç tamamlanma= 114 Cmax= 20 Tablo 13 Kısa işlem süresine göre işlerin makinelere atanması 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 Toplam Erken/Geç tamamlanma= 148 Cmax= 21 Tablo 14 İlk gelen işe ilk hizmet kuralına göre işlerin makinelere atanması 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 Toplam Erken/Geç tamamlanma= 114 Cmax= 20 Makine sayısı= 4, Teslim süresi= 10 Tablo 15 Uzun işlem süresine göre işlerin makinelere atanması 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 - Toplam Erken/Geç tamamlanma= 100 Cmax= 18 Tablo 16 Kısa işlem süresine göre işlerin makinelere atanması 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 - Toplam Erken/Geç tamamlanma= 182 Cmax= 20 50 Tablo 17 İlk gelen işe ilk hizmet kuralına göre işlerin makinelere atanması 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 Makine sayısı= 2, Teslim süresi= 26 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 - - - Toplam E/G Tamamlanma= 256 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 - Toplam E/G Tamamlanma= 224 Cmax=36 52 Makine sayısı= 3, Teslim süresi= 16 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 Toplam E/G Tamamlanma= 134 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 Toplam E/G Tamamlanma= 172 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 Toplam E/G Tamamlanma= 158 Cmax=24 Makine sayısı= 4, Teslim süresi= 12 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 - - - - - - - - - Toplam E/G Tamamlanma= 116 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 - - - - - - - - - Toplam E/G Tamamlanma= 134 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 Toplam E/G Tamamlanma= 124 Cmax=19 55 Problem 3 Makine sayısı= 2, Teslim süresi= 27 Makine sayısı= 3, Teslim süresi= 17 Makine sayısı= 4, Teslim süresi= 12 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 ) uJ 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 ) uJ 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. Makine sayısı= 2, Teslim süresi= 22 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 - - - - - - - Toplam Erken/Geç tamamlanma= 164 Cmax= 31 Makine sayısı= 3, Teslim süresi= 14 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 Toplam Erken/Geç tamamlanma= 108 Cmax= 20 62 Makine sayısı= 4, Teslim süresi= 10 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 - - - - - - Toplam Erken/Geç tamamlanma= 90 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 - Toplam Erken/Geç tamamlanma= 180 64 Cmax= 34 Makine sayısı= 3, Teslim süresi= 16 Makine sayısı= 4, Teslim süresi= 12 Tablo 33 Problem 2 KKO Sonuçları 3 Makine KKO 4 Makine E/G Cmax E/G Cmax 126 23 96 19 Tablo 34 Problem 2 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 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 Makine sayısı= 2, Teslim süresi= 27 Makine sayısı= 3, Teslim süresi= 17 Makine sayısı= 4, Teslim süresi= 12 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 Tablo 36 Problem 3 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 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 Toplam E/G Tamamlanma= 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 - - - Toplam E/G Tamamlanma= 8440 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 Toplam E/G Tamamlanma= 4530 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 Toplam E/G Tamamlanma= 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 Toplam E/G Tamamlanma= 1754 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 - - - - - - Toplam E/G Tamamlanma= 2156 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 - - - Toplam E/G Tamamlanma= 2050 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