Stronger Lagrangian bounds by use of slack variables: Applications to machine scheduling problems

Stronger Lagrangian bounds by use of slack variables: Applications to machine scheduling problems

0.00 Avg rating0 Votes
Article ID: iaor19971076
Country: Netherlands
Volume: 70
Issue: 2
Start Page Number: 173
End Page Number: 190
Publication Date: Oct 1995
Journal: Mathematical Programming (Series A)
Authors: ,
Keywords: scheduling
Abstract:

Lagrangian relaxation is a powerful bounding technique that has been applied successfully to many 𝒩𝒫-hard combinatorial optimization problems. The basic idea is to see an 𝒩𝒫-hard problem as an ‘easy-to-solve’ problem complicated by a number of ‘nasty’ side constraints. The authors show that reformulating nasty inequality constraints as equalities by using slack variables leads to stronger lower bounds. The trick is widely applicable, but they focus on a broad class of machine scheduling problems for which it is particularly useful. The authors provide promising computational results for three problems belonging to this class for which Lagrangian bounds have appeared in the literature: the single-machine problem of minimizing total weighted completion time subject to precedence constraints, the two-machine flow-shop problem of minimizing total completion time, and the single-machine problem of minimizing total weighted tardiness.

Reviews

Required fields are marked *. Your email address will not be published.