Bounds for Assembly Line Balancing Heuristics

Maurice Queyranne
Additional contact information
Maurice Queyranne: The University of British Columbia, Vancouver, British Columbia

Operations Research, 1985, vol. 33, issue 6, 1353-1359

Abstract: We analyze the asymptotic worst-case performance ratio of polynomial time heuristics for the assembly line balancing problem. Assuming that P ≠ NP , we show that no polynomial heuristic has worst-case ratio less than 1.5. (This ratio is known to be not worse than 2 for any “reasonable” heuristic.) Tighter results are established for problems with only “short” tasks, i.e., when all processing times do not exceed a given fraction of the cycle time. These results apply even to planar, series-parallel precedence constraints, and contrast with known results for situations with an empty precedence relation, i.e., the bin packing problem. In particular, if P ≠ NP , there are no fully polynomial approximation schemes for assembly line balancing, even with “short” tasks and planar, series-parallel precedence constraints.

Keywords: 586 complexity of heuristics; 632 assembly line balancing (search for similar items in EconPapers)
Date: 1985
References: Add references at CitEc
Citations: View citations in EconPapers (4)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.33.6.1353 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:33:y:1985:i:6:p:1353-1359

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().