COMPLEXITY RESULTS FOR MIXED-MODEL ASSEMBLY LINES WITH APPROXIMATION ALGORITHMS FOR THE SINGLE STATION CASE

Mixed-model assembly lines are becoming increasingly interesting as th e use of just-in-time principles in manufacturing continues to expand. This paper presents, for the first time, complexity results for the u nderlying problem of product sequencing. It is shown that the problem is intractable for both the single station and the multiple station ca se. 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.