Seite - 104 - in Algorithms for Scheduling Problems

Algorithms 2018,11, 55 The train j1 is plannedon the sectionsm1,m2, andm3. The route for the train j2 ism1,m2, andm4. Theeventso1,1 ando2,1 haveaconflictonthemachinesm1 andeventso1,2 ando2,2 on themachinem2. Topresentaconflictbetweenthetwooperationsinthemixedgraphapproachonlyoneedgeisrequired ( [ oj,i,oj′,i′ ] ∈D) (SeeFigure1a).While in thealternativegraphmodel twoarcsareneeded,denoted as (oj,i+1,oj′,i′ ) and(oj′,i′+1 oj,i ) (SeeFigure1b). 8 : 8 : Figure1.Presentingaconflict inagraphG : (a)usinganedge in themixedgraphmodel topresent aconflictbetweenthe twooperations; (b)usingtwoarcs in thealternativegraphmodel topresenta conflictbetweentwooperations. 8 : 8 : Figure 2. Resolving the conflicts on themachinem1 andm2 in a graphG : (a) conflict resolution usingthemixedgraphmodel; (b) conflict resolutionusingthealternativegraphmodel tosupport the blockingcondition. Afterconflict resolution in themixedgraphmode(Figure2a), theoperation o2,2 couldstart its processing inminute14onthemachinem2 (immediatelyafter thecompletionof theoperationo1,2). While in thealternativegraphcase (Figure2b), thestarting timeofeventso2,2 ispostponedtominute 16,which job j1 hasstartedtheevent o1,3. The job j1 haswaitedfor2minfor themachinem3 andis blockedonthemachinem2. In thispaper,weproposeanapproachthat isahybridbetweenthemixedgraphandalternative graph. This hybrid approach makes use of (1) a mixed graph formulation to represent the non-rescheduled timetable in the initial stageof the solutionprocess, and (2) analternativegraph approachwhenthe timetable is tobere-scheduled. Thereasons fordoingsoareas follows: Oneway tospeedupthealgorithmis to reduce thenumberof edgesandarcs in thegraphG. Thisreductionleadstoalowernumberofneighbourhoodverticesneedingtobehandled, lessfeasibility andconstraintcheckingbeingrequired, lesscomputational timetoupdate thedataateachstage,anda faster traverse inthegraph.Asthemixedgraphmodelusesoneedgetopresentaconflictbetweentwo verticesandalternativegraphneeds twoarcs, thenon-rescheduledtimetable in the initial stageuses themixedgraphapproach(SeeFigure1a).However,after theconflict resolution, thealgorithmuses thealternativegraphapproach(addinganarc fromnextoperation) tosatisfy theblockingcondition (SeeFigure2b). Thismeans that for theunsolvedpart, thegraphismodelled likeamixedgraph,and for thesolvedpart, it followsthealternativegraphmodellingapproach. Forsafetyreasons, the trainshave toobeyaminimumclear timeandheadwaytimedistance [23]. Theclear time(cm ) is theminimumtimethata train j′mustwaitbeforeenteringasectionm,which the train j just left. This timeintervalbetweencompletionof train jandstart timeof the train j′ can bemodelledbychangingtheweightof thepriorityarc fromzeroto cm. Theheadwaytimedistance 104