Minimizing the flow time without migration. (English) Zbl 1345.68025
Vitter, Jeffrey Scott (ed.) et al., Proceedings of the 31st annual ACM symposium on theory of computing, STOC 1999. Atlanta, GA, USA, May 1–4, 1999. New York, NY: ACM, Association for Computing Machinery (ISBN 1-58113-067-8). 198-205 (1999).
MSC:
| 68M20 | Performance evaluation, queueing, and scheduling in the context of computer systems |
| 68W25 | Approximation algorithms |
| 68W27 | Online algorithms; streaming algorithms |
Citations:
Zbl 0962.68007References:
| [1] | K.R. Baker. Introduction to Sequencing and Scheduling. Wiley, 1974. |
| [2] | 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. 10.1016/0304-3975(90)90100-V · Zbl 0701.68008 |
| [3] | L. Hall, D. Shraoys, and J. Wein. Scheduling to minimize average completion time: Off-line and on-line algorithms. In Proc. of 7th ACM-SIAM Symposium on Discrete Algorithms, pages 142-151, 1996. · Zbl 0845.90071 |
| [4] | L.A. Halt. Approximation algorithms for scheduling. In D.S. Hochbaum, edi or, Approximation atgoritl tns for NP-hard problems, pages 1-45. PWS publishing company, 1997. |
| [5] | H. Kellerer, T Tautenhahn and G.J. Woeginger. Approximability and nonapproximability results for minim/zing total flow time on a single machine. Proc. of the 28th Annual ACM Symposium on the Theory of Computing, pp. 418-426, 1996. 10.1145/237814.237989 · Zbl 0915.90151 |
| [6] | E.L. Lawler, J.K Lenstra, A.H.G. Rinnooy Kan, and D.! . Shmoys. Sequencing and scheduling: algorithms and comptexity. In Handbooks in operations research and management science, volume 4, pages 445-522. North Holland, 1993. · Zbl 0798.90028 |
| [7] | S. Leonardi and D. Raz. Approximating total flow time on parallel machines. In Proceedings of the Twenty- Ninth Annual ACM Symposium on Theory of Computing, pages t l 0-1 t 9, E1 Paso, Texas, 1997. 10.1145/258533.258562 · Zbl 0962.68007 |
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.
