Record number :
927817
Title of article :
Parallel machineschedulingwithprecedenceconstraintsandsetuptimes
Author/Authors :
Bernat Gacias ، نويسنده , , ChristianArtigues ، نويسنده , , PierreLopez ، نويسنده ,
Issue Information :
ماهنامه با شماره پیاپی سال 2010
Pages :
11
From page :
2141
To page :
2151
Abstract :
This paperpresentsdifferentmethodsforsolvingparallelmachineschedulingproblemswith precedenceconstraintsandsetuptimesbetweenthejobs.TheseproblemsarestronglyNP-hardand it isevenconjecturedthatnolistschedulingalgorithmcanbedefinedwithoutexplicitlyconsidering jointly schedulingandresourceallocation.Weproposedominanceconditionsbasedontheanalysisof the problemstructureandanextensiontosetuptimesoftheenergeticreasoningconstraint propagationalgorithm.Anexactbranch-and-boundprocedureandaclimbingdiscrepancysearch (CDS)heuristicbasedonthesecomponentsaredefined.Weshowhowtheproposeddominancerules can stillbevalidintheCDSscheme.Theproposedmethodsareevaluatedonasetofrandomly generatedinstancesandcomparedwithpreviousresultsfromtheliteratureandthoseobtainedwithan efficientcommercialsolver.Weconcludethatourpropositionsarequitecompetitiveandourresults even outperformotherapproachesinmostcases.
Keywords :
Parallel machine scheduling , Precedence constraints , Dominance conditions , branch-and-bound , Local search , Setup times , Limited discrepancy search
Journal title :
Computers and Operations Research
Serial Year :
2010
Link To Document :
بازگشت