An Integer Programming Algorithm with Network Cuts for Solving the Assembly Line Balancing Problem
提出一种整数规划算法，通过系统枚举和网络割技术，在满足工序先后顺序和节拍限制下，最小化装配线工作站数量，适用于50-100个任务的优化。
In this paper, we describe an integer programming algorithm for assigning tasks on an assembly line to work stations in such a way that the number of work stations is minimal for the rate of production desired. The procedure insures that no task is assigned to a work station before all tasks which technologically must be performed before it have been assigned (precedence restrictions are not violated), and that the total time required at each work station performing the tasks assigned to it does not exceed the time available (cycle time restrictions are not violated). The procedure is based on a systematic evaluation (enumeration) of all possible task assignments to work stations. Significant portions of the enumeration process are performed implicitly, however, by utilizing tests described in the paper which are based on the specific structure of the line balancing problem. An artifice termed a network cut is also developed which eliminates from explicit consideration the assignment of tasks to work stations where such assignments would not lead to improved line balances. Results reported demonstrate that the procedure can obtain optimal balances for assembly lines with between 50 and 100 tasks in a reasonable amount of computation time and with modest computer storage requirements.