Page - 102 - in Algorithms for Scheduling Problems

Algorithms 2018,11, 55 agraphG, thealgorithmhas tovisit all conflictpairs, andby replacing theedgeswithdirectedarcs, clarify thepriorities forusing the resources (i.e., the sections andassociated tracks). In this research, the objective is tominimize the sumof the total final delay that each train experiences at its final destination (i.e., TFDj = Max ( 0,xendj,last−einitialj,last ) , j ∈ J ). We alsomeasure the correspondingwhen the delay threshold is threeminutes, i.e., only delays larger than threeminutes are considered, i.e.,( ∑TFD+3j ,if TFDj≥3min ) . The reasonwhy the thresholdof threeminutes is selected is that this thresholdisusedtologtraindelaysinSweden.Delayssmallerorequaltothreeminutesarenotregistered inthesystemoftheresponsibleauthority,Trafikverket (theSwedishNationalTransportAdministration). Furthermore,delayslargerthanthreeminutesmaycausetrainconnectionstobemissed,whilebelowthree minutes theconsequencesfor transfers inthestudiedregional-national trainsystemarenot that likely. Tovisit theconflictingoperations,wefollowedthestrategypresentedbyGholamiandSotskovfor thehybrid job-shopschedulingproblem[27]. In thisstrategy,a listofpotential candidateoperations for conflict resolutionwill begenerated. This list is a collectionof ongoingoperations, or thefirst operationof thenext trains.Afteranyconflict resolution, the listwillbeupdated, somecandidates will beaddedand, if it isnecessary, somewill bedeleted. Anoperationwill beadded to the list if the in-degreevalueof the relatedvertexbecomeszero (thenumberofarcends toavertex is called the in-degreevalueof thevertex). The in-degreevaluedecreaseswhentheconflict resolution isdone for aparentvertex. When the list is regenerated, the shortest release timeof all vertices in the list will be calculatedorupdatedagain, and theminimumonewill be selected for conflict resolution. Are-orderingmaycauseavertex tobedeletedfromthe list. Bythisapproach,all theverticeswillbe visitedonlyonce,unlessare-orderinghappens. Thisstrategydecreases thecomputational timeof the algorithm.Thesecondbenefitof thisapproach is thataddinganewarc (oj,i, oj′,i′ )doesnotaffectany previouslyvisitedverticesunlessare-orderingoccurs.Dynamicupdateofdata ispossibledueto this feature. InAlgorithm1, thepseudocodeforconflict resolution ispresented. Thealgorithmstarts fromavertexos andfindsall theneighbourhoodverticesandaddsthemto a list of candidatevertices. At each iteration, avertexwithaminimumrelease timewill be selected fromthecandidate list forconflict resolution. If there isaconflictbetweenthecandidateeventandthose events thatpreviouslyusedthat trackorsection(checkList),a localre-routingwillbeapplied. For local re-routing,aplatformortrackwithminimumavailability timewillbeselected.Meanwhile, if there is still a conflict, thealgorithmtries touse re-timingor re-ordering. For conflict resolutionbetween the candidateoperationoj′,i′andanoperationoj,i fromthechecklist,anewarcwillbeaddedtothegraphG. Afteraddingthearc(oj,i,oj′,i′ ), thestart time(x begin j′,i′ )ofoperationoj′,i′willbepostponedtothefinishing time(xendj,i )ofoperationoj,iontheconflictingtrackorplatform. If thealgorithmaddstheoppositearc (oj′,i′,oj,i ), thenoperationoj′,i′havetobeservedbeforetheoperationoj,i,whichmeansthat thepredefined order of the trains forusing this section is changed. This conditionoccurswhen the algorithm tries topreventdeadlocks (unfeasiblesolutions),or theoperationoj,ihasahightardiness (adelayedtrain). Sixdispatchingrulesareprovidedfor theconflict resolutionprocess. Table2 isadescriptionof those dispatchingrules. In the trainschedulingproblem,a trainblocks itscurrentsectionuntilobtainingthenextsection orblock. Therefore, swappingisnotpossible in the trainschedulingproblem.Accordingly, theaddArc functionhas tosatisfy theblockingcondition in thegraphG (thealternativegraphapproach). Tofulfil theblockingcondition, insteadofaddinganarc fromtheoperation oj,i to theoperation oj′,i′, anarc fromthenextoperationoj,i+1withazeroweightwillbeaddedtotheoperationoj′,i′. Thisdirectedarc meansthat theoperationoj′,i′ cannotproceedwith itsexecutiononthemachinemuntil theoperation oj,i+1 starts (x begin j′,i′ ≥ x begin j,i+1,meanwhile, theoperationoj,i is finished). Thisconditionblocks job j′onthe previousmachine,evenif it iscompleted. If theoperationoj,i is the lastoperationof job j, thenanarc withaweightdj,ihas tobeadded. 102