A hbyrid genetic algorithm for mixed-model assembly line balancing problem with parallel workstation assignment

Abstract

Bu tezde, 1.tip karışık tipli montaj hattı dengeleme problemi ele alınmaktadır. Bu problem, maliyet veya kapasite tabanlı bir amaç fonksiyonunu optimize ederken, önceden belirlenen bir çevrim zamanına göre minimum istasyon sayısını bulma problemidir. Çeşitli çözüm yöntemleri, karışık tipli montaj hattı dengeleme problemine çözüm aramak amacıyla kullanılmışlardır. Problemin NP-Hard yapısından dolayı büyük ölçekli problemlerin çözümünde kesin sonuç veren algoritmalar etkili olamamakta ve arama algoritmaları da büyük ölçekli problemlerde çözüm uzayını etkili bir şekilde arama konusunda yetersiz kalabilmektedirler. Bu dezavantajın üstesinden gelebilmek için son yıllarda meta-sezgisellerin çeşitli algoritmalar ile kombinasyonu birçok çalışma tarafından ele alınmıştır. Bu yaklaşımlar melez meta-sezgiseller olarak adlandırılmaktadırlar. Bu tez çalışmasının temel amacı 1.tip karışık tipli montaj hattı dengeleme probleminin çözümü için genetik algoritma tabanlı hibrit bir algoritma sunmaktır. Önerilen metod, paralel istasyon ataması ve zoning kısıtları gibi gerçek karışık tipli montaj hatlarının bazı belirgin özelliklerini ele almaktadır. Melez genetik algoritmanın elde edilmesi için bilinen üç sezgisel algoritma, Kilbridge ve Wester Sezgiseli, Moodie ve Young Metodunun I. Aşaması ve RPWT, kullanılmıştır. Bu sezgisellerin orjinal versiyonları tek bir ürün tipinin üretildiği basit montaj hattı dengeleme problemlerinin çözümünde paralel istasyon ataması ve zoning kısıtları göz önünde bulundurulmadan kullanılmaktadır. Bu üç sezgiselden, Moodie ve Young Metodunun I. Aşaması ve Kilbridge ve Wester Sezgiseli karışık tipli montaj hatlarında kullanılabilecek şekilde modifiye edilmiş ve RPWT nin modifiye edilmiş versiyonu literatürden alınmıştır. Sonrasında modifiye edilmiş bu sezgisellerin, genetik algoritmanın ve önerilen melez genetik algoritmanın performansını test etmek için karşılaştırmalı deneyler 20 adet 1.tip karışık tipli montaj hattı dengeleme problemi kullanılarak yapılmıştır. Önerilen melez genetik algoritma diğer sezgisellerden ve genetik algoritmadan daha iyi sonuç vermektedir. ANTBAL ile aynı performansı göstermesine rağmen daha az hesaplama gerektirmektedir. In this thesis, we deal with the mixed-model assembly line balancing problem (MMALBP) of type-1, which consists of finding a number of stations for a predetemined cycle time as well as a line balance such that a capacity- or even cost-oriented objective is optimized. Various exact and approximation approaches have been developed to deal with MMALBP of type-1. Due to the NP-hard structure of the problem none of the optimum seeking methods have been proven to be practical to solve large scale problems. Moreover, approximation methods may lack the capability of exploring the solution space effectively. Over the last years, hybrid meta heuristics which combine the various algorithmic ideas of meta-heuristics concerning overcome these shortages have been reported. In this thesis, we propose an effective hybrid genetic algorithm, which is able to address some particular features such as parallel workstations and zoning constraints of the assembly process for MMALBP of type-1. For the hybridization of genetic algorithm three well known heuristics, Kilbridge and Wester Heuristic, Phase-I of Moodie and Young Method, and Ranked Positional Weight Tecnique are used. The original versions of them only address the simple assembly line balancing problem, where one single model is assembled, no parallel workstations are allowed and zoning constraints are not considerd. Therefore, we modified Kilbridge and Wester and Phase-I of Moodie and Young Methods for applying these heuristics to MMALBP. Comparative experiments are carried out to evaluate the performances of modified versions of the these heuristics, simulated annealing, pure genetic algorithm, ANTBAL and the proposed procudure on a benchmark data set including 20 MMALBPs of type 1. The proposed hybrid genetic algorithm outperformed the other heuristics and pure genetic algorithm. Although the proposed hybrid genetic algorithm explored the same performance with ANTBAL, it requires less computational effort than ANTBAL.