Page - 23 - in Algorithms for Scheduling Problems

Algorithms 2018,11, 66 Thestabilityapproach[5,11,12]wasappliedto theproblem1|pLi ≤ pi≤ pUi |∑wiCi in [15],where hard instanceswere generated and solved by the developedAlgorithmMAX-OPTBOXwith the averageerrorequal to1.516783%.AlgorithmMAX-OPTBOXconstructsa jobpermutationwith the optimalityboxhavingthe largestperimeter. In Sections 3–6, we continue the investigation of the optimality box for the problem 1|pLi ≤ pi≤ pUi |∑Ci. Theprovenpropertiesof theoptimalityboxallowsus todevelopAlgorithm2 forconstructinga jobpermutationwith theoptimalityboxhavingthe largest relativeperimeterand Algorithm3,whichoutperformsAlgorithmMAX-OPTBOXforsolvinghard instancesof theproblem 1|pLi ≤ pi≤ pUi |∑Ci. Algorithm3constructsa jobpermutationπk,whoseoptimalityboxprovides theminimalvalueof theerror function introducedinSection5.Randomlygenerated instancesof the problem1|pLi ≤ pi≤ pUi |∑CiweresolvedbyAlgorithm3with theaverageerrorequal to0.735154%. 3.TheOptimalityBox Let Mdenote a subset of the set N = {1,2,. . . ,n}. Wedefine an optimality box for the job permutationπk∈S for theproblem1|pLi ≤ pi≤ pUi |∑Ci as follows. Definition2. Themaximal (with respect to the inclusion) rectangularboxOB(πk,T)=×ki∈M[l∗ki,u∗ki]⊆T iscalled theoptimalitybox for thepermutationπk=(Jk1, Jk2, . . . , Jkn)∈Swithrespect toT, if thepermutation πk being optimal for the instance1|p|∑Ci with the scenario p=(p1,p2, . . . ,pn)∈ T remains optimal for the instance1|p′|∑Ci with any scenario p′ ∈ OB(πk,T)×{×kj∈N\M[pkj,pkj]}. If there does not exist a scenario p∈Tsuch that thepermutationπk is optimal for the instance1|p|∑Ci, thenOB(πk,T)=∅. Any variation p′ki of the processing time pki, Jki ∈ J , within themaximal segment [l∗ki,u∗ki] indicated inDefinition2cannotviolate theoptimalityof thepermutationπk∈Sprovidedthat the inclusion p′ki ∈ [l∗ki,u∗ki]holds. Thenon-emptymaximalsegment [l∗ki,u∗ki]withthe inequality l∗ki ≤u∗ki andthelengthu∗ki− l∗ki ≥0indicatedinDefinition2iscalledanoptimalitysegment for the job Jki ∈J in thepermutationπk. If themaximalsegment [l∗ki,u ∗ ki ] is empty for job Jki ∈J ,wesay that job Jki has nooptimalitysegment in thepermutationπk. It is clear that if job Jki hasnooptimalitysegment in thepermutationπk, thenthe inequality l∗ki>u ∗ ki holds. 3.1.AnExampleof theProblem1|pLi ≤ pi≤ pUi |∑Ci Following to [15], the notion of a block for the jobsJ may be introduced for the problem 1|pLi ≤ pi≤ pUi |∑Ci as follows. Definition 3. A maximal set Br = {Jr1, Jr2, . . . , Jr|Br|} ⊆ J of the jobs, for which the inequality maxJri∈Br p L ri ≤minJri∈Br pUri holds, is called ablock. The segment [bLr ,bUr ]with bLr =maxJri∈Br pLri and bUr =minJri∈Br p U ri is calledacoreof theblockBr. If job Ji ∈J belongs toonlyoneblock,wesay that job Ji isfixed (in thisblock). If job Jk ∈J belongs to twoormoreblocks,we say that job Jk isnon-fixed. We say that theblockBv isvirtual, if there isnofixed job in theblockBv. Remark1. Anypermutationπk ∈ Sdetermines a distribution of all non-fixed jobs to their blocks. Due to thefixingsof thepositionsof thenon-fixed jobs, somevirtualblocksmaybedestroyed for thepermutationπk. Furthermore, the coresof somenon-virtual blocksmaybe increased in thepermutationπk. WedemonstratetheabovenotionsonasmallexamplewithinputdatagiveninTable1.Thesegments [pLi ,p U i ]of the jobprocessingtimesarepresentedinacoordinatesysteminFigure1,wheretheabscissa axis isusedfor indicatingthesegmentsgivenforthe jobprocessingtimesandtheordinateaxis for the jobsfromthesetJ . Thecoresof theblocksB1,B2,B3 andB4 aredashedinFigure1. 23