负载均衡问题

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.