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

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.