Keywords and Synonyms
Flow time: response time
Problem Definition
Shortest-job-first heuristics arise in sequencing problems, when the goal is minimizing the perceived latency of users of a multiuser or multitasking system. In this problem, the algorithm has to schedule a set of jobs on a pool of m identical machines. Each job has a release date and a processing time, and the goal is to minimize the average time spent by jobs in the system. This is normally considered a suitable measure of the quality of service provided by a system to interactive users. This optimization problem can be more formally described as follows:
Input
A set of m identical machines and a set of n jobs \( { 1, 2,\ldots , n } \). Every job j has a release date r j and a processing time p j . In the sequel, \( { \mathcal{I} } \) denotes the set of feasible input instances.
Goal
The goal is minimizing the average flow (also known as average response) time of the jobs. Let C j denote the time at which job jis...
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Recommended Reading
Becchetti, L., Leonardi, S.: Nonclairvoyant scheduling to minimize the total flow time on single and parallel machines. J. ACM 51(4), 517–539 (2004)
Crovella, M.E., Frangioso, R., Harchal‐Balter, M.: Connection scheduling in web servers. In: Proceedings of the 2nd USENIX Symposium on Internet Technologies and Systems (USITS-99), 1999 pp. 243–254
Kalyanasundaram, B., Pruhs, K.: Minimizing flow time nonclairvoyantly. J. ACM 50(4), 551–567 (2003)
Kalyanasundaram, B., Pruhs, K.: Speed is as powerful as clairvoyance. J. ACM 47(4), 617–643 (2000)
Kellerer, H., Tautenhahn, T., Woeginger, G.J.: Approximability and nonapproximability results for minimizing total flow time on a single machine. In: Proceedings of 28th Annual ACM Symposium on the Theory of Computing (STOC '96), 1996, pp. 418–426
Leonardi, S., Raz, D.: Approximating total flow time on parallel machines. In: Proceedings of the Annual ACM Symposium on the Theory of Computing STOC, 1997, pp. 110–119
Motwani, R., Phillips, S., Torng, E.: Nonclairvoyant scheduling. Theor. Comput. Sci. 130(1), 17–47 (1994)
Nutt, G.: Operating System Projects Using Windows NT. Addison‐Wesley, Reading (1999)
Schrage, L.: A proof of the optimality of the shortest remaining processing time discipline. Oper. Res. 16(1), 687–690 (1968)
Smith, D.R.: A new proof of the optimality of the shortest remaining processing time discipline. Oper. Res. 26(1), 197–199 (1976)
Tanenbaum, A.S.: Modern Operating Systems. Prentice-Hall, Englewood Cliffs (1992)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2008 Springer-Verlag
About this entry
Cite this entry
Becchetti, L., Leonardi, S., Marchetti-Spaccamela, A., Pruhs, K. (2008). Flow Time Minimization. In: Kao, MY. (eds) Encyclopedia of Algorithms. Springer, Boston, MA. https://doi.org/10.1007/978-0-387-30162-4_146
Download citation
DOI: https://doi.org/10.1007/978-0-387-30162-4_146
Publisher Name: Springer, Boston, MA
Print ISBN: 978-0-387-30770-1
Online ISBN: 978-0-387-30162-4
eBook Packages: Computer ScienceReference Module Computer Science and Engineering