Page - 46 - in Algorithms for Scheduling Problems

Algorithms 2018,11, 80 interested inED-scheduleswith themaximumjob latenessnotexceedingagiventhreshold(soour analysis is carriedout in termsof theminimizationof themaximumjob lateness). First,wegivea detaileddescriptionof theEDheuristics. Theheuristicsdistinguishesn schedulingtimes, the timemomentsatwhicha job isassignedto themachine. Initially, theearliest schedulingtimeisset to theminimumjobrelease time.Amongall jobs releasedby that time, a jobwith theminimumduedate isassigned to themachine (tiesbeing brokenbyselecting the longest job). Iteratively, thenext scheduling time iseither thecompletion time of the latest jobassignedso far to themachineor theminimumrelease timeof anunassigned job, whichever ismore(no jobcanbestartedbefore themachinebecomesidle,norcanitbestartedbefore it gets released).Amongall jobsreleasedbyeverynewly-determined(as just specified)schedulingtime, a jobwith theminimumduedate isassignedto themachine.Note thatsince therearen scheduling times and at each scheduling time, aminimal element in an ordered list is searched for, the time complexityof theheuristics isO(n logn). AgapinanED-schedule is itsmaximalconsecutive time interval inwhich themachine is idle (withourconvention, thereoccursazero-lengthgap (cj,ti)whenever job i startsat its release time immediatelyafter thecompletionof job j). Ablock inanED-schedule is its consecutivepartconsistingof thesuccessivelyscheduled jobs withoutanygapinbetween,which isprecededandsucceededbya(possiblyazero-length)gap. Suppose job ipreceding job j inED-scheduleS is said topush job j inS if jwillberescheduled earlier whenever i is forced to be scheduled behind j (it follows that jobs i and j belong to the sameblock). Example1. Wehaveseven jobs inourfirstprobleminstance. Theprocessing times, the release timesandthe duedatesof these jobsaredefinedas follows: p1= p3=5,p2=30,p4= p5= p6= p7=10. r3=11,r5= r6= r7=42,whereas the rest of the jobsare releasedatTime0, except Job4, releasedatTime36. d1=75,d2=80,d3=11,d4=53,d5= d6= d7=52. It canbereadilyverifiedthat theEDheuristicswillassignthe jobs in increasingorderof their indexescreating anED-scheduleS=(1,0)(2,5)(3,35)(4,40)(5,50)(6,60)(7,70), asdepicted inFigure1(ineverypair inbrackets, the firstnumber is the job index,andthesecondnumber is its startingtime). InscheduleS,consistingofasingle block(there isnogapin it), Job2pushes Job3andthesucceedingjobs. Figure1.The initialEarliestDuedate (ED)-scheduleS for theprobleminstanceofExample1. GivenanED-scheduleS, let ibea job that realizes themaximumjob lateness in that schedule, i.e., Li(S) =maxj{Lj(S)}, and letBbe theblock inS containing job i. Amongall jobs i ∈ Bwith Li(S) =maxj{Lj(S)}, the latest scheduledone is said tobeanoverflow job in scheduleS. Clearly, everyschedulecontainsat leastoneoverflowjob,whereaseveryblock inscheduleSmaycontainone ormoreoverflowjobs (twoormoreoverflowjobs fromthesameblockwill thenbe“separated”by non-kernel jobs). Akernel inscheduleS is the longest sequenceof jobsendingwithanoverflowjobo, such thatno jobfromthissequencehasaduedatemore thando. WeshallnormallyuseK(S) for theearliestkernel in scheduleS, andabusing the terminology, weshallalsouseK(S) for thesetof jobs in thesequence. ForkernelK, let r(K)=mini∈K{ri}. Note thateverykernel iscontainedwithinsomeblock inscheduleS, andhence, itmaycontainno gap. The followingobservationstatesasufficientoptimalitycondition for thesingle-criterionproblem 1|rj|Lmax (thereadermayhavea lookat [25] foraproof): 46