article

A Lower Bound on Deterministic Online Algorithms for Scheduling on Related Machines Without Preemption

Authors:

Tomáš Ebenlendr,

Jiří SgallAuthors Info & Claims

Theory of Computing Systems, Volume 56, Issue 1

Pages 73 - 81

https://doi.org/10.1007/s00224-013-9451-6

Published: 01 January 2015 Publication History

Abstract

We consider one-by-one online scheduling on uniformly related machines. The input is a sequence of machines with different speeds and a sequence of jobs with different processing times. The output is a schedule which assigns the jobs to the machines; the completion time of a machine is the sum of the processing times of jobs assigned to it divided by its speed. The objective is to minimize the maximal completion time. The jobs arrive one by one and each has to be assigned to one machine immediately and irrevocably without the knowledge of the future jobs. We prove a new lower bound of 2.564 on the competitive ratio of deterministic online algorithms for this problem, improving the previous lower bound of 2.438.

References

[1]

Aspnes, J., Azar, Y., Fiat, A., Plotkin, S., Waarts, O.: On-line load balancing with applications to machine scheduling and virtual circuit routing. J. ACM 44, 486---504 (1997)

Digital Library

Google Scholar

[2]

Azar, Y.: On-line load balancing. In: Fiat, A., Woeginger, G.J. (eds.) Online Algorithms: The State of the Art, pp. 178---195. Springer, Berlin (1998)

Crossref

Google Scholar

[3]

Bar-Noy, A., Freund, A., Naor, J.: New algorithms for related machines with temporary jobs. J. Sched. 3, 259---272 (2000)

Crossref

Google Scholar

[4]

Berman, P., Charikar, M., Karpinski, M.: On-line load balancing for related machines. In: Proc. 5th Workshop on Algorithms and Data Structures (WADS). Lecture Notes in Comput. Sci., vol. 1272, pp. 116---125. Springer, Berlin (1997)

Crossref

Google Scholar

[5]

Berman, P., Charikar, M., Karpinski, M.: On-line load balancing for related machines. J. Algorithms 35, 108---121 (2000)

Digital Library

Google Scholar

[6]

Cai, S.Y., Yang, Q.F.: Online scheduling on three uniform machines. Discrete Appl. Math. 160, 291---302 (2011)

Digital Library

Google Scholar

[7]

Cho, Y., Sahni, S.: Bounds for list schedules on uniform processors. SIAM J. Comput. 9, 91---103 (1980)

Digital Library

Google Scholar

[8]

Ebenlendr, T.: Combinatorial algorithms for online problems: semi-online scheduling on related machines. PhD thesis, Charles University, Prague (2011)

Google Scholar

[9]

Ebenlendr, T., Jawor, W., Sgall, J.: Preemptive online scheduling: optimal algorithms for all speeds. Algorithmica 53, 504---522 (2009)

Digital Library

Google Scholar

[10]

Epstein, L., Noga, J., Seiden, S.S., Sgall, J., Woeginger, G.J.: Randomized on-line scheduling for two uniform machines. J. Sched. 4, 71---92 (2001)

Crossref

Google Scholar

[11]

Epstein, L., Sgall, J.: A lower bound for on-line scheduling on uniformly related machines. Oper. Res. Lett. 26, 17---22 (2000)

Digital Library

Google Scholar

[12]

Han, F., Tan, Z., Yang, Y.: On the optimality of list scheduling for online uniform machines scheduling. Optim. Lett. 7, 1551---1571 (2012)

Crossref

Google Scholar

[13]

Je¿, ¿., Schwartz, J., Sgall, J., Békési, J.: Lower bounds for online makespan minimization on a small number of related machines. J. Sched. (2012).

Crossref

Google Scholar

[14]

Musitelli, A., Nicoletti, J.M.: Competitive ratio of list scheduling on uniform machines and randomized heuristics. J. Sched. 14, 89---101 (2011)

Digital Library

Google Scholar

Cited By

View all

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
Englert MMezlaf DWestermann M(2021)Online Makespan Scheduling with Job Migration on Uniform MachinesAlgorithmica10.1007/s00453-021-00852-583:12(3537-3566)Online publication date: 1-Dec-2021
https://dl.acm.org/doi/10.1007/s00453-021-00852-5
Epstein L(2018)A survey on makespan minimization in semi-online environmentsJournal of Scheduling10.1007/s10951-018-0567-z21:3(269-284)Online publication date: 24-Dec-2018
https://dl.acm.org/doi/10.1007/s10951-018-0567-z

A Lower Bound on Deterministic Online Algorithms for Scheduling on Related Machines Without Preemption
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

Preemptive online scheduling with rejection of unit jobs on two uniformly related machines

We consider preemptive online and semi-online scheduling of unit jobs on two uniformly related machines. Jobs are presented one by one to an algorithm, and each job has a rejection penalty associated with it. A new job can either be rejected, in which ...
Preemptive scheduling on uniformly related machines: minimizing the sum of the largest pair of job completion times

We revisit the classic problem of preemptive scheduling on m uniformly related machines. In this problem, jobs can be arbitrarily split into parts, under the constraint that every job is processed completely, and that the parts of a job are not assigned ...
Temperature aware online algorithms for scheduling equal length jobs

We study the online scheduling problem of maximising job completion subject to temperature constraints. In our setting, jobs are of equal length and have deadlines and heat contributions. The algorithm tries to complete as many jobs as possible before ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

Theory of Computing Systems Volume 56, Issue 1

January 2015

290 pages

ISSN:1432-4350

Issue’s Table of Contents

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 01 January 2015

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

3
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

View all

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
Englert MMezlaf DWestermann M(2021)Online Makespan Scheduling with Job Migration on Uniform MachinesAlgorithmica10.1007/s00453-021-00852-583:12(3537-3566)Online publication date: 1-Dec-2021
https://dl.acm.org/doi/10.1007/s00453-021-00852-5
Epstein L(2018)A survey on makespan minimization in semi-online environmentsJournal of Scheduling10.1007/s10951-018-0567-z21:3(269-284)Online publication date: 24-Dec-2018
https://dl.acm.org/doi/10.1007/s10951-018-0567-z

Abstract

References

Cited By

Recommendations

Preemptive online scheduling with rejection of unit jobs on two uniformly related machines

Preemptive scheduling on uniformly related machines: minimizing the sum of the largest pair of job completion times

Temperature aware online algorithms for scheduling equal length jobs

Comments

Information

Published In

Publisher

Publication History

Author Tags

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations