skip to main content
10.5555/1109557.1109595acmconferencesArticle/Chapter ViewAbstractPublication PagessodaConference Proceedingsconference-collections
Article

Extra unit-speed machines are almost as powerful as speedy machines for competitive flow time scheduling

Published: 22 January 2006 Publication History

Abstract

We study online scheduling of jobs to minimize the flow time and stretch on parallel machines. We consider algorithms that are given extra resources so as to compensate the lack of future information. Recent results show that a modest increase in machine speed can provide very competitive performance; in particular, using O(1) times faster machines, the algorithm SRPT (shortest remaining processing time) is 1-competitive for both flow time [23] and stretch [12], and HDF (highest density first) is O(1)-competitive for weighted flow time [6]. Using extra unit-speed machines instead of faster machines is more challenging. This paper gives a non-trivial relationship between the extra-speed and extra-machine analysis. It shows that competitive results via faster machines can be transformed to similar results via extra machines, and hence giving the first algorithms that, using O(1) times unit-speed machines, are 1-competitive for flow time and stretch and O(1)-competitive for weighted flow time, respectively.

References

[1]
N. Avrahami and Y. Azar. Minimizing total flow time and total completion time with immediate dispatching. In SPAA, pages 11--18, 2003.]]
[2]
B. Awerbuch, Y. Azar, S. Leonardi and O. Regev. Minimizing the flow time without migration. In STOC, pages 198--205, 1999.]]
[3]
N. Bansal. On minimizing the total flow time on multiple machines. In SODA, pages 572--574, 2004.]]
[4]
N. Bansal and K. Dhamdhere. Minimizing weighted flow time. In SODA, pages 508--516, 2003.]]
[5]
N. Bansal and K. Pruhs. Server scheduling in the Lp norm: a rising tide lifts all boat. In STOC, pages 242--250, 2003.]]
[6]
L. Becchetti, S. Leonardi, A. Marchetti-Spaccamela, and K. Pruhs. Online weighted flow time and deadline scheduling. In RANDOM-APPROX, pages 36--47, 2001.]]
[7]
Becchetti, S. Leonardi, and S. Muthukrishnan. Scheduling to minimize average stretch without migration. In SODA, pages 548--557, 2000.]]
[8]
M. A. Bender, S. Chakrabarti, and S. Muthukrishnan. Flow and stretch metrics for scheduling continuous job streams. In SODA, pages 270--279, 1998.]]
[9]
M. A. Bender, S. Muthukrishnan, and R. Rajaraman. Improved algorithms for stretch scheduling. In SODA, pages 762--771, 2002.]]
[10]
P. Berman and C. Coulston. Speed is more powerful than clairvoyance. In Proc. 6th SWAT, pages 255--263, 1998.]]
[11]
H. L. Chan, T. W. Lam, and K. K. To. Non-migratory online deadline scheduling on multiprocessors. In SODA, pages 970--979, 2004.]]
[12]
W. T. Chan, T. W. Lam, K. S. Liu, and P. Wong. New Resource Augmentation Analysis of the Total Stretch of SRPT and SJF in Multiprocessor Scheduling. In MFCS, 2005.]]
[13]
C. Chekuri, A. Goel, S. Khanna, and A. Kumar. Multi-processor scheduling to minimize flow time with ε resource augmentation. In STOC, pages 363--372, 2004.]]
[14]
C. Chekuri, S. Khanna, and A. Zhu. Algorithms for minimizing weighted flow time. In STOC, pages 84--93, 2001.]]
[15]
J. Du, J. Y. T. Leung, and G. H. Young. Minimizing mean flow time with release time constraint. Theoretical Computer Science, 75(3):347--355, 1990.]]
[16]
J. Edmonds. Scheduling in the Dark. In STOC, pages 179--188, 1999.]]
[17]
B. Kalyanasundaram and K. Pruhs. Speed is as powerful as clairvoyance. J. ACM, 47(4):617--643, 2000.]]
[18]
C. Y. Koo, T. W. Lam, T. W. Ngan and K. K. To. Extra processors versus future information in optimal deadline scheduling. In SPAA, pages 133--142, 2002.]]
[19]
K. R. Baker. Introduction to Sequencing and Scheduling. Wiley, New York, 1974.]]
[20]
S. Leonardi and D. Raz. Approximating total flow time on parallel machines. In STOC, pages 110--119, 1997.]]
[21]
J. McCullough and E. Torng. SRPT optimally utilizes faster machines to minimize flow time. In SODA, pages 343--351, 2004.]]
[22]
S. Muthukrishnan, R. Rajaraman, A. Shaheen, and J. Gehrke. Online scheduling to minimize average stretch. In FOCS, pages 433--442, 1999.]]
[23]
C. A. Phillips, C. Stein, E. Torng, and J. Wein. Optimal time-critical scheduling via resource augmentation. In STOC, pages 140--149, 1997.]]
[24]
K. Pruhs, J. Sgall, and E. Torng. Online scheduling. In J. Leung, editor, Handbook of Scheduling: Algorithms, Models and Performance Analysis, pages 15-1--15-41. CRC Press, 2004.]]

Cited By

View all
  • (2011)Minimizing flow time in the wireless gathering problemACM Transactions on Algorithms (TALG)10.1145/1978782.19787887:3(1-20)Online publication date: 15-Jul-2011

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences
SODA '06: Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm
January 2006
1261 pages
ISBN:0898716055

Sponsors

Publisher

Society for Industrial and Applied Mathematics

United States

Publication History

Published: 22 January 2006

Check for updates

Qualifiers

  • Article

Acceptance Rates

Overall Acceptance Rate 411 of 1,322 submissions, 31%

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)1
  • Downloads (Last 6 weeks)0
Reflects downloads up to 28 Jan 2025

Other Metrics

Citations

Cited By

View all
  • (2011)Minimizing flow time in the wireless gathering problemACM Transactions on Algorithms (TALG)10.1145/1978782.19787887:3(1-20)Online publication date: 15-Jul-2011

View Options

Login options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media