{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,6]],"date-time":"2026-03-06T17:46:58Z","timestamp":1772819218615,"version":"3.50.1"},"reference-count":29,"publisher":"Elsevier BV","issue":"1","license":[{"start":{"date-parts":[[2000,3,1]],"date-time":"2000-03-01T00:00:00Z","timestamp":951868800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"},{"start":{"date-parts":[[2013,7,17]],"date-time":"2013-07-17T00:00:00Z","timestamp":1374019200000},"content-version":"vor","delay-in-days":4886,"URL":"https:\/\/www.elsevier.com\/open-access\/userlicense\/1.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Theoretical Computer Science"],"published-print":{"date-parts":[[2000,3]]},"DOI":"10.1016\/s0304-3975(99)00186-3","type":"journal-article","created":{"date-parts":[[2002,7,25]],"date-time":"2002-07-25T15:51:20Z","timestamp":1027612280000},"page":"109-141","source":"Crossref","is-referenced-by-count":66,"title":["Scheduling in the dark"],"prefix":"10.1016","volume":"235","author":[{"given":"Jeff","family":"Edmonds","sequence":"first","affiliation":[]}],"member":"78","reference":[{"key":"10.1016\/S0304-3975(99)00186-3_BIB1","unstructured":"P. Berman, C. Coulston, Speed is more powerful than clairvoyance SWAT 98."},{"key":"10.1016\/S0304-3975(99)00186-3_BIB2","doi-asserted-by":"crossref","first-page":"519","DOI":"10.1016\/S0166-5316(96)90044-9","article-title":"Using parallel program characteristics in dynamic multiprocessor allocation policies","volume":"27 & 28","author":"Brecht","year":"1996","journal-title":"Performance Evaluat."},{"key":"10.1016\/S0304-3975(99)00186-3_BIB3","doi-asserted-by":"crossref","unstructured":"S.H. Chiang, R.K. Mansharamani, M. Vernon, Use of application characteristics and limited preemption for run-to-completion parallel processor scheduling policies, Proc. 1994 ACM SIGMETRICS Conf. on Measurement and Modeling of Computer Systems, 1994, pp. 33\u201344.","DOI":"10.1145\/183018.183023"},{"key":"10.1016\/S0304-3975(99)00186-3_BIB4","doi-asserted-by":"crossref","unstructured":"X. Deng, P. Dymond, On multiprocessor system scheduling, 7th ACM Symp. on Parallel Architectures and Algorithms, June 1996.","DOI":"10.1145\/237502.237510"},{"key":"10.1016\/S0304-3975(99)00186-3_BIB5","unstructured":"X. Deng, N. Gu, T. Brecht, K. Lu, Preemptive scheduling of parallel jobs on multiprocessors, 7th Annual ACM-SIAM Symp. on Discrete Algorithms, Atlanta, Georgia, January 1996, pp. 159\u2013167."},{"key":"10.1016\/S0304-3975(99)00186-3_BIB6","unstructured":"X. Deng, E. Koutsoupias, Competitive implementation of parallel programs, 4th Annual ACM-SIAM Symp. on Discrete Algorithms, 1993, pp. 455\u2013461."},{"key":"10.1016\/S0304-3975(99)00186-3_BIB7","doi-asserted-by":"crossref","unstructured":"J. Edmonds, D. Chinn, T. Brecht, X. Deng, Non-clairvoyant multiprocessor scheduling of jobs with changing execution characteristics, 29th Ann. ACM Symp. on Theory of Computing, pp. 120\u2013129, 1997 and submitted to the SIAM J. Comput.","DOI":"10.1145\/258533.258565"},{"key":"10.1016\/S0304-3975(99)00186-3_BIB8","doi-asserted-by":"crossref","unstructured":"J. Edmonds, Scheduling in the Dark In 31st Ann. ACM Symp. on Theory of Computing, 1999.","DOI":"10.1145\/301250.301299"},{"key":"10.1016\/S0304-3975(99)00186-3_BIB9","doi-asserted-by":"crossref","unstructured":"B. Kalyanasundaram, K. Pruhs, Minimizing flow time nonclairvoyantly, Proc. 38th Symp. on Foundations of Computer Science, October 1997.","DOI":"10.1109\/SFCS.1997.646123"},{"key":"10.1016\/S0304-3975(99)00186-3_BIB10","doi-asserted-by":"crossref","unstructured":"B. Kalyanasundaram, K. Pruhs, Speed is as powerful as clairvoyance, Proc. 36th Symp. on Foundations of Computer Science, October 1995, pp. 214\u2013221.","DOI":"10.1109\/SFCS.1995.492478"},{"key":"10.1016\/S0304-3975(99)00186-3_BIB11","doi-asserted-by":"crossref","first-page":"79","DOI":"10.1007\/BF01762111","article-title":"Competitive snoopy caching","volume":"3","author":"Karlin","year":"1988","journal-title":"Algorithmica"},{"issue":"9","key":"10.1016\/S0304-3975(99)00186-3_BIB12","doi-asserted-by":"crossref","first-page":"1088","DOI":"10.1109\/12.2259","article-title":"Measuring parallelism in computation-intensive scientific\/engineering applications","volume":"37","author":"Kumar","year":"1988","journal-title":"IEEE Trans. Comput."},{"key":"10.1016\/S0304-3975(99)00186-3_BIB13","doi-asserted-by":"crossref","unstructured":"S. Leonardi, D. Raz, Approximating total flow time on parallel machines, ACM Symp. on Theory of Computing, 1997.","DOI":"10.1145\/258533.258562"},{"key":"10.1016\/S0304-3975(99)00186-3_BIB14","unstructured":"S. Leutenegger, M. Vernon, The performance of multiprogrammed multiprocessor scheduling policies, Proc. 1990 ACM SIGMETRICS Conf. on Measurement and Modeling of Computer Systems, Boulder, Colorado, May 1990, pp. 226\u2013236."},{"key":"10.1016\/S0304-3975(99)00186-3_BIB15","doi-asserted-by":"crossref","unstructured":"M. Manasse, L. McGeoch, D. Sleator, Competitive algorithms for on-line problems, Proc. 20th Annual ACM Symp. on the Theory of Computing, 1988, pp. 322\u2013333.","DOI":"10.1145\/62212.62243"},{"key":"10.1016\/S0304-3975(99)00186-3_BIB16","doi-asserted-by":"crossref","unstructured":"Matsumoto, Competitive analysis of the round robin algorithm, 3rd Int. Symp. on Algorithms and Computation, 1992, pp. 71\u201377.","DOI":"10.1007\/3-540-56279-6_59"},{"issue":"2","key":"10.1016\/S0304-3975(99)00186-3_BIB17","doi-asserted-by":"crossref","first-page":"146","DOI":"10.1145\/151244.151246","article-title":"A dynamic processor allocation policy for multiprogrammed, shared memory multiprocessors","volume":"11","author":"McCann","year":"1993","journal-title":"ACM Trans. Comput. Systems"},{"key":"10.1016\/S0304-3975(99)00186-3_BIB18","doi-asserted-by":"crossref","unstructured":"C. McCann, J. Zahorjan, Scheduling memory constrained jobs on distributed memory parallel computers, Proc. Inter. Joint. Conf. on Measurement and Modeling of Computer Systems, ACM SIGMETRICS 95 and Performance 95, 1995, pp. 208\u2013219.","DOI":"10.1145\/223587.223610"},{"key":"10.1016\/S0304-3975(99)00186-3_BIB19","unstructured":"R. Motwani, S. Phillips, E. Torng, Non-clairvoyant scheduling, Theoret. Comput. Sci. (Special Issue on Dynamic and On-Line Algorithms) 130 (1994) 17\u201347. Preliminary Version: Proceedings of the 4th Annual ACM-SIAM Symp. on Discrete Algorithms, 1993, pp. 422\u2013431."},{"key":"10.1016\/S0304-3975(99)00186-3_BIB20","doi-asserted-by":"crossref","unstructured":"T. Nguyen, R. Vaswani, J. Zahorjan, Maximizing speedup through self-tuning of processor allocation, Proc. 10th Int. Parallel Processing Symp. Waikiki, HI, April 1996, pp. 463\u2013468.","DOI":"10.1109\/IPPS.1996.508096"},{"key":"10.1016\/S0304-3975(99)00186-3_BIB21","doi-asserted-by":"crossref","unstructured":"C. Phillips, C. Stein, E. Torng, J. Wein, Optimal time-critical scheduling via resource augmentation, 29th Ann. ACM Symp. on Theory of Computing, pp. 140\u2013149, 1997, SIAM J. Comput., submitted.","DOI":"10.1145\/258533.258570"},{"key":"10.1016\/S0304-3975(99)00186-3_BIB22","doi-asserted-by":"crossref","unstructured":"U. Schwiegelshohn, W. Ludwig, J. Wolf, J. Turek, P. Yu, Smart SMART bounds for weighted response time scheduling, SIAM J. Comput., to appear.","DOI":"10.1137\/S0097539795286831"},{"issue":"2-3","key":"10.1016\/S0304-3975(99)00186-3_BIB23","doi-asserted-by":"crossref","first-page":"107","DOI":"10.1016\/0166-5316(94)90036-1","article-title":"Application scheduling and processor allocation in multiprogrammed parallel processing systems","volume":"19","author":"Sevick","year":"1994","journal-title":"Performance Evaluat."},{"issue":"2","key":"10.1016\/S0304-3975(99)00186-3_BIB24","doi-asserted-by":"crossref","first-page":"202","DOI":"10.1145\/2786.2793","article-title":"Amortized efficiency of list update and paging rules","volume":"28","author":"Sleator","year":"1985","journal-title":"Comm. ACM"},{"key":"10.1016\/S0304-3975(99)00186-3_BIB25","doi-asserted-by":"crossref","unstructured":"A. Tucker, A. Gupta, Process control and scheduling issues for multiprogrammed shared-memory multiprocessors, Proc. 12th ACM Symp. Operating Systems Principles, 1989, pp. 159\u2013166.","DOI":"10.1145\/74850.74866"},{"key":"10.1016\/S0304-3975(99)00186-3_BIB26","doi-asserted-by":"crossref","unstructured":"J. Turek, W. Ludwig, J.L. Wolf, L. Fleischer, P. Tiwari, J. Glasgow, U. Schwiegelshohn, P.S. Yu, Scheduling parallelizable tasks to minimize average response time, 6th Annual ACM Symp. on Parallel Algorithms and Architectures, June 1994, pp. 200\u2013209.","DOI":"10.1145\/181014.181331"},{"key":"10.1016\/S0304-3975(99)00186-3_BIB27","doi-asserted-by":"crossref","unstructured":"J. Turek, U. Schwiegelsohn, J. Wolf, P. Yu, Scheduling parallel tasks to minimize average response time, Proc. 5th SIAM Symp. on Discrete Algorithms, 1994, pp. 112\u2013121.","DOI":"10.1145\/181014.181331"},{"key":"10.1016\/S0304-3975(99)00186-3_BIB28","doi-asserted-by":"crossref","unstructured":"A. Yao, Probablistic computations: towards a unified measure of complexity, Proc. of 18th IEEE Symp. on Foundations of Computer Science, 1977, pp. 222\u2013227.","DOI":"10.1109\/SFCS.1977.24"},{"key":"10.1016\/S0304-3975(99)00186-3_BIB29","doi-asserted-by":"crossref","unstructured":"J. Zahorjan, C. McCann, Processor scheduling in shared memory multiprocessors, Proc. 1990 ACM SIGMETRICS Conf. on Measurement and Modeling of Computer Systems, Boulder, Colorado, May 1990, pp. 214\u2013225.","DOI":"10.1145\/98457.98760"}],"container-title":["Theoretical Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0304397599001863?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0304397599001863?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2024,12,4]],"date-time":"2024-12-04T10:02:24Z","timestamp":1733306544000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S0304397599001863"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2000,3]]},"references-count":29,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2000,3]]}},"alternative-id":["S0304397599001863"],"URL":"https:\/\/doi.org\/10.1016\/s0304-3975(99)00186-3","relation":{},"ISSN":["0304-3975"],"issn-type":[{"value":"0304-3975","type":"print"}],"subject":[],"published":{"date-parts":[[2000,3]]}}}