An algorithm based on tabu search method for job shop scheduling

An effective heuristic algorithm for solving the minimum makespan of job shop scheduling was presented in this paper. The tabu search method based on variable length of tabu list was applied in the algorithm. In the tabu search procedure, the lower bound of the completion time (makespan) was utilized as the secondary evaluation of solutions. The computations for achieving the lower bound are much less than those for achieving the completion time, therefore the computational time of the procedure is reduced greatly. The computational experiments on a set of benchmark problem instances showed that, in several cases, the approach, in a reasonable amount of computing time, yields better results than the ‘Tabu Search Algorithm with Backjumps’ (TSAB), which is one of best tabu search algorithms of those not using shifting bottleneck technique.