A FAST TABU SEARCH ALGORITHM FOR NO-WAIT FLOW SHOP PROBLEM WITH MAKESPAN CRITERION

摘要

This paper deals with a no-wait flow shop problem with makespan criterion. We present a fast algorithm based on the tabu search approach. In the algorithm the multimoves are used that consist in performing several moves simultaneously in a single iteration of algorithm and allow us to accelerate the convergence to good solutions. Besides, in the algorithm a dynamic tabu list is proposed that assists additionally to avoid trapped at a local optimum. The proposed algorithm is empirically evaluated and found to be relatively more effective in finding better solutions in a much shorter time than existing algorithms. The presented ideas can be applied in many local search procedures.