Seite - 30 - in Algorithms for Scheduling Problems

Algorithms 2018,11, 66 Due to Lemma 4, the optimality box OB(πk,T) with the largest relative perimeter for the originalproblem1|pLi ≤ pi≤ pUi |∑Ci isdeterminedas theCartesianproductof theoptimalityboxes OB(π(d),T(d))andOB(π(f∗),T(f))constructedforthesubproblemsPd∈P2 andPf ∈P1, respectively. The following equality holds:OB(πk,T)=×Pf∈P1OB(π(f ∗),T(f))×(×Pd∈P2OB(π(d),T(d))). Thepermutationπkwiththelargest lengthof therelativeperimeterof theoptimalityboxOB(πk,T) for theproblem1|pLi ≤ pi≤ pUi |∑Ci isdeterminedastheconcatenationof thecorrespondingpermutations π(f ∗)andπ(d).Usingthecomplexitiesof theProcedures1and3,weconcludethat thetotalcomplexityof thedescribedalgorithm(wecall itProcedure4)canbeestimatedbyO(nlogn). Lemma5. Within constructing a permutation πk with the largest relative perimeter of the optimality box OB(πk,T), any job Jimaybemovedonlywithin theblocksB(Ji). Proof. Let job Ji be located in the block Br in the permutation πk such that Ji ∈ Br. Then, either the inequality pLv > pUi or the inequality p U v < pLi holds for each job Jv ∈ Br. If pLv > pUi , job Ju dominates job Ji (duetoTheorem2). If pUv < pLi , job Jidominates job Ju.Hence, if job Ji is located in thepermutationπkbetween jobs Jv∈Br and Jw∈Br, thenOB(πk,T)=∅duetoDefinition2. DuetoLemma5, if job Ji isfixedin theblockBk∈B (or isnon-fixedbutdistributedto theblock Bk∈B), then job Ji is locatedwithin the jobs fromtheblockBk inanypermutationπkwith the largest relativeperimeterof theoptimalityboxOB(πk,T). 4.AnAlgorithmforConstructingaJobPermutationwiththeLargestRelativePerimeterof the OptimalityBox Basedonthepropertiesof theoptimalitybox,wenextdevelopAlgorithm2forconstructingthe permutationπk for theproblem1|pLi ≤ pi≤ pUi |∑Ci,whoseoptimalityboxOB(πk,T)has the largest relativeperimeteramongallpermutations in thesetS. Algorithm2 Input: Segments [pLi ,p U i ] for the jobs Ji∈J . Output: Thepermutationπk∈Swiththe largest relativeperimeterPerOB(πk,T). Step1: IF theconditionofTheorem3holds THENOB(πk,T)=∅ foranypermutationπk∈SSTOP. Step2: IF theconditionofTheorem4holds THENconstruct thepermutationπk∈S suchthatPerOB(πk,T)=n usingProcedure2described in theproofofTheorem4STOP. 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)withthe largest relativeperimeter PerOB(πs(i),T)usingProcedure3described in theproofof Theorem5 IF i=0orJ2=BmGOTOstep12ELSE 30