Complexity Results for Mixed-Model Assembly Lines with Approximation Algorithms for the Single Station Case

Mixed-model assembly lines are becoming increasingly interesting as the use of just-in-time principles in manufacturing continues to expand. This paper presents, for the first time, complexity results for the underlying problem of product sequencing. It is shown that the problem is intractable for both the single station and the multiple station case. Nevertheless, efficient 1.5-approximation algorithms are developed for the early- and late-start models associated with the former case. Empirical results demonstrate that these algorithms perform extremely well in practice.