Bounds for Assembly Line Balancing Heuristics
Operations Research · 1985 · Volume 33 · Issue 6
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
Enable JavaScript for citation tools and additional paper interactions.