Operations Research Transactions ›› 2019, Vol. 23 ›› Issue (3): 1-14.doi: 10.15960/j.cnki.issn.1007-6093.2019.03.001
ZHANG Guochuan1,*, CHEN Lin2
Received:
2019-05-03
Published:
2019-09-09
CLC Number:
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 ki-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 ki-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. |
[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. |
Viewed | ||||||
Full text |
|
|||||
Abstract |
|
|||||