The stochastic U-line balancing problem

A U-line arranges tasks around a U-shaped production line and organizes them into stations that can cross from one side of the line to the other. In addition to improving visibility and communication between operators on the line, which facilitates problem-solving and quality improvement, U-lines can reduce the total number of operators required on the line and make rebalancing the line easier compared to the traditional, straight production line. This paper studies the (type 1) U-line balancing problem when task completion times are stochastic. Stochastic completion times occur when differences between operators cause completion times to vary somewhat and when machine processing times vary. A recursive algorithm is presented for finding the optimal solution when completion times have any distribution function. An equivalent shortest path network is also presented. An improvement for the special case of normally distributed task completion times is given. A computational study to determine the characteristics of instances that can be solved by the algorithms shows that they are able to solve instances of practical size (like the 114 Japanese and U.S. U-lines studied in a literature review paper).