Page - 101 - in Algorithms for Scheduling Problems

Algorithms 2018,11, 55 Table1.Thenotationsusedforsets, indices,parameters,andvariables. SetsandIndices Description M Setofall railwaysections (i.e.,machines). m The indexusedtodenoteaspecificsection in thesetM. Mm Thesub-setof tracksandplatformsthatbelongs tosectionm. (i.e.,parallelmachines) m,u Atrack/platform/resource instancenumberu fromasetMm. J Setofall trains (i.e., jobs). j The indexusedtodenoteaspecific train. O Setofall trainevents (i.e., operations). Oj Setofall events thatbelongto train j. Om Setofall events tobescheduledonasectionm. Om,u Setofall events tobescheduledontrackuofsectionm. i The indexusedtodenoteaspecific trainevent i. oj,i Thesymbolusedtodenote theevent iwhichbelongs to train j. 〈j, i,m,u〉 Tuplewhichrefers to train janditsevent iwhichoccurs insectionmandscheduledfortracku.Whenthesection issingle lineuwillbe ignored. (′) Primesymbolusedtodistinguishbetweentwoinstances (i.e., job jand j′ ). Parameters Description cm Therequiredminimumclear timethatmustpassaftera trainhasreleasedtheassigned trackuofsectionmandbeforeanother trainmayenter trackuofsectionm. hm Theminimumheadwaytimedistance that is requiredbetweentrains (head-headand tail-tail) that run insequenceonthesametrackuofsectionm. dj,i Theminimumrunningtime,ordwell time,ofevent i thatbelongs to train j. binitialj,i Thisparameterspecifies the initial starting timeofevent i thatbelongs to train j. einitialj,i Thisparameterspecifies the initial completiontimeofevent i thatbelongs to train j. psj,i Thisparameter indicates if event i includesaplannedstopat theassociatedsegment. Variables Description xbeginj,i There-scheduledstarting timeofevent i thatbelongs to train j. xendj,i There-scheduledcompletiontimeofevent i thatbelongs to train j . tj,i Thetardiness (i.e.,delay for train j tocompleteevent i ). zj,i Delayofevent i, i∈O, exceedingμ timeunits,which isset to threeminuteshere. qj,i,u Abinaryvariablewhich is1, if theevent iuses tracku. γj,i,j′,i′ Abinaryvariablewhich is1, if theevent ioccursbeforeevent i′. λj,i,j′,i′ Abinaryvariablewhich is1, if theevent i is rescheduledtooccurafterevent i′. bufj,i Remainingbuffer timefor train j tocompleteanevent 〈j, i〉. TFDj Thedelay for train jonce it reaches itsfinaldestination, i.e., tj,lastwhichcorresponds to the delaywhencompleting its lastevent. To solve the job-shop scheduling problem modelled by a graph, for every two conflicting operationsthealgorithmisresponsible fordeterminingthebestexecutionorder toreducetheobjective functionvalue.Apotential conflictoccurswhenfor twoeventsoj,i, andoj′,i′ belongingto jobs jand j′ respectively, the followingcriteriabecometrue: xbeginj,i < x begin j′,i′ and x end j′,i′ ≤ xbeginj,i +dj′,i′ (1) The algorithm is in charge of replacing the set of edges D with a subset of arcs D′, which defines theorder tobeservedbyaresource.Asaresult, thesetofedgesDwillbesubstitutedbya selected subset ofdirectedarcsD′, and themixedgraphG= (O,C,D)will be transformed intoa digraphG′=(O,C∪D′,∅). In thispaper,amulti-trackrailwaytrafficnetworkwillbeconsideredasa job-shopscheduling problemwithparallelmachines (hybrid job-shop)ateachstage. 4.AHeuristicAlgorithmforConflictResolutionintheMixedGraphG Whenadisturbanceoccurs,agraphGhastobegeneratedfromtheongoingandremainingevents for all the trainswithin thepredefined timehorizon. Later, thealgorithmhas to resolve the conflicts between trains affectedbydisturbance andpotential knock-oneffects. To resolve all the conflicts in 101