Note—Operator Assignment and the Parametric Preflow Algorithm

This note addresses a problem of assigning human operators to operations in a manufacturing system. The problem involves a set of operations, a work load for each operation, and a set of human operators, each skilled at a subset of the operations. The task is to assign the operators to the operations so as to maximize the capacity of the system, robustly. The problem is formulated as a network flow problem with a lexicographic objective. It is then shown how to solve this problem very efficiently as a parametric sequence of network maximum flow problems, by application of the “parametric preflow” algorithm of Gallo, Grigoriadis and Tarjan.