In the assembly line balancing problem, tasks are assigned to workstations on an assembly line so as to minimize the line's cycle time. An assembly line consists of a series of workstations in which each station performs one or more specialized tasks in the manufacture of a final product. The cycle time is the maximum time it takes any workstation to complete its assigned tasks. The goal in balancing an assembly line is to assign tasks to stations so equal amounts of work are performed at each station. Improperly balanced assembly lines will experience bottlenecks--workstations with less work are forced to wait on preceding stations with more work assigned.

The problem is complicated further by precedence relations amongst the tasks, where some tasks must be completed before others may begin (e.g., when building a computer, installing the disk drives must precede putting on the outer casing). The assignment of tasks to workstations must obey the precedence relations.