Page - 49 - in Algorithms for Scheduling Problems

Algorithms 2018,11, 80 complementaryscheduleS1 (Figure2), therearisesanewkernelwithin thesecondbin.Note that the execution intervalofkernelK1 inschedulesSandS1 isdifferent (it is [35,40) inscheduleSand [30,35) inscheduleS1). Correspondingly, thefirstbin isextendedupto timemoment35 inscheduleS, and it isextendeduptoTime30 inscheduleS1. ThenewlyarisenkernelK2=K(S1)defines twonewbins in scheduleS1;hence, that schedulecontains threebins, in total. Ingeneral, thestartingandcompletiontimesofeverybinarenotapriorifixed; theyaredefinedin accordancewith theallowableflexibility for thecorrespondingkernel intervals.Ourschemeproceeds inanumberof iterations. Toevery iteration,acompleteschedulewithaparticulardistributionof jobs into thebinscorresponds,whereas thesetof jobsscheduled ineverykernel interval remains thesame. In thisway, twoormore complete schedules for the samepartitionmightbe created (for instance, schedulesS1 and (S1)1 ofExample1; seeFigures2and3).Atan iterationh,duringtheschedulingofa bin, anewkernelmayarise,which isaddedto thecurrent setofkernelsK (kernelK2 ariseswithin thesecondbin incomplementaryscheduleS1 ofExample1): theupdatedsetcontainsall the former kernels togetherwith thenewlyarisenone (since scheduleSofFigure 1 containsonlyonekernel, K={K1}, thereareonly twobins in it; thenextgeneratedscheduleS1 ofFigure2containsalready twokernelsK1 andK2,K={K1,K2}andthreebins).Note that thepartitionof theschedulinghorizon ischangedevery timeanewkernelarises. Adjustingtimeintervalsforkernelandbinsegments: Althoughthetimeintervalwithinwhich eachkernelcanbescheduledis restricted, ithassomedegreeofflexibility,aswehave illustrated in Example1. Inparticular, theearliest scheduled jobofakernelKmightbedelayedbysomeamount withoutaffecting thecurrentmaximumjob lateness. Denote thismagnitudeby δ(K).Without loss ofgenerality, themagnitudeδ(K) cantake thevalues fromthe intervalδ(K)∈ [0,pl],where l is the delayingemerging job forkernelK in the initially constructedED-scheduleσ. Indeed, if δ(K)= 0, thekernelwillnotbedelayed,whereasδ(K)= pl corresponds to thedelayof thekernel in the initial ED-scheduleS (which is19 forkernelK1 inscheduleSofFigure1). Inparticular,welet pmaxbethe maximumjobprocessingtimeandshallassume,without lossofgenerality, thatδ(K)≤ pmax. Todefineδ(K), letusconsiderapartial scheduleconstructedbytheEDheuristics foronly jobsof kernelK∈K. Thefirst job inthatschedulestartsat time r(K) (weassumethat there isnoemerging job within that sequence,asotherwisewecontinuewithourpartitioningprocess).Note that the lateness of theoverflowjobof thatpartial schedule isa lowerboundonthemaximumjob lateness;denote this magnitudebyL∗(K). Then,L∗=maxK∈K{L∗(K)} isalsoa lowerboundonthesameobjectivevalue. Now,weletδ(K)=L∗−L∗(K), foreverykernelK∈K. The followingobservation isapparent: Observation4. For δ(K) = 0, the lateness of the latest scheduled job of kernel K is a lower bound on the optimal job lateness, and forδ(K)= pl, it is avalidupperboundonthe sameobjectivevalue. Observation5. Ina scheduleSoptminimizing themaximumjob lateness, everykernelK starts eitherno later thanat timer(K)+δ(K)or it isdelayedbysomeδ≥0,whereδ∈ [0,pmax]. Proof. First note that in any feasible schedule, everykernelK canbedelayedby theamount δ(K) without increasing themaximumjob lateness.Hence,kernelKdoesnotneedtobestartedbefore time r(K)+δ(K). Furthermore, inanycreatedED-schedule, thedelayofanykernelcannotbemore than pmax, as foranydelayingemerging job l, pl≤ pmax.Hence,δ∈ [0,pmax]. Thus for a givenpartition, the starting and completion timeof every bin in a corresponding completeschedulemayvaryaccordingtoObservation5.Ourschemeincorporatesabinarysearch procedure inwhich the trialvalues forδaredrownfrominterval [0,pmax]. Toevery iteration in the binarysearchprocedure, sometrialvalueofδ corresponds,whichdetermines themaximumallowable job lateness,aswedescribebelow. Weobserve thatnotallkernelsare tight in thesense that, foragivenkernelK∈K,δ(K)mightbe strictlygreater thanzero. ByObservation5, inanygeneratedschedulewith trialvalueδ, everykernel 49