Seite - 119 - in Algorithms for Scheduling Problems

Algorithms 2018,11, 50 Theenumeration isorganizedbyshifting theoperationsof the lastorder to the left insuchaway that they trade theirplaceswithpreviouscompetingoperationsofprecedingorders (seeFigure3). Assoonastheoperationreaches its leftmost feasiblepositionandthecurrentcombinationcorresponds to a linear programming problem with no solution we roll back to the previous combination, stopshiftingoperationsof the lastorderandswitch to theoperationsof thepreviousorder.After the enumeration for orders on the current resource is over, we proceed the same iterationswith the next resource. Theformalpresentationof thedesignedbranch-and-boundalgorithmisdescribedby Procedure1. Procedure1: branch-and-bound 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 theresource r= |R| that isusedbylastoperation i= |J|of theprecedencegraphGof themanufacturingprocess. 5.Thebranch< i,r, f> isnowformulated. 6.Condition:Does theselectedresource rhavemorethanoneoperation inthemanufacturing procedure thatallocates it? 6.1. Ifyes then Beginevaluatingbranch< i,r, f> Shift theoperation ionecompetingpositionto the left Find the solution of theLPproblem (1)–(3) for current combination and calculate the objective functionΦ Condition: is thesolutionfeasible? If feasible then Condition: Is theobjective functionvalueΦbetter thantemporarilybest resultOpt? Ifyes then savecurrentsolutionas thenewbest resultOpt=Φ. Endofcondition Switch to the preceding operation i = i−1 of currently selected order f for the currentlyselectedresource r. Goto thep. 5andstartevaluatingthenewbranch Ifnot feasible then Stopevaluatingbranch< i,r, f> Switch to theprecedingresource r= r−1 Goto thep. 5andstartevaluatingthenewbranch Endofcondition: is thesolutionfeasible? Endofcondition: p. 6 7.Switchto theprecedingorder f= f−1 8.Repeatpp. 4–7untilnomorebranches< i,r, f>areavailable 9.Repeatpp. 3–8untilnomore feasibleshiftsarepossible foralloperations inallbranches. Iterating combinations for one order on one resource can be considered as evaluating one branchof thealgorithm[10]. Finding the leftmostposition for anoperation is similar todetecting a bound. Switching between branches and stopping on bounds is formalized with a general branch-and-boundprocedure. 119