Publikation

An Exact Approach for Single Machine Subproblems in Shifting Bottleneck Procedures for Job Shops with Total Weighted Tardiness Objective

Outline:

R. Braune, G. Zäpfel, M. Affenzeller - An Exact Approach for Single Machine Subproblems in Shifting Bottleneck Procedures for Job Shops with Total Weighted Tardiness Objective - EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, Vol. 218, No. 1, 2012, pp. 76-85

Abstract:

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