An improved algorithm for online machine minimization
作者： Yossi Azar , Sarel Cohen
DOI: 10.1016/J.ORL.2017.11.013
关键词:
摘要: Abstract The online machine minimization problem seeks to design a preemptive scheduling algorithm on multiple machines — each job j arrives at its release time r , has be processed for p units, and must completed by deadline d . goal is minimize the number of uses. We improve O ( log m ) -competitive Chen, Megow Schewior (SODA 2016) provide an algorithm.
sci-hub.se 参考文章(21)
Julia Chuzhoy, Paolo Codenotti, Erratum: Resource Minimization Job Scheduling Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques. pp. E1- E1 ,(2009) , 10.1007/978-3-642-03685-9_54
章治郎 室, Michael R.Garey/David S.Johnson 著, "COMPUTERS AND INTRACTABILITY A guide to the Theory of NP-Completeness", FREEMAN, A5判変形判, 338+xii, \5,217, 1979 情報処理. ,vol. 21, pp. 902- 903 ,(1980)
Michael L. Dertouzos, Control Robotics: The Procedural Control of Physical Processes. ifip congress. pp. 807- 813 ,(1974)
Nicole Megow, Kevin Schewior, Lin Chen, An O(log m)-competitive algorithm for online machine minimization symposium on discrete algorithms. pp. 155- 163 ,(2016) , 10.5555/2884435.2884447
J. Chuzhoy, S. Guha, S. Khanna, J. Naor, Machine minimization for scheduling jobs with interval constraints foundations of computer science. pp. 81- 90 ,(2004) , 10.1109/FOCS.2004.38
Mong-Jen Kao, Jian-Jia Chen, Ignaz Rutter, Dorothea Wagner, Competitive Design and Analysis for Machine-Minimizing Job Scheduling Problem Algorithms and Computation. pp. 75- 84 ,(2012) , 10.1007/978-3-642-35261-4_11
W. A. Horn, Some simple scheduling algorithms Naval Research Logistics Quarterly. ,vol. 21, pp. 177- 185 ,(1974) , 10.1002/NAV.3800210113
Cynthia A. Phillips, Cliff Stein, Eric Torng, Joel Wein, Optimal time-critical scheduling via resource augmentation (extended abstract) symposium on the theory of computing. pp. 140- 149 ,(1997) , 10.1145/258533.258570
M. R. Garey, D. S. Johnson, Two processor scheduling with start times and deadlines SIAM Journal on Computing. ,vol. 6, pp. 416- 426 ,(1977) , 10.1137/0206029
Michael R. Garey, David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness ,(1979)