Page - 55 - in Algorithms for Scheduling Problems

Algorithms 2018,11, 80 anexponentofn. In theoryandpractice,wemaytakeoneof the twoalternativeoptions: eitherwetry all suchpossiblenon-dominatedsubsetsbuildinganimplicitenumerativealgorithm,orwemayrather chooseaheuristicapproachgeneratingafixednumberof“themostpromising”subsetsofsubstitution jobs inpolynomial time. Basedonourgeneral framework,both implicitenumerationandheuristic algorithmsmightbe implemented indifferentways. Thestudyofsuchalgorithms,whichwouldrely ontheresultsofnumericalexperiments, isbeyondthescopeof thispaperandcouldratherbeasubject of independentresearch. 6.Conclusions We have proposed a general framework for the solution of a strongly NP-hard bi-criteria schedulingproblemonasinglemachinewiththeobjectives tominimize themaximumjoblateness and themakespan. Theorem2 specifies explicitly the nature of the problem instances forwhich theParetooptimal frontier canbe found inpolynomial time. Findinga feasible solutionwith the maximumjob latenessnotexceedingsomeconstant thresholdbecomes intractable if thefirst condition in the theoremisnotsatisfied.Relyingonthecomputationalexperiments from[9],wehaveobserved thatalreadyforsmall trialδ’s, thebinswouldhavebeenscheduledinPhase1, i.e.,noIA(b2)would arise inPhase1. Inaddition, since therewill benoavoidablegap leftwithin thebins for these δ’s, thesecondcondition inTheorem2wouldbesatisfied,andPhase1wouldsuccessfullycomplete in polynomial time.Wehavealsoobservedthat for themajorityof the testedprobleminstances from[9], bothobjectivecriteriaweresimultaneouslyminimizedor themaximumjob latenesswasveryclose to theoptimum,whereas themakespanwasoptimal. Theoretically,weareunable toguaranteesucha behavior,andhence,wedescribedhowthesolutionprocesscanproceedinPhase2.Wehaveshown that it suffices toenumeratesomesubsetsof thesubstitution jobsandgenerate theresultant feasible schedules.Withacompleteenumeration,weguarantee thatoneof thesesolutionswill respectagiven threshold,unless thereexistsnosuchafeasibleschedule. Inpractice, if acompleteenumerationofall dominant subsets turnsout to takeanadmissible time,wemay“switch” toheuristicmethods that enumerateaconstantnumberofthe“mostpromising”subsetsandthecorrespondingfeasiblesolutions (In the lattercase, theoretically, it ispossible thatwefail tocreatea feasibleschedulerespecting the thresholdwhere such a feasible schedule exists. Then, the Pareto frontier that the algorithmwill generatewillmiss thecorrespondingPareto-optimalsolution, i.e., it willnotbe“complete”.). By partitioning the scheduling horizon into kernel and bin intervals, we have reduced the problemofminimizing themakespan ina feasible schedule respectingagiven threshold to thatof minimizing the gaps in the bins in that schedule. Bin packingproblemswith this objective have been extensively studied in the literature, and anumber of efficient enumeration algorithms and also heuristicsswith good theoretical and also practical behavior exist. We showed how such a heuristicmethodcanbeadoptedforpackingourbinswith jobswithrelease timesandduedates (the latter jobparameters impose additional restrictions, notpresent inbinpackingproblems). In this way,our frameworkhasreducedthebi-criteriaschedulingproblemtotheabovetwosingle-criterion problems, inducingfourbasic typesofalgorithmsforthebi-criteriaproblem(dependingonwhetheran exactorheuristicmethodis incorporatedforeitherof the twoproblems). For thefuturework, itwould be interestingto testparticular implementationsof thesealgorithmsandtoverify theirperformance forprobleminstances thatsignificantlydiffer fromthose tested in [9]. Conflictsof Interest:Theauthorsdeclarenoconflictof interest. References 1. Garey, M.R.; Johnson, D.S. Computers and Intractability: A Guide to the Theory of NP—Completeness; W.H.FreemanandCompany: SanFrancisco,CA,USA,1979. 2. Jackson, J.R. Schedulig a Production Line toMinimize theMaximumTardiness. InManegement Scince ResearchProject,UniversityofCalifornia;OfficeofTechnicalServices: LosAngeles,CA,USA,1955. 55