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

article

Competitive online scheduling for server systems

Author:

Kirk PruhsAuthors Info & Claims

ACM SIGMETRICS Performance Evaluation Review, Volume 34, Issue 4

Pages 52 - 58

https://doi.org/10.1145/1243401.1243411

Published: 01 March 2007 Publication History

Abstract

Our goal here is to illustrate the competitive online scheduling research community's approach to online server scheduling problems by enumerating some of the results obtained for problems related to response and slowdown, and by explaining some of the standard analysis techniques.

References

[1]

S. Albers and H. Fujiwara. Energy-efficient algorithms for flow time minimization. In Symposium on Theoretical Aspects of Computer Science, pages 621--633, 2006.

Digital Library

[2]

N. Avrahami and Y. Azar. Minimizing total flow time and total completion time with immediate dispatching. In Proc. 15th Symp. on Parallel Algorithms and Architectures (SPAA), pages 11--18. ACM, 2003.

Digital Library

[3]

N. Bansal. On the average sojourn time under m---m---1---srpt. Opererations Research Letters, 33(2): 195--200, 2005.

Digital Library

[4]

N. Bansal and K. Dhamdhere. Minimizing weighted flow time. In Proc. 14th Symp. on Discrete Algorithms (SODA), pages 508--516. ACM/SIAM, 2003.

Digital Library

[5]

N. Bansal and K. Pruhs. Server scheduling in the L_p norm: A rising tide lifts all boats. In Proc. 35th Symp. Theory of Computing (STOC), pages 242--250. ACM, 2003.

Digital Library

[6]

N. Bansal and K. Pruhs. Server scheduling in the weighted l_p norm. Manuscript, 2003.

[7]

N. Bansal, K. Pruhs, and C. Stein. Speed scaling for weighted flow time. In ACM-SIAM Symposium on Discrete Algorithms, 2007.

Digital Library

[8]

L. Becchetti and S. Leonardi. Non-clairvoyant scheduling to minimize the average flow time on single and parallel machines. In Proc. 33rd Symp. Theory of Computing (STOC), pages 94--103. ACM, 2001. To appear in JACM.

Digital Library

[9]

L. Becchetti, S. Leonardi, A. Marchetti-Spaccamela, and K. Pruhs. Online weighted flow time and deadline scheduling. In RANDOM-APPROX, volume 2129 of Lecture Notes in Computer Science, pages 36--47. Springer, 2001.

[10]

C. Chekuri, S. Khanna, and A. Kumar. Multi-processor scheduling to minimize l_p norms of flow and stretch. Manuscript, 2003.

[11]

C. Chekuri, S. Khanna, and A. Zhu. Algorithms for weighted flow time. In Proc. 33rd Symp. Theory of Computing (STOC), pages 84--93. ACM, 2001.

Digital Library

[12]

J. Edmonds. Scheduling in the dark. Theoretical Computer Science, 235:109--141, 2000.

Digital Library

[13]

J. Edmonds and K. Pruhs. Multicast pull scheduling: when fairness is fine. Algorithmica, 36:315--330, 2003.

Digital Library

[14]

J. Edmonds and K. Pruhs. A maiden analysis of longest wait first. In Proc. 15th Symp. on Discrete Algorithms (SODA). ACM/SIAM, 2004.

Digital Library

[15]

B. Kalyanasundaram and K. Pruhs. Speed is as powerful as clairvoyance. Journal of the ACM, 47:214--221, 2000.

Digital Library

[16]

B. Kalyanasundaram and K. Pruhs. Minimizing flow time nonclairvoyantly. Journal of the ACM, 50:551--567, 2003.

Digital Library

[17]

B. Kalyanasundaram, K. R. Pruhs, and M. Velauthapillai. Scheduling broadcasts in wireless networks. Journal of Scheduling, 4:339--354, 2001.

[18]

S. Leonardi. A simpler proof of preemptive flow-time approximation. In Approximation and On-line Algorithms, Lecture Notes in Computer Science. Springer, 2003.

[19]

S. Leonardi and D. Raz. Approximating total flow time on parallel machines. In Proc. 29th Symp. Theory of Computing (STOC), pages 110--119. ACM, 1997.

Digital Library

[20]

R. Motwani, S. Phillips, and E. Torng. Non-clairvoyant scheduling. Theoretical Computer Science, 130:17--47, 1994.

Digital Library

[21]

S. Muthukrishnan, R. Rajaraman, A. Shaheen, and J. E. Gehrke. Online scheduling to minimize avarage strech. In Proc. 40th Symp. Foundations of Computer Science (FOCS), pages 433--443. IEEE, 1999.

Digital Library

[22]

C. Phillips, C. Stein, E. Torng, and J. Wein. Optimal time-critical scheduling via resource augmentation. Algorithmica, pages 163--200, 2002.

Digital Library

[23]

K. Pruhs, J. Sgall, and E. Torng. Online scheduling. In Handbook on Scheduling. CRC Press, 2004.

Cited By

Bhimaraju AVarshney L(2022)Scheduling Group Tests over Time2022 IEEE International Symposium on Information Theory (ISIT)10.1109/ISIT50566.2022.9834434(886-891)Online publication date: 26-Jun-2022
https://dl.acm.org/doi/10.1109/ISIT50566.2022.9834434
Davydow AChuprikov PNikolenko SKogan K(2021)Competitive buffer management for packets with latency constraintsComputer Networks10.1016/j.comnet.2021.107942189(107942)Online publication date: Apr-2021
https://doi.org/10.1016/j.comnet.2021.107942
Ding JYu GLi YHe XJin D(2020)Improving Implicit Recommender Systems with Auxiliary DataACM Transactions on Information Systems10.1145/337233838:1(1-27)Online publication date: 6-Feb-2020
https://dl.acm.org/doi/10.1145/3372338
Show More Cited By

Index Terms

Recommendations

Competitive Two-Agent Scheduling and Its Applications

We consider a scheduling environment with m (m ≥ 1) identical machines in parallel and two agents. Agent A is responsible for n₁ jobs and has a given objective function with regard to these jobs; agent B is responsible for n₂ jobs and has an objective ...
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 ...
Competitive algorithms for due date scheduling
ICALP'07: Proceedings of the 34th international conference on Automata, Languages and Programming

We consider several online scheduling problems that arise when customers request make-to-order products from a company. At the time of the order, the company must quote a due date to the customer. To satisfy the customer, the company must produce the ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM SIGMETRICS Performance Evaluation Review

ACM SIGMETRICS Performance Evaluation Review Volume 34, Issue 4

March 2007

69 pages

ISSN:0163-5999

DOI:10.1145/1243401

Issue’s Table of Contents

Copyright © 2007 Author.

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 March 2007

Published in SIGMETRICS Volume 34, Issue 4

Check for updates

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

82
Total Citations
View Citations
384
Total Downloads

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

Reflects downloads up to 06 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Bhimaraju AVarshney L(2022)Scheduling Group Tests over Time2022 IEEE International Symposium on Information Theory (ISIT)10.1109/ISIT50566.2022.9834434(886-891)Online publication date: 26-Jun-2022
https://dl.acm.org/doi/10.1109/ISIT50566.2022.9834434
Davydow AChuprikov PNikolenko SKogan K(2021)Competitive buffer management for packets with latency constraintsComputer Networks10.1016/j.comnet.2021.107942189(107942)Online publication date: Apr-2021
https://doi.org/10.1016/j.comnet.2021.107942
Ding JYu GLi YHe XJin D(2020)Improving Implicit Recommender Systems with Auxiliary DataACM Transactions on Information Systems10.1145/337233838:1(1-27)Online publication date: 6-Feb-2020
https://dl.acm.org/doi/10.1145/3372338
Thomas PBillerbeck BCraswell NWhite R(2019)Investigating Searchers’ Mental Models to Inform Search ExplanationsACM Transactions on Information Systems10.1145/337139038:1(1-25)Online publication date: 20-Dec-2019
https://dl.acm.org/doi/10.1145/3371390
Amer ALu HBalaji PChabbi MWei YHammond JMatsuoka S(2019)Lock Contention Management in Multithreaded MPIACM Transactions on Parallel Computing10.1145/32754435:3(1-21)Online publication date: 8-Jan-2019
https://dl.acm.org/doi/10.1145/3275443
Böhm MJeż ŁSgall JVeselý P(2019)On packet scheduling with adversarial jamming and speedupAnnals of Operations Research10.1007/s10479-019-03153-xOnline publication date: 4-Feb-2019
https://doi.org/10.1007/s10479-019-03153-x
Pruhs K(2019)Green Computing AlgorithmicsComputing and Software Science10.1007/978-3-319-91908-9_10(161-183)Online publication date: 2019
https://doi.org/10.1007/978-3-319-91908-9_10
Chuprikov PNikolenko SDavydow AKogan K(2018)Priority Queueing for Packets With Two CharacteristicsIEEE/ACM Transactions on Networking10.1109/TNET.2017.278277126:1(342-355)Online publication date: 1-Feb-2018
https://dl.acm.org/doi/10.1109/TNET.2017.2782771
Cohen IScalosub G(2018)Queueing in the mist: Buffering and scheduling with limited knowledgeComputer Networks10.1016/j.comnet.2018.10.013147(204-220)Online publication date: Dec-2018
https://doi.org/10.1016/j.comnet.2018.10.013
Eugster PKesselman AKogan KNikolenko SSirotkin A(2018)Admission control in shared memory switchesJournal of Scheduling10.1007/s10951-018-0564-221:5(533-543)Online publication date: 1-Oct-2018
https://dl.acm.org/doi/10.1007/s10951-018-0564-2
Show More Cited By

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

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents