Worst-case performance analysis of some approximation

JSchedDOI10.1007/s10951-015-0467-4Worst-caseperformanceanalysisofsomeapproximationalgorithmsforminimizingmakespanandflowtimePeruvembaSundaramRavi1·LeventTunçel2·MichaelHuang3©SpringerScience+BusinessMediaNewYork2016AbstractIn1976,CoffmanandSethiconjecturedthatanaturalextensionofLPTlistschedulingtothebicriteriaschedulingproblemofminimizingmakespanoverflowtime-optimalschedules,calledtheLDalgorithm,hasasimpleworst-caseperformancebound:5m−24m−1,wheremisthenum-berofmachines.Westudythestructureofpotentialminimalcounterexamplestothisconjecture,providesomenewtoolsandtechniquesfortheanalysisofsuchalgorithms,andprovethattoverifytheconjecture,itsufficestoanalyzethefollow-ingcase:foreverym≥4,n∈{4m,5m},wherenisthenumberofjobs.KeywordsParallelidenticalmachines·Makespan·Totalcompletiontime·Approximationalgorithmsforscheduling1IntroductionVariousperformancecriteriamaybeusedtoschedulenindependentjobsonmparallelidenticalmachines.Inappli-BPeruvembaSundaramRavipravi@wlu.caLeventTunçelltuncel@uwaterloo.caMichaelHuangMichael-Huang@u.northwestern.edu1OperationsandDecisionSciences,SchoolofBusinessandEconomics,WilfridLaurierUniversity,Waterloo,ONN2L3C5,Canada2DepartmentofCombinatoricsandOptimization,FacultyofMathematics,UniversityofWaterloo,Waterloo,ONN2L3G1,Canada3Toronto,Canadacationswherework-in-processinventoryisveryhighlyvalued(resultinginpotentiallyhugework-in-processinven-torycosts),orinapplicationswherethetotaltimespentinthesystemmustbeminimized,afundamentalobjectivefunc-tionofchoicewouldbethem