Seite - 34 - in Algorithms for Scheduling Problems

Algorithms 2018,11, 66 where thepermutationπt∈ S isoptimal for the factual scenario p∗ ∈Tof the jobprocessing times. We call the scenario p∗ = (p∗1,p ∗ 2, . . . ,p ∗ n) ∈ T factual, if pi is equal to the exact time needed for processing the job Ji ∈J . The factualprocessing time p∗i becomesknownafter completing the job Ji∈J . If thepermutationπk=(πk1,πk2, . . . ,πkn)∈Shasthenon-emptyoptimalityboxOB(πk,T) =∅, thenonecancalculate the followingerror function: F(πk,T)= n ∑ i=1 ( 1− u∗ki− l∗ki pUki−pLki ) (n− i+1) . (7) A value of the error function F(πk,T) characterizes how the objective function value of ∑ni=1Ci(πk,p ∗) for thepermutationπkmaybeclose to theobjective functionvalueof∑ni=1Ci(πt,p∗) for thepermutationπt∈S,which isoptimal for thefactualscenario p∗ ∈Tof the jobprocessingtimes. ThefunctionF(πk,T)characterizes the followingdifference n ∑ i=1 Ci(πk,p∗)− n ∑ i=1 Ci(πt,p∗), (8) whichhas tobeminimizedforagoodapproximatesolutionπk to theuncertainproblem1|pLi ≤ pi≤ pUi |∑Ci. Thebetterapproximatesolutionπk to theuncertainproblem1|pLi ≤ pi≤ pUi |∑Ciwillhave asmallervalueof theerror functionF(πk,T). The formula (7) is basedon the cumulative property of the objective function∑ni=1Ci(πk,T), namely,eachrelativeerror ( 1− u ∗ ki −l∗ki pUki −pLki ) >0obtaineddueto thewrongpositionof the job Jki in the permutationπk is repeated (n− i) times forall jobs,whichsucceedthe job Jki in thepermutationπk. Therefore,avalueof theerror functionF(πk,T)mustbeminimizedforagoodapproximationof the valueof∑ni=1Ci(πt,T) for thepermutationπk. If the equalityPerOB(πk,T) = 0holds, the error function F(πk,T)has themaximalpossible valuedeterminedas follows: F(πk,T)=∑ni=1 ( 1− u ∗ ki −l∗ki pUki −pLki ) (n− i+1)=∑ni=1(n− i+1)= n(n+1)2 . Thenecessaryandsufficientcondition for the largestvalueofF(πk,T)= n(n+1) 2 isgiven inTheorem3. If theequalityPerOB(πk,T)=nholds, theerror functionF(πk,T)has thesmallestvalueequal to 0: F(πk,T) = ∑ni=1 ( 1− u ∗ ki −l∗ki pUki −pLki ) (n− i+1) = ∑ni=1(1−1)(n− i+1) = 0. The necessary and sufficientconditionforthesmallestvalueofF(πk,T)=0isgiveninTheorem4,wherethepermutation πk∈S isoptimal foranyfactual scenario p∗ ∈Tof the jobprocessingtimes. Due to evident modifications of the proofs given in Section 3.3, it is easy to prove that Theorems5and6remaincorrect in the followingforms. Theorem7. If the equality B1 = J holds, then it takesO(n) time to find the permutation πk ∈ S and optimalityboxOB(πk,T)with the smallestvalueof the error functionF(πk,T)amongall permutationsS. Theorem8. Let each block Br ∈ B contain atmost one non-fixed job. The permutation πk ∈ Swith the smallestvalueof the error functionF(πk,T)amongall permutationsS is constructed inO(n logn) time. Using Theorems 7 and 8, we developed the modifications of Procedures 3 and 4 for the minimizationof thevalues of F(πk,T) insteadof themaximizationof thevalues ofPerOB(πk,T). ThederivedmodificationsofProcedures3and4arecalledProcedures3+F(πk,T)and4+F(πk,T), respectively.WemodifyalsoProcedures2and5forminimizationof thevaluesofF(πk,T) instead of themaximizationof thevaluesofPerOB(πk,T). ThederivedmodificationsofProcedures2and5 arecalledProcedures2+F(πk,T)and 5+F(πk,T), respectively. Basedontheprovenpropertiesof the 34