Page - 100 - in Algorithms for Scheduling Problems

Algorithms 2018,11, 55 A job-shopschedulingapproachisalsousedto insertadditional trains toanexistingtimetable without introducingsignificantconsecutivedelays to thealready-scheduledtrains [26].Abranchand boundalgorithmandaniterativere-orderingstrategyareproposedtosolve thisprobleminreal-time. Re-timingandre-orderingareconducted inagreedymanner. Theyhavesuggestedanewboundfor thebranchandboundalgorithmandaniterativere-orderingalgorithm,whichhelps tofindsolutions inanacceptablecomputational time. Themainchallenge in this studyis to—inspiredbypreviouspromisingresearchwork—develop, applyandevaluate aneffective algorithmthat,within10 s, canfindsufficientlygoodsolutions to anumberofdifferent typesof relevantdisturbancescenarios foramedium-sizedsub-networkand a timehorizonof 60–90min. Ahybridof themixedgraphandalternative graph (aderivationof thedisjunctivegraph,whichsatisfies theblockingconstraint [11]) formulation isusedformodelling the train trafficre-schedulingproblem.Thisgraphallowsus tomodel theproblemwithaminimum number of arcs, which is expected to improve the efficiency of the algorithm. Themodel of the infrastructureandtrafficdynamics isonthemesoscopic level,whichconsidersblocksections, clear timeandheadwaydistance,basedonstaticparametervalues.Aheuristicalgorithmisdevelopedfor conflict resolution. Thisalgorithmisanextensionof thealgorithmdevelopedbyGholamiandSotskov forhybrid job-shopschedulingproblems[27]. Theextendedalgorithmprovidesaneffectivestrategy forvisiting theconflictingoperationsandthealgorithmmakesuseof re-timing, re-ordering,andlocal re-routingof trainswhileminimizingtraindelays. 3.ModellingtheJob-ShopSchedulingProblemUsingaGraph Awell-knownandefficientwayofmodellingthe job-shopschedulingproblemis tousegraphs. Graphtheory isawell-studiedarea in thecomputational sciences,anditprovidesefficientalgorithms anddata structures for implementation. These featuresmake the graph a suitable candidate for modelingtheproblemaddressed in thispaper. Ina job-shopschedulingproblem, therearen jobs thathave tobeservedbymdifferent typesof machines. Each job j∈ Jhas itsownsequenceofoperationsOj= { oj,1,oj,2, . . . ,oj,m } tobeservedby differentpredefinedmachines fromthesetM. The jobshave tobeservedbymachinesexclusively. The job-shopschedulingproblemcanbe formulatedusingamixedgraphmodelG=(O,C,D), or equivalentlybyadisjunctivegraphmodel. LetOdenote thesetofalloperations tobeexecutedbya setofdifferentmachinesM. ThesetC representsapredefinedsequenceofoperations foreach job j tovisitmachines fromthesetM. The twooperationsoj,i andoj′,i′whichhavetobeexecutedonthe samemachinem∈M, cannotbeprocessedsimultaneously. This restriction ismodelledbyanedge[ oj,i,oj′,i′ ]∈D (if amixedgraphisused)orequivalentlybypairsofdisjunctivearcs{(oj,i,oj′,i′), and( oj′,i′,oj,i ) } (if adisjunctivegraphisused). In thispaper, themixedgraphisusedformodellingthe primarystateoftheproblem.Twovertices,osandodasthesourceanddestinationvertices, respectively, areaddedto themodel to transformit toadirectedacyclicgraph. Using the terms “arc” and “edge”may be confusing. Edgesmay be directed or undirected; undirectededgesarealsocalled“lines”,anddirectededgesarecalled“arcs”or“arrows”. Inthispaper, the term“edge” isusedforundirectededges,andthe term“arc” isusedfordirectededges. Toserve theoperations ina job-shopschedulingproblem,onlyone instanceofeachmachineof typem isavailable. Inahybrid job-shopasaderivationof the job-shopschedulingproblem,asetMm (|Mm|≥1 ) isavailable toserve theoperations [28]. Thenotation 〈m,u〉 isusedto indicateaspecific machineorresourceu fromasetMm if it isnecessary. Theseuniformparallelmachinesets increase the throughputandprovidemoreflexibility in theschedulingprocess. Atrain isheresynonymouswitha jobinthe job-shopschedulingproblem.Atrainroutefromthe sourcestationtothedestinationcanbeconsideredtobeasequenceofoperationsfora job j. Eachrailroad section is synonymous toamachinem. InTable1,below,we introduce thenotations thatareusedto describeanddefinethehybridgraphmodel,algorithmicapproach,andcorrespondingMIPmodel. 100