A Genetic Algorithm Approach for the Type II Assembly Line Balancing Problem

摘要: The presence of human operators in assembly lines is often preferred to automation systems, due to its flexibility and capacity to deal with complex tasks. However, there is a significant dispersion of completion times for each worker, and also a large heterogeneity among workers. The traditional metrics used to evaluate the performance of an assembly line, eg the smoothness of the workload, are overoptimistic disregarding starving and blocking phenomena, resultant from the stochasticity of the workers. In this thesis a two stage genetic algorithm approach is presented to solve the Assembly Line Balancing Problem Type II, with stochastic heterogeneous task times and buffers between workstations. A discrete event simulator is used to compute the objective function of each individual, evaluating simultaneously the effect of the buffer and worker allocation on the cycle time of the line, thus allowing to take into account the mentioned effect of the stochastic workforce. A suitable chromosomal representation allows the algorithm to iterate efficiently the possible solutions, by varying simultaneously task sequence and assignment to workstations, in one stage, and workers and buffer allocation in the other. The approach is tested on a set of benchmarking problems, which were suitably extended to analyze its performance in the presence of stochastic and heterogeneous workers. Concluding that this method is capable of efficiently searching a wide universe of solutions.