Seite - 120 - in Algorithms for Scheduling Problems

Algorithms 2018,11, 50 Figure3.Permutationsofcompetingoperations inbranch-and-boundalgorithm. 2.3.2.Gradient-AlikeAlgorithm Theoppositeof thementionedaboveapproachwouldbesearchingfora localminimumamong all combinationswithagradientalgorithm[11].Here,wewill computeananalogueof thederivative that isusedtodefinethesearchdirectionateachpoint [12]. ‘Derivative’ foreachcompetingoperation is calculatedby trying to shift it byoneposition to the left. In case theobjective function reduces (or increases formaximization problems)we shift the operation to the leftwith the defined step (thestepratio ismeasured inanumberofpositionoperationskipsmoving to the left). The formal presentationof thedesignedgradient-alikealgorithmisdescribedbyProcedure2. Procedure2: gradientalgorithm 1.FindtheinitialsolutionoftheLPproblem (1)–(3)forthecombinationck∈{0,1},k=1,. . . ,K thatcorresponds to thecasewhenallordersare inarow(firstoperationof the followingorderstarts onlyafter the lastoperationofprecedingorder iscompleted). 2.Remember thesolutionandkeepthevalueofobjective functionΦas temporarilybest result Opt=Φ. 3.Select the lastorder f= |F|. 4.Select the resource r= |R| that isusedbyfirstoperation i= 1of thesequencegraphof the manufacturingprocess. 5. The current optimization variable for gradient optimization is selected—position of operation iof theorder f ontheresource r< i,r, f>. 6.Condition:Does theselectedresource rhavemorethanoneoperation inthemanufacturing procedure thatallocates it? 6.1. Ifyes then Beginoptimizingposition< i,r, f> 6.1.1.Set thestepofshifting theoperation tomaximum(shifting to the leftmostposition). D(i,r, f)=max 6.1.2.Findthe ‘derivative’ofshifting theoperation i to the left Shift theoperation ionepositionto the left Find thesolutionof theLPproblem (1)–(3) forcurrentcombinationandcalculate the objective functionΦ ConditionA: is thesolutionfeasible? If feasible then ConditionB: Is theobjectivefunctionvalueΦbetter thantemporarilybest resultOpt? Ifyes then Wefoundtheoptimizationdirectionforposition< i,r, f>,proceedtop. 6.1.3 Ifnot then 120