A multi-objective tabu search for a single-machine scheduling problem with sequence-dependent setup times

An m-objective tabu search algorithm for sequencing of n jobs on a single machine with sequence-dependent setup times is proposed. The algorithm produces a solution set that is reflective of the objectives’ weights and close to the best observed values of the objectives. We also formulate a mixed integer linear program to obtain the optimal solution of a three-objective problem. Numerical examples are used to study the behavior of the proposed m-objective tabu search algorithm and compare its solutions with those of the mixed integer linear program.