Page - 26 - in Algorithms for Scheduling Problems

Algorithms 2018,11, 66 whichhasanoptimalitysegment inanyfixedpermutationπk∈SduetoLemma2.Hence, theequality OB(πk,T)=∅musthold, if thecondition |Br|= |B∗r |≥2holds foreachblockBr∈B. Weassume that there exists a blockBr ∈ B such that all jobs are identical in the setB−r with |B−r | ≥ 2andall jobs are identical in the setB+r with |B+r | ≥ 2. Thus, for thepermutationπk ∈ S, theequalitiesminJi∈B−r p U i =maxJi∈B−r p U i andmaxJi∈B−r p L i =minJi∈B−r p L i hold. Since |B−r | ≥ 2and all jobsare identical in thesetB−r , there isno job Jv∈B−r ,whichhas theoptimalitysegment inany fixedpermutationπk∈S. Similarly, onecanprove that there isno job Jv∈B+r ,whichhas theoptimality segment inany fixedpermutationπk∈S. Thus,weconcludethat if theconditionofTheorem3holds foreachblock Br∈B, theneach job Ji∈J hasnooptimalitysegment inanyfixedpermutationπk∈S. Thus, if the conditionofTheorem3holds, theequalityOB(πk,T)=∅holds foranypermutationπk∈S. Necessity.Weprove thenecessitybyacontradiction.Weassumethatanypermutationπk∈ S has an empty optimality boxOB(πk,T) = ∅. Let the condition |Br| = |B∗r | ≥ 2 do not hold. If |Br|= |B∗r |= 1, the setBr is a singletonandso job Jr1 ∈ Br has theoptimality segment [pLr1,pUr1] withthe length pUr1−pLr1≥0 in thepermutationπk∗ ∈S,whereall jobsareorderedaccordingto the increasingof the leftboundsof thecoresof theirblocks. Let the followingconditionhold: |Br|> |B∗r |≥2. (1) Thecondition(1) implies that thereexistsat leastone left joborright jobor left-right job Jri ∈Br. If job Jri is a left job or a left-right job (a right job) in the blockBr, then job Jri must be locatedon thefirstplace (onthe lastplace, respectively) in theabovepermutationπk∗ ∈Samongall jobs from theblockBr. All jobs from the setBr\{B∗r ∪{Jri}}must be locatedbetween job Jrv ∈ B∗r and job Jrw ∈B∗r . Therefore, the left job Jri or the left-right job Jri (theright job Jri)has the followingoptimality segment [pLri,b L r ] (segment [bUr ,pUri ], respectively)with the lengthb L r −pLri>0 (the length pUri −bUr >0, respectively) in thepermutationπk∗. Let theequalityBr=B−r ∪B+r donothold. If thereexista job Jri ∈B∗r , this jobmustbe locatedbetweenthe jobs Jrv ∈B−r and Jrw ∈B−r . It is clear that the job Jri has theoptimalitysegment [bLr ,bUr ]withthe lengthbUr −bLr >0 in thepermutationπk∗. Let the followingconditionshold:Br=B−r ∪B+r , |B−r |≥2, |B+r |≥2.However,weassumethat jobs fromthesetB−r arenot identical. Thenthe job Jru ∈B−r with the largest segment [pLru,pUru]among the jobs fromthesetB−r mustbe located in thepermutationπk∗ beforeother jobs fromthesetB−r . It is clear that the job Jru has theoptimalitysegment in thepermutationπk∗. Similarly,wecanconstruct thepermutationπk∗withthenon-emptyoptimalitybox, if the jobs fromthesetB+r arenot identical. Let the equalityBr = B−r ∪B+r hold. Let all jobs in the setB−r (and all jobs in the setB+r ) be identical.However,weassumethat theequality |B−r |=1holds. The job Jri ∈B−r has theoptimality segment in thepermutationπk∗, if the job Jri is locatedbeforeother jobs in thesetBr. Similarly,onecanconstruct thepermutationπk∗ suchthat job Jri ∈B+r hastheoptimalitysegment in thepermutationπk∗, if the inequality |B+r |≥2 isviolated. Thus,weconclude that inall casesof the violatingof theconditionofTheorem3,wecanconstruct thepermutationπk∗ ∈Swith thenon-empty optimalityboxOB(πk∗,T) =∅. Thisconclusioncontradicts toourassumptionthatanypermutation πk∈ShasanemptyoptimalityboxOB(πk,T)=∅. Next, we present Algorithm 1 for constructing the optimality boxOB(πk,T) for the fixed permutation πk ∈ S. In steps 1–4 of Algorithm 1, the problem 1|p̂Li ≤ pi ≤ p̂Ui |∑Ci with the reducedsegmentsof the jobprocessing times is constructed. It is clear that theoptimalitybox for the permutation πk ∈ S for the problem1|pLi ≤ pi ≤ pUi |∑Ci coincideswith the optimality box for the samepermutation for theproblem1|p̂Li ≤ pi ≤ p̂Ui |∑Ci,wheregiven segments of the job processing times are reduced. In steps 5 and6, the optimality box for thepermutationπk for the problem1|p̂Li ≤ pi≤ p̂Ui |∑Ci is constructed. It takesO(n) timeforconstructing theoptimalitybox OB(πk,T) foranyfixedpermutationπk∈SusingAlgorithm1. 26