Page - 45 - in Algorithms for Scheduling Problems

Algorithms 2018,11, 80 To show that Problem 2 is stronglyNP-hard, we prove that its decision version is strongly NP-complete. Let M be some threshold value for the makespan. Without loss of generality, weassumethat this threshold isattainable, i.e., there isa feasibleschedulewith theobjectivevalueM. Then, thedecisionversionofProblem2canbeformulatedas follows: Problem2-D.Foran instanceofproblem1|rj|Lmax (the input), amongall feasible scheduleswitha givenmaximumjob lateness,does thereexistonewith themakespannotexceedingmagnitudeM (here, theoutput isa“yes”ora“no”answer)? Theorem1. Problem2-Dis stronglyNP-complete. Proof. Tobeginwith, it is easy tosee that theproblemis inclassNP.First,weobserve that thesize of an instance of problem1|rj|Lmax with n jobs isO(n). Indeed, every job jhas threeparameters, rj,pj and dj; letMbe themaximumsuchmagnitude, i.e., themaximumamongall jobparameters. Then, the number of bits to represent ourproblem instance is boundedaboveby 3n logM. Since constant M fitswithin a computerword, the size of the problem isO(n). Now, given a feasible schedulewithsomemaximumjoblateness,wecanclearlyverify itsmakespaninnomorethann steps, which isapolynomial in thesizeof the input.Hence,Problem2-Dbelongs toclassNP. Next,weuse the reduction fromastronglyNP-complete three-PARTITIONproblemto show theNP-hardnessofourdecisionproblem. In three-PARTITION,wearegivenasetAof3melements, their sizesC={c1,c2, . . . ,c3m}andanintegernumberBwith 3m ∑ i=1 ci=mB,whereas thesizeofevery element fromsetA isbetweenB/4andB/2.Weareaskedif thereexists thepartitionofsetA intom (disjoint) setsA1, . . . ,Am suchthat thesizeof theelements ineverysubset sumsuptoB. Given an arbitrary instance of three-PARTITION,we construct our scheduling instancewith 3m+m jobswith the total lengthof n ∑ ι=1 cι+mas follows.Wehave3mpartition jobs1,. . . ,3mwith pi= ci, ri=0anddi=2mB+m, for i=1,. . . ,3m. Besides,wehavem separator jobs j1, . . . , jmwith pjι = 1, rjι = Bι+ ι−1, djι = Bι+ ι. Note that this transformation creatinga scheduling instance ispolynomialas thenumberof jobs isboundedbythepolynomial inm, andallmagnitudescanbe represented inbinaryencoding inO(m)bits. First,weeasilyobserve that thereexist feasible schedules inwhich themaximumjob lateness is zero:wecan just schedule theseparator jobsat their release timesand include thepartition jobs arbitrarilywithoutpushinganyseparator job. Now,wewish toknowwhetheramongthe feasible scheduleswith themaximumjob latenessofzero there isonewithmakespanmB+m.Weclaimthat thisdecisionproblemhasa“yes”answer iff thereexistsasolutionto three-PARTITION. Inonedirection, suppose three-PARTITIONhasasolution. Then,weschedule thepartition jobs corresponding to the elements fromsetA1within the interval [0,B] andpartition jobs fromsetAi within the interval [(i−1)B+ i−1, iB+ i−1], for i=2,. . . ,m (weschedule the jobs fromeachgroup inanon-delay fashion,using, for instance, theEDheuristics).Weschedule theseparator job jiwithin the interval [iB+ i−1, iB+ i], for i=1,. . . ,m. Therefore, the latest separator jobwillbecompletedat timemB+m, andthemakespanin theresultantschedule ismB+m. Intheotherdirection,supposethereexistsafeasiblescheduleSwithmakespanmB+m. Sincethe total sumof jobprocessingtimes ismB+m, theremayexistnogapinthatschedule.However, then, the time intervalof lengthBbeforeeveryseparator jobmustbefilled incompletelywith thepartition jobs,whichobviouslygivesasolutionto three-PARTITION. 3.BasicDefinitionsandProperties Thissectioncontainsnecessarypreliminaries to theproposedframework includingsomeuseful properties of the feasible schedules created by the ED heuristics (we call them ED-schedules). Our approach is basedon the analysis of theproperties ofED-schedules. This analysis is initially carriedout for thedecisionversionof single-criterionproblem1|rj|Lmax: we shall particularly be 45