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.