Page - 47 - in Algorithms for Scheduling Problems

Algorithms 2018,11, 80 Observation1. Themaximumjob lateness inakernelK cannotbe reduced if the earliest scheduled job inK startsat timer(K).Hence, if anED-scheduleScontainsakernelwith thisproperty, it is optimal forproblem 1|rj|Lmax. Thus,wemayensurethat thereexistsnofeasibleschedulewiththevalueofourobjectivefunction less than that insolutionSwhenever thecondition inObservation1 ismet. Then,we immediately proceedtothereconstructionofsolutionSaimingat theminimizationofoursecondobjectivefunction, aswedescribe in thenextsection. Suppose thecondition inObservation1 isnotsatisfied. Then, theremustexist job ewithde> do (i.e., lessurgent thantheoverflowjobo), scheduledbeforeall jobsofkernelK imposinga forceddelay for the jobsof thatkernel.Wecall job eanemerging jobforkernelK.Note thatanemerging job eand kernelKbelongto thesameblock. If theearliestscheduledjobofkernelKdoesnotstartat itsreleasetime, it is immediatelypreceded andpushedbyanemerging job,whichwecall thedelaying(emerging) job forkernelK. Wecaneasilyverify that inED-scheduleSofExample1 (seeFigure1), there isa singlekernel K1 = K(S) consistingof a single (overflow) Job3,with Lmax(S) = L3,S = 40−11= 29 (note that L7,S = 80−52= 28). Thereare twoemerging Jobs1and2 forkernelK, and Job2 is thedelaying emerging jobfor thatkernel. Clearly, themaximumjob lateness in scheduleSmayonlybedecreasedbyrestarting the jobs ofkernelK=K(S)earlier.Note that ifwerescheduleanemerging job ebehindthe jobsofkernelK, wemayrestart these jobsearlier.Asaresult, themaximumjoblateness inkernelKmaybereduced. Weshall refer to theoperationof thereschedulingofemerging job eafterkernelKas theactivationof thatemerging jobforkernelK. Toprovide theearlyrestartingfor jobsofkernelK,wemaintainany jobscheduledbehindkernelK inS scheduledbehindkernelK (all these jobsaresaid tobe in thestate ofactivationfor thatkernel).Wecall theresultantED-scheduleacomplementary to theS schedule anddenote itbySe. Ingeneral, a complementaryscheduleSE isdefinedforasetofemerging jobsE in scheduleS. InscheduleSE, all jobs fromsetEandall the jobsscheduledbehindkernelK inSare in thestateofactivationforkernelK. It iseasy tosee thatbyactivatingasingleemerging job e, kernelK willalreadyberestartedearlier;hence, themaximumjob lateness realizedbya job inkernelKwill bereduced. Observation2. Suppose the release timeof all the emerging jobs ina setE is increased to themagnitude r(K), and theEDheuristics isnewlyapplied to themodified instance. Then, if some job j scheduledbehindkernelK in scheduleSgets rescheduledbeforekernelK,dj> do,where o is the correspondingoverflowjob inkernelK. Proof. BytheEDheuristics, any job i releasedbefore the jobsofkernelKwithdi≤ dowouldhave been includedwithinkernelK inscheduleS.Hence, if a jobscheduledbehindkernelK inscheduleS becomes includedbeforekernelK, thendj> do (i.e., it is lessurgent thanallkernel jobs). By theaboveobservation, ifwemerely increase therelease timeofanyaboveavailable job jwith dj> do andthatofanyemerging jobfromsetE tomagnitude r(K), thentheEDheuristicswill create complementaryscheduleSE for themodifiedinstance. Observation 3. Let l be the delaying emerging job in schedule S. Then, in complementary schedule Sl, the earliest scheduled jobof kernelK=K(S) starts at its release timer(K)and isprecededbyagap. Proof. By the definition of complementary schedule Sl, no job j with dj > do may be included before kernelK(S) in schedule Sl. Aswehave already observed, no available job iwith di ≤ do maybe included before kernelK in complementary schedule Sl. Then, clearly, the time interval before theearliest released jobofkernelKwill remain idle in complementary scheduleSl, and the observationfollows. 47