Grafting a Branch and Bound Method on a Genetic Algorithm for Balancing I / U-Shaped Assembly Lines

Abstract

This paper presents a new efficient hybrid method that combines a branch & bound technique and a genetic algorithm for solving I/U -shaped assembly lines balancing. The basic components of a branch & bound technique that operates with topological sorting of the set of tasks are described. An order-based genetic algorithm that works with embryos that are either prefixes or pairs of prefixes - suffixes of topological sortings uses the components of the branch & bound technique and a newly introduced growing operator for evolving the population towards complete solutions. Sensitive lower bounds early predicting the quality of solutions built on the current embryos are used. Two strategies based on preventive and corrective management are proposed as a tradeoff between growing and survival selection. The results of experimental investigations show that the proposed embryonic genetic algorithm dominates the pure genetic algorithm. This is due to a better trade-off between the exploration that is mainly based on the growing population of embryos and the exploitation that is transferred to the evolving of the complete solutions.

Keywords

• Genetic algorithm
• Branch & bound
• Assembly line balancing
• Hybridization