负载均衡问题

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

Abstract

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

CLC Number:

O221.7

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

References

[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

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics

Comments

[1]	CHEN Feng. Research and application of operations research on intelligent scheduling decision support system for automotive outbound logistics [J]. Operations Research Transactions, 2021, 25(3): 37-73.
[2]	LIU Zhiping. Some advances in gene regulatory network inference [J]. Operations Research Transactions, 2021, 25(3): 173-182.
[3]	YU Shanshan, JIN Miaomiao, LUO Wenchang. Approximation scheme for rescheduling on a single machine with job delay and rejection [J]. Operations Research Transactions, 2021, 25(2): 104-114.
[4]	SHEN Yindong, QIAN Zhuang, LI Yuanyuan. A survey on driver scheduling in public transportation [J]. Operations Research Transactions, 2021, 25(1): 1-16.
[5]	HUANG Jidan, ZHENG Feifeng, XU Yingfeng, LIU Ming. Parallel machine scheduling with deteriorating installation times in the MapReduce system [J]. Operations Research Transactions, 2020, 24(4): 93-106.
[6]	ZHANG Yuzhong, LI Shuguang. Scheduling with tree-hierarchical processing set restrictions [J]. Operations Research Transactions, 2020, 24(4): 107-112.
[7]	JIANG Xiaoyan, SHUAI Tianping. Online MapReduce scheduling on two uniform machines [J]. Operations Research Transactions, 2020, 24(3): 57-66.
[8]	LU Shuxiang, Lü Changhong, QIN Tao. An algorithm based on makespan lower bound for quay crane schedule problem in container terminals [J]. Operations Research Transactions, 2020, 24(3): 67-76.
[9]	ZHONG Weiya, SHI Yimei. Robust optimization of rehearsal scheduling under uncertain duration [J]. Operations Research Transactions, 2020, 24(3): 77-86.
[10]	ZHANG Yuzhong. A survey on job scheduling with rejection [J]. Operations Research Transactions, 2020, 24(2): 111-130.
[11]	CHEN Rubing, YUAN Jinjiang. Single-machine scheduling to minimize total weighted late work with positional due-indices [J]. Operations Research Transactions, 2020, 24(2): 131-144.
[12]	LIU Xiaoxia, YU Shanshan, LUO Wenchang. Approximation algorithms for single machine parallelbatch scheduling with release dates subject to the number of rejected jobs not exceeding a given threshold [J]. Operations Research Transactions, 2020, 24(1): 131-139.
[13]	WANG Yizhan, ZHANG An, CHEN Yong, CHEN Guangting. An approximation algorithm for reclaimer scheduling [J]. Operations Research Transactions, 2020, 24(1): 147-154.
[14]	GOU Yan, DAI Qin, ZHANG Xingong. Scheduling problem with time-and-position-dependent effect on two parallel machines environments [J]. Operations Research Transactions, 2019, 23(4): 86-94.
[15]	LI Ganggang, LU Xiwen. An improved algorithm for single-machine scheduling problem with a period of maintenance to minimize total delivery time [J]. Operations Research Transactions, 2019, 23(4): 95-104.