Seite - 99 - in Algorithms for Scheduling Problems

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