Minimizing the sum of maximum earliness and maximum tardiness in the single‐machine scheduling problem with sequence‐dependent setup time

This paper considers the problem of scheduling a given number of jobs on a single machine to minimize the sum of maximum earliness and maximum tardiness when sequence‐dependent setup times exist (1|STsd|ETmax). In this paper, an optimal branch‐and‐bound algorithm is developed that involves the implementation of lower and upper bounding procedures as well as three dominance rules. For solving problems containing large numbers of jobs, a polynomial time‐bounded heuristic algorithm is also proposed. Computational experiments demonstrate the effectiveness of the bounding and dominance rules in achieving optimal solutions in more than 97% of the instances.