Optimally Balancing Large Assembly Lines with “Fable”

TLDR

The authors formulate and test a new algorithm, FABLE, for optimally balancing large assembly lines, also describing a heuristic variant. FABLE is a laser‑type depth‑first branch‑and‑bound algorithm that rapidly achieves feasibility using dominance rules and bound arguments, and its design was evaluated on 549 diverse problems. FABLE finds proven optimal solutions for ten 1000‑task lines in under 20 s and solves 64 benchmark problems in 3.16 s, demonstrating strong performance that depends on tasks per station, precedence strength, and total tasks.

Abstract

A new algorithm for optimally balancing assembly lines is formulated and tested. Named “FABLE,” it obtains proven optimal solutions for ten 1000 task lines, which each possess the computationally favorable conditions of an average of at least 6 tasks per work station and a small number of between-task precedence requirements, in less than 20 seconds of IBM 3033U CPU time for each problem. FABLE also performs very favorably on a benchmark group of 64 test problems drawn from the literature, which are of up to 111 tasks each. FABLE finds and proves an optimal solution to the 64 problems in a total of 3.16 seconds of IBM 3090 CPU time. FABLE is a ‘laser’ type, depth-first, branch-and-bound algorithm, with logic designed for very fast achievement of feasibility, ensuring a feasible solution to any line of 1000 or even more tasks. It utilizes new and existing dominance rules and bound arguments. A total of 549 problems of various characteristics are solved to determine conditions under which FABLE performs most and least favorably. Performance is sensitive to average number of tasks per work station, number of between-task precedence requirements (measured by ‘order strength’), and the total number of tasks per problem. A heuristic variant of FABLE is also described.