O. Goldschmidt et al., COMPLEXITY RESULTS FOR MIXED-MODEL ASSEMBLY LINES WITH APPROXIMATION ALGORITHMS FOR THE SINGLE STATION CASE, International journal of flexible manufacturing systems, 9(3), 1997, pp. 251-272
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.