Page - 32 - in Algorithms for Scheduling Problems

Algorithms 2018,11, 66 non-fixed jobs fromthe setJ [Bk],whicharedistributed to theblockBk in thevertex j∈Vt of the solutiontreesuchthat thearc (j,u)belongs to thesetEt. At the first iteration of Procedure 5, the setP(J [B11]) = {J [B11], . . . ,∅} of all subsets of the setJ [B11] is constructed and 2|J [B 1 1]| partial permutations are generated for all subsetsP(J [B11]) of the non-fixed jobsJ [B11]. The constructed solution tree T1 = (V1,E1) consists of the vertexes 0,1, . . . ,2|J [B11]| and2|J [B11]| arcs connectingvertex0with theothervertexes in the treeT1. Foreach generated permutation πu(Bk;J[u]), whereJ[u] ∈ P(J [Blk]), the penalty φu determined in (6) is calculated, which is equal to the difference between the lengths of themaximal possible relative perimeterPermax of theoptimalityboxOB(πk,T) and the relativeperimeter of theoptimalitybox OB(πu(Bk;J[u]),T),whichmaybeconstructedfor thepermutationπu(Bk;J[u]): PerOB(πu(Bk;J[u]),T)=∑ i≤k Perumax−φu, (6) wherePerumaxdenotes themaximal lengthof therelativeperimeterof thepermutationπu(Bk;J[u]),T). Thepenaltyφu iscalculatedusingO(n)-Procedure3describedintheproofofTheorem5.Thecomplete permutation π0→u(Bk;J[u])with the end πu(Bk;J[u]) is determined based on the permutations πs(Bc;J[s]), where each vertex s belongs to the chain (0 → u) between vertexes 0 and u in the solution treeTt=(Vt,Et)andeachblockBcbelongs to thesetBu={B1,B2, . . . ,Bk}. Thepermutation π0→u(Bk;J[u]) includesall jobs,whicharefixed in theblocksBc∈Buordistributed to theirblocks Bc∈Bu in theoptimalorder for thepenaltyφu. TheaimofProcedure5 is toconstructacomplete jobpermutationπ f(Bm;J[f])=πk∈S such that thepenaltyφf isminimal forall jobpermutations fromthesetS.At thenext iteration,apartial permutationπs(B2;J[s]) ischosenfromtheconstructedsolutiontreesuchthatthepenaltyφs isminimal amongthepermutationscorrespondingto the leafsof theconstructedsolutiontree. At the second iteration, the setP(J [B22]) = {J [B22], . . . ,∅} of all subsets of the setJ [B22] is generated and 2|J [B22]| permutations for all subsetsP(J [B22]) of the jobs from the block B2 are constructed. For each generated permutation πv(B22;J[v]), whereJ[v] ∈ P(J [B22]), the penalty φv is calculated using the equality φv = φl+Δφk, where the edge [l,v] belongs to the solution treeT2=(V2,E2)andΔφk denotes thepenalty reached for theoptimalpermutationπ0→v(B2;J[v]) constructedfromthepermutationπv(B1;J[v])usingO(n)-Procedure3. For theconsiderationat the next iteration,onechooses thepartialpermutationπd(Bc;J[d])with theminimalvalueof thepenalty for thepartialpermutations in the leavesof theconstructedsolutiontree. Thewholesolution tree is constructedsimilarlyuntil there isapartialpermutationwithasmaller valueof thepenaltyφt in theconstructedsolutiontree. 4.2. TheApplicationofProcedure5 to theSmallExample Table 1 presents input data for the example of the problem1|pLi ≤ pi ≤ pUi |∑Ci described in Section 3.1. The jobs J4, J5 and J7 are non-fixed: J [B1] = {J4, J5}, J [B2] = {J4, J5, J7}, J [B3]={J4, J6, J7},J [B4]={J7}. The job J4 must be distributed either to the block B1, B2, or to theblockB3. The job J5mustbedistributedeither to theblockB1,or to theblockB2. The job J7must bedistributedeither to theblockB2,B3,or to theblockB4. Therelativeperimeterof theoptimalitybox OB(πk,T) forany jobpermutationπk∈Scannotbegreater thanPermax=4×2=8dueto theupper boundontherelativeperimeterPerOB(πk,T)given in (5). At the first iterationofProcedure5, thesetP(J [B11])={∅,{J4},{J5},{J4, J5}} is constructedand permutationsπ1(B11;∅),π 2(B11; J4),π 3(B11; J5)andπ 4(B11; J4, J5)aregenerated. Foreachelementof the setP(J [B11]),we construct apermutationwith themaximal lengthof the relativeperimeter of the optimalityboxandcalculate thepenalty.Weobtainthefollowingpermutationswiththeirpenalties: π0→1(B11;∅)=(J1, J2, J3),φ1=1 19 30≈1.633333;π0→2(B11; J4)=(J4, J2, J1, J3),φ2=1,5;π0→3(B11; J5)= (J1, J5, J2, J3),φ3=11330≈1.433333;π0→4(B11; J4, J5)=(J4, J5, J1, J2, J3),φ4=11330≈1.433333. 32