A tabu search approach for single machine scheduling with major and minor setups

In this paper, we consider a single machine scheduling problem where jobs are grouped into classes which in turn are grouped into families. A major and a minor setup are required when jobs are switched from one family to another, while only a minor setup is required when the switch is between classes within the same family. Both of the setup times are independent. A tabu search based heuristic is developed for the problem to improve the existing dynamic programming based heuristic. The heuristic suggests a simple technique for generating neighborhoods of a given sequence and the use of hashing function. Also, a diversification scheme is employed to explore new areas in the solution space. Computational results show that the heuristic performs quite well in large-sized problems.