×

Approximating total flow time on parallel machines. (English) Zbl 1120.90022

Summary: We consider the problem of optimizing the total flow time of a stream of jobs that are released over time in a multiprocessor setting. This problem is NP-hard even when there are only two machines and preemption is allowed. Although the total (or average) flow time is widely accepted as a good measurement of the overall quality of service, no approximation algorithms were known for this basic scheduling problem.
This paper contains two main results. We first prove that when preemption is allowed, Shortest Remaining Processing Time (SRPT) is an \(O (\log(\min \{\frac{n}{m}, P\}))\) source approximation algorithm for the total flow time, where \(n\) is the number of jobs, \(m\) is the number of machines, and \(P\) is the ratio between the maximum and the minimum processing time of a job. We also provide an \(\Omega(\log (\frac {n}{m}+P))\) lower bound on the (worst case) competitive ratio of any randomized algorithm for the on-line problem in which jobs are known at their release times. Thus, we show that up to a constant factor SRPT is an optimal on-line algorithm.
Our second main result addresses the non-preemptive case. We present a general technique that allows to transform any preemptive solution into a non-preemptive solution at the expense of an \(O(\sqrt {n/m})\) factor in the approximation ratio of the total flow time. Combining this technique with our previous result yields an \(O (\sqrt {n/m} \;\log \frac {n}{m})\) approximation algorithm for this case. We also show an \(\Omega (n^{1/3-\epsilon})\) lower bound on the approximability of this problem (assuming \(\text{P} \neq \text{NP}\)).

MSC:

90B35 Deterministic scheduling theory in operations research
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
68W25 Approximation algorithms
68M20 Performance evaluation, queueing, and scheduling in the context of computer systems
68W20 Randomized algorithms
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] N. Avrahami, Y. Azar, Minimizing total flow time and total completion time with immediate dispatching, in: Proceedings of the 15th Annual ACM Symposium on Parallel Algorithms, 2003, pp. 11-18; N. Avrahami, Y. Azar, Minimizing total flow time and total completion time with immediate dispatching, in: Proceedings of the 15th Annual ACM Symposium on Parallel Algorithms, 2003, pp. 11-18 · Zbl 1111.68013
[2] Awerbuch, B.; Azar, Y.; Leonardi, S.; Regev, O., Minimizing the flow time without migration, SIAM J. Comput., 31, 5, 1370-1382 (2001) · Zbl 1051.68072
[3] Baker, K. R., Introduction to Sequencing and Scheduling (1974), Wiley: Wiley New York
[4] N. Bansal, K. Dhamdhere, Minimizing weighted flow time, in: Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms, 2003, pp. 508-516; N. Bansal, K. Dhamdhere, Minimizing weighted flow time, in: Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms, 2003, pp. 508-516 · Zbl 1092.68540
[5] Becchetti, L.; Leonardi, S., Non-clairvoyant scheduling to minimize the average flow time on single and parallel machines, J. ACM, 4, 51, 517-539 (2004) · Zbl 1204.90035
[6] Becchetti, L.; Leonardi, S.; Muthukrishnan, S., Scheduling to minimize average stretch without migration, J. Comput. System Sci., 68, 80-95 (2004) · Zbl 1072.68015
[7] C. Chekuri, S. Khanna, A. Zhu, Algorithms for minimizing weighted flow time, in: Proceedings on 33rd Annual ACM Symposium on Theory of Computing, 2001, pp. 84-93; C. Chekuri, S. Khanna, A. Zhu, Algorithms for minimizing weighted flow time, in: Proceedings on 33rd Annual ACM Symposium on Theory of Computing, 2001, pp. 84-93 · Zbl 1323.90019
[8] Du, J.; Leung, J. Y.T.; Young, G. H., Minimizing mean flow time with release time constraint, Theoret. Comput. Sci., 75, 347-355 (1990) · Zbl 0701.68008
[9] Sgall, J., On-line scheduling, (Fiat, A.; Woeginger, G., Online Algorithms: The State of the Art (1998), Springer-Verlag)
[10] Garey, M. R.; Johnson, D. S., Computers and Intractability (1979), Freeman and Company: Freeman and Company San Francisco · Zbl 0411.68039
[11] Hall, L., Approximation algorithms for scheduling, (Hochbaum, D., Approximation Algorithms for NP-Hard Problems (1997), PWS Publisher: PWS Publisher Boston)
[12] Kalyanasundaram, B.; Pruhs, K. R., Minimizing flow time nonclairvoyantly, J. ACM, 50, 4, 551-567 (2003) · Zbl 1325.90042
[13] H. Kellerer, T. Tautenhahn, G.J. Woeginger, Approximability and nonapproximability results for minimizing total flow time on a single machine, in: Proceedings of the 28th Annual ACM Symposium on the Theory of Computing, 1996, pp. 418-426; H. Kellerer, T. Tautenhahn, G.J. Woeginger, Approximability and nonapproximability results for minimizing total flow time on a single machine, in: Proceedings of the 28th Annual ACM Symposium on the Theory of Computing, 1996, pp. 418-426 · Zbl 0915.90151
[14] Hall, L. A.; Schulz, A. S.; Shmoys, D. B.; Wein, J., Scheduling to minimize average completion time: Off-line and on-line algorithms, Math. Oper. Res., 22, 3, 513-544 (1997) · Zbl 0883.90064
[15] Leonardi, S., A simpler proof of preemptive total flow time approximation on parallel machines, (Bampis, E., Efficient Approximation and Online Algorithms, Recent Progress on Classical Combinatorial Optimization Problems and New Applications. Efficient Approximation and Online Algorithms, Recent Progress on Classical Combinatorial Optimization Problems and New Applications, Lecture Notes in Comput. Sci., vol. 3484 (2006), Springer-Verlag), 203-212 · Zbl 1132.90328
[16] S. Leonardi, D. Raz, Approximating total flow time on parallel machines. in: Proceedings of the 29th ACM Symposium on Theory of Computing, 1997, pp. 110-119; S. Leonardi, D. Raz, Approximating total flow time on parallel machines. in: Proceedings of the 29th ACM Symposium on Theory of Computing, 1997, pp. 110-119 · Zbl 0962.68007
[17] Lawler, E. L.; Lenstra, J. K.; Rinnooy Kan, A. H.G.; Shmoys, D. B., Sequencing and scheduling: Algorithms and complexity, (Handbooks in Operations Research and Management Science, vol. 4: Logistics of Production and Inventory (1990)) · Zbl 0482.68035
[18] Lenstra, J. K., Sequencing by Enumerative Methods, Math. Centre Tracts, vol. 69 (1977), Mathematisch Centrum: Mathematisch Centrum Amsterdam · Zbl 0407.90025
[19] Motwani, R.; Phillips, S.; Torng, E., Non-clairvoyant scheduling, Theoret. Comput. Sci., 130, 17-47 (1994)
[20] S. Muthukrishnan, R. Rajaraman, R. Shaheen, J. Gehrke, Online scheduling to minimize average stretch, in: Proceedings of the 40th Annual IEEE Symposium on Foundations of Computer Science, 1999, pp. 433-442; S. Muthukrishnan, R. Rajaraman, R. Shaheen, J. Gehrke, Online scheduling to minimize average stretch, in: Proceedings of the 40th Annual IEEE Symposium on Foundations of Computer Science, 1999, pp. 433-442 · Zbl 1087.68017
[21] Pruhs, K.; Torng, E.; Sgall, J., Online scheduling, (Leung, Joseph Y.-T., Handbook of Scheduling: Algorithms, Models, and Performance Analysis (2004), CRC Press), 15-1-15-41, (Chapter 15)
[22] Schurman, P.; Woeginger, G. J., Polynomial time approximation algorithms for machine scheduling. Ten open problems, J. Sched., 2, 203-213 (1999) · Zbl 0938.90032
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.