Modeling and solving mixed-model assembly line balancing problem with setups

Abstract

Bu tez I. tip karma modelli montaj hattı dengeleme problemini ele almaktadır. Bu problemin kapsamı, işler arasındaki sıra bağımlı hazırlık zamanları da dikkate alınarak genişletilmiştir. Bu tezin temel amacı, problemin matematiksel formülasyonunu geliştirmek ve problemi yeni önerilen paralel hibrit meta-sezgisel algoritmalarla çözmektir. Bu kapsamda, problem için bir karma tamsayılı doğrusal programlama modeli geliştirilmiş ve modelin performansı bir deney seti üzerinde test edilmiştir. Problemin karmaşık yapısı nedeniyle, problemin çözümü için paralel hibrid algoritmalar önerilmiştir. İlk olarak, problemin çözümü için karınca kolonisi optimizasyonu ve genetik algoritmanın birlikte çalıştığı yeni bir paralel hibrit algoritma geliştirilmiştir. Önerilen algoritma, genetik algoritmayı lokal arama strateji olarak kullanmayı ve bu şekilde karınca kolonisi optimizasyonunun performansını arttırmayı amaçlamaktadır.Önerilan hibrit algoritmada, genetik algoritma kuvvetlendirme (intensification) sağlarken karınca kolonisi algoritması çeşitlendirme (diversfication) sağlar. İkinci sırada, sürü zekası tabanlı meta-sezgisel algoritmaların yeni bir üyesi olan ve gerçek bal arılarının grup içi davranışlarının benzetimi ile oluşturulan arılar algoritması ile problem çözülmüştür. Temel arılar algoritmasının tek bir koloni içindeki bal arılarının davranışlarının benzetimi üzerine kurulmuş olmasına rağmen, biz bu çalışma kapsamına bal arılarının tek bir koloni içinde ve çoklu koloniler arasındaki davranışlarının benzetimiyle yeni bir algoritma geliştirmeyi amaçlıyoruz. Çoklu koloni yapısına sahip arı algoritması, tek bir koloniden oluşan arı algoritmasına göre gerçek bal arılarının çoklu kolonili bir yapıda olmalarından dolayı daha gerçekçidir. Önerilen algoritmaların performansları bir dizi deneysel çalışma ile test edilmiş ve her iki algoritmanın da tatmin edici performansa sahip oldukları sonucuna varılmıştır. This dissertation concerns the type-I mixed-model assembly line balancing problem with setup times (MMALBPS-I). MMALBPS-I is an extension of classical MMALBP-I in which sequence-dependent setup times between tasks are taken into consideration. The main goal of this dissertation is developing the mathematical formulation of the problem and solving the problem with newly proposed parallel hybrid meta-heuristic approaches. Within this context, a mixed-integer linear programming (MILP) model for the problem is developed and the capability of our MILP is tested through a set of computational experiments. Due to the complex nature of the problem, parallel hybrid algorithms are proposed in order to tackle the problem. First, a new hybrid algorithm (ACO-GA), which executes ant colony optimization in combination with genetic algorithm, is developed. The proposed ACO-GA algorithm aims at enhancing the performance of ant colony optimization by incorporating genetic algorithm as a local search strategy for MMALBPS-I. In the proposed hybrid algorithm ACO is conducted to provide diversification, while GA is conducted to provide intensification. Second, we tackled the problem with Bees Algorithm (BA), which is a relatively new member of swarm intelligence based meta-heuristics and tries to simulate the group behavior of real honey bees. However, the basic BA simulates the group behavior of real honey bees in a single colony; we aim at developing a new BA, which simulates the group behavior of honey bees in a single colony and between multiple colonies. The multiple colony type of BA is more realistic than the single colony type because of the multiple colony structure of the real honey bees. The performances of the proposed algorithms are tested through a set of computational experiments and computational results indicate that both algorithms have satisfactory performances.