Title of article
Lagrangian relaxationwithcutgenerationforhybridflowshopschedulingproblemsto minimize thetotalweightedtardiness
Author/Authors
Tatsushi Nishi، نويسنده , , YuichiroHiranak، نويسنده , , MasahiroInuiguchi، نويسنده ,
Issue Information
ماهنامه با شماره پیاپی سال 2010
Pages
10
From page
189
To page
198
Abstract
In thispaper,weaddressanewLagrangianrelaxation(LR)methodforsolvingthehybridflowshop
scheduling problemtominimizethetotalweightedtardiness.FortheconventionalLR,theproblemrelax-
ing machinecapacityconstraintscanbedecomposedintoindividualjob-levelsubproblemswhichcanbe
solved bydynamicprogramming.TheLagrangiandualproblemissolvedbythesubgradientmethod.In
this paper,aLagrangianrelaxationwithcutgenerationisproposedtoimprovetheLagrangianboundsfor
the conventionalLR.Thelowerboundisstrengthenedbyimposingadditionalconstraintsfortherelaxed
problem. Thestatespacereductionsfordynamicprogrammingforsubproblemsarealsoincorporated.
Computational resultsdemonstratethattheproposedmethodoutperformstheconventionalLRmethod
without significantlyincreasingthetotalcomputingtime.
Keywords
Hybrid flowshop scheduling , Lagrangian relaxation , Cut generation , Dynamic programming
Journal title
Computers and Operations Research
Serial Year
2010
Journal title
Computers and Operations Research
Record number
927635
Link To Document