Page - 44 - in Algorithms for Scheduling Problems

Algorithms 2018,11, 80 2.Complexityof theBi-ObjectiveProblem In thissection,wewill seewhyfindingthePareto-optimal frontierof feasiblesolutions forour bi-criteriaschedulingproblemisNP-hard. In the Introduction,wegavean intuitivedescriptionof the Pareto-optimalityconcept (foradetailedguidelineonmulti-objectiveoptimization, thereadermay havea lookat, forexample,Ehrgott [24]).Moreformally, inabi-criteriaoptimizationproblem, two objective functions f1 and f2 over thesetF of feasible solutions isgiven. These functionsmightbe mutuallycontradictory;hence, theremayexistnofeasiblesolutionminimizingbothobjectivefunctions simultaneously (consideringtheminimizationversion).Moreprecisely, ifF∗i is theoptimalvalueofa single-criterionproblemwiththeobjective tominimize function fi, thentheremayexistnofeasible solutiontotheproblemthatattainssimultaneouslybothoptimalvaluesF∗1 andF ∗ 2 . Inthissituation, it is reasonable to lookfor feasiblesolutions thataresomehowacceptable forboth theobjective functions. Acommonly-useddominancerelation isdefinedas follows. Solution σ1 ∈ F dominates solution σ2 ∈ F if fiσ1 < fiσ2, for i = 1,2; in fact, we allow≤, insteadof< foreither i=1or i=2,andrequirehavingat leastonestrict inequality. Now,werefer toσ∈F asaPareto-optimalsolution ifnoothersolutionfromsetFdominates it, andwecall thesetofall suchsolutions thePareto-optimal frontierof feasiblesolutions. Forming a Pareto-optimal frontier of feasible solutionsmay not be easy; for instance, the corresponding single-objectiveproblemsmayalreadybe intractable (clearly, the solutionof abi-objective setting requires thesolutionof thecorrespondingsingle-objectivesettings). Considernowthetwobasicobjectivefunctionsdealtwith inthispaper, themaximumjoblateness andthemakespan. Thetwocorrespondingsingle-objectiveproblemsare1|rj|Lmax and1|rj|Cmax. Thetwoobjectivecriteriaarecontradictory, i.e.,minimizingthemaximumjoblatenessLmaxdoes not necessarilyminimize themakespanCmax, and vice versa: it can be easily seen that an optimal scheduleminimizingLmaxmaycontainavoidablegapsandhencemaynotminimizeCmax. Forexample, consideraninstanceof1|rj|Lmaxwithtwojobswith r1=0,r2=3,p1= p2=5,d1=20,d2=9. Inthe scheduleminimizing Lmax, there is a gap [0,3); Job 2 is included at its release time and is followed by Job 1, whereas in the scheduleminimizingCmax, Job 1 starts at its release time and is followed by Job 2. Themaximum job lateness and themakespan in the first and the second schedules are −1and13(respectively)and1and10(respectively). Below,westaterelatedPareto-optimalityproblems. Problem 1. Among all feasible schedules with a givenmakespan, find onewith theminimummaximum job lateness. Problem 2. Among all feasible schedules with a given maximum job lateness, find one with the minimummakespan. Clearly,Problem1isstronglyNP-hardsince,asearliermentioned,problem1|rj|Lmax is strongly NP-hard[1].Ontheotherhand,problem1|rj|Cmax caneasilybesolvedbythefollowinglinear-timelist schedulingalgorithm,which leavesnoidle timeinterval thatcanbeavoided: ateveryschedulingtime, statingfromtheminimumjobrelease time, includeanyreleased job,update thecurrentscheduling timeas themaximumbetween the completion timeof that job and thenextminimum job release timeofanunscheduled job,andrepeat theprocedureuntilall jobsarescheduled(amodificationof thisgreedyalgorithmthatat eachscheduling time,amongthereleased jobs, includesonewith the minimumduedate is theEDheuristicsmentioned in the Introduction). Thisgreedysolutionalso providesapolynomial-timesolutionfor thedecisionversionofproblem1|rj|Cmax inwhichonewishes toknowif thereexistsa feasibleschedulewithsomefixedmakespanM. Indeed, ifM is less thanthe optimum, thenclearly, theanswer is“no”. IfM isgreater thanorequal to theminimummakespan M∗, then theanswer is“yes”:wecan introduce inaschedulewith themakespanM∗gapswitha total lengthM−M∗, appropriately, so that theresultantmakespanwillbeexactlyM. 44