Seite - 22 - in Algorithms for Scheduling Problems

Algorithms 2018,11, 66 thesegments [pLi ,p U i ]:T= {p∈Rn+ : pLi ≤ pi≤ pUi , i∈{1,2,. . . ,n}}=[pL1,pU1 ]× [pL2,pU2 ]× . . .× [pLn,pUn ]=:×ni=1[pLi ,pUi ]. Eachvector p∈T is calledascenario. LetS={π1,π2, . . . ,πn!}beasetofallpermutationsπk=(Jk1, Jk2, . . . , Jkn)of the jobsJ . Givena scenariop∈Tandapermutationπk∈S, letCi=Ci(πk,p)denotethecompletiontimeofthejob Ji∈J in the scheduledeterminedby thepermutationπk. The criterion∑Ci denotes theminimizationof thesumof jobcompletiontimes:∑Ji∈JCi(πt,p)=minπk∈S { ∑Ji∈JCi(πk,p) } ,where thepermutation πt = (Jt1, Jt2, . . . , Jtn)∈ S is optimal for the criterion∑Ci. Thisproblemisdenotedas1|pLi ≤ pi ≤ pUi |∑Ciusingthethree-fieldnotationα|β|γ [13],whereγdenotes theobjective function. If scenario p∈T is fixedbeforescheduling, i.e., [pLi ,pUi ]= [pi,pi] foreach job Ji∈J , thentheuncertainproblem 1|pLi ≤ pi ≤ pUi |∑Ci is turned into thedeterministic one 1||∑Ci. Weuse thenotation1|p|∑Ci to indicatean instanceof theproblem1||∑Ci with the fixedscenario p∈ T. Any instance1|p|∑Ci is solvable inO(nlogn) time[14]since thefollowingclaimhasbeenproven. Theorem1. The jobpermutationπk=(Jk1, Jk2, . . . , Jkn)∈S isoptimal for the instance1|p|∑Ci if andonly if the following inequalities hold: pk1 ≤ pk2 ≤ . . .≤ pkn. If pku< pkv, then job Jku precedes job Jkv in any optimalpermutationπk. Sinceascenario p∈T isnotfixedfor theuncertainproblem1|pLi ≤ pi≤ pUi |∑Ci, thecompletion time Ci of the job Ji ∈ J cannot be exactly determined for the permutation πk ∈ S before the completionof the job Ji. Therefore, thevalueof theobjective function∑Ci for thepermutationπk remainsuncertainuntil jobsJ havebeencompleted. Definition1. Job Jv dominates job Jw (with respect to T) if there is no optimal permutationπk ∈ S for the instance1|p|∑Ci, p∈T, such that job Jw precedes job Jv. Thefollowingcriterionfor thedominationwasprovenin [15]. Theorem2. Job Jv dominates job Jw if andonly if pUv < pLw. Since for theproblemα|pLi ≤ pi≤ pUi |γ, theredoesnotusuallyexistapermutationof the jobsJ beingoptimal forall scenariosT, additionalobjectivesoragreementsareoftenusedin the literature. Inparticular, a robust scheduleminimizingtheworst-caseregret tohedgeagainstdatauncertainty hasbeendevelopedin [3,8,16–20]. Foranypermutationπk∈Sandanyscenario p∈T, thedifference γkp−γtp =: r(πk,p) is called the regret for permutation πk with the objective function γ equal to γkp under scenario p. ThevalueZ(πk) =max{r(πk,p) : p∈ T} is called theworst-case absolute regret. ThevalueZ∗(πk)=max{r(πk,p)γtp : p∈T} is called theworst-case relative regret.While the deterministicproblem1||∑Ci ispolynomiallysolvable [14],findingapermutationπt∈Sminimizing theworst-caseabsoluteregretZ(πk)ortherelativeregretZ∗(πk) for theproblem1|pLi ≤ pi≤ pUi |∑Ci arebinaryNP-hardevenfortwoscenarios[19,21]. In[6],abranch-and-boundalgorithmwasdeveloped tofindapermutationπk minimizing the absolute regret for theproblem1|pLi ≤ pi ≤ pUi |∑wiCi, where jobs Ji∈J haveweightswi>0. Thecomputationalexperimentsshowedthat thedeveloped algorithm is able to find such a permutation πk for the instanceswith up to 40 jobs. The fuzzy scheduling techniquewasused in [7–9,22] todevelopa fuzzyanalogueofdispatching rules or to solvemathematicalprogrammingproblemstodetermineaschedule thatminimizesa fuzzy-valued objective function. In [23], several heuristics were developed for the problem 1|pLi ≤ pi ≤ pUi |∑wiCi. Thecomputationalexperiments includingdifferentprobabilitydistributionsof theprocessingtimes showedthat theerrorof thebestperformingheuristicwasabout1%of theoptimalobjective function value∑wiCiobtainedaftercompletingthe jobswhentheir factualprocessingtimesbecameknown. 22