New observations are made about two lower bound schemes for single-machine min-sum scheduling problems. We find that the strongest bound of those provided by transportation problem relaxations can be computed by solving a linear program. We show the equivalence of this strongest bound and the bound provided by the LP relaxation of the time-indexed integer programming formulation. These observations lead to a new lower bound scheme that yields fast approximation of the time-indexed bound. Several techniques are developed to facilitate the effective use of the new lower bound in branch-and-bound. Numerical experiments are conducted on 375 benchmark problems of the total weighted tardiness problem from OR-Library. Results obtained with our new method are spectacular; we are able to solve all 125 open problems to optimality.
Citation
Mathematical Programming, Series A. Forthcoming. Available Online: http://dx.doi.org/10.1007/s10107-006-0013-4