On polynomial solvability of the high multiplicity total weighted tardiness problem (Q1208472)

The following scheduling problem is addressed in the paper. Many jobs of unit length but with only a few sets of distinct due dates and penalty weights need to be sequenced on a single machine. The objective is to minimize the total weighted tardiness. Recently, \textit{D. S. Hochbaum}, \textit{R. Shamir} and \textit{J. G. Shantikumar} [Math. Program. 55A, No. 3, 359-371 (1992; Zbl 0761.90061)] formulated this problem as an integer quadratic nonseparable transportation problem. In the paper under review the authors transform the total weighted tardiness problem to an equivalent separable problem with totally unimodular constraint matrix. The latter can be solved in time polynomial in the dimension of the problem and only the size of the maximal difference between two consecutive due dates. In the case where the due dates are large but the size of the maximal difference between two consecutive due dates is polynomially bounded by the dimension of the problem, the algorithm runs in strongly polynomial time.