Balancing U-shaped assembly lines with resource dependent task times: A Simulated Annealing approach

The advent of Just-in-Time (JIT) and Group Technology philosophies has popularized U-shaped assembly lines, which help overcome many of the disadvantages, like line inflexibility, job monotony, large inventories, etc., typically associated with straight assembly lines. Although U-shaped layout has demonstrated its supremacy over the traditional straight layout, the problem of U-shaped assembly line balancing (ULB) is much more complex. The extant literature on ULB assumes that each assembly task requires a fixed (or no) equipment and a fixed number of workers. However, it is often desirable to reduce certain task times by assigning more workers or alternative equipments at a given workstation. The problem in such cases is to assign not only the task but also resource alternatives (number of workers and equipment type) to workstations. Research on such resource dependent U-shaped assembly line balancing (RDULB) is scarce. We address the problem of RDULB and propose a Simulated Annealing (SA) based metaheuristic, which gives optimal solution for most of the small-to-medium problem instances. For very large problems, while SA generates a good feasible solution within half an hour to 1.5 h, Cplex is unable to find a single feasible solution even after 10 times the CPU time required by SA.