The alternative subgraphs assembly line balancing problem (ASALBP) is an extension of SALBP. It additionally considers that there might be different technological modes for mounting parts. This leads to a balancing problem problem where it is additionally required to select one of several mounting modes, i.e., one of alternative subgraphs (of the precedence graph), for certain parts or group of parts. The respective subgraphs differ by processing times and/or precedence relations. Therefore, solving this problem implies simultaneously selecting an assembly subgraph for each part of the assembly which has alternatives and balancing the line (i.e., assigning the task to the workstations).
The following figure (taken from Scholl et al. 2009) visualizes the mode selection problem. The precedence graph contains two alternative parts. Between the pair of “or-nodes” 2 und 10, one of the three alternative subgraphs has to be chosen. Between the “or-nodes” 12 and 17, one of both alternative subgraphs is to be realized. Thus, in total, 3*2=6 ways of assembling the product are available.
Data sets for ASALBP-1: For the problem version 1 (minimize the number of stations given the cycle time), there are two different data sets available.
Capacho, L.; Pastor, R. (2006): The ASALB problem with processing alternatives involving different tasks: Definition, formalization and resolution. Lecture Notes in Computer Science 3982, 554-563.
Capacho, L.; Pastor, R. (2008): ASALBP: The alternative subgraphs assembly line balancing problem. International Journal of Production Research 46, 3503-3516.
Capacho, L.; Pastor, R.; Guschinskaya, O.; Dolgui, A. (2006): Heuristic methods to solve the alternative subgraphs assembly line balancing problem. Automation Science and Engineering, 2006. CASE ´06. IEEE International Conference on, Shanghai, China, 501-506.
Scholl, A.; Boysen, N.; Fliedner, M. (2009): Optimally solving the alternative subgraphs assembly line balancing problem. Annals of Operations Research 172/1, 243-258.
Capacho, L.; Pastor, R.; Dolgui, A.; Gunshinskaya, O. (2009): An evaluation of constructive heuristic methods for solving the alternative subgraphs assembly line balancing problem. Journal of Heuristics 15, 109-132.