Article

Free access

Better bounds for online scheduling

Author:

Susanne AlbersAuthors Info & Claims

STOC '97: Proceedings of the twenty-ninth annual ACM symposium on Theory of computing

Pages 130 - 139

https://doi.org/10.1145/258533.258566

Published: 04 May 1997 Publication History

PDF eReader

References

[1]

J. Aspnes, Y. Azar, A. Fiat, S. Plotkin and O. Waarts. On-line machine scheduling with applications to load balancing and virtual circuit routing. In Proc. 25th A CM Symposium on Theory of Computing, pages 623-631, 1993.

Digital Library

Google Scholar

[2]

B. Awerbuch, Y. Azar, E.F. Grove, M.Y. Kao, P. Krishnan and J.S. Vitter. Load balancing in the Lp norm. In Proc. 36th IEEE Annual Symposium on Foundations of Computer Science, pages 383- 391, 1995.

Digital Library

Google Scholar

[3]

Y. Bartal, A. Fiat, H. Karloff and R. Vohra. New algorithms for all ancient scheduling problem. Journal of Computer and System Sciences, 51:359-366, 1995.

Digital Library

Google Scholar

[4]

Y. Bartal, H. Karloffand Y. Rabani. A better lower bound for on-line scheduling. Information Processing Letters, 50:113-116, 1994.

Digital Library

Google Scholar

[5]

Y. Bartal, S. Leonardi, A. Marchetti-Speccamela, J. Sgall and L. Stougie. Multiprocessor scheduling with rejection. In Proc. 7th A CM-SIAM Symposium on Discrete Algorithms, pages 95-104, 1996.

Digital Library

Google Scholar

[6]

B. Chen, A. van Vliet and G. Woeginger. New lower and upper bounds for on-line scheduling. Operations Research Letters, 16:221-230, 1994.

Digital Library

Google Scholar

[7]

U. Faigle, W. Kern and G. Turan. On the performance of on-line algorithms for particular problems. Acta Cybernetica, 9:107-119, 1989.

Digital Library

Google Scholar

[8]

G. Galambos and G. Woeginger. An on-line scheduling heuristic with better worst case ratio than Graham's list, scheduling. SIAM Journal on Computing, 22:349-355, 1993.

Digital Library

Google Scholar

[9]

M.R. Garay and D.S. Johnson. Computers and Intractability: A Guide to the Theory of NP- Completeness. W.H. Freeman and Company, New York, 1979.

Digital Library

Google Scholar

[10]

R.L. Graham. Bounds for certain multi-processing anomalies. Bell System Technical Journal, 45:1563- 1581, 1966.

Crossref

Google Scholar

[11]

D.R. Karger. S.J. Phillips and E. Torng. A better algorit, hm for an ancient scheduling problem. JournaI of Algorithms, 20:400-430, 1996.

Digital Library

Google Scholar

[12]

R. Motwani. S. Phillips and E. Torng. Non-clearvoyant scheduling. In Proc. 4th Annual ACM- SLAM Symposium on Discrete Algorithms, pages 422-431, 1993.

Digital Library

Google Scholar

[13]

D.D. Sleator and R.E. Tarjan. Amort. ized efficiency of list update and paging rules. Communications of the A CM, 28:202-208, 1985.

Digital Library

Google Scholar

[14]

D. Shmoys, J. Wein and D.P. Williamson. Scheduling parallel machines on-line. In Proc. 32nd IEEE Annual Symposium on Foundations of Computer Science, pages 131-140, 1991.

Digital Library

Google Scholar

Cited By

View all

JIANG XHASHIMA SHATANO KTAKIMOTO E(2024)Online Job Scheduling with K ServersIEICE Transactions on Information and Systems10.1587/transinf.2023FCP0005E107.D:3(286-293)Online publication date: 1-Mar-2024
https://doi.org/10.1587/transinf.2023FCP0005
Lopez JVergara J(2023)Examining the Online Food Delivery Problem on Starlike Graphs2023 International Conference on Advanced Mechatronics, Intelligent Manufacture and Industrial Automation (ICAMIMIA)10.1109/ICAMIMIA60881.2023.10427632(393-397)Online publication date: 14-Nov-2023
https://doi.org/10.1109/ICAMIMIA60881.2023.10427632
Chen X(2022)Job Scheduling on Edge and Cloud Servers2022 IEEE 8th Intl Conference on Big Data Security on Cloud (BigDataSecurity), IEEE Intl Conference on High Performance and Smart Computing, (HPSC) and IEEE Intl Conference on Intelligent Data and Security (IDS)10.1109/BigDataSecurityHPSCIDS54978.2022.00025(87-91)Online publication date: May-2022
https://doi.org/10.1109/BigDataSecurityHPSCIDS54978.2022.00025
Show More Cited By

Index Terms

Better bounds for online scheduling

Recommendations

Better Bounds for Online Scheduling

We study a classical problem in online scheduling. A sequence of jobs must be scheduled on m identical parallel machines. As each job arrives, its processing time is known. The goal is to minimize the makespan. Bartal et al. [ J. Comput. System Sci., 51 ...
Improved lower bounds for online scheduling to minimize total stretch

We consider the online scheduling problem to maximize total stretch.The stretch of a job is the ratio of the amount of time which the job spends in the system to its processing time.We improve lower bounds on the competitive ratios of deterministic ...
Online Scheduling of Precedence Constrained Tasks

A fundamental problem in scheduling theory is that of scheduling a set of n tasks, with precedence constraints, on $m \ge 1$ identical and parallel processors so as to minimize the makespan (schedule length). In the past, research has focused on the ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

STOC '97: Proceedings of the twenty-ninth annual ACM symposium on Theory of computing

May 1997

752 pages

ISBN:0897918886

DOI:10.1145/258533

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 04 May 1997

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

STOC97

Sponsor:

SIGACT

STOC97: 29th Annual Symposium on Theory of Computing

May 4 - 6, 1997

Texas, El Paso, USA

Acceptance Rates

STOC '97 Paper Acceptance Rate 75 of 211 submissions, 36%;

Overall Acceptance Rate 1,469 of 4,586 submissions, 32%

Upcoming Conference

STOC '25

Sponsor:
sigact

57th Annual ACM Symposium on Theory of Computing (STOC 2025)

June 23 - 27, 2025

Prague , Czech Republic

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

53
Total Citations
View Citations
871
Total Downloads

Downloads (Last 12 months)141
Downloads (Last 6 weeks)17

Reflects downloads up to 26 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

JIANG XHASHIMA SHATANO KTAKIMOTO E(2024)Online Job Scheduling with K ServersIEICE Transactions on Information and Systems10.1587/transinf.2023FCP0005E107.D:3(286-293)Online publication date: 1-Mar-2024
https://doi.org/10.1587/transinf.2023FCP0005
Lopez JVergara J(2023)Examining the Online Food Delivery Problem on Starlike Graphs2023 International Conference on Advanced Mechatronics, Intelligent Manufacture and Industrial Automation (ICAMIMIA)10.1109/ICAMIMIA60881.2023.10427632(393-397)Online publication date: 14-Nov-2023
https://doi.org/10.1109/ICAMIMIA60881.2023.10427632
Chen X(2022)Job Scheduling on Edge and Cloud Servers2022 IEEE 8th Intl Conference on Big Data Security on Cloud (BigDataSecurity), IEEE Intl Conference on High Performance and Smart Computing, (HPSC) and IEEE Intl Conference on Intelligent Data and Security (IDS)10.1109/BigDataSecurityHPSCIDS54978.2022.00025(87-91)Online publication date: May-2022
https://doi.org/10.1109/BigDataSecurityHPSCIDS54978.2022.00025
Hunold SPrzybylski B(2021)Teaching Complex Scheduling Algorithms2021 IEEE International Parallel and Distributed Processing Symposium Workshops (IPDPSW)10.1109/IPDPSW52791.2021.00058(321-327)Online publication date: Jun-2021
https://doi.org/10.1109/IPDPSW52791.2021.00058
Burra RSingh CKuri J(2019)Offline and Online Scheduling of Jobs with Service and Delay Costs2019 57th Annual Allerton Conference on Communication, Control, and Computing (Allerton)10.1109/ALLERTON.2019.8919660(572-579)Online publication date: Sep-2019
https://doi.org/10.1109/ALLERTON.2019.8919660
Feldman MFiat ARoytman ADaskalakis CBabaioff MMoulin H(2017)Makespan Minimization via Posted PricesProceedings of the 2017 ACM Conference on Economics and Computation10.1145/3033274.3085129(405-422)Online publication date: 20-Jun-2017
https://dl.acm.org/doi/10.1145/3033274.3085129
Xu CYang JFu DZhang H(2014)Towards Optimal Collaboration of Policies in the Two-Phase Scheduling of Cloud TasksAdvanced Information Systems Engineering10.1007/978-3-662-44917-2_26(306-320)Online publication date: 2014
https://doi.org/10.1007/978-3-662-44917-2_26
Ausiello GBecchetti L(2014)On‐Line AlgorithmsParadigms of Combinatorial Optimization10.1002/9781119005353.ch15(473-509)Online publication date: 8-Aug-2014
https://doi.org/10.1002/9781119005353.ch15
(2014)General BibliographyParadigms of Combinatorial Optimization10.1002/9781119005353.biblio(707-765)Online publication date: 8-Aug-2014
https://doi.org/10.1002/9781119005353.biblio
Ausiello GBecchetti L(2013)On‐Line AlgorithmsParadigms of Combinatorial Optimization10.1002/9781118600207.ch15(473-509)Online publication date: 13-Feb-2013
https://doi.org/10.1002/9781118600207.ch15
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

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

Cited By

Index Terms

Recommendations

Better Bounds for Online Scheduling

Improved lower bounds for online scheduling to minimize total stretch

Online Scheduling of Precedence Constrained Tasks