Seite - 31 - in Algorithms for Scheduling Problems

Algorithms 2018,11, 66 Algorithm2 Step9: IF thereexistsablock in thesetBcontainingmore thanone non-fixed jobsTHENconstruct thepermutationπs(i)withthe largest relativeperimeterPerOB(πs(i),T) for theproblemP1 usingProcedure5described inSection4.1GOTOstep11 Step10:ELSEconstruct thepermutationπs(i)withthe largest relative perimeterPerOB(πs(i),T) for theproblemP1 using O(n logn)-Procedure4described in theproofofTheorem6 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 the largestvalueof PerOB(πk,T)STOP. 4.1. Procedure5 for theProblem1|pLi ≤ pi≤ pUi |∑Ci withBlocks IncludingMoreThanOneNon-Fixed Jobs ForsolvingtheproblemP1 at step9of theAlgorithm2,weuseProcedure5basedondynamic programming. Procedure5allowsus to construct thepermutationπk ∈ S for theproblem1|pLi ≤ pi≤ pUi |∑Ciwith the largestvalueofPerOB(πk,T),where thesetBconsistsofmore thanoneblock, m≥2, theconditionofLemma4doesnotholdfor the jobsJ ={J1, J2, . . . , Jn}=:J(B0m),whereB0m denotes the followingsetofblocks: {B1,B2, . . . ,Bm}=:B0m. Moreover, theconditionofTheorem6 doeshold for the setB=B0m of theblocks, i.e., there is ablockBr ∈B0m containingmore thanone non-fixed jobs. For theproblem1|pLi ≤ pi ≤ pUi |∑Ci withJ = {J1, J2, . . . , Jn}=J(B0m), one can calculate the followingtightupperboundPermaxonthe lengthof therelativeperimeterPerOB(πk,T) of theoptimalityboxOB(πk,T): Permax=2 · |B\B|+ |B|≥PerOB(πk,T), (5) whereBdenotes thesetofallblocksBr∈Bwhicharesingletons, |Br|=1. Theupperbound(5)onthe relativeperimeterPerOB(πk,T)holds, since therelativeoptimalitysegment u∗ki−l ∗ ki pUki −pLki forany job Ji∈J isnotgreater thanone. Thus, thesumof therelativeoptimalitysegments forall jobs Ji∈J cannotbe greater than2m. InsteadofdescribingProcedure5 ina formalway,wenextdescribe thefirst two iterationsof Procedure5alongwith theapplicationofProcedure5 toasmallexamplewith fourblocksandthree non-fixed jobs (seeSection4.2). LetT =(V,E)denote thesolution treeconstructedbyProcedure5at the last iteration,whereV isasetof thevertexespresentingstatesof thesolutionprocessandE isaset of theedgespresentingtransformationsof thestates toanotherones.Asubgraphof thesolutiontree T =(V,E)constructedat the iterationh isdenotedbyTh=(Vh,Eh). Allvertexes i∈Vof thesolution treehavetheirranksfromtheset{0,1, . . . ,m= |B|}. Thevertex0inthesolutiontreeTh=(Vh,Eh)has azerorank. Thevertex0 ischaracterizedbyapartial jobpermutationπ0(∅;∅),where thenon-fixed jobsarenotdistributedto theirblocks. Allvertexesof thesolution treeThhavingthefirst rankaregeneratedat iteration1 fromvertex0 viadistributing thenon-fixed jobsJ [B1]of theblockB1,whereJ [B1]⊆B1. Each job Jv∈J [B1]must bedistributedeither to theblockB1 or toanotherblockBj∈Bwiththe inclusion Jv∈J [Bj]. LetBtk denoteasetofallnon-fixed jobs Ji∈Bk,whicharenotdistributedto theirblocksat the iterationswith thenumbers less than t. Apartialpermutationof the jobs is characterizedbythenotationπu(Bk;J[u]), whereudenotes thevertexu∈Vt in theconstructedsolutiontreeTt=(Vt,Et)andJ[u]denotes the 31