Shifting bottleneck scheduling for total weighted tardiness minimization–A computational evaluation of subproblem and re-optimization heuristics

Machine-based decomposition of total weighted tardiness job shops is known to be considerably more complicated than in the makespan case, mainly due to the structure of the underlying graph model and thus the arising one-machine subproblems. In fact, the effectiveness of a shifting bottleneck approach crucially depends on the employed subproblem solver. Although a sophisticated exact algorithm exists, problem instances involving more than 30 jobs are still challenging. In this paper, new heuristic approaches to subproblems of this kind are devised which rely on advanced problem-specific concepts like local optimality and dominance principles. The proposed subproblem solvers are combined with an iterated local search method for re-optimizing already scheduled machines. Computational experiments show that the final enhanced shifting bottleneck algorithms are not only applicable to job shops involving up to 100 jobs and 20 machines, but also able to improve existing results for benchmark instances.