Performance Comparison of Neighborhood Structures of Tabu Search Algorithms for Sequencing Problems

摘要

Tabu search is one of the well-known meta-heuristic search methods, and it has been widely applied to solve combinatorial optimization problems such as sequencing problems. Tabu search is based on local search that repetitively moves from a solution to one of its neighbors, so a tabusearch algorithm for a specific problem must incorporate an appropriate neighborhood structure. In general, neighborhood structures of tabu search algorithms for sequencing problems have been defined by applying perturbative operators such as exchange, insertion and 2-opt. Those operators,however, have an important limitation that they did not consider additional constraints of sequencing problems such as precedence among the given items. On the contrary, recently proposed candidate order approach enables a novel neighborhood structure based on constructive operator, whichcan deal with additional constraints flexibly. This paper aims to compare the candidate order approach based neighborhood structure to the traditional ones comprehensively and demonstrate its strengths and weaknesses. For comparison, the neighborhood structures are used to implement the probabilistictabu search algorithms, which are applied to the well-known job sequencing problems with different sets of precedence constraints.