A simulated annealing algorithm for balancing the assembly line type II problem with sequence-dependent setup times between tasks

摘要

This paper addresses the general assembly line balancing problem where the simple version is enriched by considering sequence-dependent setup times between tasks. Recently, Andres et al. (Andres, C, Miralles, C, and Pastor, R., 2008. Balancing and scheduling tasks in assembly lines with sequence-dependent setup times. European Journal of Operational Research, 187, (3), 1212-1223.) proposed the type I general assembly line balancing problem with setups (GALBPS-I) and developed a mathematical model and several algorithms for solving the problem. In a similar vein, we scrutinised the GALBPS type II problem where the challenge is to find the minimum cycle time for a predefined number of work stations. To solve the problem, we develop a mathematical model and a novel simulated annealing (SA) algorithm to solve such an NP-hard problem. We then employed the Taguchi method as an optimisation technique to extensively tune different parameters of our algorithm and make the classical SA algorithm more efficient in terms of running time and solution quality. Computational results reflected the high efficiency of the SA algorithm in both aspects.