A balancing problem for a mixed model assembly line with uncertain task processing time and daily model mixed changes is considered, and the objective is to minimize the work variances be- tween stations in the line. For the balancing problem for the scenario-based robust assembly line with a finitely large number of potential scenarios, the direct solution methodology considering all potential scenarios is quite time-consuming. A scenario relaxation algorithm that embeds genetic al- gorithm is developed. This new algorithm guarantees termination at an optimal robust solution with relatively short running time, and makes it possible to solve robust problems with large quantities of potential scenarios. Extensive computational results are reported to show the efficiency and effective- ness of the proposed algorithm.