Seite - 35 - in Algorithms for Scheduling Problems

Algorithms 2018,11, 66 optimalitybox(Section3),wepropose the followingAlgorithm3forconstructing the jobpermutation πk∈S for theproblem1|pLi ≤ pi≤ pUi |∑Ci,whoseoptimalityboxOB(πk,T)provides theminimal valueof theerror functionF(πk,T)amongallpermutationsS. Algorithm3 Input: Segments [pLi ,p U i ] for the jobs Ji∈J . Output: Thepermutationπk∈SandoptimalityboxOB(πk,T),whichprovide theminimalvalueof theerror functionF(πk,T). Step1: IF theconditionofTheorem3holds THENOB(πk,T)=∅ foranypermutationπk∈S andtheequalityF(πk,T)= n(n+1) 2 holdsSTOP. Step2: IF theconditionofTheorem4holds THENusingProcedure2+F(πk,T)construct thepermutationπk∈S suchthatbothequalities PerOB(πk,T)=nandF(πk,T)=0holdSTOP. Step3:ELSEdetermine thesetBofallblocksusingthe O(n logn)-Procedure1described in theproofofLemma1 Step4: IndextheblocksB={B1.B2, . . . ,Bm}accordingto increasing leftboundsof theircores (Lemma3) Step5: IFJ =B1THENproblem1|pLi ≤ pi≤ pUi |∑Ci is calledproblemP1 (Theorem5)set i=0GOTOstep8ELSEset i=1 Step6: IF thereexist twoadjacentblocksBr∗ ∈BandBr∗+1∈B such thatBr∗ ∩Br∗+1=∅; let rdenote theminimumof theabove index r∗ in theset{1,2, . . . ,m}THENdecompose theproblemP into subproblemP1with thesetof jobsJ1=∪rk=1Bk andsubproblemP2 with thesetof jobsJ2=∪mk=r+1BkusingLemma4; setP=P1,J =J1,B={B1,B2, . . . ,Br}GOTOstep7ELSE Step7: IFB ={B1}THENGOTOstep9ELSE Step8:Construct thepermutationπs(i)withtheminimalvalueof theerror functionF(πk,T)usingProcedure3+F(πk,t) IF i=0orJ2=BmGOTOstep12ELSE Step9: IF thereexistsablock in thesetBcontainingmore thanone non-fixed jobsTHENconstruct thepermutationπs(i)with theminimalvalueof theerror functionF(πk,T) for theproblemP1 usingProcedure5+F(πk,t)GOTOstep11 Step10:ELSEconstruct thepermutationπs(i)withtheminimalvalueof the error functionF(πk,T) for theproblemP1 usingProcedure3+F(πk,t) Step11:Construct theoptimalityboxOB(πs(i),T) for thepermutationπs(i) usingAlgorithm1 IFJ2 =Bm and i≥1THEN set i := i+1,P=P2,J =J2,B={Br+1,Br+2, . . . ,Bm} GOTOstep6ELSEIFJ2=BmTHENGOTOstep8 Step12: IF i>0THENsetv= i,determine thepermutation πk=(π s(1),πs(2), . . . ,πs(v))andtheoptimalitybox: OB(πk,T)=×i∈{1,2,...,v}OB(πs(i),T)GOTOstep13 ELSEOB(πk,T)=OB(πs(0),T) Step13:TheoptimalityboxOB(πk,T)has theminimalvalue of theerror functionF(πk,T)STOP. InSection6,wedescribe theresultsof thecomputationalexperimentsonapplyingAlgorithm3 to therandomlygeneratedproblems1|pLi ≤ pi≤ pUi |∑Ci . 6.ComputationalResults For thebenchmark instances1|pLi ≤ pi≤ pUi |∑Ci,where therearenopropertiesof therandomly generated jobsJ , whichmake theproblemharder, themid-point permutationπmid−p = πe ∈ S, whereall jobs Ji∈J areorderedaccordingtothe increasingof themid-points p U i +p L i 2 of theirsegments [pLi ,p U i ], isoftenclose to theoptimalpermutation. Inourcomputationalexperiments,wetestedseven 35