Ja. Hoogeveen et Sl. Vandevelde, STRONGER LAGRANGIAN BOUNDS BY USE OF SLACK VARIABLES - APPLICATIONS TO MACHINE SCHEDULING PROBLEMS, Mathematical programming, 70(2), 1995, pp. 173-190
Citations number
33
Categorie Soggetti
Operatione Research & Management Science",Mathematics,"Operatione Research & Management Science",Mathematics,"Computer Science Software Graphycs Programming
Lagrangian relaxation is a powerful bounding technique that has been a
pplied successfully to many NP-hard combinatorial optimization problem
s. The basic idea is to see an NP-hard problem as an ''easy-to-solve''
problem complicated by a number of ''nasty'' side constraints. We sho
w that reformulating nasty inequality constraints as equalities by usi
ng slack variables leads to stronger lower bounds. The trick is widely
applicable, but we focus on a broad class of machine scheduling probl
ems for which it is particularly useful. We provide promising computat
ional results for three problems belonging to this class for which Lag
rangian bounds have appeared in the literature: the single-machine pro
blem of minimizing total weighted completion time subject to precedenc
e constraints, the two-machine flow-shop problem of minimizing total c
ompletion time, and the single-machine problem of minimizing total wei
ghted tardiness.