article

A new algorithm for online uniform-machine scheduling to minimize the makespan

Authors:

T. C. E. Cheng,

C. T. Ng,

Vladimir KotovAuthors Info & Claims

Information Processing Letters, Volume 99, Issue 3

Pages 102 - 105

https://doi.org/10.1016/j.ipl.2006.02.012

Published: 16 August 2006 Publication History

Abstract

We consider the online scheduling problem with m - 1, m ≥ 2, uniform machines each with a processing speed of 1, and one machine with a speed of s, 1 ≤ s ≤ 2, to minimize the makespan. The well-known list scheduling (LS) algorithm has a worst-case bound of (3m - 1)/(m + 1) [Y. Cho, S. Sahni, Bounds for list schedules on uniform processors, SIAM J. Comput. 9 (1980) 91-103]. An algorithm with a better competitive ratio was proposed in [R. Li, L. Shi, An on-line algorithm for some uniform processor scheduling, SIAM J. Comput. 27 (1998) 414-422]. It has a worst-case bound of 2.8795 for a big m and s = 2. In this note we present a 2.45-competitive algorithm for m ≥ 4 and any s, 1 ≤ s ≤ 2.

References

[1]

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

Crossref

Google Scholar

[2]

[2] R.L. Graham, Bounds on multiprocessing timing anomalies, SIAM J. Appl. Math. 17 (1969) 263-269.

Crossref

Google Scholar

[3]

[3] R. Li, L. Shi, An on-line algorithm for some uniform processor scheduling, SIAM J. Comput. 27 (1998) 414-422.

Digital Library

Google Scholar

Cited By

View all

Dolgui AKotov VNekrashevich AQuilliot A(2019)General parametric scheme for the online uniform machine scheduling problem with two different speedsInformation Processing Letters10.1016/j.ipl.2018.01.009134:C(18-23)Online publication date: 6-Jan-2019
https://dl.acm.org/doi/10.1016/j.ipl.2018.01.009
Cai SYang Q(2019)Online scheduling on three uniform machinesDiscrete Applied Mathematics10.1016/j.dam.2011.10.001160:3(291-302)Online publication date: 1-Jan-2019
https://dl.acm.org/doi/10.1016/j.dam.2011.10.001
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
Show More Cited By

Index Terms

Recommendations

Scheduling parallel jobs to minimize the makespan

We consider the NP-hard problem of scheduling parallel jobs with release dates on identical parallel machines to minimize the makespan. A parallel job requires simultaneously a prespecified, job-dependent number of machines when being processed. We ...
Online Scheduling to Minimize Average Stretch

We consider the classical problem of online job scheduling on uniprocessor and multiprocessor machines. For a given job, we measure the quality of service provided by an algorithm by the stretch of the job, which is defined as the ratio of the amount ...
Minimizing Makespan and Preemption Costs on a System of Uniform Machines

It is well known that for preemptive scheduling on uniform machines there exist polynomial time exact algorithms, whereas for non-preemptive scheduling there are probably no such algorithms. However, it is not clear how many preemptions (in total, or ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

Information Processing Letters Volume 99, Issue 3

16 August 2006

41 pages

ISSN:0020-0190

Issue’s Table of Contents

Publisher

Elsevier North-Holland, Inc.

United States

Publication History

Published: 16 August 2006

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

4
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

Dolgui AKotov VNekrashevich AQuilliot A(2019)General parametric scheme for the online uniform machine scheduling problem with two different speedsInformation Processing Letters10.1016/j.ipl.2018.01.009134:C(18-23)Online publication date: 6-Jan-2019
https://dl.acm.org/doi/10.1016/j.ipl.2018.01.009
Cai SYang Q(2019)Online scheduling on three uniform machinesDiscrete Applied Mathematics10.1016/j.dam.2011.10.001160:3(291-302)Online publication date: 1-Jan-2019
https://dl.acm.org/doi/10.1016/j.dam.2011.10.001
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
Musitelli ANicoletti J(2011)Competitive ratio of List Scheduling on uniform machines and randomized heuristicsJournal of Scheduling10.1007/s10951-010-0177-x14:1(89-101)Online publication date: 1-Feb-2011
https://dl.acm.org/doi/10.1007/s10951-010-0177-x

Abstract

References

Cited By

Index Terms

Recommendations

Scheduling parallel jobs to minimize the makespan

Online Scheduling to Minimize Average Stretch

Minimizing Makespan and Preemption Costs on a System of Uniform Machines

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