Abstract
Tabu search is a local search algorithm that widely used for solve scheduling problem. The most important architecture of this algorithm called tabu list. It is designed to resolve the situation that algorithm may fall in a loop. Starting from a current solution, tabu search moves to a best neighborhood solution. The procedure will repeat until a certain terminating condition is satisfied. Because of the design of neighborhood solutions, when tabu search deal with job shop scheduling problems, there is a condition may result a miss of a better solution. If a neighborhood solution N is not the best neighborhood solution, it will not be chosen as next solution. However,if tabu search is allowed to move to N, it will be able to find a outstanding solution N’, that is a neighborhood of N. Nowicki and Smutnicki [1996] reported an algorithm called fast tabu search that is modified from simple tabu search with a neighborhood definition that reduced the number of neighborhood solutions. It can solve job shop scheduling problem in a short time. However, Demirkol and Uzsoy [1998] illustrated that fast tabu search algorithm may miss better solutions when deals with job shop scheduling problem with sequence dependent setup time, because its design of neighborhood solution does not contain all improving neighborhood solutions. This thesis tries to modify the design of neighborhood solutions to solve job shop scheduling problem with sequence dependent setup times with a better solutions. After our experiment we find that muiti-step tabu search algorithm demonstrates the ability to escape local optimal solution and perform a little bit better than simple tabu search.