Solving buffer allocation problem in production lines using tabu search based approaches

Abstract

Üretim sistemi tasarımcılarının karşılaştığı başlıca eniyileme problemlerinden biri olan tampon stok dağılımı problemi bir üretim sisteminde tampon stokların bu stoklar için ayrılmış alana en iyi şekilde dağıtılmasını içermektedir. Bu doktora tezinin başlıca amacı üretim hatlarında tampon stok dağılımı problemini çözmek üzere özgün tabu arama tabanlı yaklaşımlar sunmaktır. Tampon stok dağılımı problemi bu tezde üç aşamada çözülmüştür. İlk aşamada, deterministik üretim zamanlarına sahip ve bozulmalara maruz kalan makinelerin oluşturduğu homojen üretim hatlarında tampon stok dağılımı problemini çözmek için yeni hareket tanımlarını içeren özgün bir tabu arama algoritması önerilmiştir. En iyi tabu arama parametrelerini belirlemek üzere yapılan bir pilot çalışmadan sonra tampon stok dağılımı problemi için yeni hareket tanımları sunulmuştur. İkinci aşamada, söz konusu problem, homojen olmayan üretim hatlarında tampon stok dağılımı olarak genişletilerek, üretim oranınını maksimize etmek amacıyla özgün bir adaptif tabu arama algoritması önerilmiştir. Tabu arama parametrelerini arama süresince adaptif bir şekilde değiştirmek üzere yeni bir stratejinin önerilmesinin yanı sıra, arama için sarf edilen eforun azaltılması amacıyla üç alternatif başlangıç çözümü önerilmiştir. Önerilen bu alternatif başlangıç çözümlerinden birini seçmek üzere de deneysel bir çalışma yürütülmüştür. Bu doktora çalışmasının son aşamasında da bozulmalara maruz kalan ve deterministik üretim zamanlarına sahip makinelerden oluşan üretim hatlarında tampon stok dağılımı problemini çözmek üzere üç ayrı yaklaşım önerilmiştir. İkili arama, tabu arama ve tavlama benzetimi algoritmalarını bir adaptif tabu arama mekanizması ile birleştiren bu üç yaklaşım istenilen üretim oranını sağlamak üzere hattaki toplam tampon miktarını minimize etmeyi amaçlamaktadır. Tabu arama ve tavlama benzetimi algoritmalarının arama etkinliğini artırmak üzere alternatif komşuluk yaratma mekanizmaları önerilmiş ve bunların performansları test edilmiştir. The buffer allocation problem, which involves the distribution of buffer space among the intermediate buffers of a production line, arises in a wide range of manufacturing systems, and it is one of the most important optimization problems faced by manufacturing systems designers. The primary aim of this Ph.D. study is to introduce novel tabu search based solution approaches for solving buffer allocation problem in production lines. In this thesis, the buffer allocation problem is solved in three stages. In the first stage, a novel TS algorithm including new move definitions is proposed to solve the buffer allocation problem under the objective of throughput maximization for homogeneous production lines involving unreliable machines with deterministic processing times. Following a pilot experiment to identify the best TS parameters, the new move definitions for buffer allocation problem are introduced. In the second stage, the problem is extended to non-homogeneous production lines, and an adaptive TS algorithm is proposed to solve the revised problem under the objective of throughput maximization. Besides proposing a new strategy to tune the parameters of TS adaptively during the search, an experimental study is carried out to select an intelligent initial solution scheme among three alternatives so as to decrease the search effort to obtain the best solutions. Finally, in the last stage, three approaches are proposed to solve the buffer allocation problem for non-homogeneous production lines involving unreliable machines with deterministic processing times. These three approaches which integrate binary search, tabu search, and simulated annealing with an adaptive tabu search mechanism aim at minimizing the total buffer size to achieve a desired throughput level. To improve the searching efficiency of TS and SA algorithms alternative neighborhood generation mechanisms are suggested and their performance are tested.