Metaheuristic for scheduling with dependent setup times

This article focuses on the one machine scheduling problem where jobs can be grouped in classes with the same machine setups. The setup times between classes are sequence dependent. An approximation method based on Tabu Search metaheuristic is proposed. The objective is to minimize the weighted sum of setup costs, tardiness and inventory holding costs. The performance of the heuristic is evaluated through three sets of computational tests: (1) empirical performance analysis of the heuristic with different data sets; (2) comparison between the heuristic and the well known dispatching rules EDD and SPT; (3) application of the heuristic for solving a real life scheduling problem.