Seite - 104 - in Algorithms for Scheduling Problems
Bild der Seite - 104 -
Text der Seite - 104 -
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
zurück zum
Buch Algorithms for Scheduling Problems"
Algorithms for Scheduling Problems
- Titel
- Algorithms for Scheduling Problems
- Autoren
- Frank Werner
- Larysa Burtseva
- Yuri Sotskov
- Herausgeber
- MDPI
- Ort
- Basel
- Datum
- 2018
- Sprache
- englisch
- Lizenz
- CC BY 4.0
- ISBN
- 978-3-03897-120-7
- Abmessungen
- 17.0 x 24.4 cm
- Seiten
- 212
- Schlagwörter
- Scheduling Problems in Logistics, Transport, Timetabling, Sports, Healthcare, Engineering, Energy Management
- Kategorien
- Informatik
- Technik