Article

Free access

Flow and stretch metrics for scheduling continuous job streams

Authors:

Michael A. Bender,

Soumen Chakrabarti,

S. MuthukrishnanAuthors Info & Claims

SODA '98: Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms

Pages 270 - 279

Published: 01 January 1998 Publication History

PDF eReader

References

[1]

M.J. Bach. The Design of the UNIX Operating System. Prentice-Hall, Englewood Cliffs, N5 07632, USA, 1986.

Digital Library

Google Scholar

[2]

K. R. Baker. Introduction to Sequencing and Scheduling. Wiley, 1974.

Google Scholar

[3]

K. P. Brown, M. Mehta, M. J. Csrey, and M. Livny. Towards automated performance tuning for complex workloads. Technical Report TR 1247, Computer Sciences Department, University of Wisconsin, Madison, WI, Sept. 1994.

Google Scholar

[4]

M. J. Carey, M. Livay, and H. Lu. Dynamic task allocation in a distributed database system. CS TR.

Google Scholar

[5]

S. Chakrabarti, C. Phillips, A. Schuls, D. Shmoys, C. Stein, and J. Wein. Improved scheduling algorithms for reinsure criteria. In ICALP: Annual International Colloquium on Automata, Languages and Programming, 1996.

Digital Library

Google Scholar

[6]

C. Chekuri, R. Johnson, R. Motwani, B. Natarajan, B. R. Rau, and M. Schlansker. Profile-driven instruction level parallel scheduling with application to super blocks. In Proceedings of the ~gth Annual International Symposium on Microarchitecture, pages 58--67, Paris, France, Dec. 2--4, 1996. IEEE Computer Society TC- MICRO and ACM SIGMICRO.

Digital Library

Google Scholar

[7]

A. Demers, S. Keshav, and S. Shenker. Analysis and simulation of a fair queueing algorithm. In Proc. A CM SIGCOMM '89, pages 1-12, Austin, TX, Sept. 1989.

Digital Library

Google Scholar

[8]

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

Digital Library

Google Scholar

[9]

S. J. Golestani. A seli-clocked fair queueing scheme for broadband applications. In Proceedings of the 13th Annual Joint Conference of the IF, BE Computer and Communications Societies on Networking for Global Communciation. Volume ~, pages 636-646, Los AlsmJtos, CA, USA, June 1994. IEEE Computer Society Press.

Google Scholar

[10]

P. Goyal, X. Guo, and H. M. Via. A hierarchical CPU scheduler for multimedia operating systems. Technical Report CS-TR-96-12, The University of Texas at Austin, Department of Computer Sciences.

Digital Library

Google Scholar

[11]

R. L. Graham. Bounds on multiprocessor timing anomalies. SIAM Journal of Applied Mathematics, 17(2):416-429, March 1969.

Google Scholar

[12]

L. Hall, D. Shmoys, and J. Wein. Scheduling to minimize average completion time: Off-line and online algorithms. In Symposium on Discrete Algorithms (SODA). ACM-SIAM, 1996.

Digital Library

Google Scholar

[13]

L. A. Hall. Appro~rimation Algorithms for AFT'- Hard Problems, chapter Approximation Algorithms for Scheduting. PWS Publishing Company, Boston, MA, 1996.

Digital Library

Google Scholar

[14]

L. A. Hall, A. S. Schulz, D. B. Shmoys, and J. Wein. Scheduling to minimize average completion time: off'- line and online algorithms. Math of OR, i997. To appear.

Digital Library

Google Scholar

[15]

D. Karger, C. Stein, and J. Wein. Scheduling algorithms. In CRC Handbook of Computer Science, 1997. To appear.

Google Scholar

[16]

H. Kellerer, T. Tauterthahn, and G. J. Woeginger. Approximability and nonapproximability results for minimizing total flow time on a single roaching. In Proceedings of the Twenty-Eighth Annual A CM Symposium on Theory of Computing, pages 418--426, Philadelphia, Pennsylvania, 22-24 May 1996.

Digital Library

Google Scholar

[17]

E. L. Lawler, J. K. Lenstra, A. H. R. Kan, and D. B. Shmoys. Sequencing and scheduling: Algorithms and complexity, pages 445-522, 1993.

Google Scholar

[18]

S. Leonardi mad D. Ra~. Approximating total flow time on parallel m~es. In Proceedings of the Twenty- Ninth Annual A CM Symposium on Theory of Computing, pages 110-119, E1 Paso, Texas, 4-6 May 1997'.

Digital Library

Google Scholar

[19]

M. Mehta and D. J. DeWitt. Dynamic memory allocation for multiple-query workloads. In R. Agrawal, S. Baker, and D. Bell, editors, Very large data bases, VLDB '93: proceedings of the 19th International Con- .ference on Very Large Data Bases, August ~4-~7, 1993, Dublin, Ireland, pages 354-367, Palo Alto, Calif., USA, 1993. Morgan Kaufmann Publishers.

Digital Library

Google Scholar

[20]

M. Mehta and D. J. DeWitt. Dynamic memory allocation for multiple-query workloads. Technical Report TR 1151, Computer Science Department, University of Wisconsin-Madison, June 1993.

Google Scholar

[21]

C. Phillips, C. Stein, and J. Wein. Scheduling jobs that arrive over time. Lecture Notes in Computer Science, 955:86, 1995.

Google Scholar

[22]

C. A. Phillips, C. Stein, E. Tomg, aud J. Wein. Optimed time-critical scheduling via resource augmentation (extended abstract). In Proceedings of the Twenty- Ninth Annual A CM Symposium on Theory of Computing, pages 140-149, E1 Paso, Texas, 4--6 May 1997.

Digital Library

Google Scholar

[23]

M. Pinedo. On-Line Algorithms, Lecture Notes in Computer Science. Prentice Hall, 1995.

Google Scholar

[24]

J. Stall. On-line algorithms, lecture notes in computer science. In A. Fiat and G. Woeginger, editors, On-Line Scheduling-- A survey, Berlin, 1997. Springer Verlag. To appear.

Google Scholar

[25]

C. A. Waldspurger, T. Hogg, B. A. Huberman, J. O. Kephart, and W. S. Stornetta. Spawn: A distributed computational economy. IEEE Transactions on Software Engineering, 18(2):103--117, Feb. 1992.

Digital Library

Google Scholar

[26]

L. Zhang. Virtual clock: A new traffic control algorithm for packet switching networks. SIGCOMM 90, pages 19-29, 1990.

Digital Library

Google Scholar

Cited By

View all

Palyvos-Giannas DMencagli GPapatriantafilou MGulisano VZhang KGherbi AVenkatasubramanian NVeiga L(2021)LachesisProceedings of the 22nd International Middleware Conference10.1145/3464298.3493407(365-378)Online publication date: 6-Dec-2021
https://dl.acm.org/doi/10.1145/3464298.3493407
Jahanjou HRajaraman RStalfa DScheideler CSpear M(2020)Scheduling Flows on a Switch to Optimize Response TimesProceedings of the 32nd ACM Symposium on Parallelism in Algorithms and Architectures10.1145/3350755.3400218(305-315)Online publication date: 6-Jul-2020
https://dl.acm.org/doi/10.1145/3350755.3400218
Palyvos-Giannas DGulisano VPapatriantafilou M(2019)HarenProceedings of the 13th ACM International Conference on Distributed and Event-based Systems10.1145/3328905.3329505(19-30)Online publication date: 24-Jun-2019
https://dl.acm.org/doi/10.1145/3328905.3329505
Show More Cited By

Index Terms

Flow and stretch metrics for scheduling continuous job streams

Recommendations

Flow shop scheduling with two distinct job due dates
Highlights
- Flow shop scheduling problems with two distinct job due dates.
- Solvability with ordered or proportionate job processing times.
- Proportionate flow shop with variable machine speeds is NP-hard.
- No-wait problem with ordered jobs/...
Abstract
We consider flow shop scheduling problems with two distinct job due dates. Motivated by the NP-hardness of these problems with arbitrary job processing times, we focus on their solvability with ordered or proportionate job processing times. We ...
Parallel job scheduling algorithms
Scheduling to Minimize Average Stretch

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

SODA '98: Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms

January 1998

704 pages

ISBN:0898714109

Chairman:
Howard Karloff

Publisher

Society for Industrial and Applied Mathematics

United States

Publication History

Published: 01 January 1998

Check for updates

Qualifiers

Article

Conference

SODA98

Sponsor:

SIGACT
SIAM

SODA98: 1998 Conference on Discrete Algorithms

January 25 - 27, 1998

California, San Francisco, USA

Acceptance Rates

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

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

67
Total Citations
View Citations
870
Total Downloads

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

Reflects downloads up to 18 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Palyvos-Giannas DMencagli GPapatriantafilou MGulisano VZhang KGherbi AVenkatasubramanian NVeiga L(2021)LachesisProceedings of the 22nd International Middleware Conference10.1145/3464298.3493407(365-378)Online publication date: 6-Dec-2021
https://dl.acm.org/doi/10.1145/3464298.3493407
Jahanjou HRajaraman RStalfa DScheideler CSpear M(2020)Scheduling Flows on a Switch to Optimize Response TimesProceedings of the 32nd ACM Symposium on Parallelism in Algorithms and Architectures10.1145/3350755.3400218(305-315)Online publication date: 6-Jul-2020
https://dl.acm.org/doi/10.1145/3350755.3400218
Palyvos-Giannas DGulisano VPapatriantafilou M(2019)HarenProceedings of the 13th ACM International Conference on Distributed and Event-based Systems10.1145/3328905.3329505(19-30)Online publication date: 24-Jun-2019
https://dl.acm.org/doi/10.1145/3328905.3329505
Shirali AKazemi Kordestani JMeybodi M(2018)Self-adaptive multi-population genetic algorithms for dynamic resource allocation in shared hosting platformsGenetic Programming and Evolvable Machines10.1007/s10710-018-9326-319:4(505-534)Online publication date: 1-Dec-2018
https://dl.acm.org/doi/10.1007/s10710-018-9326-3
Lucarelli GMendonca FTrystram D(2017)A new on-line method for scheduling independent tasksProceedings of the 17th IEEE/ACM International Symposium on Cluster, Cloud and Grid Computing10.1109/CCGRID.2017.82(140-149)Online publication date: 14-May-2017
https://dl.acm.org/doi/10.1109/CCGRID.2017.82
Anand SBringmann KFriedrich TGarg NKumar A(2017)Minimizing Maximum (Weighted) Flow-Time on Related and Unrelated MachinesAlgorithmica10.1007/s00453-015-0082-y77:2(515-536)Online publication date: 1-Feb-2017
https://dl.acm.org/doi/10.1007/s00453-015-0082-y
Pietri ISakellariou R(2016)Mapping Virtual Machines onto Physical Machines in Cloud ComputingACM Computing Surveys10.1145/298357549:3(1-30)Online publication date: 12-Oct-2016
https://dl.acm.org/doi/10.1145/2983575
Agrawal KLi JLu KMoseley BScheideler CGilbert S(2016)Scheduling Parallelizable Jobs Online to Minimize the Maximum Flow TimeProceedings of the 28th ACM Symposium on Parallelism in Algorithms and Architectures10.1145/2935764.2935782(195-205)Online publication date: 11-Jul-2016
https://dl.acm.org/doi/10.1145/2935764.2935782
Im SKulkarni JScheideler CGilbert S(2016)Fair Online Scheduling for Selfish Jobs on Heterogeneous MachinesProceedings of the 28th ACM Symposium on Parallelism in Algorithms and Architectures10.1145/2935764.2935773(185-194)Online publication date: 11-Jul-2016
https://dl.acm.org/doi/10.1145/2935764.2935773
Serwadda APhoha V(2015)When Mice devour the ElephantsComputers and Security10.1016/j.cose.2015.04.01453:C(31-43)Online publication date: 1-Sep-2015
https://dl.acm.org/doi/10.1016/j.cose.2015.04.014
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

Flow shop scheduling with two distinct job due dates

Parallel job scheduling algorithms

Scheduling to Minimize Average Stretch