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
Journal title
Computers and Operations Research
Record number
927817
Link To Document