ISSN:
1572-9370
Keywords:
approximation
;
assembly lines
;
NP-completeness
;
product sequencing
Source:
Springer Online Journal Archives 1860-2000
Topics:
Mechanical Engineering, Materials Science, Production Engineering, Mining and Metallurgy, Traffic Engineering, Precision Mechanics
Notes:
Abstract 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.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1023/A:1007965312977
Permalink