On a learning precedence graph concept for the automotive industry

Assembly line balancing problems (ALBP) consist in assigning the total workload for manufacturing a product to stations of an assembly line as typically applied in automotive industry. The distribution of the tasks to the stations is due to restrictions which can be expressed in a precedence graph. However, automotive manufacturers usually do not know complete precedence graphs describing the production processes of their models. Unfortunately, the known approaches for graph generation are not suitable for the conditions in the automotive industry. We describe a new graph generation approach that is based on learning from past production sequences and forms a sufficient precedence graph. This graph, indeed, restricts the ALBP instance but guarantees feasible line balances. Computational experiments indicate that the proposed procedure is able to approximate the real precedence graph sufficiently well to detect optimal or nearly optimal solutions for all instances of a benchmark data set. So, the new approach is applicable and effective and might be a major step to close the gap between theoretical line balancing research and practice of assembly line planning.