On the equivalence of the max-min transportation lower bound and the time-indexed lower bound for single-machine scheduling problems

Yunpeng Pan (ypancombinenet.com)
Leyuan Shi (leyuanengr.wisc.edu)

Abstract: 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.

Keywords: Scheduling--Combinatorial optimization--Time-indexing

Category 1: Integer Programming ((Mixed) Integer Linear Programming )

Category 2: Applications -- OR and Management Sciences (Scheduling )

Category 3: Combinatorial Optimization

Citation: Mathematical Programming, Series A. Forthcoming. Available Online: http://dx.doi.org/10.1007/s10107-006-0013-4

Download:

Entry Submitted: 03/28/2005
Entry Accepted: 03/28/2005
Entry Last Modified: 12/06/2006

Modify/Update this entry