Seite - 52 - in Algorithms for Scheduling Problems

Algorithms 2018,11, 80 Proof. By Lemma 1 and the construction of the first pass, if at that pass, no IA(b2) arises, the constructed partial schedule S(B,y) contains all the y-jobswith the lateness nomore than L(δ), whichproves the lemma. Phase 1, secondpass (schedulingx-jobs): The secondpass is invoked if no IA(b2)during the execution of the first pass occurs. The first passwill then output a y-complete schedule S(B,y) (Lemma2),whichis the input for thesecondpass.At thesecondpass, theavailablex-jobsare included within the idle time intervals remaining inscheduleS(B,y).Now,wedescribeamodifiedversionofa commonDecreasingNextFitheuristics, adaptedtoourproblemforschedulingbinB (DNFheuristics forshort). Theheuristicsdealswitha listof thex-jobs forkernelK sorted innon-increasingorderof theirprocessingtimes,whereasthe jobswiththesameprocessingtimearesortedinthenon-decreasing orderof theirduedates (i.e.,moreurgent jobsappearearlier in that list). Iteratively, theDNFheuristics selects thenext jobx fromthelistandtries toschedule itat theearliest idle timemoment t′atorbehind its release time. If timemoment t′+pi isgreater thantheallowableupperendpointof the intervalof binB, jobxis ignored,andthenextx-job fromthe list is similarlyconsidered(ifnounconsideredx-job is left, thenthesecondpass forbinBcompletes).Otherwise (t′+pi fallswithin the intervalofbinB), the followingstepsarecarriedout. (A) If jobx canbescheduledat timemoment t′withoutpushingany-job includedinthefirstpass (andbecompletedwithin the intervalof thecurrentbin), then it is scheduledat time t′ (being removedfromthe list), andthenextx-job fromthe list is similarlyconsidered. (B) Jobx is includedat time t′ if itpushesnoy-job fromscheduleS(B,y). Otherwise, suppose job x, if includedat time t′,pushesay-job,andletS(B,+x)bethecorresponding(auxiliary)partial ED-scheduleobtainedbyrescheduling(right-shifting) respectivelyall thepushedy-jobsbythe EDheuristics. (B.1) Ifnoneof theright-shiftedy-jobs inscheduleS(B,+x) result ina latenessgreater than thecurrent thresholdL(δ) (all these jobsbeingcompletedwithin the intervalofbinB), then job i is included,andthenextx-job fromthe list is similarlyconsidered. Weneedthe following lemmatocomplete thedescriptionof thesecondpass. Lemma3. If atStep (B), the right-shiftedy-joby results ina latenessgreater than the thresholdvalue L(δ), then therearises anewkernelK consistingof solelyType (a)y-jobs including joby. Proof. Since the latenessof joby surpassesL(δ), it formspartofanewlyarisenkernel, thedelaying emerging jobofwhich isx. Furthermore (similarlyas inLemma1),kernelK cannotcontainanyType (b)y-job,asotherwise, suchay-jobwouldhavebeen includedwithin the idle timeinterval inwhich jobx is included.Hence, thatType(b)y-jobcouldnotsucceed jobx. (B.2) If thecondition inLemma3issatisfied, thenthecorrespondingnewkernel isdeclared, andthecurrentsetofkernelsandbins isupdated. Similarly,as inStep2, thefirstpass is called for thefirst newlydeclaredbin (initiatedat timemoment t′) from thenewly updatedpartition. (B.3) If the latenessofsomey-jobsurpasses the thresholdL(δ) inscheduleS(B,+x), thenthe nextx-job fromthe list is similarlyprocessedfromStep(A). (B.4) If all thex-jobs fromthe listhavebeenprocessed, thenthesecondpass forschedulingbin Bcompletes. The following theorem tackles a frontier between the polynomially solvable instances and intractable ones for finding a Pareto-optimal frontier (the two relatedNP-hard problems are the schedulingproblemwithourprimaryobjectiveandthederivedbinpackingproblem): 52