Hacettepe Üniversitesi Sosyal Bilimler Enstitüsü İşletme Anabilim Dalı Üretim ve Sayısal Yöntemler Bilim Dalı PARALEL MAKİNELİ ROBOTİK HÜCRELERDE ÇİZELGELEME PROBLEMİ Mohammad Reza KOMARİ ALAİE Doktora Tezi Ankara, 2017 PARALEL MAKİNELİ ROBOTİK HÜCRELERDE ÇİZELGELEME PROBLEMİ Mohammad Reza KOMARİ ALAİE Hacettepe Üniversitesi Sosyal Bilimler Enstitüsü İşletme Anabilim Dalı Üretim ve Sayısal Yöntemler Bilim Dalı Doktora Tezi AnkaraOcak, 2017 v TEKKÜRLER Bu tezimim tamamlanması süresince, çalışmalarımı her aşamasında en az benim kadar emeği olduğunu düşündüğüm, değerli yardım ve katkılarıyla beni yönlendiren, deneyimlerinden faydalanarak bilimsel çalışma nosunu kazanmamı sağlayan hocam Dr.Mehmet Soysal’a ; Verdikleri büyük destek ve önerilerle çalışmama değerli katkılarda bulunan Prof.Dr. Mehmet Baha Karan’a. Destekleriyle beni hiç bir zaman yanlız bırakmayan aileme (Anneme. Kız kardeşime ve herzaman desteklerini esirgemeyen Dayıma) ve Dr. Gahder Zemestaniye teşekkürlerimi sunuyorum. vi ÖZET Mohammad Reza Komari Alaie, Paralel Makineli Robotik Hücrelerde Çizelgeleme Problemi, Ankara, 2017. Bu çalışmada, paralel makineli robotik hücrelerde çizelgeleme problemi ele alınacaktır. (PM- RC) . PM-RC probleminde tamamlanma zamanını en aza indirmek için bir karma tam sayılı doğrusal proglamlama (MILP) modeli önerilecektir. MILP modellerinin özelliklerinden dolayı çoğunlukla uygun bir çözüm üretilememektedir. Bu nedenle, PM-RC probleminin çözümünde Benders Ayrıştırma yöntemine dayanan bir yöntem araştırılmaktadır. Anahtar Sözcükler Seri Üretim, Paralel Makine Çizelgeleme Problemi, Robotik Hücreler, Benders Ayrıştırma Yöntemi vii ABSTRACT Mohammad Reza Komari Alaie, “Parallel Machine Robotic Cell Scheduling Problem” Ankara, 2017. This research address the Parallel Machine Robotic Cell Scheduling Problem (PM-RC) considering static identical parallel machine at the processing stage and multi part types. A mixed- integer linear programming (MILP) would be proposed for the PM-RC problem to minimize the makespan. Due to the characteristics of MILP models, mostly they are incapable of producing good feasible solution. Therfore, a method based on Benders decomposition method is considered to be investigated for solving the PM-RC problem. KEY WORDS Flow shop, Robotic Cell Scheduling Problem, Benders decomposition Method. viii İÇİNDEKİLER KABUL VE ONAY..................................................................................................i BİLDİRİM................................................................................................................ii YAYIMLAMA VE FİKRİ MÜLKİYET HAKLARI BEYANI.........................iii ETİK BEYANI........................................................................................................iv TEŞEKKÜR.............................................................................................................v ÖZET.......................................................................................................................vi ABSTRACT............................................................................................................vii İÇİNDEKİLER.....................................................................................................viii KISALTMALAR......................................................................................................x TABLOLAR.............................................................................................................xi ŞEKİLLER..............................................................................................................xii GİRİŞ.........................................................................................................................1 BİRİNCİ BÖLÜM LİTERATÜR İNCELENMESİ...................................................................................6 İKİNCİ BÖLÜM PROBLEM TANITIMI ve ÖNERİLEN KARMA TAMSAYILI DOĞRUSAL PROGRAMLAMA MODELİ………………………….……………….………......10 2.1 Matimatik Problem……………………………………………………….....13 ix 2.1.1 İNDİSLER……………………………………………………......13 2.1.2 PARAMETRELER…………… ………………………………….13 2.1.3 KARAR DEĞİŞKENLERİ……………………………………….14 2.5 AMAÇ FONKSİYONU ve KISITLAR… …………………………....16 ÜÇÜNCÜ BÖLÜM ÇÖZÜM PROSEDÜRÜ: MANTIK TABANLI BENDERS AYRIŞTIRMA METODU 3.1 BENDERS AYRIŞTIRMA METODU………………….…………..21 3.1.1 KLASİK VERSİYON…………………………………………...21 3.2 BENDER AYRIŞTIRMASI İÇİN MODEL SEÇİMİ.......................24 3.3 DİĞER AYRIŞTIRMA METODLARİ İLE İLİŞKİLER……….....25 3.4 ANA ROBLEM……………………………………………………...…29 3.5 ALT PROBLEM…………………………………………………….....30 3.6 MANTIK TABANLI BENDERZ KESMELERİ………………….....32 SAYISALBULGULAR………………………………………………………….......33 SONUÇ…………………………………………………………………………….....39 KAYNAKÇA……………………………………………………………………......41 EKLER EK. 1 TEZ ÇALIŞMASI OPJİNALLİK RAPORU…………………………..47 EK. 2 TEZ ÇALIŞMASI ETİK KURULU İZİN MUAFİYET FORMU……48 ÖZGEÇMİŞ ……………………………………………..…………………….….49 x KISALTMALAR PM-RC Paralel makineli robotik hücrelrde çizelgeleme problem. MILPM Karma tam sayılı doğrusal proglamlama. MPS En küçük Parça Kümesi AGV Otomatik güdümlü araçların. TSP Gezgin satıcı problem. BD Benders Ayrıştırma, LBBD Mantık tabanlı Benders ayrıştırması. xi TABLOLAR TABLO 1-1 Çok parçalı robotik hücre çizelgeleme problemleri üzerine yapılan araştırmaların sınıflandırılması. TABLO 3- 1 Benders ayrıştırma yönteminin bazı uygulamaları. TABLO 3- 2 Benders yöntemi ile ele alınan optimizasyon problemlerine örnekler. TABLO 4- 1 Paralel makine robotik hücre çizelgeleme problemi için önerilen MILP modeli ve LBBD yönteminin hesaplama sonuçları. xii ŞEKİLLER ŞEKIL 1.1 Paralel Makineler İçeren ve Çok-Robotlu Bir Robotik Hücre. ŞEKİL 2.1 Paralel makineli robotik hücrelerde örğneyi. ŞEKIL 3.1 Benders ayrıştırma yönteminin şematik gösterimi. ŞEKIL 4. 1 LBBD yöntemi ile çözülen tüm MS ve MP modellerinin toplam CPU zamanları. ŞEKIL 4. 2 Aynı parça sayıları ile 3 ve 5 makineli hücrelerin bitiş zamanı karşılaştırmaları. 1 GİRİŞ Bitmiş bir parça veya ürün üretmek için gerekli olan, çoklu imalat aşamalarında ham maddeleri ileten bilgisayar-kontrollü malzeme taşıma sistemleri, endüstride yaygın olarak kullanılmaktadır. Böyle bir uygulama olan robotik hücre, modern imalatta standart bir araç haline gelmiştir. Bu tür hücrelerin etkin kullanımı, çeşitli zorlayıcı kombinasyonel optimizasyon problemlerine algoritmik çözümler gerektirir. Tipik problemler arasında, hücre tasarımı, robot hareketlerinin optimal dizilimi ve üretilecek ürünlerin çizelgelenmesi bulunmaktadır. Birçok farklı endüstride, robotik hücreler kullanılmaktadır.Başlıca uygulama alanı ise yarı iletken üretimidir.Diğer uygulamalar arasında, baskılı devre kartlarından, parçaları arasındaki kimyasal tankları kaldıraçlar vasıtasıyla transfer eden uçak kanatlarına kadar çeşitli ürünlerin elektrokaplama hatları bulunmaktadır. Robotik hücreler aynı zamanda ana bilgisayarlarda kullanılan kartların test edilmesi ve incelenmesi, kamyon diferansiyel montajları için dökümlerin işlenmesi, bilgisayar destekli üretim için vinç çizelgelemesi, tekstil fabrikaları ve motor bloğu imalatı için de kullanılmaktadır. Üreticiler, daha büyük ve daha karmaşık robotik hücreler kullanırken, bu hücrelerin operasyonlarını optimize etmek için daha gelişmiş modeller ve algoritmalar kurmaları gerekmektedir. Bu talebi karşılamanın yollarını bulmak için ise bir dizi çalışma yapılmıştır. Bu çalışmaların bazıları 1970'lerin sonlarına dayansa da, çoğu çalışma 1990 yılından sonra gerçekleştirilmiştir. Bir robotik hücre; her biri sabit bir sırayla her bir bölüm üzerinde farklı işlem aşamaları gerçekleştiren bir giriş cihazı ve hücrenin içindeki parçaları taşımakla görevli bir veya daha fazla robot barındıran bir çıkış cihazından oluşmaktadır. Her bir aşamada, o aşamaya ait işlemi gerçekleştiren bir veya birden fazla makine bulunmaktadır.Robotik bir hücrenin varsayılan düzenlenme biçimi; her aşamada bir veya birden fazla makinenin parçalarına tutunabilmesi ve hücre içinde, aşamalar arası ara-depolama için tampon bulundurulmaması şeklindedir. Her makinede sadece bir parça utulabileceğinden, robotik bir hücre, özünde, işleme istasyonları arasındaki tüm materyal transferlerini gerçekleştiren, yaygın sunucuları bulunan, blokajlı bir seri üretim veya atölye tipi üretimdir. Robotik hücrelerde, işlemdeki her fonksiyon bir makine tarafından gerçekleştirilmektedir. 2 Malzeme taşıma ve makineler arasındaki hareket ve makinelerin yüklenmesi veya boşaltılması, robotlar tarafından gerçekleştirildiğinden, parçaların doğru yönlendirmelerle makinalara yüklenmesini sağlamak için çeşitli uzaktan merkez uyumlu cihazlar bulunmaktadır. Bu gerçekleştirildiğinde, robotlar malzeme kullanımı için avantajlı duruma gelmektedir, çünkü uzun süreler boyunca hız ve hassasiyetle çalışabilmektedirler. Buna ek olarak, bazı ortamlarda kirliliği önlediği için tercih edilmektedirler ve bunun örnekleri arasında, farmasötik bileşimler ve yarı iletken imalatı bulunmaktadır. Diğer imalat ortamları insanlar için rahatsız edici ortamlar olabilmektedir. Bazı yarı iletken imalatları vakumla yapılmakta; kaynakçılık ve demircilik uygulamaları yüksek sıcaklık ortamlarında olabilmekte; boyama veya diğer kaplama türlerinin uygulanması zararlı dumanlar yayabilmektedir. Bu nedenle robotlar doğal bir alternatiftir. Endüstriyel uygulamalarda farklı tipte robotlar kullanılmaktadır. Yarı iletken imalatı için yaygın bir uygulamada, robotun sabit bir tabanı ve dönen bir kolu bulunmaktadır. Böyle bir hücre, genellikle robot merkezli hücre olarak adlandırılmaktadır. Baskılı devre kartlarını elektro kaplama için sıklıkla kullanılan başka bir yapılandırmada ise, robot kaldıraç vasıtasıyla bir destek-işlem hattına bağlanmakta ve tüm robot bu hat boyunca doğrusal olarak hareket etmektedir. Daha genel bir ifade ile bu iki yargı birleştirilmek istenirse; robotun kolu kendi tabanında dönmekte ve robot kendisi etrafındaki bir hat boyunca doğrusal olarak hareket etmektedir. Buna ek olarak, işleme aşamalarında paralel makineler içeren çoklu robot hücreleri, Şekil 1.1 ile gösterilmiştir: 3 Şekil 1.1 Paralel Makineler İçeren ve Çok-Robotlu Bir Robotik Hücre. Parçaların veya ürünlerin işlem gereksinimlerinin standartlaştırılması, gerekli sayı ile birlikte tekrarlanan üretim için ideal bir ortam yaratmaktadır. Uygulamadaki tipik kullanımlarında, robotik hücreler, önemli miktarda 4 adet tek parça veya az sayıda yakından ilişkili birkaç parça üretmek için kullanılmaktadır. İşleme gereksinimleri göz önüne alındığında, üreticilerin en çok ilgilendiği amaç, hücre üretkenliğinin maksimize edilmesidir. Üretkenliğin doğal ve yaygın olarak kullanılan bir ölçüsü; birim zaman başına üretilen bitmiş parça sayısı olan, iş hacmidir. Hücrenin verimini maksimize etme hedefi göz önüne alındığında, iki uyarı dikkate alınmalıdır.Birincisi; hücrenin önemli sayıda üretim yapması, ürünlerin yüksek pazar değeri gibi iş hacmindeki küçük iyileştirmeler ile gelir önemli ölçüde arttırılabilmektedir.İkincisi ise; bir takım hücre özelliklerinin iş hacmine olan etkisidir. Bunlar, makinelerin ve robotların işlenme hızlarını, hücre düzenini ve robot hareketlerinin sırasın içermektedir. Belirli bir imalat ortamı için, bu özelliklerin nispi etkileri hakkında önceden varılmış bir yargının saptanması genellikle zor olmaktadır. 4 Pratikte, birçok hücre parametresi fiziksel kısıtlarla sabitlenmekte ve değiştirilememektedir. Hücrenin yerleşiminde genellikle az bir esneklik bulunmakta ve bunu değiştirmenin iş hacmi üzerinde göreceli olarak daha da az etkisi olmaktadır. Çoğu uygulamada, işleme gereksinimleri kurallara uygun yapılmalıdır; Bir aşamada işleme süresinin düşürülmesi, bu işlemin niteliğini ve sonucunu değiştirmektedir. Hücrenin farklı evrelerindeki işlem hızları, mevcut olan en son teknolojiyle kısıtlandırılmıştır. Farklı hızlara sahip çeşitleri mevcut olmasına rağmen, robotlar, önceden belirlenmiş ve değiştirilemeyen bir işlem hızı ile birlikte gelmektedir. Bir dizi makine ve bir malzeme taşıma robotundan oluşan bir üretim hücresine robotik hücre adı verilmektedir. Bu tür hücrelerin etkin kullanılması, bazı önemli ve zorlu problemlerin üstesinden gelmeyi gerektirmektedir. Robotik hücreler, çok sayıda farklı türde parçalar içeren işlem birimlerini işleyebilmektedir. Genel olarak, farklı türdeki parçaların belirli bir makine için farklı işlem süreleri bulunmaktadır. Çoklu parça tipli problemler, az sayıda makine için bile özdeş parça tipi sayaç problemlerinden daha zordur. En küçük Parça Kümesi (MPS) terimi, parça türünün nispi oranlarının, talebin nispi oranlarıyla aynı olan parça kümesini tanımlamaktadır. İlgilenilen problem, robot hareketlerinin sırasını ve çevrim süresini ortaklaşa minimize eden MPS için parça giriş sırasını bulmaktır. Çok parçalı üretim kapsamında, robot hareket çevriminin bulunması ve üretim çevrim süresini veya ortalama kararlı durum çevrim süresini ortaklaşa minimize eden parça sıralamasını içeren kararlar alınmaktadır. Buna ek olarak, burada, bir seri üretim sistemi olan ve robotun hücredeki makineleri beslemek için kullanıldığı yerlerde, bir robotik hücredeki robot hareketlerinin ve parçalarının sıralanması sorunu ele alınmaktadır. Bu tezde, tüm parçaları işleyebilen çok sayıda özdeş makinelerin robotik hücreleri üzerine odaklanılmıştır. Paralel makine sistemlerinde robotik hücre çizelgeleme çalışmaları ve mevcut çalışma arasındaki bir diğer ilişki, araştırmacılar tarafından, kabul edilen kurulum işlemleri, mevcut noktadan ilgili makineye kadar olan yolculuk süresi ve yükleme / boşaltma süreleri gibi bir tür robot operasyonu olarak görülebilmesidir. 5 Bu tezde, eşzamanlı olarak üretim sürecini minimize etmek için, işlemlerin makinelere yerleşimi sağlanırken; aynı zamanda optimum robot hareket döngüsünü bulma problemi dikkate alınmıştır. Sonuçlar göstermiştir ki; makine kapasiteleri daha etkin kullanıldığı taktirde, yerleşimin daha iyi sonuçlar verdiği görülmüştür. Bu çalışmada mevcut literatürden farklı olarak, birden fazla özdeş makine düşünülmüş ve problemi çözmek için de Benders ayrıştırma yöntemine dayalı bir yöntem sunulmuştur. 6 BİRİNCİ BÖLÜM: LİTERATÜR İNCELEMESİ Literatürde genel bağlamda, robotik hücrelerdeki döngüsel çizelgeleme için, üretim hızını maksimize etmek ve en uygun robot hareket çevriminin tekrarlarını kullanarak, döngü zamanını en aza indirgemek bazında çalışmalar yapılmıştır (Sriskandarajah, Hall, ve Kamoun, 1998). Aslında, tekrarlı olarak üretilen çoklu parça tiplerinde, seçilen en küçük parça kümesi (Minimal Part Set, MPS) için en uygun çevrim sırasını belirlemeye çalışmak, farklı parça tiplerinin üretimindeki döngüsel sistem çizelgelemesi bakımından özel bir durum olarak düşünülebilir. Dolayısıyla, bu döngüsel sistemlerde MPS için ürünlerin üretim süresini minimize etmek, iş hacmini maksimize etmek veya çevrim süresini minimize etmek şeklinde düşünülebilir. Sethi vd. (1992) çoklu parça tiplerini içeren, iki ve üç makineli robotik hücreleri ele almıştır. Problemin karmaşıklığını araştırmışlar ve robot hareket çevrimi göz önüne alındığında, çoklu parça döngüsünü belirleyen bir polinomsal zaman algoritması önermişlerdir. Bilge ve Ulusoy (1995) m-makine (m-machine) esnek üretim sistemi içerisinde Otomatik Güdümlü Araçların (Automatic Guided Vehicles, AGV) çizelgelemesini incelemişlerdir. Bu çalışmalarıyla, doğrusal olmayan karma tamsayılı programlama modeli ve ürün üretim süresini en aza indirgemeyi amaçlayan bir iterasyon süreci ortaya çıkarmışlardır. Chen ve Proth (1997) robotik hücreler için, iki-makineli ve m-makinelerin (çok-makine) seri üretimini araştırmışlardır. Robot hareket sıralaması verildiğinde, parçaların optimum çevrimini bulmak için bir dal ve sınır yöntemi algoritması önermişlerdir. Hall vd. (1998) üç-makineli bir robotik hücrenin karmaşıklığını ve kararlı durum performansını incelemişlerdir. Araştırmalarında, robot hareketlerini ve parça sıralamalarını belirleyerek çevrim süresini minimize etmeye çalışmışlardır. Sriskandarajah vd. (1998) çok parçalı türleri içeren, çoklu-makine robotik hücresini incelemişlerdir. Çalışmalarında, tek birim robot hareket döngülerinin tümü ile ilişkili olan parça sıralaması problemini dört kategoriye ayırmışlardır: (i) sıralamadan bağımsız; (ii) gezgin satıcı problemi (travelling salesman problem, TSP) olarak formülize edilebilen, fakat çözümü polinomsal 7 olan; (iii) bir TSP ve tekli NP-zor olarak formülize edilebilen; (iv) tekli NP-zor, fakat TSP yapısında olmayan. Aneja ve Kamoun (1999) iki-makineli robotik bir hücrede robot hareket sırasını ve parça çizelgeleme problemini ortaklaşa optimize eden karmaşıklık algoritmasını O (n log n) öngörmüşlerdir. Agnetis (2000) Agnetis ve Pacciarelli (2001) bir robotun parçalarının hareket ettirilmesi için kullanılan ve iki ve üç-makineli hücreler için en uygun parça çizelgelemelerinin bulunduğu, bekleme süresi içermeyen seri üretim probleminin karmaşıklığını incelemişlerdir. Hurink ve Knust (2001) seri üretim çizelgemelerinde, malzemelerin net taşıma kapasitesi ve taşıma sürelerini çalışmışlardır. Buna ek olarak, makineler ve ihmal edilebilir boş hareket saatleri arasında sınırsız bir tampon bölge olduğunu varsaymışlardır. Ayrıca, Hurink ve Knust (2002) tarafından, tek bir robotlu atölye tipi üretim çizelgeleme probleminin, NP-zor olduğu ispatlanmış ve tabu arama algoritması önerilmiştir. Soukhal ve Martineau (2005) çok parçalı tipler ve tek bir taşıma robotu ile seri üretim robotik hücre çizelgelemesi problemini incelemişlerdir. Problemi çözmek için, bir tamsayılı doğrusal programlama modeli ve bir genetik algoritma önermişlerdir. Soukhal vd. (2005) taşıma kısıtlamalarını hesaba katarak, iki-makineli seri üretim çizelgelemesi problemini araştırmıştır. Bu gibi durumlarda, biten işler proses tesisinden transfer edilip, daha sonra müşterilere teslim edilmektedir. Engelleme gibi, ek kısıtlar içeren bu problemlerin NP-zor olduğu kesin olarak kanıtlanmıştır. Carlier vd. (2010) tek bir taşıma robotu ve engelleme kısıtlı seri üretim robotik hücre çizelgeleme problemi için yaklaşık ayrıştırma algoritması önermiştir. Başlangıçta, parçaların çevrim sırasını belirlemişler, sonrasında belirlenen parça çevrim sıraları için robot hareketlerini sıraya koymuşlardır. Kharbeche vd. ( 2011) tek bir robotla seri üretim robotik hücre çizelgeleme problemi için yeni bir MILP modeli bulmuş ve bir dal ve sınır algoritması önermiştir. Buna ek olarak, büyük ölçekli problemleri çözmek için bir genetik algoritma sunmuşlardır. Zahrouni ve Kamoun (2012) farklı parçalı tipleri içeren üç-makineli seri üretim robotik hücresini incelemiş ve Nawaz (1983) NEH algoritması ile sezgisel bir yöntem önermiştir. 8 Fazel-Zarandi vd. (2013) her bir parçayı yüklemek / boşaltmak için çevrime bağlı kurulum sürelerine sahip iki-makineli robotik hücreleri araştırmışlardır. Verilen parça dizisi için robot hareket sırasını bulmak adına bir MILP modeli önermişlerdir. Buna ek olarak, büyük ölçekli problemleri çözmek için bir dal ve sınır algoritması ve gelişmiş bir SA algoritması geliştirmişlerdir. Ayrıca, Geismar vd. (2004) paralel makineler ve sabit hareket süresi ile döngüsel seri üretimli tek tutuculu robotik hücreleri incelemişlerdir. Geismar vd. (2006) aynı problemi çift tutuculu robotik hücreler için de incelemiş ve elde edilen döngülerin tek tutuculu robotlu hücrelerdeki olası en iyi döngülere kıyasla daha yüksek verim alındığını belirtmiştir. Dawande vd. (2005) döngüsel üretim üzerine yoğunlaşmış ve robotik hücre çizelgeleme problemi üzerine bir araştırma yapmıştır. Shafiei-Monfared vd. (2009) tek parçalı tip için, stokastik işleme süreleri ile seri üretim ve açık atölye tipi üretim robotik hücresini incelemişlerdir. Sarkheil ve Jenab (2012) klasik robotlu hücredeki tek birim çevrimlerinin optimalitesini incelemişlerdir. Optimal döngünün, tek tutuculu robot tarafından sunulan robotik hücrelerdeki rastgele sayıda-makine için 1-birim döngüsü olduğunu kanıtlamışlardır. Buna ek olarak,Geismar vd. (2008) robotik hücreleri, paralel makineler ve çoklu çift tutuculu robotlarla değerlendirmiştir. Robotlar arasındaki değişen parçalar metodunun, iş hacmi üzerinde çok az etkisi olduğunu belirtmişlerdir. Öte yandan, işlem basamaklarının robotlara atanmasının, bir hücrenin potansiyel çıktısında önemli bir etkisi olabileceğini iddia etmişlerdir. Batur vd. (2012) çok parçalı tipler üreten iki-makineli robotik hücrelerdeki çizelgeleme problemini dikkate almışlardır. Çevrim süresini optimize etmek için iki aşamalı bir sezgisel yöntem önermişlerdir. Foumani ve Jenab (2013) kullanımda olan robotlar üzerinde karşılıklı değiştirme kabiliyeti varsayarak, iki makineli ve özdeş parçalar kullanarak robotik hücre çizelgeleme problemi üzerinde çalışmışlardır. 9 Çok parçalı robotik hücre çizelgeleme problemini inceleyen araştırmalar tablo1-1'de gösterilmektedir. Ayrıca tablo 1-1 de bu araştırmanın ilgili literatürdeki yeri belirtilmiştir. Tablo 1-1 Çok parçalı robotik hücre çizelgeleme problemleri üzerine yapılan araştırmaların sınıflandırılması Araştırmalar SN MS PCri RMS PS Sol-Proc Yöntemler Sethi vd. (1992) 2, 3 1 Serbest Belirti lmiş  - Gilmore ve Gomory algoritmasının uygulanması. Bilge ve Ulusoy (1995) S 1 Serbest   Paralel MILP modeli ve iteratif çözüm prosedürü. Chen vd. (1997) 3, S 1 Serbest Belirti lmiş  - Dal-Sınır algoritması. Hall vd. (1998) 3 1 Serbest   Ayrı Robot hareket sıralarının NP- bütünlüğü. Sriskandarajah vd.(1998) S 1 Serbest   Ayrı Parça sıralarının 4 gruba ayrılması. Aneja ve Kamoun (1999) 2 1 Serbest   Ayrı O (n log n) algoritması. Agnetis (2000) 2, 3 1 Beklem e-Yok   Paralel 2-makine durumu için bir O (n log n) algoritması.3-makine durumunun optimallik analizi. Hurink ve Knust (2001) 3, S 1 Serbest   Paralel 2, 3 ve m-makineli robotik hücre seri üretiminin karmaşıklık analizi. Hurink ve Knust (2002) S 1 Serbest   Paralel Atölye tipi robotik hücre için tabu arama yaklaşımı. Soukhal ve Martineau (2005) S 1 Serbest   Paralel MILP modeli and genetik algoritma. Soukhal vd. (2005) 2 1 Serbest   - Nakliye kapasitesi için karmaşıklık analizi. Carlier vd. (2010) S 1 Serbest   Ayrı Robot hareket sıraları için Dal- Sınır algoritması ve genetik algoritma. Kharbeche vd.(2010) S 1 Serbest   Paralel Bir MILP modeli, yeni bir Alt Sınır ve Dal-Sınır algoritması. Zahrouni ve Kamoun (2012) 3 1 Serbest   Paralel 3-makineli robotik hücre için yapıcı sezgisel MinMPSCycle. Fazel-Zarandi vd.(2013) 2 1 Serbest   Paralel Robotik seri üretim analizinin sıraya bağlı kurulum süresine genişletilmesi. Elmi ve Topaloglu (2014) S M Serbest   Paralel Yeni bir MILP modeli ve etkin tavlama simülasyonu algoritması. Her bir aşamada farklı hız makineleri ve makine uygunluk kısıtları. Bu Çalışma 1 M Serbest   Paralel Benders Ayrıştırması' na dayalı kesin bir yöntem. SN: Aşama Sayısı; MS: Makine Sayısı (her bir aşamadaki); PCri: Pickup Kriteri; RMS: Robot Hareket Sırası; PS: Parça Sırası; Sol-Proc: RMS ve PS için Çözüm Prosedürü. 10 İKİNCİ BÖLÜM: PROBLEM TANITIMI ve ÖNERİLEN KARMA TAMSAYILI DOĞRUSAL PROGRAMLAMA MODELİ Bu bölümde, bu tez çalışmasında kullanılacak formüller belirtilmiş ve problemimizin biçimsel tanımı yapılmıştır. Bu tez boyunca, özdeş makinelerden oluşan robotik üretim hücrelerine odaklanılmıştır. Robotik hücreler farklı türde parçalardan oluşan partileri işleyebilmektedir. Genellikle, bu parçaların belirli bir makinede farklı işlem süreleri bulunmaktadır. Tam zamanında üretime uygun olarak, parça tiplerinin nispi oranları, her bir partideki talebin nispi oranlarına eşit olmalıdır. Dolayısıyla, araştırmacılar aynı oranlara sahip olan en küçük parça kümesini (MPS) içeren çevrimlere odaklanmaktadırlar. Örneğin, bir şirketteki üç ürün için talepler; A ürünü için % 40, B ürünü için% 35 ve C ürünü için % 25 olarak dağıtılmıştır.Buna göre, en küçük parça kümesi (MPS)' nin 20 parçası olduğu düşünüldüğünde: A ürününe 8 parça, B ürününe 7 parça ve C ürünü de 5 parça düşmektedir. Birçok uygulamada, robotik hücreler, en küçük parça kümelerinin tekrarlı veya çevrimsel üretiminde kullanılmaktadır. Çok parçalı çizelgeleme problemlerinde, toplam üretim hedefiyle aynı oranlara sahip, mümkün olabilecek en küçük parça seti olarak tanımlanan bir MPS, tekrarlanarak üretilmektedir. Amaç, çevrimsel bir üretim ortamında bir MPS üretmek için ortalama süreyi minimize etmektir. İş hacmi oranı, bu ortalama sürenin tersi olarak tanımlanmaktadır. Genel olarak, hücre k sayıda farklı parça tiplerini işlemektedir. Bir MPS'de, i = 1. . . k olduğu durumda, i tipi ri parçaları üretilmektedir. Bir çevrimdeki tamamlanmış parça sayısı ise, n = 𝑟1 + . . . +𝑟𝑘, olarak tanımlanmıştır. Bir MPS çevrimi, MPS parçalarının girişte sisteme girdiği, sonrasında işlendiği, çıkışta sistemden ayrılarak sistemi başlangıçtaki aynı durumuna döndürdüğü bir döngü olarak tanımlanmıştır. Ayrıca MPS çevrimi, MPS parçalarının girişten hücrenin içine girdiği sıranın ve hücre içindeki bu parçalarda gerçekleştirilecek işlemlerin çizelgelenmesi olarak da tanımlanabilmektedir. 11 MPS parçalarının sıralanmasına, MPS parça dizisi adı verilmiştir. MPS robot hareket dizisi, bir MPS çevrimi sırasında gerçekleştirilen robot aktivitelerinin sıralanmasıdır. Minimum çevrim süresi ile bir MPS çevriminin hesaplanması iki kat zor olmaktadır. Şöyle ki, bu durumda iki karar alınması gerekmektedir: (a) bir robot hareket sırası seçmek, ve (b) bir parça sırası belirlemektir. Robotik bir hücredeki parçaların optimal olarak çizelgelenmesinin amacı, minimum çevrim süresi ile MPS çevrimini bulmaktır. Bu, çevrim süresinin minimize edilebilmesi için, bir parçanın sırasının ve robot hareket sırasının aynı anda belirlenmesini gerektirmektedir. Bir makinenin, bir parça türünün tüm işlemlerini gerçekleştirebileceğini ve bu işlemlerin işleme sırasının değiştirilebileceğini belirten operasyonel ve süreç esneklikleri tanımlarına dayanılarak; gerekli tüm işlemleri gerçekleştirebilen, aynı özdeş makinelerin bulunduğu sıralı bir robotik hücre düşünülmektedir. Şekil 2.1 'de bu tür hücreler gösterilmektedir. Her bir parçanın faaliyet göstereceği bilinen işlem sürelerine sahip olduğu kabul edilmektedir. Robotik hücre sistemlerini etkin bir şekilde kullanabilmek için, robot hareketlerinin çizelgelendirilmesi ve her bir parçanın işlenmesine yönelik makinelerin belirlenmesi problemleri çözülmelidir. Bu çalışmada, işlemleri kendilerine tahsis ederek, makinelerde işlenecek parçalar ve ortaklaşa çevrim süresini minimize edecek robot hareket döngüsü bulunmaya çalışılacaktır. 12 S1 S3 Input Device Output Device S2 m1 m2 m3 m4 Şekil 2.1: Paralel makineli robotik hücrelerde örneği Bu çalışma süresince, parçaların işlem sürelerinin tam sayı değerinde olacağını varsayılmaktadır. Çalışmamızda ve literatürdeki çalışmalarının bir çoğunda yaygın olan temel varsayımlar şu şekildedir:  Tüm veriler deterministiktir.  Parçalar her zaman giriş tamponunda mevcuttur ve çıkış tamponunda daima boş bir yer bulunmaktadır.  Makineler arasında tampon bellek yoktur, her bir parça, bir makinede veya robot tarafından işlenmektedir.  Hem robot hem de makineler herhangi bir zamanda birden fazla parçaya sahip olamamaktadır.  Robot ve işleme makineleri hiçbir zaman arıza yaşamamakta ve asla bakım gerektirmemektedir.Ayrıca, kurulum sürelerinin ihmal edilebilir olduğu varsayılmaktadır.  Herhangi bir işleme, süreçte öncelik tanınmamaktadır 13 Yukarıda belirtildiği gibi, bu çalışmada odak noktası olarak çok parçalı üretim alınmıştır. Dolayısıyla, parçaların makinelere tahsis edilmesi, parçaların çizelgelenmesi ve robotik hücreler için robot hareketlerinin sıralanması gibi tüm problemlerin çözülmesi gerekmektedir. Araştırmacılar, optimum parça dizisi ve robot hareket döngüsü için, çevrim süresini verilen işlem süresine göre minimize etmeyi hedeflemektedir. Çoklu parça türüne sahip olunduğu halde, aynı parça türüne ait iki özdeş parça farklı yerleşimlerde olabilir. Bu nedenle, bu çalışma kapsamında MPS' deki her bir bölüm, bağımsız bir parça türü olarak değerlendirilmektedir. Paralel makine robotik hücre çizelgeleme problemi için karma tamsayılı doğrusal programlama (MILP) modeli, işlemlerin tamamlanma sürelerine dayalı olarak ürün üretim süresini minimize etmek için önerilmiştir. Açıkça görülmektedir ki, ürün üretim süresini minimize etmek iş hacmini arttırmaktadır. Geliştirilen model aşağıda sunulmaktadır: 2.1 Matimatik Problem 2.1.1 İndisler: J = Parça sayısı, j ∈ {1, 2... J}, S = Giriş ve çıkış aşamaları dikkate alınan kademe sayısı, s ∈ {1, 2, 3}, Ms = Giriş ve çıkış aşamalarının sadece bir makineye sahip olduğu s aşamasındaki ilgili makinelerin sayısı, m ∈ {1, 2... Ms}, W = Robotun taşıma işlemlerinin sayısı, f ∈ {1, 2... W}, 2.1.2 Parametreler: Pj = İşlem aşamasındaki j inci parçanın giriş ve çıkış aşamalarındaki (sırasıyla, s = 1, 3) tüm bölümlerin işlem süresi sıfıra eşit olan standart işlem süresi, SP = Robotun işlenme hızı, BM = çok büyük sayı, geleneksel "Büyük M ". 14 2.1.3 Karar Değişkenleri: Xj, j’ = Eğer j inci parça işlem aşamasında 𝑗′ inci parçadan önce işlenirse 1; aksi takdirde 0’dır, Zj, s, f = Eğer s aşamasındaki j parçası, robot tarafından bir sonraki aşamaya aktarılabilecek f inci işlem ise 1, Yj, s, m = Eğer m makinesi s aşamasında j parçasını işliyor ise 1, aksi takdirde 0'dır. Dj,s = s aşamasından j inci parçanın ayrılma zamanı, CMAX = Tüm parçaların çıkış cihazına ulaşma süresi. 2.2 Amaç Fonksiyonu ve Kısıtlar: 𝑴𝒊𝒏𝒊𝒎𝒊𝒛𝒆 ∶ 𝐶𝑀𝐴𝑋 Dj,2 + BM × (2 − (Yj,2,m + Yj,1,m′)) ≥ Dj,1 + (SP × (1 + |m − m′|)) + Pj,2 (1) j ∈ {1,2, … , J}; m ∈ M2; m′ ∈ M1 (∑ Yj,s,m Ms m ) = 1 (2) j ∈ {1,2, … , J}; s ∈ {1,2,3} (∑ Zj,s,f W f=1 ) = 1 (3) j ∈ {1,2, … , J}; s ∈ {1,2} (∑ ∑ Zj,s,f 2 s=1 J j=1 ) = 1 (4) f ∈ {1,2, … , W} (∑ Zj,2,f f′ f=1 ) − BM × (1 − Zj,1,f′) ≤ 0 (5) j ∈ {1,2, … , J};f′ ∈ {1,2, … , W} (∑ Zj,1,f f′ f=1 ) − BM × (3 − Yj′,2,m − Yj,2,m − Zj′,2,f′ + Xj,j′) ≤ 0 (6) j, j′ ∈ {1,2, … , J}, j ≠ j′; m ∈ Ms; f′ ∈ {1,2, … , W} 15 (∑ Zj′,1,f f′ f=1 ) − BM × (4 − Yj′,2,m − Yj,2,m − Zj,2,f′ − Xj,j′) ≤ 0 (7) j, j′ ∈ {1,2, … , J}, j ≠ j′;m ∈ Ms; f′ ∈ {1,2, … , W} Dj,s + (BM × (5 − Yj,s,m − Yj′,s′,m1 ′ − Yj′,s′+1,m2 ′ − Zj′,s′,f−1 − Zj,s,f)) ≥ Dj′,s′ + (SP × ((|s′ − (s′ + 1)| + |m1 ′ − m2 ′ |) + (|(s′ + 1) − s| + |m2 ′ − m|))) (8) j, j′ ∈ {1,2, … , J}, j ≠ j′;s, s′ ∈ {1,2}; m′1 ∈ Ms′;m′2 ∈ Ms′+1; m ∈ Ms;f ∈ {2, … , W} CMAX + BM × (2 − Yj,2,m − Zj,2,W) ≥ Dj,2 + (SP × (1 + |1 − m|)) (9) j ∈ {1,2, … , J};m ∈ M2 Xj,j′ , Yj,s,m , Zj,s,f ∈ {0,1} (10) Kısıt (1); sadece, giriş aygıtından ayrılmış ve robot ile işlem aşamasına taşınmış bir parçanın işlenebileceğini belirtmektedir. Başka bir deyişle, bir parçanın işlem aşamasından ayrılma süresinin, giriş cihazından ayrılma süresi ile ulaştırma ve işlem sürelerinin toplamına eşit veya bundan daha büyük olmalıdır. Kısıt (2); bir parçanın yalnızca giriş ve çıkış aşamalarının sıfır-işlem süresi olan tek bir makineye sahip olduğu kabul edilen her aşamadaki makinelerden birinde işlenmesini sağlamaktadır. Kısıt (3, 4); robotun bir seferde yalnızca bir parçayı transfer ettiğinden emin olmaktadır. Kısıt (5); bir parçanın ancak bir önceki aşamayı geçtikten sonra, bir sonraki aşamaya geçebileceğini belirtmektedir. Kısıt (6, 7); aynı makinede bir aşamada işlenen işlem sırasının, robotun boşaltma sırasına göre belirlendiğini belirtmektedir. 16 Kısıt (8); robot tarafından aynı anda iki boşaltma işleminin gerçekleştirilmemesini sağlamaktadır. Ayrıca bu kısıt, robot tarafından işlenen boşaltma işlemlerinin sırasını da belirtmektedir. Kısıt (9); ürün üretim süresinin, son parçanın ayrılma zamanının, işlem aşaması ve nakliye süresinin toplamından çıkarılmasına eşit veya bundan daha büyük olduğunu belirtmektedir. 17 ÜÇÜNCÜ BÖLÜM: ÇÖZÜM PROSEDÜRÜ: MANTIK TABANLI BENDERS AYRIŞTIRMA METODU Benders Ayrıştırma (BD) algoritması, Benders (1962) arafından önerildiğinden bu yana elli yıldan fazla bir süre geçmiştir. Temel amaç, geçici olarak sabitlendiğinde çözülmesi kolaylaşan karmaşık değişkenler ile problemi çözmektir. BD yöntemi (değişken bölümleme ve dış doğrusallaştırma olarak da adlandırılır), en yaygın kullanılan kesin algoritmalardan biri haline gelmiştir, çünkü problemin yapısından yararlanmakta ve toplam hesaplama yükünü ortadan kaldırmaktadır. Bu yöntem ile birçok çeşitli alanda başarılı uygulamalar bulunmaktadır; planlama ve çizelgeleme Canto (2008) ve Hooker (2007) sağlık Luong (2015) ulaştırma ve telekomünikasyon Costa (2005) enerji ve kaynak yönetimi vd. (2006) ve kimyasal işlemler tasarımı Zhu ve Kuno (2003) dahil olmak üzere, bu uygulamalar. Tablo 3-1 de gösterilmektedir: 18 Tablo 3- 1 Benders ayrıştırma yönteminin bazı uygulamaları Referans Uygulama 1 Behnamian (2014) Üretim Planlama 2 Adulyasak vd. (2015) Üretim Rotalama 3 Boland vd. (2015) Tesis Yeri 4 Boschetti ve Maniezzo (2009) Proje Çizelgeleme 5 Botton vd. (2013) Ağ Tasarımı 6 Cai vd. (2001) Su Kaynakları Yönetimi 7 Canto (2008) Bakım Çizelgelemesi 8 Codato ve Fischetti (2006) Haritalama 9 Cordeau vd. (2006) Mantıksal Ağ Tasarımı 10 Cordeau vd. (2001a) Lokomotif Ataması 11 Cordeau vd. (2001b) Havayolu Çizelgelemesi 12 Corréa vd.(2007) Araç Rotalama 13 Côté vd. (2014) Şerit Paketleme 14 Fortz ve Poss (2009) Ağ Tasarımı 15 Gelareh vd. (2015) Taşımacılık 16 Jenabi vd. (2015) Güç Yönetimi 17 Jiang vd. (2009) Dağıtım Planlama 18 Kim vd. (2015) Stok kontrol 19 Laporte vd. (1994) Seyyar Satış 20 Luong (2015) Sağlık Planlaması 21 Maravelias ve Grossmann (2004) Kimyasal İşlemler Tasarımı 22 Moreno-Centeno ve Karp (2013) IHS 23 Oliveira vd. (2014) Yatırım Planlama 24 Osman ve Baki (2014) Transfer Hattı Dengelemesi 25 Pérez-Galarce vd. (2014) Kapsama Ağacı 26 Pishvaee vd. (2014) Tedarik Zinciri Ağı Tasarımı 27 Rubiales vd. (2013) Hidrotermal Koordinasyon 28 Saharidis vd. (2011) Rafineri Sistemi Şebeke Planlaması 29 Sen vd. (2015) Bölüm Dağılımı 30 Bloom (1983) Kapasite Genişletme 31 Wang vd. (2016) Optimal Güç Akışı 19 BD yöntemi, bir proje planlama dizisi, dış doğrusallaştırma ve hafifletmeye dayanmaktadır. Geoffrion (1970a ve 1970b). Bu yüzden, model ilk önce, karmaşık değişkenler kümesi tarafından tanımlanan alt uzay üzerine yoğunlaşmaktadır. Ortaya çıkan formül, sonrasında dualize edilmekte, ilişkili sınır doğruları ve noktaları sırasıyla olurluluk gereksinimlerini (olurlu kesmeler) ve karmaşık değişkenlerin öngörülen maliyetlerini (optimumluk kesmeleri) tanımlamaktadır. Böylece, eşdeğer bir formülasyon tüm sınır noktaları ve doğruları numaralandırılarak oluşturulabilmektedir. Bununla birlikte, bu numaralandırmayı gerçekleştirmek ve daha sonra ortaya çıkan formülasyonu çözmek, imkansız olmasa da, genellikle hesaplama açısından yorucu olmaktadır. Bu nedenle, olurluluk ve optimumluk kesmelerine bir hafifletme stratejisi uygulanarak eşdeğer modeli çözülmektedir. İhlal edilen kesmeleri oluşturmak ve arama sürecini yönlendirmek için sırasıyla tekrarlı bir şekilde çözülen bir Ana Problem (MP) ve bir alt problem beraberinde getirmektedir. BD algoritması, önceleri karma tamsayı doğrusal programlama (MILP) problemleri için önerilmiştir. Tamsayı değişkenleri sabitlendiğinde ortaya çıkan problem, kesmeleri geliştirmek için standart dualite teorisi kullanılabilinen sürekli (kesiksiz) doğrusal programlamadır (LP). Birçok ekleme ile, algoritma daha geniş bir problem aralığına uygulanmak için geliştirilmiştir Geoffrion (1972) ve (Hooker ve Ottosson 2003). Bazı optimizasyon sınıfları üzerinde algoritmanın etkinliğini artırmak için diğer gelişmeler önerilmiştir Costa vd. (2012) ve (Crainic vd. 2014). Buna ek olarak, BD, sıklıkla problemler için etkin sezgisel yöntemlerin tasarımı için bir temel oluşturmaktadır Cote (1984) Raidl ( 2015). BD yaklaşımı, Tablo 3-2 'de gösterildiği gibi doğrusal, doğrusal olmayan, tamsayı, stokastik, çok aşamalı, iki seviyeli ve diğer optimizasyon problemleri için yaygın olarak kullanılmaya başlamıştır. 20 Tablo 3- 2 Benders yöntemi ile ele alınan optimizasyon problemlerine örnekler Referans Model 1 Adulyasak vd. (2015) Çokaşamalı Stokastik Problem 2 Behnamian (2014) Çok amaçlı MILP 3 Cai vd. (2001) Çok amaçlı konveks ve doğrusal olmayan problem 5 Cordeau vd. (2001b) Pure 0–1 formülasyonu 6 Corréa vd. (2007) Mantıksal ifadeler ile binary problem 7 Gabrel vd. (1999) Artan maliyet 8 Côté vd. (2014) Mantıksal kısıtlı MILP 9 de Camargo vd. (2011) Karma-tamsayılı doğrusal olmayan program (MINLP) 10 Emami vd. (2016) Robust optimizasyon problemi 11 Fontaine ve Minner (2014) İki-seviyeli kısıtlı çift-doğrusal problem 12 Fortz ve Poss (2009) Çok katmanlı kapasite ağ problemi 13 Gendron vd. (2014) Doğrusal olmayan kısıtlarla binary problem 14 Grothey vd. (1999) Konveks-doğrusal olmayan problem 15 O’Kelly vd. (2014) İçbükey amaç fonksiyonu ve merdiven kısıt matris yapısı ile MINLP 16 Jenabi vd. (2015) Kesitsel doğrusal karma-tamsayı problemi 17 Kim vd. (2015) Çok aşamalı stokastik program 18 Laporte vd. (1994) Olasılıksal tamsayı formülasyonu 19 Li (2013) Büyük ölçekli konveks olmayan MINLP 20 Moreno-Centeno ve Karp (2013) Önceden bilinmeyen kısıtlamalar problemi 21 Bloom (1983) Güven kısıtlı doğrusal olmayan çok periyotlu problem 22 Osman ve Baki (2014) Doğrusal olmayan tamsayı formülasyonu 23 Pérez-Galarce vd. (2014) En küçük/En büyük pişmanlık problemi 24 Pishvaee vd. (2014) Çok Amaçlı Olasılıksal Programlama Modeli 25 Raidl vd. (2014) Tamsayılı, iki-seviyeli, kapasite problemi 27 Rubiales vd. (2013) İkinci derece MILP ana problemi ve doğrusal olmayan alt problem 28 Sahinidis ve Grossmann (1991) MINLP ve konveks olmayan problem 29 Harjunkoski ve Grossmann (2001) Mantıksal ve Büyük-M kısıtlı çok aşamalı problem 21 (Costa, 2005) tarafından yapılan güncel araştırmada, yalnızca sabit bedelli ağ tasarımı problemleri incelenmektedir. Bu çalışmanın asıl amacı; bu boşluğun doldurulmasına şimdiki en son teknolojinin incelenmesi ile katkıda bulunmak, yöntemin hızlandırılması için ana fikirlere odaklanmak, daha genel sorunları halletmeyi amaçlayan ana değişkenleri ve uzantılarını tartışmak ve doğrusal olmayan / tamsayılı / kısıtllı programlama alt problemlerini , eğilimleri ve umut verici araştırma yönlerini belirleyebilmektir. 3.1 Benders Ayrıştırma Metodu Bu bölümde, Benders algoritmasının klasik versiyonunu gösterilmiştir (Benders, 1962). 3.1.1 Klasik Versiyon Modelin bir MILP olduğu düşünülmüştür: Minimize f T y + cT x (1) Öyle ki Ay = b (2) 𝐵𝑦+𝐷𝑥 = d (3) X ≥ 0 (4) y ≥ 0 (5) y ∈ 9n1 karmaşık değişkenleri; A ∈ 9m1 × n1 bilinen bir matris ve b ∈ 9m1 verilen bir vektör olmak üzere, Ay = b kısıt setini karşılaması ve pozitif tam sayı değerlerini alması gerekmektedir. Sürekli değişken x ∈ 9n2, y değişkenleri ile birlikte, By + Dx = d bağlanma kısıtını , B ∈ 9m2 × n1, D ∈ 9m2 × n2 ve d ∈ 9m2 ile karşılamalıdır. Amaç fonksiyonu, toplam maliyeti f ∈ 9n1 ve c ∈ 9n2 maliyet vektörleri ile minimize etmektedir. 22 Model (1-5) şu şekilde yeniden ifade edilebilir: Min {𝑓𝑇 �̅� + min {𝑐𝑇 x: 𝐷𝑥 = d -𝐵�̅�},} (6) İç minimizasyon, Y = {y|𝐴𝑦 = b, y≥ 0} kısıt kümesiyle ilişkili π dual değişkenleri vasıtasıyla dualleştirilebilen sürekli bir doğrusal problemdir Dx = d − Bȳ: Min {π𝑇 d -𝐵�̅�): π𝑇 D ≤ c} (7) Dualite teorisine dayanarak, birincil ve dual formülasyonlar, aşağıdaki eşdeğer formülasyonu çıkarmak için değiştirilebilmektedir: Min {𝑓𝑇�̅� + max {π𝑇 d -𝐵�̅�): π𝑇 D ≤ c}} (8) İç maksimizasyonun olurlu alanı, şöyle ki, F = {π | 𝜋 𝑇D ≤ c}, �̅� 'nin seçiminden bağımsızdır. Dolayısıyla, F boş küme değilse, iç problem, herhangi bir y ̅ rastgele seçimi için sonsuz ya da olurlu olabilmektedir.İlk durumda; 𝑟𝑇 (d - B�̅�) > 0, 𝑟 𝑞, q ∈ Q için; sonsuzluk mevcuttur; Bu durumdan kaçınılmalıdır, çünkü �̅� ‘nin çözümsüzlüğünü belirtmektedir. Kesme eklendiği 𝑟𝑞 𝑇 (d - B�̅�) ≤ 0 ∀ q∈ Q (9) Model (9) un tüm kesmelerini dış minimizasyona eklersek, iç problemin değeri kendi sınır noktalarından biri olacaktır.Bu nedenle, model (8) şu şekilde yeniden formüle edilebilmektedir: Min 𝑓𝑇 �̅� + max {𝜋𝑒 𝑇 (d-𝐵�̅�)} (10) Öyle ki 𝑟𝑞 𝑇(d- 𝐵�̅�)≤ 0 ∀ q ∈ Q (11) �̂� ∈ 𝑌 x≥ 0 π∈ ℜ 𝑚2 �̂� ∈ 𝑌 π∈ ℜ 𝑚2 �̂� ∈ 𝑌 e∈ 𝐸 23 e q Bu problem, Benders Ana Problemi (MP) olarak adlandırdığımız problem (1-5) için aşağıdaki denk formülasyon ile sürekli bir değişken olan η ∈ 9 vasıtasıyla kolay bir şekilde doğrusal hale getirilebilmektedir: Min 𝑓𝑇 𝑦 + ŋ (12) Öyle ki Ay = b (13) η ≥ πT (d − By) ∀e ∈ E (14) 0 ≥ rT (d − By) ∀q ∈ Q (15) y ≥ 0 ve tamsayı Kısıt (14) ve (15) ‘e sırasıyla optimumluk ve olurluluk kesmeleri adı verilmiştir. Bu kesmelerin bütün olarak listelenmesi genellikle pratik değildir. Bu nedenle, Benders (1962), olurluluk ve optimallik kesmelerine bir hafifletme ve iteratif bir yaklaşım önermiştir. Böylece, BD algoritması, y değişkenleri için bir deneme değeri elde etmek için (14) ve (15) kısıtlarının sadece bir alt kümesini içeren MP' yi tekrarlı bir şekilde çözmektedir. Daha sonra y¯ ile birlikte alt problemi çözmektedir. Alt problem olurlu ve sınırlanmışsa, (14) tipi bir kesme üretilmektedir. Alt problem sınırlanmamışsa, (15) teki türde bir kesim üretilmektedir. Kesmeler mevcut çözüm ile ihlal edilirse, bunlar mevcut MP'ye sokulmakta ve süreç tekrarlanmaktadır. Şekil.3.1 BD algoritmasını göstermektedir. İlk MP ve altproblemi türettikten sonra, algoritma, MP ve altproblem arasında (MP'den başlayarak) en uygun çözüm bulunana kadar sürekli olarak, sıra ile yapılmaktadır. MP'nin amaç fonksiyonu, eşdeğer Benders-yeniden formülasyonunun bir hafifletmesi olduğundan optimum maliyet üzerinde geçerli düşük bir sınır vermektedir. Bunun yanısıra, orjinal formülasyonda y¯ ifadesini sabitlemeye eşdeğer olan alt problemin objektif değeri ile y¯ çözümünün birleştirilmesi, optimal maliyet üzerinde geçerli bir üst sınır getirmektedir. 𝑦,̂ ŋ 24 Şekil 3.1 Benders ayrıştırma yönteminin şematik gösterimi. 3.2 Benders Ayrıştırması için Model Seçimi Verilen bir problem, genellikle farklı ama eşdeğer formülasyonlar ile modellenebilmektedir. Bununla birlikte, hesaplama açısından çeşitli formülasyonlar eşdeğer olmayabilmektedir. Geoffrion ve Graves (1974) formülasyonun BD' nin performansı üzerinde doğrudan etkisi olduğunu gözlemlemiştir. Magnanti ve Wong (1981) daha güçlü bir doğrusal programlama hafifletmesine sahip bir formülasyonun daha iyi performans göstereceğini göstermiştir. Bu, daha küçük kesirli değişkenlerin sayısının ve ayrıca kesme kısımların büyük olasılıkla daha güçlü olması nedeniyle oluşmaktadır. Sahinidis ve Grossmann (1991) sıfır NLP hafifletme aralığına sahip karma tamsayılı doğrusal olmayan programlama (NLP) formülasyonuna uygulanan BD yönteminin yakınsama için sadece en uygun çözüme karşılık gelen kesmenin gerekliliğini kanıtlamıştır. Cordeau vd. ( 2006) stokastik bir lojistik ağ tasarımı problemi üzerinde çalışmışlardır. Orijinal formülasyon bir dizi geçerli eşitsizlikler (VIs) ile güçlendirildiğinde BD yönteminin performansının önemli ölçüde arttığını bulmuşlardır. Bu gözlemler, BD yöntemi bağlamında sıkı formülasyonların önemini açığa çıkarmıştır. Bununla birlikte, sıkı formülasyonlar genellikle ek kısıtlar eklenerek elde edilmektedir. Bu, daha yüksek derecede yakınsama gösterebilen, daha zaman alıcı bir alt problemin ortaya çıkmasıyla sonuçlanabilmektedir. Bu nedenle, iterasyon sayısındaki azalma ile alt probleme gelecek ek zorluklar arasında bir dengelenme olmalıdır. 25 3.3 Diğer Ayrıştırma Metodları ile İlişkiler BD yöntemi, doğrusal programlama için Dantzig-Wolfe ve Lagrangian optimizasyonu gibi diğer ayrıştırma yöntemleriyle yakından ilişkilidir (Lim 2010). Özellikle, bir doğrusal programlamanın Dantzig-Wolfe ayrıştırması ile çözülmesi, BD yaklaşımına dualite uygulanmasına eşdeğerdir. Dantzig-Wolfe ile BD yöntemleri arasında problemler için karmaşık değişkenlerin dual olması nedeniyle son derece açık bir ilişki mevcuttur. Alt problemlerin iki yöntemde de eşdeğer olduğu unutulmaması gerekmektedir. BD yöntemi, ayrıca Lagrange dualine uygulanan bir kesen düzlem metoduna eşdeğerdir. Tamsayılı programlamada, durum daha karmaşıktır ve ayrıştırma yöntemleri arasında basit bir ilişki bulunmamaktadır. Lagrange hafifletmesi ve Dantzig-Wolfe ayrıştırmasının aksine, BD yöntemi, sorunun hafifletilmesinden ziyade MILP’ ye doğrudan optimal bir çözüm getirmektedir. Son olarak, Benders kesmeleri ile çeşitli klasik eşitsizlikler arasında yakın bir ilişki bulunmaktadır (Magnanti vd. 1986). Örneğin, Costa vd. (2009) eşitsizliklerin temelde Benders olurluluk kesmeleri olduğunu göstermiştir.Klasik BD yöntemi, çeşitli arttırma ve ivme stratejileri önerilen sayısal ve teorik sınırlamalara sahiptir. Bu tez, kaynak kısıtları ile paralel makine çizelgelemesi gibi imalat bağlamında sıklıkla ortaya çıkan bir çizelgeleme problemini ele almaktadır. Parçalar, tesislere atanmalı ve her tesis üzerinde, işlem sürelerine bağlı olarak çizelgelenmelidir. Belirli bir tesise atanan parçalardan bazıları herhangi bir zamanda paralel olarak çalışamamaktadır. Öncelikli kısıtlar, parçaların nakliye işlemleri nedeniyle gözardı edilmektedir. Amaç, üretim süresini minimize etmektir. Bu tür problemler sıklıkla ortaya çıkmasına rağmen, çözümün oldukça zor olduğu kanıtlanmıştır. Etkili bir biçimsel algoritmanın yokluğunda, uygulamada genellikle sağduyulu bir yaklaşım kullanılmaktadır. Problem, atama kısmı ve çizelgeleme kısmı olarak ayrıştırılabilmektedir. Probleme bir çözüm metodolojisi olarak Benders ayrıştırma yöntemi uygulanabilmektedir. Benders ana problemi, tesislere bölümler tahsis etmekte; alt problem ise, birkaç bağımsız çizelgeleme problemlerine ayrılmaktadır. Benders ana problemine eklenen kesmeler, ilgili tahsislerden kaçınmak için olan operasyonların matematiksel karşılıklarıdır. Normal koşullar altında, Benders algoritması, toplam tahsis ve çizelgeleme problemlerinin optimal çözümü ile son bulmaktadır. 26 Alt problem, ya sürekli doğrusal ya da doğrusal olmayan bir programlama problemi olmasını gerektirdiğinden, klasik Benders yaklaşımı Benders (1962) ve Geoffrion (1972) bu problem için uygun olmamaktadır.Çizelgeleme; herhangi bir doğrusal veya doğrusal olmayan programlama modeline sahip olmayan, oldukça kombinasyonel bir problemdir. Neyse ki Benders ayrıştırma fikri, kesikli bir çizelgeleme problemi gibi rastgele bir alt probleminin yer aldığı mantık tabanlı bir forma genişletilebilmektedir. Bu çalışma, mantık tabanlı Benders yönteminin paralel makine robotik hücre çizelgeleme problemine nasıl uygulanabileceğini araştırmaktadır. Klasik Benders yaklaşımının aksine, mantık tabanlı Benders, Benders kesmelerini üretmek için standart bir şema oluşturamamaktadır. Her bir problem sınıfı için kesmeler oluşturulmalıdır ve bu araştırmanın temel hedefi, bu eylemin paralel makine robotik hücre çizelgeleme problemi için yapılabileceğini göstermektir. Klasik Benders ayrıştırması, birincil değişkenlerin değerlerini numaralandırarak problemi çözmektedir. Numaralandırılan her bir değer kümesi için, birincil değişkenlerin bu değerlere sabitlenmesinden kaynaklanan alt problemi çözülmektedir. (Bizim çalışmamızda, birincil değişkenler parçaların makinalara tahsisini ifade etmektedir.) Alt problemin çözümü, numaralandırılmış sonraki tüm çözümlerde birincil değişkenleri karşılamasını gerektiren Benders kesmesini üretmektedir. Benders kesmesi, bir alt problem dualinin çözümünden elde edilen Lagrange çarpanlarına dayanan lineer bir eşitsizliktir. Birincil değişkenler için bir sonraki değer kümesi, şimdiye kadar üretilen tüm Benders kesmelerini içeren ana problemi çözerek elde edilmektedir. Süreç, ana problem ve alt problem bir değerde birleşinceye kadar devam etmektedir. Mantık tabanlı Benders ayrıştırması, Hooker ve Yan (1995) tarafından mantık devresi doğrulaması bağlamında açıklanmıştır. Fikir, resmen Hooker (2000) tarafından geliştirilmiş ve Hooker ve Ottosson (2003) tarafından 0-1 programlaması üzerinde uygulanmıştır. Mantık tabanlı Benders ' da, Benders kesmeleri, alt problemin tahmin duali çözülerek elde edilmektedir. Tahmin dualinin çözümü, birincil değişkenler mevcut değerlerine sabitlendiğinde bir optimallik ispatı olarak görülmektedir. Benders kesmesi, birincil değişkenler başka değerler aldığında optimum değer üzerinde geçerli bir sınır elde etmek için bu aynı ispat kullanılarak oluşturulmuştur. Mantık tabanlı Benders kesmeleri, herhangi bir formda varsayılabilecek olmasına 27 rağmen, mevcut bağlamda doğrusal eşitsizlikler olarak formüle edilmelidir; çünkü ana problem MILP'dir. Mantık tabanlı Benders uygulaması, planlama ve çizelgeleme için Hooker (2000) tarafından önerilmiş ve ilk kez Jain ve Grossmann (2001) tarafından uygulanmıştır. Bu fikri, kümülatif çizelgeleme problemlerine uygulamaktan çok; alt problemlerinin görevlerin tek tek yapılması gereken ayrık çizelgeleme problemi olduğu, minimum maliyetli planlama ve çizelgeleme problemlerine uygulamışlardır. Harjunkoski ve Grossmann (2002) bu çalışmayı çok aşamalı problemlere kadar genişletmiştir. Benders kesmeleri bu durumlarda özellikle basittir, çünkü alt problem bir optimizasyon probleminden çok, bir olurluluk problemidir. Hooker (2005) gecikmiş iş sayısını minimize etmek için Benders yöntemini uygulamıştır. Chu ve Xia (2005) alt problemin tamsayılı programlama modeliyle Benders kesmeleri üreterek minimum üretim süresi problemini çözmüşlerdir, fakat hızlanmalar burada rapor edilenlerden önemli ölçüde daha az olmuştur. Hooker (2000) ana problemin yalnızca bir kez, Benders kesmelerini ürettikçe biriktiren bir dallanma algoritması ile çözülmesi gerektiğini gözlemlemiştir. Thorsteinsson (2001) bu yaklaşımın, Jain ve Grossmann (2001) ın problemleri üzerinde standart mantık tabanlı Benders 'lardan çok daha iyi bir performans sergileyebileceğini göstermiştir. Mantık tabanlı Benders yöntemleri, tamsayılı programlama problemlerini Chu ve Xia (2004) Hooker ve Ottosson (2003) ve önermeli tatmin edilebilirlik problemini Hooker (2000) Hooker ve Ottosson (2003) çözme üzerine uyarlamıştır. Benzer düşünceler, otomatik kılavuzlu araçların minimum sevkiyat sürelerine Correa vd. (2004) çelik üretim çizelgelemesine Harjunkoski ve Grossmann (2002) bilgisayar işlemcilerinin gerçek zamanlı çizelgelemesine Cambazard vd. (2004) trafik güzergah yöntemine Chu ve Xia (2004) Kimyasal bir fabrikada parti çizelgeleme Maravelias ve Grossmann (2004) ve polipropilen parti çizelgeleme Timpe (2002) çalışmalarında uygulanmıştır. Bütün bu uygulamalarda (tamsayı programlama hariç) alt problem olurluluk problemidir. Mantık Tabanlı Benders Ayrıştırması (LBBD), Hooker (2000) Hooker ve Ottosson (2003) Hooker ve Yan (1995) tarafından geliştirilen klasik Benders Ayrıştırması’nın Benders (1962) genellemesidir. Mantıksal devrelerin doğrulanması Hooker ve Yan (1995) planlama ve çizelgeleme Bajestani ve Beck (2013) Benini vd. (2005) Hooker (2005, 2007) stokastik ve deterministik konum / filo yönetimi Fazel-Zarandi ve Beck (2012) Fazel-Zarandi vd. (2013) ve 28 kuyruk tasarımı ve kontrolü Terekho vd. (2009) çalışmalarını içeren çok çeşitli kombinasyonel optimizasyon problemlerinde uygulanmıştır. Bu çalışmada, Hooker ve Ottosson (2003) 'a göre notasyon ve açıklama sunulmaktadır. LBBD de bir problemi modellemek için, öncelikle karar değişkenlerini iki vektöre (x ve y) ayırmak gerekmektedir. Genellikle, problem aşağıdaki gibidir: Minimize f(x, y) (16) s.t. (x,y) ∈ S, (17) x ∈ 𝐷𝑥 , y ∈ 𝐷𝑦 (18) Burada; f: gerçek değerli bir fonksiyondur; S: olurlu küme (genellikle kısıtların toplanmasıyla tanımlanmaktadır) ve 𝐷𝑥 ve 𝐷𝑦: sırasıyla x ve y 'nin etkinlik alanlarıdır. Problem, sadece x'i içeren veya ana problem değişkenleri ve alt problem değişkenleri x ve y 'yi karıştıran kısıtlara bölünmüştür. Ana problemde yalnızca x değişkenleri dikkate alındığından, olurlu set S, hafifleticidir ve S¯ olarak gösterilmektedir. Klasik Benders ayrıştırmalarından farklı olarak, ayrışmanın farklı bileşenleri üzerinde yapısal kısıtlamalar (ör.doğrusallık) yoktur. Ana problem aşağıdaki gibi tanımlanabilmektedir: Minimize z (19) s.t. x ∈ 𝑆̅ , (20) z ≥ 𝛽𝑥𝑘 (x), k=1,………., K (21) x ∈ 𝐷𝑥 . (22) 29 Burada z, gerçek değerli bir karar değişkenidir; S¯, S'nin bir hafifletmesidir ve 𝛽𝑘𝑥,(x)'in 𝑥𝑘 'ye sabitlenmesinde bulunan amaç fonksiyonu f(x, y) üzerindeki Benders kesmeleridir. Kısıt (20), alt problemin çözülmesinden türetilir ve 𝑥1…. .𝑥𝑘, önceki iterasyonlarda bulunan ana problem çözümlerindeki x değişkeninin değerleridir.İterasyon-k için alt problem: Minimize f (𝑥𝑘 ,y) (23) s.t. (𝑥𝑘 , y) ∈ S) (24) y ∈ 𝐷𝑦 . (25) Bir LBBD modelinin çözülmesi, tekrarlı bir şekilde ana problemin ve alt problemlerin yakınsanmasına kadar çözülmesini içermektedir.Ana problem, iterasyon-k da, zk maliyeti ile xk üretmek amacıyla optimal durum için çözülmüştür. Daha sonra bu çözüm, her biri z üzerinde üretilen sınırlayıcı fonksiyonların (Benders kesenleri) çözülmesi, bir veya daha fazla alt problemi formüle etmek için kullanılmıştır. Eğer k inci ana problemin çözümü iterasyon-1 den iterasyon-k ya kadar elde edilen tüm yeni sınırlayıcı fonksiyonları karşılarsa, yöntem optimum çözüme yakınsanmıştır (zk = f (xk,yk) ; yk, Alt problemin çözümü). Aksi takdirde, Ana problem tekrar çözülmeli ve iterasyonlar devam etmelidir. Uygun koşullar altında Benders kesmeleri üzerinde, işlemin sonlu sayıda iterasyonlarla optimal bir çözüme yaklaştığı gösterilebilmektedir (Chu ve Xia 2005). 3.4 Ana Problem Burada, işleme aşamasındaki (ikinci aşama) her bir makinenin toplam işlem süresi ve de üretim süresi minimize edilirken, işler makinelere atanmaktadır. Ana problemde robot hareket süreleri dikkate alınmamaktadır.Bu atama, tüm makineler için uygulanabilir bir çizelgeyi de beraberinde getirmektedir.Ana problem aşağıda gösterilmiştir: 30 [𝐌𝐏]: 𝑀𝑖𝑛𝑖𝑚𝑖𝑧𝑒 CMAX Öyle ki: (∑ Yj,2,m Ms m ) = 1 (26) j ∈ {1,2, … , J}; s ∈ {1,2,3} Yj,1,1 = 1 (27) j ∈ {1,2, … , J} Yj,3,1 = 1 (28) j ∈ {1,2, … , J} ∑ Yj,2,m × Pj,2 J j=1 ≤ Cmax (29) m ∈ M2 𝐶𝑢𝑡𝑐 ∈ 𝐶𝑢𝑡𝑠𝑒𝑡 (30) c ∈ {1,2, … , |Cutset|} 3.5 Alt problem Ana problem işleme aşamasında işleri makinelere atamadan önce, makinelerdeki işlerin ve nakliye işlemlerinin sırası belirlenmelidir. Her makinedeki iş kümeleri bilindiği taktirde, alt problem oluşturulmaktadır. Robot tabanlı alt problem, işlerin ve nakliye operasyonlarının sırasını bulup, üretim süresini minimize etmiş olacaktır. Her bir iterasyonda, aşağıdaki alt problem çözülmüş ve makine atamaları için ilgili mantıksal kesmeler oluşturulmuştur: 31 [𝐒𝐏]: 𝑀𝑖𝑛𝑖𝑚𝑖𝑧𝑒 Cmax SP Dj,2 ≥ Dj,1 + (SP × (1 + |m − m′|)) + Pj,2 (31) j ∈ {1,2, … , J}; m ∈ M2; m′ ∈ M1 ; Y̅j,2,m = Y̅j,1,m′ = 1 (∑ Zj,s,f W f=1 ) = 1 (32) j ∈ {1,2, … , J}; s ∈ {1,2} (∑ ∑ Zj,s,f 2 s=1 J j=1 ) = 1 (33) f ∈ {1,2, … , W} (∑ Zj,2,f f′ f=1 ) − BM × (1 − Zj,1,f′) ≤ 0 (34) j ∈ {1,2, … , J};f′ ∈ {1,2, … , W} (∑ Zj,1,f f′ f=1 ) − BM × (1 − Zj′,2,f′ + Xj,j′) ≤ 0 (35) j, j′ ∈ {1,2, … , J}, j ≠ j′; m ∈ Ms; f′ ∈ {1,2, … , W} ; Y̅j′,2,m = Y̅j,2,m = 1 (∑ Zj′,1,f f′ f=1 ) − BM × (2 − Zj,2,f′ − Xj,j′) ≤ 0 (36) j, j′ ∈ {1,2, … , J}, j ≠ j′;m ∈ Ms; f′ ∈ {1,2, … , W} ; Y̅j′,2,m = Y̅j,2,m = 1 Dj,s + (BM × (2 − Zj′,s′,f−1 − Zj,s,f)) ≥ Dj′,s′ + (SP × ((|s′ − (s′ + 1)| + |m1 ′ − m2 ′ |) + (|(s′ + 1) − s| + |m2 ′ − m|))) (37) j, j′ ∈ {1,2, … , J}, j ≠ j′;s, s′ ∈ {1,2}; m′1 ∈ Ms′;m′2 ∈ Ms′+1; m ∈ Ms;f ∈ {2, … , W} ; Y̅j,s,m = Y̅j′,s′,m1 ′ = Y̅j′,s′+1,m2 ′ = 1 Cmax SP + BM × (2 − Zj,2,W) ≥ Dj,2 + (SP × (1 + |1 − m|)) (38) j ∈ {1,2, … , J};m ∈ M2 ; Y̅j,2,m = 1 Xj,j′ , Zj,s,f ∈ {0,1} (39) 32 3.6 Mantık Tabanlı Benders Kesmeleri Ana problem için bir çözüm bulunduğunda, mantık tabanlı Benders kesmesi yaratılmakta ve ana probleme eklenmektedir, böylelikle daha iyi çözümler bulmak adına ana probleme etkin bir şekilde yol gösterilmektedir. Alt problemden oluşturulmuş kesmeler şu şekildedir: 𝒍𝒃𝒄𝒖𝒕 ≡ {Cmax SP − BM × (∑ ∑ Yj,2,m J 𝑗=1|Y̅j,2,m=0 M2 m=1 + ∑ ∑ (1 − Yj,2,m) 𝐽 𝑗=1|Y̅j,2,m=1 M2 m=1 ) ≤ CMAX} (40) Burada, her bir makineye atanmış işler dolayısıyla tüm 𝑙𝑏𝑐𝑢𝑡 kesmeleri ana probleme dahil edilecektir. Bahsi geçen kesmeler, tüm nakliye operasyonlarının optimum sırasını göz önünde bulundurarak operasyonların gerçek tamamlanma zamanını sağlamaktadır. 𝑙𝑏𝑐𝑢𝑡, ana problemin amaç fonksiyonunu, tek bir robotla tahsis edilen paralel makine çizelgelemesinin amaç fonksiyonundan büyük veya eşit olmaya zorlamaktadır. Bu nedenle, ana problem, eğer mümkünse bu durumdan kurtulmak adına farklı atamalar bulmak için yol aramaktadır. Başlatma: 𝑼𝑩 = ∞, 𝑳𝑩 = 𝟎, 𝑪𝒖𝒕𝒔𝒆𝒕 = ∅ (𝑳𝑩 ≠ 𝑼𝑩) İken 1) 𝑪𝒖𝒕𝒔𝒆𝒕 göz önüne alınarak [𝑴𝑷] çözülür , çözüm elde edilir (�̅�𝒋,𝒔,𝒎 ← 𝒀𝒋,𝒔,𝒎), 2) Update 𝑳𝑩 ← 𝑪𝑴𝑨𝑿 3) [𝑺𝑷] çözülür ve çözüm elde edilir 𝑪𝒎𝒂𝒙 𝑺𝑷 4) Update 𝑼𝑩 ← 𝑪𝒎𝒂𝒙 𝑺𝑷 5) Mantık tabanlı kesme olarak 𝒍𝒃𝒄𝒖𝒕 oluşturulur 6) Kesme setleri update edilir: 𝑪𝒖𝒕𝒔𝒆𝒕 ← 𝑪𝒖𝒕𝒔𝒆𝒕 + 𝒍𝒃𝒄𝒖𝒕 33 DÖRDÜNCÜ BÖLÜM: SAYISAL BULGULAR Paralel makineli robotik hücrenin çizelgeleme problemi için önerilen MILP matematiksel model ve LBBD yöntemi algoritmaları, C # 2012'de kodlanmış ve 3.30 Gigahertz hız, 4 Gigabyte RAM ve WINDOWS 64-bit işletim sistemi ile Core TM i5-4590 CPU da çalışılmıştır. Hesaplamalı analizin bu kısmı, LBBD'nin ve MILP'nin, göz önüne alınan örneklerin, çözümleme süresi açısından performans değerlendirmesiyle ilgilidir. LBBD, Visual Studio C # 2012'de kodlanmıştır ve karşılaştırma amacıyla en fazla bir saat çalışmasına izin verilmiştir. Sonuçlar sırasıyla, hem MILP hem de LBBD için oluşturulan örnekler bazında tablo 4.1'de sunulmuştur. Tabloların sütunları açıklayıcı niteliktedir. Ek olarak, tablolar, SP ve MP için toplam çözüm sürelerini (CPU zamanları) içermektedir. Tablo 4-1'de görüldüğü üzere, LBBD yöntemi, 45 örneği, hesaplama süresinin birkaç dakikasında optimal hale getirebilmektedir, MILP ise sadece 15 problemi çözebilmektedir. Bahsedilen problemlerde 50 adet parça (16-25) bir saat içerisinde optimal duruma getirilememiştir. Elde edilen ürün üretim süresi değerleri, bir saat içinde bulunan ve optimum olmayan değerlerdir. Tablo 4. 1. önerilen LBBD yönteminin duyarlılığını göstermektedir. Şekil 4. 1' de, her problem için, LBBD yöntemi ile çözülen tüm MP ve SP modellerinin toplam CPU süreleri karşılaştırılmıştır. Şekil 1'de görüldüğü üzere, SP modellerinin çalışma süresinin toplamı, MP modellerinden daha büyüktür. MP sadece parçalar için makine atamalarını belirlemekte iken; SP probleminin karmaşıklığı, parça sıralamalarını belirleme ve nakliye operasyon sıralamalarından kaynaklanmaktadır. Şekil 4. 2 de, 20 ,30,40 ve 50 parça sayısı için 3 ve 5 makineli sistemler arasındaki seri üretim farklarını göstermektedir. Parçaların sayısı arttıkça, 3-5 paralel makineler arasındaki seri üretim süresi farkının arttığı açıkça görülmektedir. Robotik hücredeki parçaların sayısı arttıkça, paralel makinelerin sayısının arttırılması daha etkili olacaktır sonucuna varılabilmektedir. 34 Ayrıca, paralel makine robotik hücre çizelgeleme problemi için önerilen LBBD yönteminin çalışma süresi, paralel makinelerin sayısından etkilenmektedir. 6-10 ve 16-20 problemleri için LBBD yönteminin çalışma süresi, sırasıyla 11-15 ve 20-25 problemlerinden daha fazladır. Paralel makine sayısının az olduğu durumda, her bir makineye atanan parçalar için çözüm sayısı, parallel makine sayısının çok olduğu durumdan daha fazladır. Dolayısıyla, kesme ve iterasyonların sayısı arttıkça LBBD'nin çalışma süresi artmaktadır. 35 Tablo 4- 1 Paralel makine robotik hücre çizelgeleme problemi için önerilen MILP modeli ve LBBD yönteminin hesaplama sonuçları. parça Makine Üretim Süresi CPU Süresi Toplam CPU Süresi GAP % Problem MILP LBBD MILP LBBD MP SP 10 3 492 492 1105.38 24.35 7.06 17.28 0 1 421 421 1214.15 31.61 9.79 21.81 0 2 503 503 1005.54 22.26 6.67 15.58 0 3 516 516 1116.54 26.81 7.50 19.30 0 4 488 488 1204.64 33.10 10.92 22.17 0 5 20 3 1058 1058 2166.72 154.75 46.42 108.32 0 6 1114 1114 2018.33 142.29 41.26 101.02 0 7 1104 1104 1974.87 165.67 46.38 119.28 0 8 1046 1046 2083.77 155.15 48.09 107.05 0 9 1083 1083 2117.33 149.31 49.27 100.03 0 10 5 751 751 3124.12 138.85 40.26 98.58 0 11 793 793 3101.52 130.19 36.45 93.73 0 12 709 709 3204.96 127.73 39.59 88.13 0 13 815 815 2961.24 139.95 46.18 93.76 0 14 762 762 3087.57 149.11 44.73 104.37 0 15 30 3 1731 1552 3600 293.47 88.04 205.42 -10.34 16 1803 1487 3600 301.91 90.57 211.33 -17.52 17 1792 1563 3600 243.55 73.06 170.48 -12.77 18 1649 1449 3600 288.47 86.54 201.92 -12.12 19 1711 1603 3600 251.79 75.53 176.25 -6.31 20 5 1293 947 3600 274.61 82.38 192.22 -26.75 21 1351 1031 3600 237.89 71.36 166.52 -23.68 22 1285 918 3600 208.06 62.41 145.64 -28.56 23 1291 883 3600 264.44 79.33 185.10 -31.60 24 1163 949 3600 225.71 67.71 157.99 -18.40 25 40 3 1933 1737 3600 341.18 105.7658 235.41 -10.13 26 1967 1805 3600 327.75 95.0475 232.70 -8.23 27 1849 1597 3600 339.51 112.0383 227.47 -13.62 28 2013 1897 3600 349.47 104.841 244.62 -5.76 29 1784 1617 3600 350.47 98.1316 252.33 -9.36 30 5 1352 1149 3600 328.15 91.882 236.26 -15.01 31 1374 1169 3600 310.59 96.2829 214.30 -14.91 32 1289 1091 3600 325.94 107.5602 218.37 -15.36 33 1417 1209 3600 330.07 95.7203 234.34 -14.67 34 1286 1180 3600 343.95 103.185 240.76 -8.24 35 50 3 3094 2507 3600 851.85 255.55 596.29 -18.97 36 3271 2376 3600 902.56 270.76 631.79 -27.36 37 3158 2451 3600 812.93 243.87 569.05 -22.38 38 2974 2329 3600 784.40 235.32 549.08 -21.68 39 3052 2385 3600 806.95 242.08 564.86 -21.85 40 5 2842 1749 3600 752.17 225.65 526.51 -38.45 41 2937 1672 3600 811.49 243.44 568.04 -43.07 42 36 2566 1659 3600 715.62 214.68 500.93 -35.34 43 2732 1532 3600 771.91 231.57 540.33 -43.92 44 2691 1471 3600 735.41 220.62 514.78 -45.33 45 37 Şekil 4. 1 LBBD yöntemi ile çözülen tüm MSve MP modellerinin toplam CPU zamanları. 0 100 200 300 400 500 600 700 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 2223 24 2526 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 Total run time of MP models Total run time of SP models 38 Şekil 4.2 Aynı parça sayıları ile 3 ve 5 makineli hücrelerin bitiş zamanı karşılaştırmaları; {20 𝑝𝑎𝑟ç𝑎: 6&11, … ,10&15}, {30 𝑝𝑎𝑟ç𝑎: 16&21, … ,20&25}, {40 𝑝𝑎𝑟ç𝑎: 26&31, … ,30&35}, {50 𝑝𝑎𝑟ç𝑎: 36&41, … ,40&45} 0 250 500 750 1000 1250 1500 1750 2000 2250 2500 2750 6&11 7&12 8&13 9&14 10&15 16&21 17&22 18&23 19&24 20&25 26&3127&32 28&33 29&34 30&35 36&41 37&42 38&43 39&44 40&45 3 number of parallel machines 5 number of parallel machines 39 SONUÇ Bu çalışma, tek bir nakliye robotu ile Paralel Makineli Robotik Hücre Çizelgeleme problemini ele almaktadır. Başlangıçta, makina atamaları sorununu aynı anda gidermek ve makinedeki işleme parçaları ve robot hareketleri için en iyi sıralamayı belirleyen karma tamsayılı doğrusal programlama modeli (MILP) geliştirilmiştir. Geliştirilen yeni MILP modeli, nakliye kısıtlamalarını dikkate alarak, paralel makineli robotik hücre çizelgeleme problemini en aza indirgemektedir. Dikkate alınan problem NP-zor olduğundan, geliştirilen modeli sezgisel olarak çözümlemek için bir Bender Ayrıştırma algoritması önerilmiştir. Dikkate alınan problem, özelliklerinden dolayı Mantık Tabanlı Bender Ayrıştırması (Logic Based Bender's Decomposition, LBBD) uygulanmaya elverişli olmaktadır. Önerilen MILP modeli, robot hareket sıralaması içeren alt problemlerin paralel makine çizelgelemesini ve makine atama alt problemlerini içermektedir. Bu yapı kullanılarak ve makine atamasının bu problemin kilit parçası olduğunu düşünülerek, atama alt problemini ana problem gibi çözümleyen, parça ve robot hareket sıralaması alt problemlerini mantık tabanlı Benders üretmek için kesen bir Benders ayrıştırması algoritması geliştirilmiştir. Robotik hücre çizelgeleme problemleri ile ilgili mevcut literatür, bu problemlerin tam olarak çözümü ile ilgili eksikliği açıkça göstermektedir; çünkü mevcut matematiksel programlama modelleri yalnızca küçük boyutlu örnekleri çözümleyebilmektedir. Önerilen MILP modeli ve LBBD yöntemi, 5 kategori ve 45 rastgele oluşturulmuş problem örneği üzerinde test edilmiştir. Bu çalışma, paralel makineli robotik hücre çizelgeleme probleminde ayrıştırma yöntemlerini kullanmanın avantajlarını ve LBBD yönteminin oldukça başarılı olduğu göstermektedir. Bu çalışmada tanımlanan Benders ayrıştırma algoritması, robotik hücre çizelgeleme problemi ile ilgili araştırmalarda Benders kesme optimalliğini kullanan ilk çalışma olacak, bu sınırların ötesine geçerek orta ve büyük boyutlu problem örneklerine tam çözüm sağlayacaktır. Ayrıca, elde edilen sonuçlar, önerilen algoritmanın hesaplama süreleri bakımından oldukça üstün performans gösterdiğini doğrular niteliktedir. Gelecekte yapılacak olan araştırmalarda, çift tutuculu robotların da göz önüne alınmasıyla çalışmada incelenen problem genişletilebilecektir. 40 Ayrıca, önerilen Benders ayrıştırma yaklaşımı, diğer robotik hücre çizelgeleme problemleri için genişletilebilmektedir. 41 KAYNAKÇA Agnetis, A. (2000). Scheduling no-wait robotic cells with two and three machines. European Journal of Operational Research, 123(2), 303-314. doi:Doi 10.1016/S0377- 2217(99)00258-1 Agnetis, A., & Pacciarelli, D. (2001). Number Sequencing in Three Machine No-Wait Robotic Cells. Operations Research Letters, 27(4), 185–192. Aneja, Y. P., & Kamoun, H. (1999). Scheduling of parts and robot activities in a two machine robotic cell. Computers & Operations Research, 26(4), 297-312. doi:Doi 10.1016/S0305- 0548(98)00063-X Bajestani, M. A., & Beck, J. C. (2013). Scheduling a Dynamic Aircraft Repair Shop with Limited Repair Resources. Journal of Artificial Intelligence Research, 47, 35-70. Batur, G. D., Karasan, O. E., & Akturk, M. S. (2012). Multiple part-type scheduling in flexible robotic cells. International Journal of Production Economics, 135(2), 726-740. doi:10.1016/j.ijpe.2011.10.006 Benders, J. (1962). Partitioning procedures for solving mixed-variables programming problems. Numerische Mathematik, 4(1), 238-252. Benini, L., Bertozzi, D., Guerri, A., & Milano, M. (2005). Allocation and scheduling for MPSoCs via decomposition and no-good generation. Principles and Practice of Constraint Programming - Cp 2005, Proceedings, 3709, 107-121. Bilge, U., & Ulusoy, G. (1995). A time window approach to simultaneous scheduling of machines and material handling system in an FMS. Operations Research, 43(6), 1058-1070. doi:DOI 10.1287/opre.43.6.1058 Cai, X. M., McKinney, D. C., Lasdon, L. S., & Watkins, D. W. (2001). Solving large nonconvex water resources management models using generalized benders decomposition. Operations Research, 49(2), 235-245. doi:DOI 10.1287/opre.49.2.235.13537 Cambazard, H., Hladik, P. E., Deplanche, A. M., Jussien, N., & Trinquet, Y. (2004). Decomposition and learning for a hard real time task allocation problem. Principles and Practice of Constraint Programming - Cp 2004, Proceedings, 3258, 153-167. 42 Canto, S. (2008). Application of Benders' decomposition to power plant preventive maintenance scheduling. European Journal of Operational Research, 184(2), 759-777. doi:10.1016/j.ejor.2006.11.018 Carlier, J., Haouari, M., Kharbeche, M., & Moukrim, A. (2010). An optimization-based heuristic for the robotic cell problem. European Journal of Operational Research, 202(3), 636-645. doi:10.1016/j.ejor.2009.06.035 Chen, H. X., Chu, C. B., & Proth, J. M. (1997). Sequencing of parts in robotic cells. International Journal of Flexible Manufacturing Systems, 9(1), 81-103. doi:Doi 10.1023/A:1007930010707 Chu, Y. Y., & Xia, Q. S. (2004). Generating benders cuts for a general class of integer programming problems. Integration of Ai and or Techniques in Constraint Programming for Combinatorial Optimization Problems, 3011, 127-141. Chu, Y. Y., & Xia, Q. S. (2005). A hybrid algorithm for a class of resource constrained scheduling problems. Integration of Ai and or Techniques in Constraint Programming for Combinatorial Optimization Problems, 3524, 110-124. Cordeau, J. F., Pasin, F., & Solomon, M. M. (2006). An integrated model for logistics network design. Annals of Operations Research, 144(1), 59-82. doi:10.1007/s10479-006-0001-3 Correa, A. I., Langevin, A., & Rousseau, L. M. (2004). Dispatching and conflict-free routing of automated guided vehicles: A hybrid approach combining constraint programming and mixed integer programming. Integration of Ai and or Techniques in Constraint Programming for Combinatorial Optimization Problems, 3011, 370-379. Costa, A. M. (2005). A survey on benders decomposition applied to fixed-charge network design problems. Computers & Operations Research, 32(6), 1429-1450. doi:10.1016/j.cor.2003.11.012 Costa, A. M., Cordeau, J. F., & Gendron, B. (2009). Benders, metric and cutset inequalities for multicommodity capacitated network design. Computational Optimization and Applications, 42(3), 371-392. doi:10.1007/s10589-007-9122-0 Costa, A. M., Cordeau, J. F., Gendron, B., & Laporte, G. (2012). Accelerating Benders decomposition with heuristic master problem solutions. Pesquisa Operacional, 32(1), 3-20. 43 Cote, G., & Laughton, M. A. (1984). Large-Scale Mixed Integer Programming - Benders-Type Heuristics. European Journal of Operational Research, 16(3), 327-333. doi:Doi 10.1016/0377-2217(84)90287-X Crainic, T. G., Hewitt, M., & Rei, W. (2014). Partial decomposition strategies for two-stage stochastic integer programs. Publication CIRRELT-2014- 13, Centre interuniversitaire de recherche sur les réseaux d’entreprise, la logistique et le transport, Université de Montréal, Montréal, QC, Canada. Dawande, M., Geismar, H. N., Sethi, S. P., & Sriskandarajah, C. (2005). Sequencing and scheduling in robotic cells: Recent developments. Journal of Scheduling, 8(5), 387-426. doi:DOI 10.1007/s10951-005-2861-9 Fazel-Zarandi, M. M., & Beck, J. C. (2012). Using Logic-Based Benders Decomposition to Solve the Capacity- and Distance-Constrained Plant Location Problem. Informs Journal on Computing, 24(3), 387-398. doi:10.1287/ijoc.1110.0458 Fazel-Zarandi, M. M., Berman, O., & Beck, J. C. (2013). Solving a stochastic facility location/fleet management problem with logic-based Benders' decomposition. Iie Transactions, 45(8), 896-911. doi:10.1080/0740817x.2012.705452 Foumani, M., & Jenab, K. (2013). Analysis of flexible robotic cells with improved pure cycle. International Journal of Computer Integrated Manufacturing, 26(3), 201-215. doi:10.1080/0951192x.2012.684722 Geismar, H. N., Dawande, M., & Sriskandarajah, C. (2004). Robotic cells with parallel machines: Throughput maximization in constant travel-time cells. Journal of Scheduling, 7(5), 375- 395. doi:DOI 10.1023/B:JOSH.0000036861.28456.5d Geismar, H. N., Dawande, M., & Sriskandarajah, C. (2006). Throughput optimization in constant travel-time dual gripper robotic cells with parallel machines. Production and Operations Management, 15(2), 311-328. Geismar, H. N., Pinedo, M., & Sriskandarajah, C. (2008). Robotic cells with parallel machines and multiple dual gripper robots: a comparative overview. Iie Transactions, 40(12), 1211-1227. doi:10.1080/07408170801965108 Geoffrion, A. M. (1970a). Elements of large-scale mathematical programming: Part I: Concepts. Management Science, 16(11), 652–675. 44 Geoffrion, A. M. (1970b). Elements of large scale mathematical programming: Part II: Synthesis of algorithms and bibliography. Management Science, 16(11), 676–691. Geoffrion, A. M. (1972). Generalized Benders Decomposition. Journal of Optimizition Theory and Applications, 10(4), 237-260. Geoffrion, A. M., & Graves, G. W. (1974). Multicommodity Distribution System-Design by Benders Decomposition. Management Science Series a-Theory, 20(5), 822-844. doi:DOI 10.1287/mnsc.20.5.822 Hall, N. G., Kamoun, H., & Sriskandarajah, C. (1998). Scheduling in robotic cells: complexity and steady state analysis. European Journal of Operational Research, 109(1), 43-65. doi:Doi 10.1016/S0377-2217(96)00333-5 Harjunkoski, I., & Grossmann, I. E. (2002). The composition techniques for multi stage scheduling problem using Mixed–Integer and constraint programming methods. Computers and Chemical Engineering, 26, 1533–1552. Hooker, J. N. (2000). Logic-based Methods for Optimization: Wiley. Planning and Scheduling by logic-based benders decomposition 1-29 (2005). Hooker, J. N. (2007). Planning and scheduling by logic-based benders decomposition. Operations Research, 55(3), 588-602. doi:10.1287/opre.1060.0371 Hooker, J. N., & Ottosson, G. (2003). Logic-based Benders decomposition. Mathematical Programming, 96(1), 33-60. doi:10.1007/s10107-003-0375-9 Hooker, J. N., & Yan, H. (1995). Verifying logic circuits by benders decomposition. Principles and Practice of Constraint Programming, 269-290. Hurink, J., & Knust, S. (2001). Makespan minimization for flow-shop problems with transportation times and a single robot. Discrete Applied Mathematics, 112(1-3), 199-216. doi:Doi 10.1016/S0166-218x(00)00316-4 Hurink, J., & Knust, S. (2002). A tabu search algorithm for scheduling a single robot in a job-shop environment. Discrete Applied Mathematics, 119(1-2), 181-203. doi:Pii S0166- 218x(01)00273-6 .Doi 10.1016/S0166-218x(01)00273-6 Jain, V., & Grossmann, I. E. (2001). Algorithms for hybrid MILP/CP models for a class of optimization problems. Informs Journal on Computing, 13(4), 258-276. doi:DOI 10.1287/ijoc.13.4.258.9733 45 Kharbeche, M., Carlier, J., Haouari, M., & Moukrim, A. (2011). Exact methods for the robotic cell problem. Flexible Services and Manufacturing Journal, 23(2), 242-261. doi:10.1007/s10696-011-9079-2 Lim, C. (2010). Relationship among Benders, Dantzig-Wolfe, and Lagrangian optimization. Wiley Encyclopedia of Operations Research and Management Science. Luong, C. (2015). An examination of benders decomposition approaches in large-scale healthcare optimization problems. University of Toronto. Magnanti, T. L., Mireault, P., & Wong, R. T. (1986). Tailoring Benders Decomposition for Uncapacitated Network Design. Mathematical Programming Study, 26, 112-154. Magnanti, T. L., & Wong, R. T. (1981). Accelerating Benders Decomposition - Algorithmic Enhancement and Model Selection Criteria. Operations Research, 29(3), 464-484. doi:DOI 10.1287/opre.29.3.464 Maravelias, C. T., & Grossmann, I. E. (2004). Using MILP and CP for the scheduling of batch chemical processes. Integration of Ai and or Techniques in Constraint Programming for Combinatorial Optimization Problems, 3011, 1-20. Nawaz, M. (1983). A heuristic algorithm for the m-machine, n-job flow-shop sequencing problem. Omega, 11(1), 91-95. Raidl, G. R. (2015). Decomposition based hybrid metaheuristics. European Journal of Operational Research, 244(1), 66-76. doi:10.1016/j.ejor.2014.12.005 Sahinidis, N. V., & Grossmann, I. E. (1991). Convergence Properties of Generalized Benders Decomposition. Computers & Chemical Engineering, 15(7), 481-491. doi:Doi 10.1016/0098-1354(91)85027-R Sarkheil, N., & Jenab, K. (2012). On the optimality of 1-unit cycles in flow-shop networks. International Journal of Production Research, 50(10), 2705-2709. doi:10.1080/00207543.2011.588268 Sethi, S. P., Sriskandarajah, C., Sorger, G., Blazewicz, J., & Kubiak, W. (1992). Sequencing of Parts and Robot Moves in a Robotic Cell. International Journal of Flexible Manufacturing Systems, 4, 331-338. Shafiei-Monfared, S., Salehi-Gilani, K., & Jenab, K. (2009). Productivity analysis in a robotic cell. International Journal of Production Research, 47(23), 6651-6662. doi:10.1080/00207540802372298 46 Soukhal, A., & Martineau, P. (2005). Resolution of a scheduling problem in a flowshop robotic cell. European Journal of Operational Research, 161(1), 62-72. doi:10.1016/j.ejor.2003.08.028 Soukhal, A., Oulamara, A., & Martineau, P. (2005). Complexity of flow shop scheduling problems with transportation constraints. European Journal of Operational Research, 161(1), 32-41. doi:10.1016/j.ejor.2003.03.002 Sriskandarajah, C., Hall, N. G., & Kamoun, H. (1998). Scheduling large robotic cells without buffers. Annals of Operations Research, 76, 287-321. doi:Doi 10.1023/A:1018952722784 Terekhov, D., Beck, J. C., & Brown, K. N. (2009). A Constraint Programming Approach for Solving a Queueing Design and Control Problem. Informs Journal on Computing, 21(4), 549-561. doi:10.1287/ijoc.1080.0307 Thorsteinsson, E. S. (2001). Branch-and-Check: A Hybrid Framework Integrating Mixed Integer Programming and Constraint Logic Programming. In Proceedings of the Seventh International Conference on Principles and Practice of Constraint Programming, 2239, 16- 30. doi:10.1007/3-540-45578-7_2 Timpe, C. (2002). Solving planning and scheduling problems with combined integer and constraint programming. Or Spectrum, 24(4), 431-448. Zahrouni, W., & Kamoun, H. (2012). Sequencing and scheduling in a three-machine robotic cell. International Journal of Production Research, 50(10), 2823-2835. doi:10.1080/00207543.2011.596999 Zhang, J. L., & Ponnambalam, K. (2006). Hydro energy management optimization in a deregulated electricity market. Optimization and Engineering, 7(1), 47-61. doi:10.1007/s11081-006- 6590-5 Zhu, Y. S., & Kuno, T. (2003). Global optimization of nonconvex MINLP by a hybrid branch-and- bound and revised general benders decomposition approach. Industrial & Engineering Chemistry Research, 42(3), 528-539. doi:10.1021/ie0200813 49 ÖZGEÇMİŞ Curriculum Vitae (CV) Personal Information: Marital Status Gender Nationality Date of Birth Surname Name Female Male Lecturer  Iran 23.07.197 2 Komari Alaie Mohammad Reza Email Fax Telephone Mobile Office Home Komari.reza@hacettepe.edu.tr Komari.reza@gmail.com 0098-9141014640 0090-5073295610 00984113811550 mailto:Komari.reza@hacettepe.edu.tr 50 Educational Background: (last one first) Academic Rank Received Date Country City Name of Institution Field of Specialization Degree Lecturer From 2010- Turkey Ankara Hacettepe University Quantitative Model PhD. Student 2005 Iran Tabriz Islamic Azad University Production and Operation Ms. 1999 Iran Tabriz Islamic Azad University Production and Operation Bc. Master Thesis: A study Relationship Between Manufacturer Product Strategy and Supply Chain Structure Ph. D. Dissertation: Parallel Machine Robotic Cell Scheduling Problem Administrative Positions: Name of Institution Date Place of Work Job Title To From Mazloumiyan –Nevar Bafiy 2006 2005 Textile Factory Production Management Islamic Azad University 2011 2005 Tabriz-Bonab- Sarab- Memeqan- Hadishehr Cities University Lecturer Ahrar Office 2002 2000 Ahrar Office Financial Management 51 Master and Doctorate Theses Supervision: Publications: (papers) Date Journal Title of the Article 2008 Vol.10 No.38 Management and Development The Presentation of Points of Strength and Weakness and Performance of Self – Assessment of Power Elements Engineering co.at Azerbayjan Based on EFQM Excellence Model 2010 Vol .11 No.43 Management and Development A study Relationship Between Manufacturer Product Strategy and Supply Chain Structure Date Title MS / Ph. D. Students Full Name No 10.01.2017 A Hybrid Model of ANP and TOPSIS Multiple Attribute Decision Making for Packaging Products in the effect of improving purchasing behavior of consumers MS Layla Sedigi 1 10.01.2017 A Hybrid Model of ANP and TOPSIS Multiple Attribute Decision Making for Ranking Suppliers in Sustainable Supply Chain Management MS Ali Aliyari 2 52 2012. Vol.9 No.4 Life Secince Jurnal Relationship between Manufacturer Product Strategies and Supply Chain Inventory in a Company 2012 Vol6 No.4 Advance in Environmental Biology Effective factors in the existence of waste time and its effects on poroduct system Publications (Conference Full Papers) Date Title and Place Title of the Article September 12-14, 2013 International Conference on New Directions in Business, Management, Finance and Economics Famagusta, Northern Cyprus. The Impact of Non- Stationary Demand on Supply Chain Inventory May 2011 China-USA Business Review Effective Factors in the Existence of Waste Time and its Effects on the Production system Membership to Scientific Associations: Date Country Name of /Association Institution 2013 USA-(ISSN2328-2185) Management Studies Journal 53 Research Interests: Non-Stationary Demand in Industrial Management and Engineering Supply Chain in Inventory Control, Manufacturer Product Strategy Inventory Control Operation Research