Scheduling in the dark. (English) Zbl 1345.68028
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). 179-188 (1999).
MSC:
| 68M20 | Performance evaluation, queueing, and scheduling in the context of computer systems |
| 68Q17 | Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) |
References:
| [1] | P. Berman and C. CouLston. Speed is more powerful than clairvoyance SWAT 98. |
| [2] | T. Brecht and K. Guha. Using parallel program characteristics in dynamic multiproceasor allocation policies. Performance Evatualion, 27 & 28:519-539, Oct. · Zbl 0875.68122 |
| [3] | X. Deng and P. Dymond. On multiprocessor system scheduling. {n Seventh A CM Symposium on Parallel Architectures and Algorithms, June 1996. 10.1145/237502.237510} · Zbl 0911.90206 |
| [4] | X. Deng, N. Gu T. Brecht, and K. Lu. Preempti scheduling of parallel jobs on multiprocessors. In Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, pages 159- t67, Atlanta, Georgia, January 1996. · Zbl 0845.90069 |
| [5] | X. Deng and E. Koutsoupias. Competitive implementation of parallel programs. In Fourth Annual ACM-SIAM Symposium on Discrete Algorithms , pages 455-461, 1993. · Zbl 0801.68075 |
| [6] | J. Edmonds, D. Chinn, T. Brecht, X. Deng. Non-clairvoyant Multiprocessor Scheduling of Jobs with Changing Execution Characteristics. In 29th Ann. A CM Syrup, on Theory o/ Computing, pp. 120-129, 1997 and submitted to the SIAM Journal o Computing. 10.1145/258533.258565 · Zbl 0968.68009 |
| [7] | J. Edmonds. Scheduling in the Dark In 31st Ann. ACM S tmp. on Th or t of Computing, 1999 10.1145/301250.301299 · Zbl 1345.68028 |
| [8] | B. Kalyanasundararn and K. Pruhs. Minimizing flow time nonclairvoyantly In Proceedings of the 38th Symposium on FoundaIions of Computer Science, October 1997. |
| [9] | B. Kalyanasundaram and K. Pruhs. Speed is as powerful as clairvoyance. In Proceedings o · Zbl 0938.68545 |
| [10] | M. Kumar. Measuring parallelism in computation-intensive scientific/engineering applications. IEEE Trunsactions on Computers, 37(9):1088-1098, September 1988. 10.1109/12.2259 |
| [11] | S. Leonardi and D. Raz, Approximating total flow time on parallel machines, In A CM Symposium on Theory o Computing, 1997. 10.1145/258533.258562 · Zbl 0962.68007 |
| [12] | Matsumoto. Competitive An lys s of the Round Robin Algorithm 3rd International Symposium on Algorithms and Computation, 71-77, 1992. |
| [13] | R. Motwanl, S. Phillips, and E. Torng. Non-clairvoyant scheduling. Theoretical Computer Science (Special Issue on Dynamic and On-Line Algorithms), 130 (1994), pp. 17-47. Preliminary Version: Proceedings of the 4th AnnuaI ACM- SIAM Symposium on Discrete Algorithms, 1993, pp. 422- 431. 10.1016/0304-3975(94)90151-1 · Zbl 0801.68013 |
| [14] | C. Phillips, C. Stein, E. Torng, J. Wein. Optimal Time- Critical Scheduling Via Resource Augmentation In 29 a Ann. ACM Syrup. on Theory o/ Computing, pp. 140-149, 1997 and submitted to the SlAM Journal on Computing. 10.1145/258533.258570 · Zbl 0962.68010 |
| [15] | U. Schwiegelshohn, W. Ludwig, J. Wolf, J. Turek, and P. Yu. Smart SMART bounds for weighted response time scheduling. To appear in SIAM Journal on Computing. 10.1137/S0097539795286831 · Zbl 0914.68094 |
| [16] | A. Tucker and A. Gupta. Process control and scheduling issues for rault programmed shared-memory multiprocessors. In Proceedings o/the Twelfth A CM Symposium on Operating Systems Principles, pages 159-{66, 1989. 10.1145/74850.74866} |
| [17] | J. Turek, W. Ludwig, J. L. Wolf, L. Fleischer, P. Tiwari, J. Glasgow, U. Schwiegelshohn, and P. S. Yu. Scheduling paratletizable tasks to minimize a erage response time. In 6th Annual A CM Symposium on Parallel Algorithms and Architectures, pages 200-209, June 1994. 10.1145/181014.181331 |
| [18] | J. Turek, U. Schwiegelshohn, J. Wolf, and P. Yu. Scheduling parallel tasks to minimize average response time. In Proceedings of the 5th SIAM Symposium on Discrete Algorithms, pages 112-12 t, 1994. · Zbl 1114.68337 |
| [19] | A. Yao, Probablistic Computations: Towards a Unified Measure of Complexity. In Proc. o/18th IEEE Syrup. on Foundations of Computer Schience (1977) 222-227. |
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.
