Seite - 98 - in Algorithms for Scheduling Problems

Algorithms 2018,11, 55 Thesepreviouslyproposedapproacheshavedifferent strengthsand limitations,dependingon the intendedapplicationandcontext inmind. InSection2,weprovideamorecomprehensivesummary ofstate-of-the-artmethodsaddressingthisproblem. In thispaper,weproposeaheuristicapproachtosolve thereal-timetrain trafficre-scheduling problem. We view the problem as a blocking/no-wait, parallel-machine job-shop scheduling problem[3]. A jobcorresponds toa train’spathalongapre-determinedsequenceof tracksections (i.e.,machines). Eachpartof thatpathcorresponds toanoperation. “blocking/no-wait”constraint refers to that there isnopossibility tofinishanoperation if thenextoperationof thesame jobcannot get access to the requiredmachine forprocessing, i.e. there isno storage spacebetweenmachines that allows jobs and their current operation towait for anoccupiedmachine to becomeavailable. That is,whenanoperationofa job iscompleted, thenextoperationof that jobmust immediatelystart. Thiscorrespondsto the trainneedingatall times tohaveexplicitaccess toa tracksection(independent ofwhether the train ismoving orwaiting). This problem is heremodeled as a graph,where the graph is ahybridbetweenamixedgraphandanalternativegraph. Thebenefitofusingahybrid graphis thepossibilityof reducingthenumberof requiredcomputationswhenconstructingthegraph. Theproblemis thensolvedbyaheuristicalgorithm.Theproposedmixedgraphmodel isdiscussed in Section3,andtheproposedheuristicalgorithmispresented indetail inSection4. Theperformanceof theproposedapproach isassessed inanexperimental study,where theapproachhasbeenappliedto solveanumberofdisturbancescenarios foradensepartof theSwedishsouthernrailwaynetwork system.Theperformanceassessmentalso includesabenchmarkwiththecommercialoptimization softwareGurobi (v6.5.1),using thecorrespondingmixed integerprogramming(MIP)model (which is presented inAppendixA).Thisexperimental studyispresented inSection5. Section6presentssome conclusions fromtheexperimental studyandprovidespointers to futurework. 2.RelatedWork Szpigel [7]was, in 1973, oneof thepioneers, adapting the job-shopscheduling (JSS)problem formulationfor the trainschedulingproblem.Thiswas laterdevelopedbyotherresearcherssuchas D’Arianoetal. [8],Khosravietal. [9],LiuandKozan[10],MascisandPacciarelli [11], andOliveiraand Smith [12]. The JSSparadigmisalsoexplored in themixed-integer linearprogramming(MILP)approach proposedbyTörnquistKrasemannandPersson in2007 [13],where theprimaryfocuswasoncreating andevaluatingstrategies for reducingthesearchspaceviamodel re-formulations.Differentproblem formulations were experimentally evaluated in several disturbance scenarios occurring on a double-trackednetworkwith bi-directional traffic, and solvedby commercial software for a time horizonof60–90min. Theeffectivenessof theapproachandthedifferentstrategieswereshowntobe highlydependentonthesizeof theproblemandtypeofdisturbance. AheuristicapproachbasedonaMILPformulationwasalsoproposed in [14]. Atimehorizon of30 to60minwasdefinedfor testingthedisturbingscenarios. Thecommercial solverCPLEXwas usedtosolve theproblem,withanallowedcomputationtimeof180s. Significanteffortwasmadeto tunetheheuristicalgorithm,andtheresultswerecomparedwithexactones. Foruptoa40mintime horizon, thealgorithmgeneratedgoodresults. AMIPmodelwasalsoappliedonadouble-trackrailwaycorridor,where the focus ison local re-routing of trains to allow for bi-directional traffic and special constraints to respect the safety requirements [15]. Asalreadymentioned, thereal-timetrain trafficre-schedulingproblemisahardproblemtosolve. This isoftenaneffectof the largesolutionspace,whichmaybedifficult toefficientlynavigate indueto significantredundancy. That is,dependingontheproblemformulationandselectedobjectivefunction, particularly,optimizationsolversmayfindmultipleequallygoodsolutionsandalsohavedifficulties findingstrongbounds. Findingoptimal,ornear-optimal, solutionsmaythusbevery time-consuming. 98