Page - 99 - in Algorithms for Scheduling Problems
Image of the Page - 99 -
Text of the Page - 99 -
Algorithms 2018,11, 55
Inorder toreducethecomputational time,onecanpartitiontheproblemintoasetofdifferent
sub-problems and solve them inparallel, in adistributedmannerwith some sort of coordination
mechanism.Thepartitioningcanbedoneinspace(i.e.,bydividingtheinfrastructure,or theassociated
constraints, intoseparateparts),or in time(i.e., rolling-timehorizon).Cormanetal. [16–18]proposed
andbenchmarkedacentralizedandadistributedre-schedulingapproachfor themanagementofa
partof theDutchrailwaynetworkbasedonabranch-and-boundapproach. Thesevariationscome
fromvarious static anddynamic priorities that are considered for scheduling. They alsoworked
ona coordination systembetweenmultipledispatching areas. The aimwas to achieve aglobally
optimalsolutionbycombining local solutions. Someconstraintsaredefinedfor theborderareaanda
branch-and-boundalgorithmsolves thecoordinatorproblem.
Anotherapproachforreducingthecomplexityof theproblemis touseclassicaldecomposition
techniques, which are becoming more frequently used to overcome the complexity (and the
associated longcomputationtimes)of the trainre-schedulingproblemwhenusingexactapproaches.
LamorgeseandManninoproposedanexactmethod,whichdecomposesandsolves theproblemwith
amaster-slaveprocedureusingcolumngeneration[19]. Themaster isassociatedwith the line traffic
controlproblemandtheslaveswith thestationtrafficcontrol.
Decompositionhasalsobeenusedtoreducethecomplexityof theassociatedMIPmodelof thetrain
re-schedulingproblem[20].AniterativeLagrangianrelaxationalgorithmisusedtosolvetheproblem.
Tormoetal. [21]haveinvestigateddifferentdisturbancemanagementmethods, for thepurposeof
supportingrailwaydispatcherswiththeassessmentoftheappropriatenessofeachmethodfordifferent
problemsintherailwayoperations. Theycategorizedthedisturbancemanagementapproaches into
threesubcategories. Thefirstone is tominimize theoveralldelaysat thenetwork level. Thesecond
one is theevaluationofdisturbancesbasedontheseverity,andthethirdone is toassumetheequal
importanceofeach incident.Anincrementalheuristicmethodhasbeencomparedwitha two-phase
heuristicapproach in [22].Ateachprocessingstep,partial resourceallocationandpartial scheduling
arerepeateduntil acompletesolution isgenerated. Ina two-phaseheuristicapproach, thealgorithm
creates theroutes forall the trainswithacomplete labellingprocedure inphaseone,andthensolves
theproblemwithanapproximationalgorithminphase two.
Theuseof taskparallelization to reducecomputation timewasexploredbyBettinelli et al. [23],
whoproposedaparallel algorithmfor the train schedulingproblem. Theproblem ismodelledbya
graph. Forconflictresolution,somedispatchingrulesareapplied.Thealgorithmsolvestheprobleminan
iterative,greedymanner,andtodecreasethecomputationaltime,thetasksareparallelized.Thealgorithm
enhancesthequalityof thesolutionsusingneighbourhoodsearchandtabusearch.Theneighbourhood
searchhasasignificant impactonthequalityofgeneratedsolutions,accordingtotheauthors.
Another interestingstudyofdifferentapproaches tovariableneighbourhoodsearchandquality
assessment is available in [24]. Local search techniquesarealsoused in [25],where theproblemis
modeledasahybrid job-shopschedulingproblem.
In [10], the train scheduling problem is formulated as a blocking parallel-machine job-shop
schedulingproblemandmodeledasanalternativegraph.Aheuristicalgorithm,referredtoas“the
feasibilitysatisfactionprocedure”, isproposedtoresolve theconflicts. Themodelattempts toconsider
train length,upgradingthe tracksections, increasingthe trains’ speedonthe identifiedtardysection
andshorteningthe local runtimeofeachtrainonbottlenecksections. Theapplicationwasdesigned
for the trainschedulingproblemandisnotconsideringre-scheduling. In thefirst step, theproblemis
solvedbyashiftingbottleneckalgorithmwithoutconsidering theblockingcondition. In thenext step,
theblockingcondition issatisfiedbyusinganalternativegraphmodel.
Khosravi et al. [9] also address the train scheduling and re-scheduling problem using a
job-shop scheduling problem formulation, and the problem is solved using a shifting bottleneck
approach. Decomposition is used to convert the problem into several single-machine problems.
Different variations of the method are considered for solving the single-machine problems.
Thealgorithmbenefits fromre-timingandre-orderingtrains,butnore-routingof trains isperformed.
99
back to the
book Algorithms for Scheduling Problems"
Algorithms for Scheduling Problems
- Title
- Algorithms for Scheduling Problems
- Authors
- Frank Werner
- Larysa Burtseva
- Yuri Sotskov
- Editor
- MDPI
- Location
- Basel
- Date
- 2018
- Language
- English
- License
- CC BY 4.0
- ISBN
- 978-3-03897-120-7
- Size
- 17.0 x 24.4 cm
- Pages
- 212
- Keywords
- Scheduling Problems in Logistics, Transport, Timetabling, Sports, Healthcare, Engineering, Energy Management
- Categories
- Informatik
- Technik