Optimization Online


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

Yunpeng Pan (ypan***at***combinenet.com)
Leyuan Shi (leyuan***at***engr.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


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

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society