Two Phase Technique for Assembly Line Balancing

A two-phase technique for solving flexible assembly line balancing problems is proposed. In the first phase a global solution is found to the task assignment problem using known algorithmic branch-and-bound techniques. In the second phase the workstations with critical workload are selected and the workstation time is re-calculated/reduced using task models of finer granularity. The workstation models in the second stage are represented as parallel compositions of timed automata to which the parametric model checking technique can be efficiently applied. The method combines the advantages of coarse level line balancing algorithms and fine grain model checking. The modeling rules of second stage are defined which guide the model construction and property specification for estimating the workstation load and parameters in the presence of specific operational and timing constraints.