Bounds for Assembly Line Balancing Heuristics

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.