Page - 28 - in Algorithms for Scheduling Problems

Algorithms 2018,11, 66 in (3).Hence, theequalities (4)hold, if thereexistblocksBr∈Bwith theequalitiesBr=B−r ∪B+r and |Br|=2. Thissufficiencyproofcontains thedescriptionof Procedure2with thecomplexityO(n). Necessary. If thereexistsat leastoneblockBr∈B suchthatneithercondition |Br|= |B∗r |=1nor conditionBr=B−r ∪B+r , |Br|=2hold, thentheequality (3) isnotpossible forat leastone job Jki ∈Br. Therefore, the inequalityPerOB(πk,T)<nholds foranypermutationπk∈S. The lengthof the relativeperimeterPerOB(πk,T)maybeusedas a stabilitymeasure for the optimalpermutationπk. If thepermutationπk∈Shas thenon-emptyoptimalityboxOB(πk,T)with a larger lengthof therelativeperimeter thantheoptimalityboxOB(πt,T)has,πk =πt∈S, thenthe permutationπk∈Smayprovideasmallervalueof theobjective function∑Ci thanthepermutation πt. Onecanexpect that the inequality∑Ji∈JCi(πk,p)≤∑Ji∈JCi(πt,p)holds formorescenarios p fromthesetT thantheopposite inequality∑Ji∈JCi(πk,p)>∑Ji∈JCi(πt,p).Next,weshowhowto construct apermutationπk∈ Swith the largestvalueof the relativeperimeterPerOB(πk,T). The proofofTheorem4isbasedonProcedure3. Theorem5. If the equality B1 = J holds, then it takesO(n) time to find the permutation πk ∈ S and the optimality boxOB(πk,T)with the largest length of the relative perimeter PerOB(πk,T) among all permutationsS. Proof. SincetheequalityB1=J holds,eachpermutationπk∈S looksasfollows:πk=(Jk1, Jk2, . . . , Jkn), where {Jk1, Jk2, . . . , Jkn}= B1. Due toLemma2, only job Jk1 mayhave the optimality segment (this segment looksasfollows: [pLk1,u ∗ k1 ])andonly job Jnmayhavethefollowingoptimalitysegment [l∗kn,p U kn ]. Thelengthu∗k1−pLk1 of theoptimalitysegment [pLk1,u∗k1] for the job Jk1 isdeterminedbythesecondjob Jk2 in thepermutationπk. Similarly, the length p U kn − l∗kn of theoptimalitysegment [l∗kn,pUkn] for the job Jkn isdeterminedbythesecond-to-last job Jkn−1 in thepermutationπk.Hence, tofindtheoptimalitybox OB(πk,T)withthelargestvalueofPerOB(πk,T), it isneededtotestonlyfour jobs Jk1, Jk2, Jkn−1 and Jkn fromtheblockB1=J ,whichprovidethelargestrelativeoptimalitysegments for the jobs Jk1 and Jkn. To this end, we should choose the job Jki such that the following equality holds: pLki =minJks∈B1 bU1−pLks pUks−pLks . Then, ifB1\{Jki} =∅,we shouldchoose the job Jkv such that the equality pUkv =maxJks∈B1\{Jki} pUks−bL1 pUks−pLks holds. Then, ifB1\{Jki, Jkv} =∅,weshouldchoosethe job Jki+1 suchthat theequality pLki+1 =minJks∈B1\{Jki,Jkv}p L ks holds. Then, ifB1\{Jki, Jki+1, Jkv} =∅,weshouldchoose the job Jkv−1 suchthat theequality p U kv−1 =maxJks∈B1\{Jki,Jki+1,Jkv}p U ks holds. Thus, todetermine the largest valueofPerOB(πk,T), onehaseither to testasingle jobor to test two jobsor three jobsor tochoose andtest four jobs fromtheblockB1,where |B1|≥4, independentlyofhowlarge thecardinality |B1| of the setB1 is. In theworst case, onehas to test atmost 4!= 24permutationsof the jobs chosen fromthe setB1. Due to thedirect testingof the chosen jobs, one selects apermutationof |B1| jobs, whichprovides the largest lengthof therelativeperimeterPerOB(πk,T) forall |B1|! permutationsπk. IfB1=J , theabovealgorithm(wecall it Procedure3) forfindingthepermutationπkwiththe largest valueofPerOB(πk,T) takesO(n) time. Theorem5hasbeenproven. Remark2. If Ji ∈Br∈B, then the job Jimustbe located eitheron the left side fromthecoreof theblockBr or on the right side fromthis core inanypermutationπk having the largest relativeperimeter of the optimality boxOB(πk,T). Hence, job Ji mustprecede (or succeed, respectively) each job Jv∈ Bk. Thepermutationπt of the jobs fromtheblockBr obtainedusingProcedure3described in theproof ofTheorem5,where jobsBr are sequenced, remains the same if job Ji ∈Br∈Bisadded to thepermutationπt. Lemma4. Let there exist twoadjacent blocksBr∈BandBr+1∈B, such that the equalityBr⋂Br+1=∅ holds. Thentheproblem1|pLi ≤ pi≤ pUi |∑Ci canbedecomposed into the subproblemP1with the set of jobs J1 :=⋃rk=1Bk and the subproblemP2with the set of jobsJ2 :=⋃mk=r+1Bk =J \J1. The optimality box 28