Assembly line design with incompatible task assignments

Assembly lines are widely used for the mass production of consumer goods and components in large volume production systems. Design of these lines warrants taking into consideration not only cycle time and precedence constraints, but also other restrictions. An important recurring restriction is that some pairs of tasks cannot be assigned to the same station due to factors such as safety, physical demands placed on workers, quality, and technological considerations. The paper investigates this problem and a current industry practice used for solving this problem. The present investigation of this problem yields three findings. First, the paper identifies a new class of heuristic procedures which dynamically updates task priorities. The investigations show that this class of heuristics yields better results. Second, extremely greedy procedures such as knapsack heuristics (Hoffmann procedure) continue to perform better than competing heuristics for industrial grade problems even when additional restrictions on task assignments are present. However, when task restrictions are severe, this is no longer true. Lastly, the paper presents an enumerative procedure to search for optimal solutions in the presence of restrictions. The present study shows that while most simple assembly line balancing problems can be solved optimally, presence of additional restrictions such as task assignments makes them inherently more difficult. The paper provides insights into this aspect.