Polyhedral andLagrangianapproachesforlotsizingwithproductiontimewindows and setuptimes

In thispaper,wesolvethecapacitatedmultiitemlot-sizingproblemwithnon-customerspecificpro- duction timewindowsandsetuptimesusingtwoapproaches:(i)usingaLagrangianrelaxation-based heuristic and(ii)usingreformulationsandacommercialsoftware.Theresultsofthetwoapproachesare analyzed andcomparedbasedonrandomlygenerateddatasets.Theresultsshowthatthefirstapproach finds feasiblesolutionmorerapidlybutasteadystateisreachedveryquickly.Ontheotherhandthe second approachquicklyfindsgoodlowerboundsandfindsgoodfeasiblesolutionsifmoreCPUtimeis allowed. Itturnsoutthat,forawidevarietyofinstancesvaryinginsizeandotherparameters,wecan obtain feasiblesolutionswithin1–5%ofoptimalwithin10sandalsoobtainsolutionsthatareguaranteed within 1–2%ofoptimalwithin60–120s.