More Web Proxy on the site http://driver.im/

article

Online Scheduling with Bounded Migration

Authors:

Naveen Sivadasan,

Martin SkutellaAuthors Info & Claims

Mathematics of Operations Research, Volume 34, Issue 2

Pages 481 - 498

https://doi.org/10.1287/moor.1090.0381

Published: 01 May 2009 Publication History

Abstract

Consider the classical online scheduling problem, in which jobs that arrive one by one are assigned to identical parallel machines with the objective of minimizing the makespan. We generalize this problem by allowing the current assignment to be changed whenever a new job arrives, subject to the constraint that the total size of moved jobs is bounded by some constant times the size of the arriving job. This constant is called the migration factor. For small migration factors, we obtain several simple online algorithms with constant competitive ratio. We also present a linear time “online approximation scheme,” that is, a family of online algorithms with competitive ratio arbitrarily close to 1 and constant migration factor.

References

[1]

Afrati, F., Bampis, E., Chekuri, C., Karger, D., Kenyon, C., Khanna, S. and Milis, I., "Approximation schemes for minimizing average weighted completion time with release dates," Proc. 40th Annual IEEE Sympos. Foundations Comput. Sci., New York, pp. 32-43, 1999.

Digital Library

[2]

Albers, S., "Better bounds for online scheduling," SIAM J. Comput., v29, pp. 459-473, 1999.

Digital Library

[3]

Albers, S., "Online algorithms: A survey," Math. Programming, v97, pp. 3-26, 2003.

[4]

Andrews, M., Goemans, M. X. and Zhang, L., "Improved bounds for on-line load balancing," Algorithmica, v23, pp. 278-301, 1999.

[5]

Azar, Y. and Epstein, L., "On-line machine covering," J. Algorithms, v1, pp. 67-77, 1998.

[6]

Bartal, Y., Fiat, A., Karloff, H. and Vohra, R., "New algorithms for an ancient scheduling problem," J. Comput. System Sci., v51, pp. 359-366, 1995.

Digital Library

[7]

Brinkmann, A., Salzwedel, K. and Scheideler, C., "Compact, adaptive placement schemes for non-uniform requirements," 14th ACM Sympos. Parallel Algorithms and Architectures, ACM, New York, pp. 53-62, 2002.

Digital Library

[8]

Chen, B., van Vliet, A. and Woeginger, G. J., "Lower bounds for randomized online scheduling," Inform. Processing Lett., v51, pp. 219-222, 1994.

Digital Library

[9]

Coffman, E. G., Garey, M. R. and Johnson, D. S., "An application of bin-packing to multiprocessor scheduling," SIAM J. Comput., v7, pp. 1-17, 1978.

Digital Library

[10]

Epstein, L., Levin, A., Bugliesi, M., Preneel, B., Sassone, V. and Wegener, I., "A robust APTAS for the classical bin packing problem," Automata, Languages and Programming, v4051, Springer, Berlin, pp. 214-225, 2006.

Digital Library

[11]

Fleischer, R. and Wahl, M., "Online scheduling revisited," J. Scheduling, v3, pp. 343-353, 2000.

[12]

Friesen, D. K., "Tighter bounds for the multifit processor scheduling algorithm," SIAM J. Comput., v13, pp. 170-181, 1984.

[13]

Garey, M. R. and Johnson, D. S., "Strong np-completeness results: Motivation, examples and implications," J. ACM, v25, pp. 499-508, 1978.

Digital Library

[14]

Graham, R. L., "Bounds for certain multiprocessing anomalies," Bell System Tech. J., v45, pp. 1563-1581, 1966.

[15]

Graham, R. L., "Bounds on multiprocessing timing anomalies," SIAM J. Appl. Math., v17, pp. 263-269, 1969.

[16]

Graham, R. L., Lawler, E. L., Lenstra, J. K. and Rinnooy Kan, A. H. G., "Optimization and approximation in deterministic sequencing and scheduling: A survey," Ann. Discrete Math., v5, pp. 287-326, 1979.

[17]

Hochbaum, D. S. and Hochbaum, D. S., "Various notions of approximation: Good, better, best, and more," Approximation Algorithms for NP-Hard Problems, Thomson, PWS Publishing Company, Boston, pp. 346-398, 1996.

Digital Library

[18]

Hochbaum, D. S. and Shmoys, D. B., "Using dual approximation algorithms for scheduling problems: Theoretical and practical results," J. ACM, v34, pp. 144-162, 1987.

Digital Library

[19]

Karger, D. R., Phillips, S. J. and Torng, E., "A better algorithm for an ancient scheduling problem," J. Algorithms, v20, pp. 400-430, 1996.

Digital Library

[20]

Langston, M. A., "Processor scheduling with improved heuristic algorithms," 1981.

[21]

Lenstra, H. W., "Integer programming with a fixed number of variables," Math. Oper. Res., v8, pp. 538-548, 1983.

Digital Library

[22]

Patterson, D., Gibson, G. and Katz, R., "A case for redundant arrays of inexpensive disks (RAID)," Proc. ACM SIGMOD'88, ACM, New York, pp. 109-116, 1988.

Digital Library

[23]

Rudin, J. F., "Improved bounds for the on-line scheduling problem," 2001.

[24]

Rudin, J. F. and Chandrasekaran, R., "Improved bounds for the online scheduling problem," SIAM J. Comput., v32, pp. 717-735, 2003.

Digital Library

[25]

Sahni, S., "Algorithms for scheduling independent tasks," J. ACM, v23, pp. 116-127, 1976.

Digital Library

[26]

Sanders, P., "Algorithms for scalable storage servers," SOFSEM 2004: Theory and Practice of Computer Science, LNCS, v2932, Springer, Berlin, pp. 82-101, 2004.

[27]

Sanders, P., Sivadasan, N., Skutella, M., Diaz, J., Karhumäki, J., Lepistö, A. and Sannella, D., "Online scheduling with bounded migration," Automata, Languages and Programming, v3142, Springer, Berlin, pp. 1111-1122, 2004.

[28]

Schrijver, A., Theory of Linear and Integer Programming, John Wiley & Sons, Chichester, UK, 1986.

Digital Library

[29]

Sgall, J., "A lower bound for randomized on-line multiprocessor scheduling," Inform. Processing Lett., v63, pp. 51-55, 1997.

Digital Library

[30]

Sgall, J., Fiat, A. and Woeginger, G. J., "On-line scheduling---A survey," Online Algorithms: The State of the Art, v1442, Springer, Berlin, pp. 196-231, 1998.

Digital Library

[31]

Sgall, J., "Personal communication," 2008.

[32]

Westbrook, J., "Load balancing for response time," J. Algorithms, v35, pp. 1-16, 2000.

Digital Library

[33]

Woeginger, G. J., "A polynomial-time approximation scheme for maximizing the minimum machine completion time," Oper. Res. Lett., v20, pp. 149-154, 1997.

Digital Library

Cited By

Mellou KMolinaro MZhou R(2024)The Power of Migrations in Dynamic Bin PackingProceedings of the ACM on Measurement and Analysis of Computing Systems10.1145/37004358:3(1-28)Online publication date: 10-Dec-2024
https://dl.acm.org/doi/10.1145/3700435
Foussoul AGoyal VKumar A(2024)Fully-Dynamic Load BalancingInteger Programming and Combinatorial Optimization10.1007/978-3-031-59835-7_14(182-195)Online publication date: 3-Jul-2024
https://dl.acm.org/doi/10.1007/978-3-031-59835-7_14
Räcke HSchmid SZabrodin RAgrawal KShun J(2023)Polylog-Competitive Algorithms for Dynamic Balanced Graph Partitioning for Ring DemandsProceedings of the 35th ACM Symposium on Parallelism in Algorithms and Architectures10.1145/3558481.3591097(403-413)Online publication date: 17-Jun-2023
https://dl.acm.org/doi/10.1145/3558481.3591097
Show More Cited By

Online Scheduling with Bounded Migration
1. Theory of computation
  1. Design and analysis of algorithms
    1. Approximation algorithms analysis
    2. Online algorithms
      1. Online learning algorithms
  2. Theory and algorithms for application domains
    1. Machine learning theory
      1. Reinforcement learning

Recommendations

Online Flexible Job Scheduling for Minimum Span
SPAA '17: Proceedings of the 29th ACM Symposium on Parallelism in Algorithms and Architectures

In this paper, we study an online Flexible Job Scheduling (FJS) problem. The input of the problem is a set of jobs, each having an arrival time, a starting deadline and a processing length. Each job has to be started by the scheduler between its arrival ...
Optimal algorithms for online single machine scheduling with deteriorating jobs

In many realistic scenarios of job processing, one job consumes a longer time to be satisfied with a later start time of processing. This phenomenon is known as job's deterioration effect. Such effect is unexplored in the context of online environment. ...
Competitive ratios for preemptive and non-preemptive online scheduling with nondecreasing concave machine cost

We consider an online scheduling problem where jobs arrive one by one and each job must be irrevocably scheduled on the machines. No machine is available initially. When a job arrives, we either purchase a new machine to process it or schedule it for ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Mathematics of Operations Research

Mathematics of Operations Research Volume 34, Issue 2

May 2009

256 pages

ISSN:0364-765X

Issue’s Table of Contents

Publisher

INFORMS

Linthicum, MD, United States

Publication History

Published: 01 May 2009

Received: 16 March 2007

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

55
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 30 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Mellou KMolinaro MZhou R(2024)The Power of Migrations in Dynamic Bin PackingProceedings of the ACM on Measurement and Analysis of Computing Systems10.1145/37004358:3(1-28)Online publication date: 10-Dec-2024
https://dl.acm.org/doi/10.1145/3700435
Foussoul AGoyal VKumar A(2024)Fully-Dynamic Load BalancingInteger Programming and Combinatorial Optimization10.1007/978-3-031-59835-7_14(182-195)Online publication date: 3-Jul-2024
https://dl.acm.org/doi/10.1007/978-3-031-59835-7_14
Räcke HSchmid SZabrodin RAgrawal KShun J(2023)Polylog-Competitive Algorithms for Dynamic Balanced Graph Partitioning for Ring DemandsProceedings of the 35th ACM Symposium on Parallelism in Algorithms and Architectures10.1145/3558481.3591097(403-413)Online publication date: 17-Jun-2023
https://dl.acm.org/doi/10.1145/3558481.3591097
Maack M(2023)Online load balancing on uniform machines with limited migrationOperations Research Letters10.1016/j.orl.2023.02.01351:3(220-225)Online publication date: 1-May-2023
https://dl.acm.org/doi/10.1016/j.orl.2023.02.013
Berndt SEpstein LJansen KLevin AMaack MRohwedder L(2023)Online bin covering with limited migrationJournal of Computer and System Sciences10.1016/j.jcss.2023.01.001134:C(42-72)Online publication date: 1-Jun-2023
https://dl.acm.org/doi/10.1016/j.jcss.2023.01.001
Levin A(2023)Online Minimization of the Maximum Starting Time: Migration HelpsAlgorithmica10.1007/s00453-023-01097-085:8(2238-2259)Online publication date: 26-Jan-2023
https://dl.acm.org/doi/10.1007/s00453-023-01097-0
Räcke HSchmid SZabrodin RAgrawal KLee I(2022)Approximate Dynamic Balanced Graph PartitioningProceedings of the 34th ACM Symposium on Parallelism in Algorithms and Architectures10.1145/3490148.3538563(401-409)Online publication date: 11-Jul-2022
https://dl.acm.org/doi/10.1145/3490148.3538563
Berndt SEberle FMegow N(2022)Online load balancing with general reassignment costOperations Research Letters10.1016/j.orl.2022.03.00750:3(322-328)Online publication date: 1-May-2022
https://dl.acm.org/doi/10.1016/j.orl.2022.03.007
Levin A(2022)Robust algorithms for preemptive scheduling on uniform machines of non-increasing job sizesInformation Processing Letters10.1016/j.ipl.2021.106211174:COnline publication date: 23-Apr-2022
https://dl.acm.org/doi/10.1016/j.ipl.2021.106211
Epstein LLevin A(2022)Starting time minimization for the maximum job variantDiscrete Applied Mathematics10.1016/j.dam.2021.10.013307:C(79-87)Online publication date: 30-Jan-2022
https://dl.acm.org/doi/10.1016/j.dam.2021.10.013
Show More Cited By

View Options

View options

Media

Figures

Other

Tables

View Issue’s Table of Contents