  In traditional assembly lines, it is reasonable to assume that task execution
times are the same for each worker. However, in sheltered work centres for
disabled this assumption is not valid: some workers may execute some tasks
considerably slower or even be incapable of executing them. Worker
heterogeneity leads to a problem called the assembly line worker assignment and
balancing problem (ALWABP). For a fixed number of workers the problem is to
maximize the production rate of an assembly line by assigning workers to
stations and tasks to workers, while satisfying precedence constraints between
the tasks. This paper introduces new heuristic and exact methods to solve this
problem. We present a new MIP model, propose a novel heuristic algorithm based
on beam search, as well as a task-oriented branch-and-bound procedure which
uses new reduction rules and lower bounds for solving the problem. Extensive
computational tests on a large set of instances show that these methods are
effective and improve over existing ones.
