Page - 51 - in Algorithms for Scheduling Problems

Algorithms 2018,11, 80 partitionof theschedulinghorizon.Whileschedulingthebins,our (secondary)goal is toreduce the lengthof the total idle time interval,whichyieldsareducedmakespan.Althoughmostbinscheduling problemsareNP-hard, thereareheuristicalgorithmswithgoodapproximation for theseproblems. Adoptingsuchaheuristics forourschedulingmodel,wemaypackourbinswithclose to theminimal totalgaplength(makespan),aswedescribebelow.Wheneverstrictoptimality is important,animplicit enumerativealgorithmcanbeapplied. First,weneedafewadditionalnotions. LetBbe thebin immediatelyprecedingkernelK (ourconstruction is similar for the lastbinof thecurrentpartition).WhileschedulingbinB,wedistinguishtwotypesof theavailable jobs for that bin.Wecall jobs thatmayonlybe feasiblyscheduledwithin thatbiny-jobsandones thatmayalso be feasiblyscheduledwithinasucceedingbin thex-jobs.Wehavetwosub-typesof they-jobs forbin B: aType(a)y-jobmayonlybefeasiblyscheduledwithin thatbin,unlike theType(b)y-jobs,which couldhavealsobeen includedinsomeprecedingbin (aType(b)y-job is releasedbefore the intervalof binBandcanpotentiallybescheduledwithinaprecedingbin). Theprocedure forschedulingbinBhas twophases: Phase1consistsof two passes. In thefirst pass, y-jobs are scheduled. In the secondpass, x-jobs are includedwithin the remainingavailable spaceof thebinbyaspecially-modifieddecreasingnextfitheuristics, commonlyusedforbinpacking problems. Note that all Type (a) y-jobs canbe feasibly scheduledonlywithinbinB. BesidesType (a)y-jobs,wearealso forcedto includeall theType(b)y-jobs inbinB,unlesswecarryoutaglobal jobrearrangementandrescheduleaType(b)y-jobwithinsomeprecedingbins.Weconsidersucha possibility inPhase2. Phase1,firstpass (schedulingy-jobs): ThefirstpassofPhase1consistsof twosteps. InStep1, they-jobsarescheduled inbinBbytheEDheuristics resulting inapartialED-schedule,whichwe denotebyS(B,y). It consistsofall they-jobs that theEDheuristicscould includewithoutsurpassing thecurrent thresholdL(δ) (recall thatL(δ) is thecurrentlymaximumallowable lateness). If scheduleS(B,y) isy-complete, i.e., it containsall they-jobs forbinB, then it is theoutputof the firstpass.Otherwise, thefirstpasscontinueswithStep2.Weneedthe followingdiscussionbeforewe describe thatstep. If schedule S(B,y) is not y-complete, then the lateness of the next consideredy-job at Step 1 surpasses thecurrentL(δ). If thaty-job isaType(b)y-job, thenaninstanceofAlternative (b2)with thatType(b)y-job (abbreviatedIA(b2)) is said tooccur (thebehavioralternativeswere introduced ina widercontextearlier in [26]). IA(b2) isdealtwith inPhase2, inwhichat leastoneType (b)y-job is rescheduledwithin the intervalof someearlierconstructedbin. Lemma1. If no IA(b2) at thefirstpass ofPhase1occurs, i.e., the earliest ariseny-joby that couldnothave been included inscheduleS(B,y) is aType (a)y-job), thenanewkernel consistingofType (a)y-jobs including jobyoccurs. Proof. First, note that allType (a)y-jobs canbe feasibly scheduledwithout surpassing the current allowable latenessandbecompletedwithinbinB.Hence, if theearliestariseny-joby thatcouldnot havebeenincludedturnsout tobeaType(a)y-job,a forcedright-shiftbysomeothery-joband/or theorderchange in thesequenceof thecorrespondingType(a)y-jobsmusthaveoccurred. Therefore, theremustexistacorrespondingdelayingemerging job,andhence,anewkernel canbedeclared. If scheduleS(B,y) isnoty-completeandnoIA(b2)at thefirstpassofPhase1occurs, thenStep2 atPhase1 is invoked.At thatstep, thenewkernel fromLemma3isdeclared,andthecurrentsetof kernelsandbins is respectivelyupdated. Then, thefirstpass iscalledrecursively for thenewlyformed partition; inparticular,Step1 is invokedfor theearliestof thenewly-arisenbins. Thiscompletes the descriptionof thefirstpass. Lemma2. IfduringtheschedulingofbinBatthefirstpass,noIA(b2)arises, thenthispassoutputsay-complete scheduleS(B,y) inwhich the latenessofnoy-job isgreater thanL(δ). 51