An efficient hybrid genetic algorithm to solve assembly line balancing problem with sequence-dependent setup times
In this paper the setup assembly line balancing and scheduling problem (SUALBSP) is considered. Since this problem is NP-hard, a hybrid genetic algorithm (GA) is proposed to solve the problem. This problem involves assigning the tasks to the stations and scheduling them inside each station. A simple permutation is used to determine the sequence of tasks. To determine the assignment of tasks to stations, the algorithm is hybridized using a dynamic programming procedure. Using dynamic programming, at any time a chromosome can be converted to an optimal solution (subject to the chromosome sequence). Since population diversity is very important to prevent from being trapped in local optimum solutions some diversity maintaining schemes are used to overcome this issue. Operators and parameters of the algorithm is calibrated using design of experiments (DOEs) method. The computational results show that the proposed GA outperforms all of the algorithms presented to solve SUALBSP so far. (C) 2011 Elsevier Ltd. All rights reserved.
genetic algorithm assembly line balancing sequence-dependent setup time dynamic programming design of experiments