Page - 54 - in Algorithms for Scheduling Problems

Algorithms 2018,11, 80 Phase2: If thefirstconditioninTheorem2isnotsatisfied, i.e., anIA(b2)at thefirstpassofPhase1 occurs, thenPhase2 is invoked. Letybe theearliestarisenType (b)y-job that couldnothavebeen included inscheduleS(B,y). Ingeneral, job jmaybepushedbyoneormoreotherType (b)y-jobs. Since the latenessof joby surpassesL(δ), a completeschedulerespecting this thresholdvaluecannot becreatedunless the latenessof joby isdecreased. Thenextobservationfollows: Observation6. SupposeanIA(b2)with(aType(b)y-job)yat thefirstpassofPhase1 inbinBarises. Then, the resultantmaximumjob lateness inbinByieldedby joby cannotbedecreasedunless joby and/or otherType (b)y-jobs currentlypushing joby inbinBare rescheduled to someearlier bin(s). Accordingto theaboveobservation, inPhase2,either joby is toberescheduledtoanearlierbin orasubsetof theaboveType(b)y-jobs (withanappropriate totalprocessing time) is tobe formedand all jobs fromthatsubsetare toberescheduledtosomeearlierbin(s). Inparticular, if the latenessof job y surpassesL(δ)byamountλ, then the totalprocessing timeof jobs insuchasubset is tobeat leastλ. Bytheconstruction,nonewjobcanfeasiblybe introducedintoanyalreadyscheduledbinBunless some jobs (withanappropriate total length) fromthatbinarerescheduledbehindall theaboveType (b)y-jobs. Sucha job,whichwecallasubstitution jobfor joby, shouldclearlybeanemerging jobfor joby, i.e.,ds> dy (asotherwise,oncerescheduled, its latenesswill surpassL(δ)). Theorem3. If for an IA(b2)with a (Type (b) y-job) y, there exists no substitution job for job y, then there existsno feasible schedule respecting thresholdvalueL(δ). Hence, there existsnoPareto-optimal solutionwith maximumjob lateness L(δ). Proof. DuetoObservation6, jobyorsomeotherType(b)y-job(s)pushing jobymustberescheduled toabinprecedingbinB. By thewayweconstructourbins,nonewjobcan feasiblybe introduced intoanybinprecedingbinBunlesssome(sufficiently long) job s fromthatbin is rescheduledbehind all theaboveType (b)y-jobs. ds< dymustholdasotherwise job sor some joboriginally included before jobywill surpass thecurrent threshold; i.e., s isasubstitution job. It followsthat if thereexists nosubstitution job, the latenessofat leastone jobfrombinBor fromitsprecedingbinwill surpass thresholdvalueL(δ), andhence, theremayexistno feasible schedule respectingL(δ). The second claimimmediately follows. Due to the above theorem, if these exists no substitution job, the call from the binary search procedure for thecurrentδhaltswith the failureoutcome,andtheprocedureproceedswith thenext (larger) trialvalue forδ; if thereremainsnosuchδ, thewholeschemehalts. Thecasewhenthereexistsasubstitution jobfor joby isdiscussednow.We observe that there mayexistaPareto-optimalsolution. Tovalidatewhether it exists,wefirstneedtoverify if thereexists a feasible solution respecting threshold L(δ) (given that the call to thebinpackingprocedurewas performedfromthe iteration in thebinarysearchprocedurewith that thresholdvalue). This task is easilyverifiedif, for instance, there isasinglesubstitution job s. Indeed,wemayconstructanauxiliary ED-schedule inwhichwe activate that substitution job for job y (similarly as before,we increase artificially the release timeof job s to that of job y, so that once theEDheuristics isnewlyapplied to thatmodifiedprobleminstance, thesubstitution job swillbe forcedtoberescheduledbehind job y). In the resultantED-schedulewith theactivated job s, if the latenessofnoneof the rescheduled y-jobs isnogreater thanL(δ),Phase1canberesumedforbinB. Otherwise, theremayexitnofeasible solutionrespectingthresholdL(δ) (hence,noPareto-optimalsolutionwith themaximumjob lateness notexceedingL(δ)mayexist), andtheschemecanproceedwith thenext trialδ. In practice, with a known upper limit on the total number of substitution jobs, the above activationprocedurecanbegeneralizedtoanotherprocedure thatenumeratesall thepossiblesubsets of substitution jobs inpolynomial time. Ingeneral, if thenumberofsubstitution jobs isboundedonly byn, thenumberofpossiblesubsetsof substitution jobswith totalprocessing timeλormoremightbe 54