Page - 27 - in Algorithms for Scheduling Problems

Algorithms 2018,11, 66 Algorithm1 Input: Segments [pLi ,p U i ] for the jobs Ji∈J . Thepermutationπk=(Jk1, Jk2, . . . , Jkn). Output: TheoptimalityboxOB(πk,T) for thepermutationπk∈S. Step1:FOR i=1 tonDOset p̂Li = p L i , p̂ U i = p U i ENDFOR set tL= p̂L1, tU= p̂ U n Step2:FOR i=2 tonDO IF p̂Li < tLTHENset p̂ L i = tLELSEset tL= p̂ L i ENDFOR Step3:FOR i=n−1 to1STEP−1DO IF p̂Ui > tU THENset p̂ U i = tU ELSEset tU= p̂ U i ENDFOR Step4:Set p̂U0 = p̂ L 1, p̂ L n+1= p̂ U n . Step5:FOR i=1 tonDOset d̂−ki =max { p̂kLi , p̂ U ki−1 } , d̂+ki =min { p̂Uki , p̂kLi+1 } ENDFOR Step6:SetOB(πk,T)=×d̂−i ≤d̂+i [ d̂−ki , d̂ + ki ] STOP. 3.3. TheLargestRelativePerimeterof theOptimalityBox If the permutation πk ∈ S has the non-empty optimality boxOB(πk,T) = ∅, then one can calculate the lengthof therelativeperimeterof thisboxas follows: PerOB(πk,T)= ∑ Jki∈J(πk) u∗ki− l∗ki pUki−pLki , (2) whereJ(πk)denotes thesetofall jobs Ji∈J havingoptimalitysegments [l∗ki,u∗ki]withthepositive lengths, l∗ki<u ∗ ki , in thepermutationπk. It is clear that the inequality l∗ki<u ∗ ki mayholdonly if the inequalitypLki< p U ki holds. Theorem3givesthesufficientandnecessaryconditionforthesmallestvalue ofPerOB(πk,T), i.e., the equalitiesJ(πk) =∅ andPerOB(πk,T) = 0hold for eachpermutation πk ∈ S. Anecessaryandsufficient condition for the largestvalueofPerOB(πk,T) = n is given in Theorem4. ThesufficiencyproofofTheorem4isbasedonProcedure2. Theorem4. For theproblem1|pLi ≤ pi≤ pUi |∑Ci, there exists apermutationπk∈S, forwhich the equality PerOB(πk,T)=nholds, if andonly if for eachblockBr∈B, either |Br|= |B∗r |=1orBr=B−r ∪B+r with |Br|=2. Proof. Sufficiency. Let the equalities |Br|= |B∗r |= 1hold for eachblockBr ∈ B. Therefore, both equalities Br = B∗r and |B|= nhold. Due toTheorem2 andLemma3, all jobsmust be ordered with the increasingof the left boundsof the coresof theirblocks ineachpermutationπk ∈ S such thatOB(πk,T) =∅. Each job Jki ∈J in thepermutationπk = (Jk1, Jk2, . . . , Jkn)has theoptimality segments [l∗ki,u ∗ ki ]withthemaximalpossible length u∗ki− l∗ki = pUki−pLki. (3) Hence, thedesiredequalities PerOB(πk,T)= ∑ Jki∈J(πk) pUki−pLki pUki−pLki =n (4) hold, if theequalities |Br|= |B∗r |=1holdforeachblockBr∈B. Let thereexistablockBr∈B suchthat theequalitiesBr=B−r ∪B+r and |Br|=2hold. It is clear that theequalities |B−r |= |B+r |=1holdaswell, and job Jki fromthesetB−r (fromthesetB+r ) in the permutationπkhas theoptimality segments [l∗ki,u ∗ ki ]with themaximalpossible lengthdetermined 27