| 负载均衡问题 |
| |
| 引用本文： | 张国川,陈林.负载均衡问题[J].运筹学学报,2019,23(3):1-14. |
| |
| 作者姓名： | 张国川 陈林 |
| |
| 作者单位： | 1. 浙江大学计算机学院, 杭州 310058;2. 美国德克萨斯理工大学计算机系 |
| |
| 基金项目： | 国家自然科学基金（No.11531014） |
| |
| 摘 要： | 自Ron Graham20世纪60年代发表第一篇负载均衡算法的论文以来,平行机排序作为组合优化近似算法理论的首个问题引起了学界的广泛兴趣,其本身研究的不断深化也一路见证了该领域的发展历程.介绍负载均衡问题的来龙去脉,特别是作者所在团队在相关问题的研究进展,从算法和复杂性不同的视角分析经典问题的计算本质,并对未来的研究提出一些建议.
|
| 关 键 词： | 组合优化 排序 复杂性 近似算法 在线算法 |
| 收稿时间： | 2019-05-03 |
The load balancing problem |
| |
| ZHANG Guochuan,CHEN Lin.The load balancing problem[J].OR Transactions,2019,23(3):1-14. |
| |
| Authors: | ZHANG Guochuan CHEN Lin |
| |
| Institution: | 1. College of Computer Science, Zhejiang University, Hangzhou 310058, China;2. Department of Computer Science, Whitacre College of Engineering, Texas Tech University, 902 Boston Ave, Lubbock, TX 79409, USA |
| |
| Abstract: | Since the seminal paper on load balancing by Ron Graham in 1960's, parallel machine scheduling, served as the very first problem in approximation algorithms of combinatorial optimization, has attracted a great attention. The improvement on load balancing has also witnessed the birth and grow of the research field. In this paper we will present a brief state-of-art of this fundamental problem. In particularly we will introduce several achievements made by our group, which offer some insights on the approximability and hardness from different angles. A couple of potentially interesting questions will be posed as well. |
| |
| Keywords: | combinatorial optimization scheduling hardness approximation algorithms online algorithms |
| 本文献已被 CNKI 等数据库收录！ |
| 点击此处可从《运筹学学报》浏览原始摘要信息 |
| 点击此处可从《运筹学学报》下载免费的PDF全文 |
|
