article

Semi-online scheduling with decreasing job sizes

Authors:

Gerhard WoegingerAuthors Info & Claims

Operations Research Letters, Volume 27, Issue 5

Pages 215 - 221

https://doi.org/10.1016/S0167-6377(00)00053-5

Published: 01 December 2000 Publication History

Abstract

We investigate the problem of semi-online scheduling jobs on m identical parallel machines where the jobs arrive in order of decreasing sizes. We present a complete solution for the preemptive variant of semi-online scheduling with decreasing job sizes. We give matching lower and upper bounds on the competitive ratio for any fixed number m of machines; these bounds tend to (1+3)/2~1.36603, as the number of machines goes to infinity. Our results are also the best possible for randomized algorithms. For the non-preemptive variant of semi-online scheduling with decreasing job sizes, a result of Graham (SIAM J. Appl. Math. 17 (1969) 263-269) yields a (4/3-1/(3m))-competitive deterministic non-preemptive algorithm. For m=2 machines, we prove that this algorithm is the best possible (it is 7/6-competitive). For m=3 machines we give a lower bound of (1+37)/6~1.18046. Finally, we present a randomized non-preemptive 8/7-competitive algorithm for m=2 machines and prove that this is optimal.

References

[1]

S. Albers, Better bounds for online scheduling, Proceedings of the 29th ACM Symposium on Theory of Computing, 1997, pp. 130-139.

Digital Library

[2]

Y. Azar, O. Regev, Online bin stretching, Proceedings of RANDOM, 1998, pp. 71-82.

[3]

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

Digital Library

[4]

Bartal, Y., Karloff, H. and Rabani, Y., A better lower bound for on-line scheduling. Inform. Process. Lett. v50. 113-116.

Digital Library

[5]

Chen, B., van Vliet, A. and Woeginger, G., A lower bound for randomized on-line scheduling algorithms. Inform. Process. Lett. v51. 219-222.

Digital Library

[6]

Chen, B., van Vliet, A. and Woeginger, G., New lower and upper bounds for on-line scheduling. Oper. Res. Lett. v16. 221-230.

Digital Library

[7]

Chen, B., van Vliet, A. and Woeginger, G., An optimal algorithm for preemptive on-line scheduling. Oper. Res. Lett. v18. 127-131.

Digital Library

[8]

Faigle, U., Kern, W. and Turín, G., On the performance of on-line algorithms for partition problems. Acta Cybernet. v9. 107-119.

[9]

Galambos, G. and Woeginger, G., An online scheduling heuristic with better worst case ratio than Graham's list scheduling. SIAM J. Comput. v22. 349-355.

[10]

Graham, R.L., Bounds for certain multiprocessing anomalies. Bell Systems Tech. J. v45. 1563-1581.

[11]

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

[12]

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

[13]

Kellerer, H., Kotov, V., Speranza, M. and Tuza, Z., Semi online algorithms for the partition problem. Oper. Res. Lett. v21. 235-242.

Digital Library

[14]

Ordinal algorithms for parallel machine scheduling. Oper. Res. Lett. v18. 223-232.

[15]

Reingold, N., Westbrook, J. and Sleator, D., Randomized competitive algorithms for the list update problem. Algorithmica. v11. 15-32.

[16]

S.S Seiden, Randomized algorithms for that ancient scheduling problem, Proceedings of the Fifth Workshop on Algorithms and Data Structures, 1997, pp. 210-223.

[17]

S.S. Seiden, Randomized online multiprocessor scheduling, Algorithmica, to appear.

[18]

J. Sgall, On-line scheduling on parallel machines, Ph.D. thesis, Carnegie-Mellon University, 1994

[19]

Sgall, J., A lower bound for randomized on-line multiprocessor scheduling. Inform. Process. Lett. v63. 51-55.

Digital Library

Cited By

Epstein L(2023)Parallel solutions for ordinal scheduling with a small number of machinesJournal of Combinatorial Optimization10.1007/s10878-023-01069-846:1Online publication date: 24-Jul-2023
https://dl.acm.org/doi/10.1007/s10878-023-01069-8
Epstein L(2022)Parallel solutions for preemptive makespan scheduling on two identical machinesJournal of Scheduling10.1007/s10951-022-00764-426:1(61-76)Online publication date: 29-Oct-2022
https://dl.acm.org/doi/10.1007/s10951-022-00764-4
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: 1-Jun-2018
https://dl.acm.org/doi/10.1007/s10951-018-0567-z
Show More Cited By

Semi-online scheduling with decreasing job sizes
1. Software and its engineering
  1. Software creation and management
    1. Software verification and validation
2. 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 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 ...
Online malleable job scheduling for m≤3

A malleable parallel job is one that may be assigned to any number of processors in a parallel computing environment. In our particular problem, we assume that the execution time of a job j with processing requirement p"j is p"j/k"j+(k"j-1)c if the job ...
Semi-online Multiprocessor Scheduling with Nonsimultaneous Machine Available Times
ICIC '10: Proceedings of the 2010 Third International Conference on Information and Computing - Volume 03

This paper investigates scheduling problems on parallel identical machines with non-simultaneous machine available times. Each machine is not available until time. Jobs arrive one by one, and we are required to schedule jobs irrevocably on machines as ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Operations Research Letters

Operations Research Letters Volume 27, Issue 5

December, 2000

47 pages

ISSN:0167-6377

Issue’s Table of Contents

Copyright © Elsevier Science B.V. © 2000.

Publisher

Elsevier Science Publishers B. V.

Netherlands

Publication History

Published: 01 December 2000

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

32
Total Citations
View Citations
0
Total Downloads

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

Reflects downloads up to 28 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Epstein L(2023)Parallel solutions for ordinal scheduling with a small number of machinesJournal of Combinatorial Optimization10.1007/s10878-023-01069-846:1Online publication date: 24-Jul-2023
https://dl.acm.org/doi/10.1007/s10878-023-01069-8
Epstein L(2022)Parallel solutions for preemptive makespan scheduling on two identical machinesJournal of Scheduling10.1007/s10951-022-00764-426:1(61-76)Online publication date: 29-Oct-2022
https://dl.acm.org/doi/10.1007/s10951-022-00764-4
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: 1-Jun-2018
https://dl.acm.org/doi/10.1007/s10951-018-0567-z
Boyar JFavrholdt LKudahl CLarsen KMikkelsen J(2017)Online Algorithms with AdviceACM Computing Surveys10.1145/305646150:2(1-34)Online publication date: 11-Apr-2017
https://dl.acm.org/doi/10.1145/3056461
Boyar JFavrholdt LKudahl CLarsen KMikkelsen J(2016)Online Algorithms with Advice: A SurveyACM SIGACT News10.1145/2993749.299376647:3(93-129)Online publication date: 31-Aug-2016
https://dl.acm.org/doi/10.1145/2993749.2993766
Epstein LZebedat-Haider H(2016)Online scheduling of unit jobs on three machines with rejectionInformation Processing Letters10.1016/j.ipl.2015.11.012116:3(252-255)Online publication date: 1-Mar-2016
https://dl.acm.org/doi/10.1016/j.ipl.2015.11.012
Cao QWan G(2016)Semi-online scheduling with combined information on two identical machines in parallelJournal of Combinatorial Optimization10.1007/s10878-014-9778-131:2(686-695)Online publication date: 1-Feb-2016
https://dl.acm.org/doi/10.1007/s10878-014-9778-1
Gabay MKotov VBrauner N(2015)Online bin stretching with bunch techniquesTheoretical Computer Science10.1016/j.tcs.2015.07.065602:C(103-113)Online publication date: 18-Oct-2015
https://dl.acm.org/doi/10.1016/j.tcs.2015.07.065
Wang XYuen CChen XHassan NOuyang Y(2015)Cost-aware demand scheduling for delay tolerant applicationsJournal of Network and Computer Applications10.1016/j.jnca.2015.04.00253:C(173-182)Online publication date: 1-Jul-2015
https://dl.acm.org/doi/10.1016/j.jnca.2015.04.002
Epstein LZebedat-Haider H(2014)Preemptive online scheduling with rejection of unit jobs on two uniformly related machinesJournal of Scheduling10.1007/s10951-013-0326-017:1(87-93)Online publication date: 1-Feb-2014
https://dl.acm.org/doi/10.1007/s10951-013-0326-0
Show More Cited By

View Options

View options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Issue’s Table of Contents