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

Citation
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
Citations number
7
Categorie Soggetti
Engineering, Manufacturing
ISSN journal
09206299
Volume
9
Issue
3
Year of publication
1997
Pages
251 - 272
Database
ISI
SICI code
0920-6299(1997)9:3<251:CRFMAL>2.0.ZU;2-E
Abstract
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.