Title of article :
A bileveldecompositionalgorithmforsimultaneousproductionscheduling
and conflict-freeroutingforautomatedguidedvehicles
Author/Authors :
Tatsushi Nishi، نويسنده , , YuichiroHiranaka ، نويسنده , , IgnacioE.Grossmann، نويسنده ,
Issue Information :
ماهنامه با شماره پیاپی سال 2011
Abstract :
We addressabileveldecompositionalgorithmforsolvingthesimultaneousschedulingandconflict-free
routing problemsforautomatedguidedvehicles.Theoverallobjectiveistominimizethetotalweighted
tardinessofthesetofjobsrelatedtothesetasks.Amixedintegerformulationisdecomposedintotwo
levels:theupperlevelmasterproblemoftaskassignmentandscheduling;andthelowerlevelrouting
subproblem.ThemasterproblemissolvedbyusingLagrangianrelaxationandalowerboundis
obtained.Eitherthesolutionturnsouttobefeasibleforthelowerlevelorafeasiblesolutionforthe
problemisconstructed,andanupperboundisobtained.Iftheconvergenceisnotsatisfied,cutsare
generatedtoexcludepreviousfeasiblesolutionsbeforesolvingthemasterproblemagain.Twotypesof
cuts areproposedtoreducethedualitygap.Theeffectivenessoftheproposedmethodisinvestigated
from computationalexperiments.
Keywords :
Automated guided vehicle , Bilevel decomposition , Lagrangian relaxation , Scheduling , Routing
Journal title :
Computers and Operations Research
Journal title :
Computers and Operations Research
