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

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.