Balancing mixed-model assembly lines for random sequences

Assembly lines are the standard choice for the manufacturing of large products and must combine efficiency with flexibility. Since multiple product variants are assembled on the same line, the variation in the processing time and the production sequence must be accounted for. This is especially hard in the planning phase of assembly lines when the demand is only forecast and the production sequence is not yet known. In this paper, an exact method and heuristic extensions are proposed to tackle the paced assembly-line balancing problem considering a random production sequence. Along with the assignment of tasks, the length of the stations is optimized in a Branch-and-Bound algorithm using Markov chains to evaluate the expected costs, which require the solution of a convex subproblem on each node. Product variants are modelled with a given probability, which can be either independent or correlated. Results of the model can be then further improved by optimizing the sequencing once the orders are known. The exact method can solve instances of small and medium-size containing up to 1012 product variants and the heuristic extensions can give good solutions with up to 1020 products. Results show that the optimization of station lengths is more important for the total cost than the difference between optimal and good task assignment solutions.