Heuristic approaches for the lot streaming problem in multi-product flow shops

Abstract

Bu proje kapsamında, çok makineli akış tipi üretim sistemleri için çok ürünlü kafile bölme ve kaydırma problemlerine (ÇÜ-KBK problemleri) sezgisel çözüm yaklaşımları geliştirilmiştir. Amaç fonksiyonu olarak tüm ürünlerin bitiş zamanını en küçükleme fonksiyonu kullanılmıştır. İlk olarak, literatürde ÇÜ-KBK problemlerinin eşit ve tutarlı alt kafile problemleri üzerine yazılmış makaleler incelenmiş ve ÇÜ-KBK problemlerinin daha anlaşılır olması için gerekli arka plan bilgileri sağlanmıştır. Daha sonra, proje kapsamında eşit ve tutarlı alt kafileli ÇÜ-KBK problemlerine çözüm yaklaşımı getiren iki sezgisel (Sezgisel RO ve Sezgisel RO - Tutarlı) detaylı olarak anlatılmıştır. Aynı problem türlerine çözüm getiren literatürden seçilmiş farklı çözüm yaklaşımlarıyla karşılaştırmalı sonuç analizlerine yer verilmiştir. Sonuç analizleri göstermektedir ki, proje kapsamında geliştirilen sezgisel yaklaşımlar karşılaştırıldıkları çözüm yöntemlerine yakın ya da daha iyi sonuçlar verebilmektedirler. Ayrıca, sezgisel yaklaşımların oluşturulmasında kullanılan ?İç kafile? kavramını destekleyici olarak sunulan bir savın ispatı da araştırma içerisinde yer almaktadır.Geliştirilen sezgiseller, darboğaz ve tersten darboğaz egemen kafileleri sıralamada ve eşitlik bozmadaki farklı yaklaşımları, iç kafile kavramını sezgisellerin ve tabu arama metodunun farklı yerlerinde kullanmaları ve karşılaştırıldıkları çözüm yöntemlerine yakın ya da daha iyi sonuçlar vermeleriyle ÇÜ-KBK literatürüne katkı sağlamaktadırlar.Anahtar Kelimeler: Kafile Bölme ve Kaydırma, Eşit Alt Kafile, Tutarlı Alt Kafile, Darboğaz Egemenliği, İç Kafile, Tabu Arama, Giriş Zamanı, Çıkış Zamanı

In thesis research, we consider the multi-product lot streaming (MPLS) problem with equal and consistent sublots in multi-machine flow shops (MMFS) with objective of minimizing the makespan. We firstly introduce various types of scheduling problems and provide detailed background information and literature review on lot streaming problems with equal and consistent sublots. Then we develop two heuristic procedures for equal and consistent sublot sized MPLS problems respectively.First heuristic approach that we develop for MPLS problem with equal sublots in MMFS (heuristic RO) is a constructive procedure, which has many distinguishing characteristics. Its fast and easy construction method of initial lot sequence lets tabu search algorithm start with a better initial solution in contrast with random initial solutions. Moreover, we utilize the concept of ?Interior Lots? in order to restrict the insertion of a given lot into first position. We also provide a proof of the claim, which supports the use of ?Interior Lot? concept in both of the heuristics. Second heuristic approach (heuristic RO-C) deals with the MPLS problem with consistent sublots in MMFS. In compliance with the different characteristics of the problem we develop an additional tabu search algorithm in order to generate better initial sublot size matrix.Finally we present comparative results of experimental studies for both heuristics. We show that solution qualities of both heuristics that we develop are better than or equal to those obtained by the heuristic and exact methods that we choose to compare with.Proposed heuristics have considerable contributions to MPLS literature due to their unique ordering and tie breaking rules for sorting bottleneck dominant and reversely bottleneck dominant lots, utilization of interior lot concept in several steps of heuristics and solution quality with respect to similar studies from the literature.Keywords: Lot Streaming, Equal Sublot, Consistent Sublot, Bottleneck Dominance, Interior Lots, Tabu Search, Run-in Time, Run-out Time