Seite - 105 - in Algorithms for Scheduling Problems

Algorithms 2018,11, 55 (hm ) is theminimumtimebetweentwotrains jand j′ running in thesamedirectionandonthesame trackofsectionm. Theheadwaydistance is theminimumtimeintervalbetweenthestart times,and endtimesrespectively,of twoconsecutive trains, jand j′,whichcanbemodelledbyaddinganew arcwithaweighthm fromoperationoj,i tooj′,i′. TheaddArcprocedure is responsible foradoptingthe clear timeandheadwaydistance. Figure3, isan illustrationofconflict resolution,consideringtheclear timeandheadwaydistance for thealternativegraphmodel. InFigure3a, thestartingtimeofoperationo2,1 is increasedtominute 11,because, theoperationo1,1 had4minofprocessingtimeand1minofclear time. InFigure3b, the headwaydistance ish1= 7,whichmeans that thestart timeofoperation o2,1mustbeat least7min after thestart timeof theoperationo1,1. Thestartingtimeof theoperationo2,1 is increasedtominute13. 8 : 8 : Figure3.Addingtheclear timeandheadwaytimedistance to thealternativegraph: (a) thestarting timeofoperationo2,1 is increasedduetothecleartime; (b) thestartingtimeofoperationo2,1 is increased dueto theheadwaydistance. Foradecision-makingprocedure, thealgorithmneedssomedata,suchasreleasetime,orbuffertime. Afteranyre-timing,re-orderingor local re-routing, thesedatachange.Theexperimentsdemonstrate that recalculationof thesedatahasasignificanteffectonthecomputational timeof thealgorithm.Ourspecial visitingapproachenablesadynamicupdateofdatafor thosevertices thatwillbeaffected. Afteraddinganewdirectedarc fromtheoperationoj,i to theoperationoj′,i′, byconsideringthe commercial stoptime(passenger trainsarenotallowedto leaveastationbefore the initial completion time einitialj,i ) theminimumstart timeofanoperationoj′,i′onatrackm.uwillbe xbeginj′,i′ = ⎧⎪⎨⎪⎩ Max(binitialj′,i′ ,x end j′,i′−1, maxj∈O′m,u ( xbeginj,i +dj,i ) ) if i′−1wasacommercial stop, Max(xendj′,i′−1, maxj∈O′m,u ( xbeginj,i +dj,i ) ) if i′−1wasnotacommercial stop, (2) whereO′m,u is a set of all operations processed by the same resource u froma set Mm until now. Additionally, theendingtimecanbecalculatedas follows: xendj′,i′= ⎧⎨⎩max ( einitialj′,i′ ,x begin j′,i′ +dj′,i′ ) if i′ isacommercial stop. xbeginj′,i′ +dj′,i′ if i ′ isnotacommercial stop. (3) Consideringtheclear timerestriction, thestarting timeforanoperation oj′,i′willbecalculated as follows: xbeginj′,i′ = ⎧⎪⎨⎪⎩ Max(binitialj′,i′ ,x end j′,i′−1, maxj∈O′m,u ( xendj,i +cm ) ) if i′−1wasacommercial stop. Max(xendj′,i′−1, maxj∈O′m,u ( xendj,i +cm ) ) if i′−1wasnotacommercial stop. (4) 105