Page - 25 - in Algorithms for Scheduling Problems

Algorithms 2018,11, 66 Lemma2. Atmost two jobs in the blockBr∈Bmayhave thenon-emptyoptimality segments inanyfixed permutationπk∈S. Proof. DuetoDefinition3, the inclusion [bLr ,bUr ]⊆ [pLi ,pUi ]holds foreach job Ji∈Br. Thus,due to Definition2,only job Jki,which is thefirstone in thepermutationπk amongthe jobs fromtheblock Br, andonly job Jkv ∈Br,which is the lastone in thepermutationπk amongthe jobs fromtheblock Br,mayhavethenon-emptyoptimalitysegments. It is clear that thesenon-emptysegments lookas follows: [pLki,u ∗ ki ]and [l∗kv,p U kv ],whereu∗ki ≤ bLr andbUr ≤ l∗kv. Lemma3. IfOB(πk,T) =∅, then any two jobs Jv ∈ Br and Jw ∈ Bs,which are fixed indifferent blocks, r< s,mustbeordered in thepermutationπk∈Swith the increasingof the left bounds (and the rightbounds aswell) of the coresof theirblocks, i.e., thepermutationπk looksas follows:πk=(. . . , Jv, . . . , Jw, . . .),where bLr < bLs . Proof. For any two jobs Jv ∈ Br and Jw ∈ Bs, r< s, the condition [pLv,pUv ]∩ [pLw,pUw] = ∅holds. Therefore, thesamepermutationπk=(. . . , Jv, . . . , Jw, . . .) isobtainedif jobs Jv∈Br and Jw∈Bs are orderedeither in the increasingof the leftboundsof thecoresof theirblocksor in the increasingof therightboundsof thecoresof theirblocks.WeproveLemma3byacontradiction. Let thecondition OB(πk,T) =∅hold.However,weassumethat therearefixed jobs Jv∈Br and Jw∈Bs, r< s,which are located inthepermutationπk∈S in thedecreasingorderof the leftboundsof thecoresof their blocksBr andBs.Note thatblocksBr andBs cannotbevirtual. Due toourassumption, thepermutationπk looksas follows: πk = (. . . , Jw, . . . , Jv, . . .),where bLr < bLs . UsingDefinition3,onecanconvince that thecoresofanytwoblockshavenocommonpoint. Thus, the inequalitybLr < bLs implies the inequalitybUr < bLs . The inequalities pLv ≤ pv≤ bUr < bLs ≤ pLw≤ pwholdforanyfeasibleprocessingtime pv andanyfeasibleprocessingtime pw,where p∈T. Hence, the inequality pv< pwholdsaswell, andduetoTheorem1, thepermutationπk∈Scannot beoptimal foranyfixedscenario p∈T. Thus, theequalityOB(πk,T)=∅holdsduetoDefinition2. Thiscontradictionwithourassumptioncompletes theproof. Next, we assume that blocks in the set B = {B1,B2, . . . ,Bm} are numbered according to the increasing of the left bounds of their cores, i.e., the inequality bLv < bLu implies v < u. Due to Definition3,eachblockBr={Jr1, Jr2, . . . , Jr|Br|}mayincludejobsofthefollowingfourtypes. IfpLri = bLr and pUri = b U r ,we say that job Jri is a core job in theblockBr. LetB ∗ r bea set of all core jobs in the blockBr. If pLri< b L r ,wesaythat job Jri isa left job in theblockBr. If p U ri > b U r ,wesaythat job Jri isa right job in theblockBr. LetB−r (B+r )beasetofall left (right) jobs in theblockBr.Note that some job Jri ∈Brmaybe left-right job in theblockBr, since it ispossible thatB\{B∗r∪B−r ∪B+r } =∅. Twojobs Jv and Jw are identical ifbothequalities pLv = pLw and pUv = pUw hold.Obviously, if the setBr∈B is a singleton, |Br|= 1, then theequalityBr=B∗r holds. Furthermore, the latterequality cannotholdforavirtualblockBt∈B sinceanytrivialblockmustcontainat least twonon-fixed jobs. Theorem3. For theproblem1|pLi ≤ pi≤ pUi |∑Ci, anypermutationπk∈ Shasanemptyoptimality box OB(πk,T)=∅, if andonly if for eachblockBr∈B,eithercondition |Br|= |B∗r |≥2holdsorBr=B−r ∪B+r , all jobs in the setB−r (in the setB+r ) are identical and the following inequalitieshold: |B−r |≥2and |B+r |≥2. Proof. Sufficiency. It is easy to prove that there is no virtual block in the considered set B. First, weassumethat foreachblockBr∈B, thecondition |Br|= |B∗r |≥2holds. DuetoLemma3, in thepermutationπk∈Swiththenon-emptyoptimalityboxOB(πk,T) =∅, all jobs must be located in the increasing order of the left bounds of the cores of their blocks. However, in the permutation πk ∈ S, the following two equalities hold for each block Br ∈ B: minJi∈Br p U i =maxJi∈Br p U i andmaxJi∈Br p L i =minJi∈Br p L i . Since |Br| ≥ 2, there is no job Jv ∈ Br, 25