负载均衡问题

doi:10.15960/j.cnki.issn.1007-6093.2019.03.001

摘要/Abstract

摘要： 自Ron Graham20世纪60年代发表第一篇负载均衡算法的论文以来，平行机排序作为组合优化近似算法理论的首个问题引起了学界的广泛兴趣，其本身研究的不断深化也一路见证了该领域的发展历程.介绍负载均衡问题的来龙去脉，特别是作者所在团队在相关问题的研究进展，从算法和复杂性不同的视角分析经典问题的计算本质，并对未来的研究提出一些建议.

关键词: 组合优化, 排序, 复杂性, 近似算法, 在线算法

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.

Key words: combinatorial optimization, scheduling, hardness, approximation algorithms, online algorithms

中图分类号:

O221.7

张国川, 陈林. 负载均衡问题[J]. 运筹学学报, 2019, 23(3): 1-14.

ZHANG Guochuan, CHEN Lin. The load balancing problem[J]. Operations Research Transactions, 2019, 23(3): 1-14.

[1] Johnson S M. Optimal two-and three-stage productionschedules with set up times included[J]. Naval Research LogisticsQuarterly, 1954, 1, 61-68.
[2] Graham R L. Bounds for certain multi-processing anomalies[J]. Bell System Technical Journal, 1966, 45, 1563-1581.
[3] Potts C N, Strusevich V A. Fifty years of scheduling:asurvey of milestones[J]. Journal of Operational Research Society, 2009,60, S41-S68.
[4] McNaughton R. Scheduling with deadlines and loss functions[J]. Management Science, 1959, 6, 1-12.
[5] Graham R L. Bounds on multiprocessing timing anomalies[J]. SIAM Journal of Applied Mathematics, 1969, 17, 416-429.
[6] Hochbaum D S, Shmoys D B. Using dual approximationalgorithms for scheduling problems:practical and theoreticalresults[J]. Journal of the ACM, 1987, 34, 144-162.
[7] Alon N, Azar Y, Woeginger G J, et al. Approximationschemes for scheduling on parallel machines[J]. Journal onScheduling, 19981, 55-66.
[8] Jansen K, Klein K M, Verschae J. Closing the gap for makespan scheduling via sparsification techniques. In Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming (ICALP), 2016, 72:1-72.
[9] Galambos G, Woeginger G J. An on-line schedulingheuristic with better worst case ratio than Graham's list scheduling[J]. SIAM Journal on Computing, 1993, 22, 349-355.
[10] Fleischer R, Wahl M. On-line scheduling revisited[J].Journal of Scheduling,2000, 3, 343-353.
[11] RudinJ F, Chandrasekaran R. Improved bound for theonline scheduling problem[J]. SIAM Journal on Computing,2003, 32,717-735.
[12] Sgall J. On-line scheduling[M]. In A. Fiat and G.J. Woeginger,editors, Online Algorithms:The State of the Art, Springer, 1998, 196-231.
[13] Lenstra J K, Shmoys DB, Eva Tardos. Approximationalgorithms for scheduling unrelated parallel machines[J]. Mathematical Programing, 1990, 46, 259-271.
[14] Impagliazzo R, Paturi R, Zane F. Which problems havestrongly exponential complexity?[J]Journal of Computer and SystemScience, 2001, 63, 512-530.
[15] Lokshtanov D, Marx D, Saurabh S. Lower bounds based onthe Exponential Time Hypothesis[J]. Bulletin of the EATCS, 2011, 105,41-72.
[16] Chen L, Jansen K, Zhang G. On the optimality ofexact and approximation algorithms for scheduling problems[J]. Journal of Computer and System Sciences, 2018, 96, 1-32.
[17] Garey M R, Johnson D S. Computers and Intractability:AGuide to the Theory of NP-Completeness[M]. W. H.Freeman and Company.
[18] Chen L, Ye D, Zhang G. Approximating the optimal algorithm for online scheduling problems via dynamic programming[J]. Asia-Pacific Journal of Operational Research, 2015, 32.
[19] Albers S. Better bounds for online scheduling[J]. SIAMJournal on Computing, 1999, 29, 459-473.
[20] Günther E, Maurer O, Megow N, et al.A new approach to online scheduling:Approximating the optimal competitive ratio. In Proceedings of the 24th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2013, 118-128.
[21] Bhaskara A, Krishnaswamy R, Talwar K, et al.Minimum makespan scheduling with low rank processing times. In Proceedings of the 24 Annual ACM-SIAM Symposium on DiscreteAlgorithms (SODA), 2013, 937-947.
[22] Chen L, Marx D, Ye D, et al. Parameterized andapproximation results for scheduling with a low rank processing timematrix[J]. STACS, 2017, 22:1-14.
[23] Chen L, Ye D, Zhang G. An improved lower bound forrank four scheduling[J]. Operations Research Letters, 2014, 42, 348-350.
[24] Zhang C, Wang G, Liu X, et al. Approximatingscheduling machines with capacity constraints[J]. FAW, 2009, 283-292.
[25] Rushmeier R A, Hoffman K L, Padberg M. Recent advances inexact optimization of airline scheduling problems.George Mason University, 1995.
[26] Magazine M J, Ball M O. Sequencing of insertions in printedcircuit board assembly[J]. Operations Research, 1988, 36, 192-201.
[27] Bruglieri M, Ehrgott M, Hamacher H W, et al. Anannotated bibliography of combinatorial optimization problems withfixed cardinality constraints[J]. Discrete Applied Mathematics, 2006,154, 1344-1357.
[28] Kellerer H, Woeginger G. A tight bound for 3-partitioning[J]. Discrete Applied Mathematics, 1993, 45, 249-259.
[29] Kellerer H, Kotov V. A 7/6-approximation algorithm for3-partitioning and its application to multiprocessor scheduling[J].Information Systems and Operational Research, 1999, 37, 48-56.
[30] Babel L, Kellerer H, Kotov V. The k-partitioning problem[J]. Mathematical Methods of Operations Research, 1998, 47, 59-82.
[31] Dell'Amico M, Lori M, Martello S, et al. Lowerbounds and heuristic algorithms for the k_i-partitioning problem[J].European Journal of Operational Research, 2004, 171, 725-742.
[32] Woeginger G. A comment on scheduling two parallel machines withcapacity constraints[J]. Discrete Optimization, 2005, 2, 269-272.
[33] Jain K. A factor 2 approximation algorithm for the generalizedSteiner network problem[J]. Combinatorica, 2001, 39-60.
[34] Barna S, Aravind S. A new approximation technique forresource-allocation problems. In proceedings of the 1st AnnualSymposium on Innovations in Computer Science, 2010, 342-357.
[35] Kellerer H, Kotov V. A 3/2-approximation algorithm for k_i-partitioning[J]. Operations Research Letters, 2011, 39, 359-362.
[36] Chen L, Jansen K, Luo W, et al. An efficientPTAS for parallel machine scheduling with capacity constraints[J].COCOA, 2016, 608-623.
[37] Kannan R. Minkowski's convex body theorem and integerprogramming[J]. Mathematics of Operations Research, 1987, 12, 415-440.
[38] Eisenbrand F, Shmonin G. Caratheodory bounds for integercones[J]. Operations Research Letters, 2006, 34, 564-568.
[39] Shabtay D, Steiner G. A survey of scheduling withcontrollable processing times[J]. Discrete Applied Mathematics, 2007,155, 1643-1666.
[40] Chen J, Miranda A. A polynomial time approximationscheme for general multiprocessor job scheduling[J]. SIAM Journalon Computing, 2001, 31, 1-17.
[41] Jansen K, Porkolab L. General multiprocessor taskscheduling:Approximate solutions in linear time. In Proceedings of the 6th International Workshop on Algorithms and Data Structures (WADS 1999), 110-121.
[42] Jansen K, Mastrolilli M. Scheduling unrelated parallelmachines:linear programming strikes back. University of Kiel, 2010,Technical Report 1004.
[43] Jansen K, Porkolab L. Improved approximation schemes forscheduling unrelated parallel machines[J]. Mathematics ofOperations Research, 2001, 26, 324-338.
[44] Kellerer H, Strusevich V A. Scheduling paralleldedicated machines with the speeding-up resource[J]. NavalResearch Logistics, 2008, 55, 377-389.
[45] Kellerer H. An approximation algorithm for identicalparallel machine scheduling with resource dependent processingtimes[J]. Operations Research Letters, 2008, 36, 157-159.
[46] Chen L, Ye D, Zhang G. Parallel machine schedulingwith speed-up resources[J]. European Journal of OperationalResearch, 2018, 268, 101-112.

负载均衡问题

The load balancing problem

PDF

可视化

摘要/Abstract

引用本文

使用本文

相关文章 15

编辑推荐

Metrics

本文评价

[1]	赵弘欣, 孔令臣. 分散化投资组合的优化模型和方法研究[J]. 运筹学学报（中英文）, 2026, 30(1): 75-92.
[2]	陈荣军, 刘永财, 黄河, 唐国春. 单机供应链排序问题动态规划算法[J]. 运筹学学报（中英文）, 2026, 30(1): 171-178.
[3]	吴弘一, 王冬, 万龙, 罗文昌. 嵌套加工型限制下的混合分批平行机排序问题的近似算法[J]. 运筹学学报（中英文）, 2026, 30(1): 188-196.
[4]	李大伟, 李刚刚. 考虑人员不可用及工件带退化效应的单机排序问题[J]. 运筹学学报（中英文）, 2025, 29(4): 14-26.
[5]	夏倩, 张新功. 具有前瞻区间和不相容工件族的两台流水车间在线排序问题[J]. 运筹学学报（中英文）, 2025, 29(4): 103-111.
[6]	靳凯媛, 郑斐峰, 刘明. 考虑订单类型和准备时间的批处理机在线调度模型研究[J]. 运筹学学报（中英文）, 2025, 29(4): 231-240.
[7]	赵娣, 余金, 鲁习文. 单机两代理串行分批排序问题的近似算法[J]. 运筹学学报（中英文）, 2025, 29(2): 184-193.
[8]	袁园, 兰艳, 韩鑫. 带有维护窗口的调度问题的综述[J]. 运筹学学报（中英文）, 2025, 29(1): 1-18.
[9]	李娜, 马冉, 李龙, 张玉忠. 具有学习效应的预制构件生产调度研究[J]. 运筹学学报（中英文）, 2025, 29(1): 19-30.
[10]	崔同欣, 夏倩, 张新功. 基于松弛工期的总加权误工单机双代理排序问题[J]. 运筹学学报（中英文）, 2025, 29(1): 31-40.
[11]	杜诗翩, 顾满占. 带机器维护的最小化总误工数期望的随机排序问题研究[J]. 运筹学学报（中英文）, 2025, 29(1): 142-158.
[12]	李文杰, 杜智慧, 苏孟龙. 加工时间与运输时间具有一致性的单机NDP约束在线排序问题研究[J]. 运筹学学报（中英文）, 2024, 28(4): 18-28.
[13]	葛晴, 录岭法, 原晋江, 张利齐. 单机上一个与总完工时间及最大完工时间相关的工件可拒绝的ND双代理排序问题[J]. 运筹学学报（中英文）, 2024, 28(4): 66-74.
[14]	焦成文. 具有线性前瞻区间的单机平行批在线排序[J]. 运筹学学报（中英文）, 2024, 28(4): 111-116.
[15]	徐娟年, 马冉, 韩雯雯, 张玉忠. 工件权重带限制的最小化最大加权完工时间的单机在线排序问题[J]. 运筹学学报（中英文）, 2024, 28(2): 71-80.