Seite - 121 - in Algorithms for Scheduling Problems

Algorithms 2018,11, 50 Nooptimizationdirectionfor thecurrentposition< i,r, f> stopoptimizingposition< i,r, f> switch to thenextoperation i= i+1 gotop6andrepeatsearchforposition< i+1,r, f> EndofconditionB Ifnot feasible then Nooptimizationdirectionfor thecurrentposition< i,r, f> stopoptimizingposition< i,r, f> switch to thenextoperation i= i+1 gotop6andrepeatsearchforposition< i+1,r, f> EndofconditionA 6.1.3.Definethemaximumpossibleoptimizationstep for thecurrentposition< i,r, f>, initial stepvalueD(i,r, f)=max Shift theoperation i leftusingthestepD(i,r, f). Find thesolutionof theLPproblem (1)–(3) forcurrentcombinationandcalculate the objective functionΦ Condition C: Is the solution feasible and objective function value Φ better than temporarilybest resultOpt? Ifyes then savecurrentsolutionas thenewbest resultOpt=Φ stopoptimizingposition< i,r, f> switch to thenextoperation i= i+1 gotop6andrepeatsearchforposition< i+1,r, f> Ifnot then reduce thesteptwiceD(i,r, f)= D(i,r,f)2 andrepeatoperationsstartingfromp. 6.1.3 EndofconditionC Switchto thenextoperation i= i+1,go top. 6andoptimizeposition< i,r, f> 7.Switchto theprecedingresource r= r−1 8.Repeatpp. 5–7 forcurrentlyselectedresource< i,r−1, f> 9.Switchto theprecedingorder f= f−1 10.Repeatpp. 4–9 forcurrentlyselectedorder< i,r, f−1>. 11.Repeatpp. 3–10untilnoimprovementsand/ornomore feasiblesolutionsexist. Theoptimizationvariables ingradientalgorithmrepresentpositionsofall competingoperations relative to eachother. Themaximumoptimization step for each iteration isdetectedon-the-flyby tryingtoshift thecurrentoperationto the leftmostposition(as it is showninFigure4) that showsthe LPproblem(1)–(3) is solvableandtheobjective function is improved. Figure4.Permutationsofcompetingoperations ingradientalgorithm. 121