Page - 50 - in Algorithms for Scheduling Problems

Algorithms 2018,11, 80 K is tobestartedwithin the interval [r(K)+δ(K),r(K)+δ(K)+δ], thecorrespondingbin intervals beingdeterminedwithrespect to thesestartingtimes.Notice that if the latest jobofkernelK completes atorbefore timemoment r(K)+P(K)+δ, thenthe latenessofno jobof thatkernelwill surpass the magnitudeL(δ)= r(K)+P(K)+δ−d,whered is theduedateof thecorrespondingoverflowjoband P(K) is the totalprocessingtimeof the jobs inkernelK. Weshall refer to themagnitudeL(δ)= r(K)+P(K)+δ−das the thresholdonthemaximum allowable job lateness corresponding to the current trial value δ. Ideally, notonly jobsofkernelK, butnoother job is tohavethe latenessmore thanL(δ).Ourschemeverifies if thereexistsa feasible schedulewith themaximumjob latenessnomore thanL(δ). If it succeeds (fails, respectively) tocreate afeasibleschedulewiththemaximal joblatenessnomorethanthresholdL(δ), the nextsmaller (larger, respectively)valueofδ is takeninthebinarypartitionmode.Accordingtoourpartition, the latenessof nokernel jobmaysurpass the thresholdL(δ).Hence, itbasically remains toschedule thebin intervals (see thenext section).Asalreadynoted, ifwhileschedulingsomebin, thenext incoming jobresults in a latenessgreater thanL(δ), thenanewkernelK includingthis job isdetermined(see thenextsection for thedetails). Then, the current set of the kernels is updatedasK :=K∪{K}, and the scheme proceedswith theupdatedpartition. Apositivedelay forakernelmightbeunavoidable inanoptimal jobarrangement. For instance, the time interval of kernel K1 in schedules S and S1 (Figures 1 and 2) is [35,40) and [30,35), respectively. The time interval of kernelK1 remains tobe [30,35) in theoptimal solution. Indeed, letus formournextsetEagainwith thesameemergingJob1constructingcomplementaryschedule (S1)1=(2,0)(3,30)(4,36)(5,46)(6,56)(7,66)(1,76); seeFigure3 (thiscomplementaryschedulehasa gap [35,36)markedasadarkregion in thefigure). Figure3.AcomplementaryED-schedule (S1)1. It is easily verified that schedule (S1)1 with kernelsK1 andK2 and the corresponding three arrangedbins isoptimalwithLmax((S1)1)=L3,(S1)1 =35−11=24=L7,(S1)1 =76−52=24. In that schedule,wehaveachievedanoptimalbalancebetweenthedelaysof thetwokernelsbyredistributing theavailable jobswithinthebins.Asaresult, themakespanisreducedwithoutaffectingthemaximum job lateness.Note that the jobsofkernelK1 andalso thoseofkernelK2 aredelayedbyanappropriate amountof timeunitswithoutaffecting themaximumjob lateness.Our frameworkdeterminessuchan appropriatedelayforeverydetectedkernel, resulting inanoptimalbalancebetweenkernelandbin intervals.Observe that,althoughthepartitionof theschedulinghorizon inschedulesS1 and (S1)1 is thesame, the binsarepackedindifferentways in these twocomplementaryschedules. Instead of forming the complementary schedules, we shall construct a direct algorithm for schedulingthebins in the followingsection. 5. SchedulingtheBins Attheiterationinthebinarysearchprocedurewiththetrialvalueδandagivenpartition,wehave reducedtheschedulingproblemtothatoffilling in thebin intervalsbynon-kernel jobs.Weschedule thebinsaccordingtotheorder inwhichtheyappear inthecurrentpartitionofbinandkernelsegments. Ifall thebins fromthecurrentpartitionarescheduledwithoutsurpassingcurrent thresholdvalueL(δ) (see theprevioussection), thesebins togetherwith thecorrespondingkernelsaremergedrespectively, formingtheoverallcompleteschedule(wehavethesuccessfuloutcomefortrialδ). Thecreatedfeasible solutionrespectingthresholdL(δ)willhaveanoptimalorsub-optimalmakespanamongall feasible solutionsrespectingL(δ) (seeTheorem2andLemma3). In this section,wedescribehowthebinscanefficientlybefilled inwithnon-kernel jobsandhow duringthisprocess,newkernelsandthecorrespondingbinsmaybedeclared,yieldinganupdated 50