Page - 42 - in Algorithms for Scheduling Problems

Algorithms 2018,11, 80 According to the conventional three-fieldnotation introducedbyGrahamet al., ourprimary problemwith theobjective tominimizemaximumjob lateness (thesecondaryone tominimize the makespan, respectively) isabbreviatedas1|rj|Lmax (1|rj|Cmax, respectively);here in thefirstfield, the single-machine environment is indicated; the secondfield specifies the jobparameters; and in the thirdfield, theobjectivecriterion isgiven. Theproblem1|rj|Lmax isknowntobestronglyNP-hard (GareyandJohnson [1]),whereas1|rj|Cmax is easily solvablebyagreedyalgorithmthat iteratively includesanyearliest released jobat its release timeor thecompletion timeof the latest so farassigned job,whichevermagnitude is larger. AlthoughbeingstronglyNP-hard, the formerproblemcanbe efficiently approximated. AvenerableO(n logn) two-approximation algorithm that is commonly used forproblem1|rj|Lmax wasoriginallyproposedby Jackson [2] for theversionof theproblem without release timesand thenwasextendedbySchrage [3] to take intoaccount job release times. This heuristics, that is also referred to as theED (EarliestDuedate) heuristics, iteratively, at each schedulingtime t (givenbyjobreleaseorcompletiontime),amongthejobsreleasedbytime t, schedules theonewiththesmallestduedate. Letusnotehere that, in termsof theminimizationof themakespan, theEDheuristicshasan importantadvantage that it createsnomachine-idle timethatcanbeevaded. Potts [4] showedthatbyarepeatedapplicationof theheuristicsO(n) times, theperformanceratiocan beimprovedto3/2resultinginanO(n2 logn) timeperformance. Later,HallandShmoys[5] illustrated that theapplicationof theEDheuristics to theoriginalandaspecially-definedreversedproblemmay lead toa further improvedapproximationof4/3. NowickiandSmutnicki [6]haveshownthat the approximationratio3/2canalsobeachievedin timeO(n logn). Inpractice, theEDheuristics turned out to be themost efficient fast solutionmethod forproblem1|rj|Lmax, far better thanonewould suggestbasedontheabovetheoreticalworst-caseperformanceratio (seeLarsonetal. [7],Kiseetal. [8] andVakhaniaetal. [9]).Weshall reveal thebenefitof suchperformance forourbi-criteriascheduling problemlater. As for the exact solution methods for problem 1|rj|Lmax, the branch-and-bound algorithm with good practical behavior was proposed in McMahon and Florian [10] and Carlier [11] (thepractical behaviorof these twoalgorithmswascomparedalsomore recentlybySadykovand Lazarev[12]). Twomoreexactimplicitenumerativealgorithmswereproposed, inGrabowskietal. [13] andLarsonetal. [14].Morerecently,PanandShi [15]andLiu[16]presentedotherbranch-and-bound algorithms (in the latter reference, the version with precedence constraints was studied). Thepreemptivesetting1|rj,pmtn|Lmax iseasilysolvedbythepreemptiveversionofJackson’sextended heuristics,as italways interruptsnon-urgent jobs in favorofanewly-releasedmoreurgentone. In fact, thepreemptiveEDheuristics isalsouseful for thesolutionof thenon-preemptiveversion,as itgivesa strong lowerboundfor the latterproblem(see, forexample,GharbiandLabidi [17] forarecentstudy onthissubject). Theversion inwhicha feasible schedulemaynot includeany idle time interval, abbreviated 1|rj,nmit|Lmax, is stronglyNP-hardaccording toLenstra et al. [18] (minimizationof themakespan andthatof the lengthof idle time intervalsare closely relatedobjectives). Theproblemadmits the sameapproximationas theunrestrictedversion;asKacemandKellerer [19]haveobserved, jobrelease timescanbeadoptedsothat theEDheuristicsandPotts’sabove-mentionedextensionmaintain the sameapproximationratio forproblem1|rj,nmit|Lmax as for1|rj|Lmax.Hoogeveenhasconsideredthe nomachine idle timeversion in thebi-criteria setting. Insteadofminimizing the lateness, hehas introducedtheso-calledtarget start time sjof job j; sj is thedesirablestarting timefor job j, similarly to the duedate dj being the desirable completion time for job j. Then, besides theminimization of themaximumjob lateness, themaximumjobpromptness (thedifferencebetweenthe targetand real start times of that job) can also beminimized. The abovepaper considers the corresponding bi-criteria schedulingproblemandfinds thePareto-optimal set of feasible solutions. Lazarev [20] andLazarevetal. [21]haveproposedapolynomial timesolutionfindingthePareto-optimalset for twospecial casesofourbi-criteriaproblemwithspecially-ordered jobparametersandequal-length jobs, respectively.Anexactenumerativealgorithmfor theno idle timeproblemwith theobjective to 42