U-Shaped assembly lines with stochastic tasks execution times: heuristic procedures for balancing and re-balancing problems

Despite the fact that most of the published papers concerning the assembly line balancing problem contemplate straight-lines configurations, an increasing number of researchers recently pointed out advantages related to U-shaped lines. Literature presents only a few number of algorithms for balancing such a line type. The main difference between straight-lines and U-shaped lines models concerns the identification of available operations to be assigned to a station. In the former case, each task can be assigned to a station only after its predecessors have been allocated, whereas in the latter one, available operations are those where both predecessor and successor tasks are assigned. Thus, solving approaches to balance a U-shaped line can be obtained by applying modified techniques for straight-lines. In this paper, a heuristic methodology is proposed for solving the U-shaped version of the balancing problem, which aims at minimizing both labor and incompletion costs. Moreover, an algorithm for re-balancing an existing line is presented. An existing balance may change in order to accommodate modifications in cycle time, tasks completion time, precedence constraints, tasks adding or removing, etc. The necessity of a procedure for minimizing differences between new and initial balancing solutions is highlighted, in accordance with tasks movements, which involve several execution time consumption and costs in changing system configuration, moving and installing equipment, training workers, etc. The proposed model is based on a multi-objective approach to obtain valuable compromises between costs minimization and tasks re-assignment. Lastly, a wide experimentation within a large family of simulated scenarios is carried out, to assess the suitability of the proposed procedures.