Two-Stage Assembly Flow Shop Scheduling Problem with Sequence-Dependent Setup Times

In this paper, we consider the two-stage assembly flow shop scheduling problem with sequence-dependent setup times to minimize the makespan. We propose that the critical path is the basis for job sequencing. Based on Johnson's rule and the NEH algorithm, we present three heuristics to construct feasible solutions to the problem. We develop a hybrid variable neighborhood search algorithm to generate new solutions by four perturbation operators and three neighborhood change strategies, and combine the probabilistic selection formula of simulated annealing to determine whether the new solution is selected. The effectiveness of our algorithm is verified by comparing it with the basic simulated annealing algorithm and the variable neighborhood search algorithm.