Optimally balancing large assembly lines: updating Johnson's 1988 Fable algorithm

In 1988 Roger Johnson published a paper entitled ‘Optimally Balancing Large Assembly Lines with Fable’ describing a depth-first, branch-and-bound algorithm for solving the type-1 line balancing problem. The Fable algorithm sought to achieve three goals: 1. The algorithm could be a heuristic that would quickly find good solutions to instances containing 1000 or more tasks. 2. After finding a good solution the algorithm could continue until it found a verifiable optimal solution. 3. The algorithm would require a small and predictable amount of computer memory. The objective of this paper is to apply the best of these improvements to the original Fable algorithm to see what progress has been made in 15 years and where work is still needed. The resulting algorithm is called Fable 2003 and it seems to perform as well as the current best algorithms in the literature.