Seite - 33 - in Algorithms for Scheduling Problems

Algorithms 2018,11, 66 At the second iteration, the block B2 is destroyed, and we construct the permutations π5(B23;∅) and π 6(B23; J7) from the permutation π 4(B11; J4, J5). We obtain the permutation π0→5(B23;∅) = (J4, J5, J1, J2, J3, J6)with the penalty φ5 = 4 13 30 ≈ 4.433333 and the permutation π0→6(B32; J7) = (J4, J5, J1, J2, J3, J7, J6)with the penalty φ6 = 5 1 3 ≈ 5.333333. Since all non-fixed jobs are distributed in the permutation π0→6(B11; J3, J8), we obtain the complete permutation J4, J5, J1, J2, J3, J6, J8, J10, J9, J7)∈Swiththefinalpenaltyφ∗6=6 712≈6.583333. Fromthepermutation π0→3(B11; J5), we obtain the permutationswith their penalties: π 0→7(B33;∅) = (J1, J5, J3, J2, J4, J6), φ7 = 52990 ≈ 5.322222 andπ0→8(B33; J7) = (J1, J5, J3, J2, J4, J7, J6), φ8 = 51. Weobtain the complete permutationπ=(J1, J5, J3, J2, J4, J7, J6, J9, J10, J8)withthepenaltyφ∗8=6.35. Weobtain the followingpermutationswith theirpenalties:π0→9(B42;∅)=(J4, J2, J3, J1, J5),φ9= 3 124≈3.041667andπ0→10(B42; J7)=(J4, J2, J1, J3, J7, J5),φ10=3.5 fromthepermutationπ0→2(B11; J4). We obtain the following permutationswith their penalties: π0→11(B52;∅) = (J1, J2, J3, J5,), φ11 = 3.175, π0→12(B52; J4) = (J1, J2, J3, J4, J5), φ12 = 3.3, π 0→13(B52; J7) = (J1, J2, J3, J7, J5), φ13 = 3 19 30 ≈ 3.633333, π0→14(B52; J4, J7) = (J1, J2, J3, J4, J7, J5), φ14 = 3 19 30 ≈ 3.633333 from the permutation π0→1(B11;∅). We obtain the complete permutation (J1, J2, J3, J4, J7, J5, J6, J9, J10, J8) ∈ S with the final penalty φ∗14 = 5 53 60 ≈ 5.883333. We obtain the following permutationswith their penalties: π0→15(B63;∅) = (J4, J2, J3, J1, J5, J6), φ15 = 4 1 24 ≈ 4.041667, π0→16(B63; J7) = (J4, J2, J3, J1, J5, J7, J6), φ16 = 5 760 ≈ 5.116667 from the permutation π0→9(B42;∅). We obtain the complete permutation (J4, J2, J3, J1, J5, J7, J6, J9, J10, J8)∈Swiththefinalpenaltyφ∗16=61130≈6.366667. Weobtain the followingpermutationswith theirpenalties: π0→17(B73;∅)= (J1, J2, J3, J5, J4, J6), φ17 = 51145 ≈ 5.244444, π0→18(B73; J7) = (J1, J2, J3, J5, J7, J4, J6), φ18 = 4.925 from the permutation π0→11(B52;∅).Weobtain thecompletepermutation (J1, J2, J3, J5, J7, J4, J6, J9, J10, J8)∈Swiththefinal penaltyφ∗18=6.175. We obtain the followingpermutationswith their penalties: π0→19(B83;∅) = (J1, J2, J3, J4, J5, J6), φ19=4.3, π0→20(B83; J7) = (J1, J2, J3, J4, J5, J7, J6), φ20 = 5.7 from the permutation π 0→12(B52; J4). Weobtainthecompletepermutation (J1, J2, J3, J4, J5, J7, J6, J9, J10, J8)∈Swiththefinalpenaltyφ∗20=6.95. From the permutation π0→10(B42; J7), we obtain the permutation with its penalty as follows: π0→21(B93; J4) = (J4, J2, J1, J3, J7, J5, J4, J6), φ21 = 5.05. We obtain the complete permutation J4, J2, J1, J3, J7, J5, J4, J6, J9, J10, J8) ∈ S with the final penalty φ∗21 = 6.3. We obtain the following permutationwith theirpenalties: π0→22(B103 ; J4) = (J1, J2, J3, J7, J5, J4, J6),φ22 = 5 1 12 ≈ 5.083333 from thepermutationπ0→13(B52; J7).Weobtainthecompletepermutation (J1, J2, J3, J7, J5, J4, J6, J9, J10, J8)∈S with the final penaltyφ∗22 = 6 1 3 ≈ 6.333333. Weobtain the complete permutationπ0→23(B114 ; J4) = (J4, J2, J3, J1, J5, J6, J8, J10, J9, J7),φ23=5 17120≈5.141667fromthepermutationπ0→15(B63;∅).Weobtainthe completepermutationπ0→24(B124 ; J4)=(J1, J2, J3, J4, J5, J6, J8, J10, J9, J7),φ22=5.4fromthepermutation π0→19(B83;∅)). Weobtain the completepermutationπ 0→25(B124 ; J4) = (J4, J5, J1, J2, J3, J6, J8, J10, J9, J7), φ25=5 815≈5.533333fromthepermutationπ0→5(B23;∅)). UsingProcedure5,weobtain the followingpermutationwith the largest relativeperimeterof the optimalitybox:π0→23(B114 ; J4). Themaximal relativeperimeterPer(OB(πk,T))of theoptimalitybox isequal to2103120≈2.858333,wherePermax=22andtheminimalpenaltyobtainedfor thepermutation πk isequal to5 17120≈5.141667. Sinceallnon-fixed jobsaredistributed in thepermutationπ0→23(B114 ; J4),weobtain thecomplete permutation (J4, J2, J3, J1, J5, J6, J8, J10, J9, J7)∈Swiththefinalpenaltyφ∗23 equal to5 17120≈5.141667. 5.AnApproximateSolutionto theProblem1|pLi ≤ pi≤ pUi |∑Ci The relative perimeter of the optimality boxOB(πk,T) characterizes the probability for the permutationπk tobeoptimal for the instances1|p|∑Ci,where p∈T. It is clear that thisprobability maybeclosetozerofor theproblem1|pLi ≤ pi≤ pUi |∑Ciwithahighuncertaintyof the jobprocessing times (if thesetThasa largevolumeandperimeter). If theuncertaintyof the inputdata ishighfor theproblem1|pLi ≤ pi≤ pUi |∑Ci, onecanestimate howthevalueof∑ni=1Ci(πk,p)withavectorp∈Tmaybeclosetotheoptimalvalueof∑ni=1Ci(πt,p∗), 33