Seite - 29 - in Algorithms for Scheduling Problems

Algorithms 2018,11, 66 OB(πk,T)with the largest length of the relative perimetermaybe obtained as theCartesianproduct of the optimalityboxes constructed for the subproblemsP1 andP2. Proof. Since theblocksBr andBr+1 haveno common jobs, the inequality pUu < pLv holds for each pair of jobs Ju ∈⋃rk=1Bk and Jv ∈⋃mk=r+1Bk. Due toTheorem2, any job Ju ∈⋃rk=1Bk dominates any job Jv ∈⋃mk=r+1Bk. Thus, due toDefinition1, there is nooptimalpermutationπk ∈ S for the instance1|p|∑Ciwithascenario p∈T suchthat job Jvprecedes job Ju in thepermutationπk. Dueto Definition2,anon-emptyoptimalityboxOB(πk,T) ispossibleonly if job Ju is locatedbefore job Jv in thepermutationπr. TheoptimalityboxOB(πk,T)with the largest relativeperimeter for theproblem 1|pLi ≤ pi≤ pUi |∑CimaybeobtainedastheCartesianproductof theoptimalityboxeswiththe largest lengthof the relativeperimeters constructed for the subproblemsP1 andP2,where the set of jobs⋃r k=1Bk andthesetof jobs ⋃m k=r+1Bk areconsideredseparatelyonefromanother. LetB∗denoteasubsetofallblocksof thesetB,whichcontainonlyfixed jobs. LetJ∗denotea setofallnon-fixed jobs in thesetJ . Let thesetB(Ju)⊆B∗denoteasetofallblockscontaining the non-fixed job Ju∈J∗. Theorem5,Lemma6andtheconstructiveproofof the followingclaimallows us todevelopanO(n logn)-algorithmforconstructingthepermutationπkwiththe largestvalueof PerOB(πk,T) for the special caseof theproblem1|pLi ≤ pi ≤ pUi |∑Ci. TheproofofTheorem6 is basedonProcedure4. Theorem6. Let eachblockBr∈Bcontainatmost onenon-fixed job. Thepermutationπk∈Swith the largest valueof the relativeperimeterPerOB(πk,T) is constructed inO(n logn) time. Proof. There isnovirtualblock in thesetB, sinceanyvirtualblockcontainsat least twonon-fixed jobs while each block Br ∈ B contains at most one non-fixed job for the considered problem 1|pLi ≤ pi≤ pUi |∑Ci. UsingO(n logn)-Procedure1describedin theproofofLemma1,weconstruct thesetB={B1,B2, . . . ,Bm}ofallblocks.UsingLemma3,weorderthejobsinthesetJ \J∗according to the increasingof the leftboundsof thecoresof theirblocks.Asaresult, alln−|J∗| jobsare linearly orderedsinceall jobsJ \J∗ arefixed in theirblocks. Suchanorderingof the jobs takesO(n logn) timeduetoLemma1. Since each block Br ∈ B contain at most one non-fixed job, the equality B(Ju)∩B(Jv)=∅ holds for each pair of jobs Ju ∈ B(Ju) ⊆ B \B∗ and Jv ∈ B(Jv) ⊆ B \B∗, u = v. Furthermore, theproblem1|pLi ≤ pi≤ pUi |∑Cimaybedecomposedintoh= |J∗|+ |B∗|subproblems P1,P2,. . . ,P|J∗|,P|J∗|+1,. . . ,Ph such that the condition of Lemma 4 holds for each pair Pr and Pr+1 of the adjacent subproblems, where 1 ≤ r ≤ h−1. Using Lemma4,wedecompose the problem 1|pLi ≤ pi≤ pUi |∑Ci intohsubproblems{P1,P2,. . . ,P|J∗|,P|J∗|+1,. . . ,Ph}=P. ThesetP ispartitioned into twosubsets,P=P1∪P2,where thesubsetP1= {P1,P2,. . . ,P|J∗|}containsall subproblemsPf containingallblocksfromthesetB(Jif),where Jif ∈J∗and |P1|= |J∗|. ThesubsetP2={P|J∗|+1, . . . ,Ph} containsall subproblemsPd containingoneblockBrd fromthe setB∗, |P2|= |B∗|. If subproblemPdbelongs to thesetP2, thenusingO(n)-Procedure3described in theproofofTheorem5,weconstruct theoptimalityboxOB(π(d),T(d))withthe largest lengthof the relativeperimeter for thesubproblemPd,whereπ(d)denotes thepermutationof the jobsBrd ⊂B∗ and T(d)⊂T. It takesO(|Brd|) timetoconstructasuchoptimalityboxOB(π(d),T(d)). If subproblem Pf belongs to the setP1, it is necessary to consider all |B(Jjf)| fixings of the job Jif in theblockBfj fromthe setB(Jjf) = {Bf1,Bf2, . . . ,Bf|B(Jjf )|}. Thus,wehave to solve |B(Jjf)| subproblemsPgf ,where job Jif isfixed in theblockBfg ∈ B(Jjf)and job Jif isdeleted fromallother blocksB(Jjf)\{Bfg}.WeapplyProcedure3forconstructingtheoptimalityboxOB(π(g),T(f))with the largest length of the relative perimeterPerOB(π(g),T(f)) for each subproblemPgf , where g ∈ {1,2, . . . , |B(Jjf)|}. Then,wehave tochoose the largest lengthof therelativeperimeteramong |B(Jif)| constructedones:PerOB(π(f∗),T(f))=maxg∈{1,2,...,|B(Jjf )|}PerOB(π (g),T(f)). 29