An exact approach for single machine subproblems in shifting bottleneck procedures for job shops with total weighted tardiness objective

In this paper, we propose an exact solution method for single machine scheduling problems typically arising from bottleneck-based decomposition of weighted tardiness job shops. The encountered subproblems are characterized by delayed precedence constraints, multiple local due dates per operation and an objective function that is given by a weighted sum of maximum tardiness values. The key concept for solving these subproblems to optimality is a dominance rule whose underlying concepts have been newly developed to cope with the given structural properties. Furthermore, a simple lower bound and a dedicated constraint programming technique are presented. The efficiency of the proposed method is demonstrated by means of single machine problems collected during a run of a shifting bottleneck procedure for job shops in different size and due date tightness configurations.

► Shifting bottleneck procedures decompose a job shop into single machine subproblems. ► The total weighted tardiness case requires specific considerations. ► We present dedicated CP techniques for pre-processing subproblems. ► We establish criteria for dominance between partial sequences of operations. ► The final branch-and-bound algorithm can solve instances with up to 30 jobs.