A Branch and Bound Algorithm for Assembly Line Balancing Problems with Formulation Irregularities
提出一种分支定界算法，能处理装配线平衡问题中九种公式化修改，包括允许计划不平衡、特定任务分配到特定站等，并给出计算时间。
This paper describes a branch and bound algorithm which can solve assembly line balancing probems with nine modifications to the originally formulated problem of minimizing the required number of assembly stations, given a cycle time, a set of tasks with given deterministic performance times, and between-task precedence relationships. The first two formulation modifications are those of permitting planned imbalance in the total of task performance times at each assembly station, and allowing specific tasks to be assigned to specific types of assembly stations. Seven further problem modifications can be solved by the proposed algorithm, or by any algorithm or heuristic that can solve problems containing these first two modifications. They are: treatment of stochastic task performance times on unpaced lines; requirement of particular tasks to be assigned to particular stations; requirement of task groupings according to task skill levels; requirement of particular tasks to be assigned to only a left-of-line or right-of line station; required task separations; some mixed model situations; and where paralleling of a specified task into two (or more stations) is permitted. The algorithm is presented in both conceptual and detailed form. Computer computation times to solve a selected cross-sectional sample of problems are provided.