您好,欢迎访问知识创客N-你的免费文库

上传文档

当前位置:首页 > 论文下载 > 国外论文 > Worst-case performance analysis of some approximation

Worst-case performance analysis of some approximation

二扫码支付 微信
二扫码支付 支付宝

还剩... 页未读,继续阅读

免费阅读已结束,点击付费阅读剩下 ...

¥ 0 元,已有21人购买

免费阅读

阅读已结束,您可以下载文档离线阅读

¥ 0 元,已有2人下载

免费下载
文档简介:

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

文档达人
文档达人
  • 10722

    文档
  • 64.1

    金币
Ta的主页 发私信

10722篇文档

评论

发表评论
< /15 > 免费下载 ¥ 0 元

Powered by DS文库

Copyright © 知识创客N-你的免费文库 All Rights Reserved. 蜀ICP备2020030266号-1
×
保存成功