Tabu search based solution approaches for lot streaming problems in flow shops

Abstract

Kafile bölme ve kaydırma (KBK), üretimi hızlandırmak ve sistem performansını iyileştirmek için, üretim kafilesini daha küçük alt kafilelere bölme ve bu alt kafileleri makineler boyunca çizelgeleme yöntemidir. Bu tezde, çok makineli akış tipi sistemlerde toplam üretim süresini en küçüklemeyi amaçlayan bir dizi KBK problemi çalışılmıştır. İlk problemde, tek ürünlü stokastik bir akış tipi sistem incelenmiştir. Bu problem için tabu arama ve benzetim yöntemlerini bütünleştiren bir çözüm yaklaşımı önerilmiştir. Bu yaklaşımda, alt kafile büyüklük seçeneklerini değerlendirmek için tabu arama yöntemi ve sistemin stokastik yapısını yansıtabilmek üzere benzetim yöntemi kullanılmıştır. Çalışılan diğer üç problem, birbirlerinden alt kafile tipi ve alt kafilenin bölünebilirliği karakteristikleri açılarından farklılaşmaktadır ve çok ürünlü deterministik akış tipi sistemlerini ele almaktadır. Çok ürünlü KBK problemi; sıralama ve alt kafile bölme/kaydırma alt problemlerine ayrıştırılmıştır. Sıralama alt problemi için, genel akış tipi sistemlerde geliştirilmiş olan basit ve etkin sıralama algoritmaları, KBK probleminin gereksinimleri doğrultusunda revize edilmiştir. Alt kafile bölme/kaydırma problemi için ise, karışık tamsayılı programlama tabanlı yaklaşımlar geliştirilmiştir. Çok ürünlü KBK problemini çözmek için; sıralama alt problemini, revize edilmiş sezgisel yöntemlerden en iyi sonucu veren (NEH,TPLS) yöntem ile ele alan ve alt kafile bölme/kaydırma problemini önerilen karışık tamsayılı programlama yaklaşımı ile çözen melez bir çözüm prosedürü geliştirilmiştir. Önerilen melez yöntem, sadece küçük ve orta ölçekli problemlere kısa zamanda etkin sonuçlar vermekle kalmayıp, aynı zamanda büyük ölçekli problemler için de çözüm sunabilmektedir. Son olarak, küçük ve orta ölçekli problemlerde çözüm etkinliğini arttırmak için, yukarıdaki melez yaklaşımı içeren ve alternatif ürün sıralarını tabu arama yöntemi ile değerlendirerek geliştiren bir diğer çözüm yöntemi önerilmiştir. Lot streaming (LS) splits the production lot into sublots, and schedules these sublots in an overlapping way on the machines in order to accelerate the process of orders and improve the overall system performance. In this thesis, a number of LS problems all of which aim to minimize makespan in multi machine flow shops are investigated. First problem considers a single-product case in stochastic flow shops. For this problem, a solution approach that integrates tabu search (TS) and simulation is proposed. Sublot size configurations are searched via TS and stochastic behavior of the system is handled by simulation. Remaining three problems differ from each other by sublot types and divisibility of sublot sizes and deal with multi-product cases in deterministic flow shops. Entire problem is partitioned into sequencing and sublot allocation sub-problems. For sequencing sub-problem, a number of simple and efficient sequencing heuristics developed for general flow shops are modified according to LS requirements. For sublot allocation sub-problem, mixed integer programming (MIP) based approaches are proposed. For entire problem, a hybrid solution approach which uses the best sequencing heuristic (i.e., NEH(D,TPLS)) in sequencing sub-problem and applies MIP-based approaches for sublot allocation sub-problem, is proposed. Proposed hybrid approach not only gives efficient results for small/medium sized problems in short computation times but also solves large-sized problems in reasonable times. Finally, to improve solution quality in small/medium sized problems, same approach is also integrated to a solution procedure where initial sequence is taken as NEH(D,TPLS) and alternative sequences are evaluated via TS.