ASALBP: The Alternative Subgraphs Assembly Line Balancing Problem

The classic assembly line balancing problem basically consist in assigning a set of tasks to a group of workstations while maintaining the task’ precedence relations. Habitually, such relations are represented by a predetermined precedence graph. However, a product’s assembly process may admit, for one or more of its parts, alternative precedence subgraph. This may be due to the fact that the processing time for some task are dependent on their processing sequence, or because there are alternatives for such a subassembly. In general, because of the great difficulty of the problem and the impossibility of representing alternative subgraphs in a precedence graph, the system designer will decide to select, a priori, one of such alternative subgraphs, which sometimes imposes additional constrains other than technological ones. In this paper we present, characterize and formulate a new general assembly line balancing problem: the Alternative Subgraphs Assembly Line Balancing Problem (ASALBP). Its novel characteristic is that it considers the possibility of having alternative assembly subgraphs, in which the processing times and/or the precedence relations of certain task are dependent on the assembly subgraph selected. Therefore, solving this problem implies simultaneously selecting an assembly subgraph for each part of the assembly that allows alternatives and balancing the line (i.e., assigning the task to the workstations). The potentially positive effects of this on the solution of the problem are shown here in a numerical example. Finally, the mathematical programming model developed is described and the results of a brief computational experiment are presented