A Computational Study of Lower Bounding Schemes for Total Weighted Tardiness Job Shops

In this paper, we perform a computational study of lower bounding schemes for job shop scheduling problems under special consideration of total weighted tardiness costs. Due to the characteristics of this objective function, lower bounds are much more difficult to derive than for the classical makespan. On the other hand, the practical relevance of tardiness related costs makes it even more important to have corresponding bounds available, especially for rating the results of approximate optimization approaches. Apart from the quality of the bounds, i.e. the tightness with respective to an existing optimal solution or upper bound, a further important focus of our investigations is the required computation time, since this is a determining criterion for the applicability. Computational results are reported based on selected benchmark problems.