Approximation

ApproximationalgorithmsforminimizingthetotalweightedtardinessonasinglemachineStavrosG.Kolliopoulos∗GeorgeSteiner†AbstractGivenasinglemachineandasetofjobswithduedates,theclassicalNP-hardproblemofschedulingtominimizetotaltardinessisawell-understoodone.LawlergaveanFPTASforitsometwentyyearsago.Ifthejobshavepositiveweightstheproblemofminimizingtotalweightedtardinessseemstobeconsiderablymoreintricate.Inthispaper,wegivesomeofthefirstapproximationalgorithmsforit.Weexaminefirsttheweightedproblemwithafixednumberofduedatesandwedesignapseudopolynomialalgorithmforit.WeshowhowtotransformthepseudopolynomialalgorithmtoanFPTASforthecasewheretheweightsarepolynomiallybounded.Forthecasewithanarbitrarynumberofduedatesandpolynomiallyboundedprocessingtimes,weprovideaquasipolynomialalgorithmwhichproducesaschedulewhosevaluehasanadditiveerrorproportionaltotheweightedsumoftheduedates.Wealsoinvestigatetheperformanceofalgorithmsforminimizingtherelatedtotalweightedlateworkobjective.1IntroductionWestudytheproblemofschedulingjobsonasinglemachinetominimizethetotalweightedtardiness.Wearegivenasetofnjobs.Jobj,1≤j≤n,becomesavailableattime0,hastobeprocessedwithoutinterruptionforanintegertimepj,hasaduedatedj,andhasapositiveweightwj.ForagivensequencingofthejobsthetardinessTjofjobjisdefinedasmax{0,Cj−dj},whereCjisthecompletiontimeofthejob.TheobjectiveistofindaprocessingorderofthejobswhichminimizesPnj=1wjTj.Inthe3-fieldnotationusedinschedulingtheproblemisdenoted1||PjwjTj.AccordingtoCongrametal.,1||PjwjTjisan“NP-hardarchetypalmachineschedulingprob-lem”whoseexactsolutionappearsverydifficultevenonverysmallinputs[2].Weproceedtoreviewwhatisknownonthecomplexityoftheproblem.Inthecaseofonemachineithaslongbeenknownthatanoptimalpreemptiveschedulehasthesametotalweightedtardinessasanopti-malnonpreemptiveschedule[13].EarlyontheproblemwasshowntobeNP-hardintheordinary∗DepartmentofInformaticsandTelecommunications,NationalandKapodistrianUniversityofAthens;(˜sgk).ResearchsupportedinpartbytheprogramEPEAKIIunderthetaskPYTHAGORASII(projecttitle:AlgorithmsandComplexityinNetworkTheory)whichisfundedbytheEuropeanSocialFund(75%)andtheGreekMinistryofEducation(25%).†ManagementScienceandInformationSystems,McMasterUniversity,1280MainStreetWest,Hamilton,On-tario,L8S4M4,Canada.ResearchpartiallysupportedbyNSERCGrantOG0001798;Correspondingauthor([e-mail]).1sensebyLenstraetal.[12]whenthejobshaveonlytwodistinctduedatesbyareductionfromtheknapsackproblem.ItwasshowntobestronglyNP-hardforanarbitrarynumberofduedatesin[9].MuchlaterYuan[15]showedthattheproblemremainsNP-hardevenforthecasewhereallthejobshaveacommonduedate.LawlerandMoore[11]havepresentedapseudopolynomialsolutionforthecasewhenalljobshaveasinglecommonduedate.Fromtheapproximationpointofviewthereisverylittleknown.Theonlycasethatseemstobebetterunderstoodistheusuallyeasiercaseofagreeableweights:inthatcasepjpiimplieswj≥wi.Lawlergaveapseudopolynomialalgorithmfortheagreeable-weightedcase[9].In1982heshowedhowtomodifythatalgorithmtoobtainafullypolynomial-timeapproximationschemeforthecaseofunitweights[10].Afullypolynomial-timeapproximationscheme(FPTAS)foraminimizationproblemisanalgorithmwhichforanyε0runsintimepolynomialin1/εandthesizeoftheinputandoutputsasolutionofcostatmost(1+ε)timestheoptimum.Afterthefirstpublicationofthiswork[7],thepaperbyCheng,Ng,YuanandLiuappeared[1].ThereitisshownthattheschedulewhichminimizesmaxjwjTjyieldsan(n−1)-approximationfor1||PjwjTj.Interestingly,thecomplexityoftheunitweightcase,1||PjTj,wasanopenproblemformanyyearsuntilDuandLeungshoweditisNP-hard[3].Inthispaperwemakeprogressontheproblemofminimizingthetotalweightedtardinessbyexaminingfirstthecasewherethenumberofdistinctduedatesisfixed.Ourmaincontributionisapseudopolynomialalgorithmwhosecomplexitydependsonthetotalprocessingtime.ThisimpliesthattheproblemisinPwhentheprocessingtimesarepolynomiallybounded.Wethenshowhowtomodifythepseudopolynomialalgorithmintwosteps:firstsothatitscomplexitydependsonanyupperboundonthemaximumtardinessofanoptimalscheduleandsecond,sothatityieldsanFPTASwhenthemaximumjobweightisboundedbyapolynomialinn.Ourmainapproachisbasedonviewingtheproblemashavingtopackthejobsintoafinitenumberofbinswherethecostofeachjobdependsonwhichbinitisassignedtoandsomejobsmaybesplitbetweentwobins.Hopefullysomeoftheideasweintroducecouldbeofuseforfurtherstudyofapproximatingthelong-opengeneralcasewithanarbitrarynumberofduedates.Forthegeneralcasewithanarbitrarynumberofdistinctduedateswegivearesultthatmaybeofinterestwhentheduedatesareconcentratedaroundsmallvalues.Undertheassumptionthatthemaximumprocessingtimeisboundedbyapolynomialinn,weprovideaquasipolynomialalgorithmwhichproducesaschedulewhosevaluehasanadditiveerrorequaltoδPjwjdjforanyfixedδ0.1||PjwjTjfallsintotheclassofNP-hardproblemswheretheoptimumvaluecanbezero.Thisrendersthenotionofamultiplicativeapproximationsomewhatproblematic.Additiveguaranteesmaybeofparticularinterestinthissetting.Weobtainthelatterresultbycombiningapartitionofthetimehorizonintogeometricallyincreasingintervalswithashiftoftheduedate