Fast, Effective Algorithms for Simple Assembly Line Balancing Problems

TLDR

The paper proposes a simple, fast, and effective heuristic to minimize the number of workstations in the Simple Assembly Line Balancing Type I problem. The authors develop a fast, effective branch‑and‑bound algorithm that uses the heuristic for bounding, applies heuristic fathoming to shrink the search tree, and extends the approach to solve the Simple Assembly Line Balancing Type II problem of maximizing production rate. Upper bounds for all heuristics on both Type I and Type II problems are presented.

Abstract

A simple, fast and effective heuristic for the Simple Assembly Line Balancing Type I problem (minimizing the number of workstations) is proposed. A fast and effective branch-and-bound algorithm, which incorporates this heuristic for use in bounding, is developed. The algorithm introduces heuristic fathoming as a technique for reducing the size of the branch-and-bound tree. Methods to solve the Simple Assembly Line Balancing Type II problem (maximizing the production rate) are also described. Upper bounds on all heuristics for both problems are provided.