Seite - 103 - in Algorithms for Scheduling Problems

Algorithms 2018,11, 55 Algorithm1.Thepseudocodeforconflict resolutionstrategy HeuristicAlgorithmforConflictResolutionintheMixedGraphG Require: TheweightedmixedgraphG=(O,C,D); candidList =findNeighbours(os); current=findMinimumReleaseTime(candidList); while (current =od); checkList = findConflictOperations(current.machineNumber); if(conflictExist(current, checkList)) /*local re-routing*/ vt = minimumVacantTrack(current.machineNumber); modifyGraph(G, current, vt); checkList = findConflictOperations(vt); end_if for(node cl: checkList) /*conflict resolution, re-timing, re-ordering*/ a,b = findBestOrder(current, cl); if (notreachable(b, a)) addArc(a, b); updateData(G,a); else_if(not reachable(a,b)) addArc(b, a); updateData(G,b); else checkFeasibility(G); end_if end_if end_for candidList += findNeighbours(current); candidList -= current; current = findMinimumReleaseTime(candidList); end_while Table2.Descriptionofdispatchingrulesusedforconflict resolution. ConflictResolution Strategy Description 1.Minimumrelease time goesfirst Thetrainwith theearliest initial start time(binitialj,i )goesfirst ifnodeadlockoccurs. 2.Moredelaygoesfirst If there isaconflictbetweentwotrains, theonewith the largest tardiness (delay)goesfirst. The tardiness iscalculatedas tj,i=Max ( 0,xbeginj,i −binitialj,i ) . 3. Less realbuffer timegoes first The trainwith thesmallestbuffer timegoesfirst. Buffer time isdefinedasasubtractionof initial endingtimeandrealfinishingtime ( bufj,i= einitialj,i − ( xbeginj,i +dj,i )) for two operations tobescheduledonthesame,occupiedmachine. 4. Lessprogrammedbuffer timegoesfirst Thetrainwithsmallestbuffer timegoesfirst. Buffer timeisdefinedasasubtractionof initial endingtimeandprogrammedendingtime ( bufj,i= einitialj,i − ( binitialj,i +dj,i )) for twooperations tobescheduledonthesame,occupiedmachine. 5. Less totalbuffergoes first Thetrainwithsmallest totalbuffer timegoesfirst. Totalbuffer timeisdefinedasa summationofprogrammedbuffer timesuntil thedestinationpoint for the trains, i.e., ( last ∑ k=i bufj,k ) . 6. Less totalprocessing time Thetrainwithsmallest runningtimetoget to thedestinationgoesfirst (i.e., theminimum totalprocessingtime). The totalprocessingtimeisdefinedasasummationof required timetopasseachsection, fora train, i.e., ( last ∑ k=i dj,k ) . Figures1and2 illustrate thedifferencebetweenthemixedgraphandalternativegraphmodels for conflict resolution. Thereare twoconflicting trains in thesamepathon thesectionsm1 andm2. 103