Application of Adaptive Tabu Search to U-Shaped Assembly Line Balancing under Heuristic Organization

S. Suwannarongsri and W. Supithak (Thailand)


Adaptive tabu search, U-shaped assembly line balancing, Practicing heuristic, and COMSOAL


The adaptive tabu search (ATS) is one of the meta heuristic AI search techniques. The ATS possesses the backtracking (BT) mechanism to escape local entrapments and the adaptive radius (AR) mechanism to speed up the search process. This article proposes the application of the ATS associated with the practicing heuristic (PH) technique to solve the U-shaped assembly line balancing (UALB) problems considered as NP-hard combinatorial optimization problems. Under a novel heuristic organization, application of the ATS and the PH for solving the UALB consists of three phases, i.e. (i) transforming the UALB to the straight assembly line balancing (SALB), (ii) balancing the SALB, and (iii) transforming the balanced SALB to the UALB. In search process, the workload variance, the idle time, and the line efficiency are combined as the multiple-objective function. The proposed approach is tested against five benchmark UALB problems suggested by Scholl and one real world problem. As results, the ATS can well address the number of tasks for each workstation, while the PH can well assign the sequence of tasks according to precedence constrains. By comparison, results obtained by the proposed approach yield the optimal solutions superior to those obtained by the conventional COMSOAL method for all problems.

Important Links:

Go Back