{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,14]],"date-time":"2026-04-14T16:24:05Z","timestamp":1776183845406,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":97,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540635741","type":"print"},{"value":"9783540695998","type":"electronic"}],"license":[{"start":{"date-parts":[[1997,1,1]],"date-time":"1997-01-01T00:00:00Z","timestamp":852076800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1997]]},"DOI":"10.1007\/3-540-63574-2_14","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T23:30:07Z","timestamp":1330299007000},"page":"1-34","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":184,"title":["Theory and practice in parallel job scheduling"],"prefix":"10.1007","author":[{"given":"Dror G.","family":"Feitelson","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Larry","family":"Rudolph","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Uwe","family":"Schwiegelshohn","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Kenneth C.","family":"Sevcik","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Parkson","family":"Wong","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,7,12]]},"reference":[{"issue":"5","key":"1_CR1","doi-asserted-by":"crossref","first-page":"339","DOI":"10.1002\/cpe.4330070502","volume":"7","author":"I. Ahmad","year":"1995","unstructured":"I. Ahmad, \u201cEditorial: resource management of parallel and distributed systems with static scheduling: challenges, solutions, and new problems\u201d. Concurrency \u2014 Pract. & Exp. 7(5), pp. 339\u2013347, Aug 1995.","journal-title":"Concurrency \u2014 Pract. & Exp."},{"key":"1_CR2","doi-asserted-by":"crossref","unstructured":"G. Alverson, S. Kahan, R. Korry, C. McCann, and B. Smith, \u201cScheduling on the Tera MTA\u201d. In Job Scheduling Strategies for Parallel Processing, D. G. Feitelson and L. Rudolph (eds.), pp. 19\u201344, Springer-Verlag, 1995. Lecture Notes in Computer Science Vol. 949.","DOI":"10.1007\/3-540-60153-8_21"},{"key":"1_CR3","doi-asserted-by":"crossref","unstructured":"S. V. Anastiadis and K. C. Sevcik, \u201cParallel application scheduling on networks of workstations\u201d. J. Parallel & Distributed Comput., Jun 1997. (to appear).","DOI":"10.1006\/jpdc.1997.1335"},{"key":"1_CR4","doi-asserted-by":"crossref","unstructured":"J. M. Barton and N. Bitar, \u201cA scalable multi-discipline, multiple-processor scheduling framework for IRIX\u201d. In Job Scheduling Strategies for Parallel Processing, D. G. Feitelson and L. Rudolph (eds.), pp. 45\u201369, Springer-Verlag, 1995. Lecture Notes in Computer Science Vol. 949.","DOI":"10.1007\/3-540-60153-8_22"},{"key":"1_CR5","doi-asserted-by":"crossref","unstructured":"T. B. Brecht, \u201cAn experimental evaluation of processor pool-based scheduling for shared-memory NUMA multiprocessors\u201d. In Job Scheduling Strategies for Parallel Processing, D. G. Feitelson and L. Rudolph (eds.), Springer Verlag, 1997. Lecture Notes in Computer Science (this volume).","DOI":"10.1007\/3-540-63574-2_20"},{"issue":"7","key":"1_CR6","doi-asserted-by":"publisher","first-page":"382","DOI":"10.1145\/361011.361064","volume":"17","author":"J. Bruno","year":"1974","unstructured":"J. Bruno, E. G. Coffman, Jr., and R. Sethi, \u201cScheduling independent tasks to reduce mean finishing time\u201d. Comm. ACM 17(7), pp. 382\u2013387, Jul 1974.","journal-title":"Comm. ACM"},{"key":"1_CR7","doi-asserted-by":"crossref","unstructured":"S. Chakrabarti, C. Phillips, A. S. Achulz, D. B. Shmoys, C. Stein, and J. Wein, \u201cImproved approximation algorithms for minsum criteria\u201d. In Intl. Colloq. Automata, Lang., & Prog., pp. 646\u2013657, Springer-Verlag, 1996. Lecture Notes in Computer Science Vol. 1099.","DOI":"10.1007\/3-540-61440-0_166"},{"key":"1_CR8","doi-asserted-by":"crossref","unstructured":"S-H. Chiang, R. K. Mansharamani, and M. K. Vernon, \u201cUse of application characteristics and limited preemption for run-to-completion parallel processor scheduling policies\u201d. In SIGMETRICS Conf. Measurement & Modeling of Comput. Syst., pp. 33\u201344, May 1994.","DOI":"10.1145\/183018.183023"},{"key":"1_CR9","doi-asserted-by":"crossref","unstructured":"S-H. Chiang and M. K. Vernon, \u201cDynamic vs. static quantum-based parallel processor allocation\u201d. In Job Scheduling Strategies for Parallel Processing, D. G. Feitelson and L. Rudolph (eds.), pp. 200\u2013223, Springer-Verlag, 1996. Lecture Notes in Computer Science Vol. 1162.","DOI":"10.1007\/BFb0022295"},{"key":"1_CR10","unstructured":"R. W. Conway, W. L. Maxwell, and L. W. Miller, Theory of Scheduling. Addison-Wesley, 1967."},{"key":"1_CR11","unstructured":"X. Deng, N. Gu, T. Brecht, and K. Lu, \u201cPreemptive scheduling of parallel jobs on multiprocessors\u201d. In 7th SIAM Symp. Discrete Algorithms, pp. 159\u2013167, Jan 1996."},{"key":"1_CR12","doi-asserted-by":"crossref","unstructured":"A. B. Downey, \u201cUsing queue time predictions for processor allocation\u201d. In Job Scheduling Strategies for Parallel Processing, D. G. Feitelson and L. Rudolph (eds.), Springer Verlag, 1997. Lecture Notes in Computer Science (this volume).","DOI":"10.1007\/3-540-63574-2_15"},{"issue":"4","key":"1_CR13","doi-asserted-by":"publisher","first-page":"473","DOI":"10.1137\/0402042","volume":"2","author":"J. Du","year":"1989","unstructured":"J. Du and J. Y-H. Leung, \u201cComplexity of scheduling parallel task systems\u201d. SIAM J. Discrete Math. 2(4), pp. 473\u2013487, Nov 1989.","journal-title":"SIAM J. Discrete Math."},{"key":"1_CR14","doi-asserted-by":"crossref","unstructured":"K. Dussa, K. Carlson, L. Dowdy, and K-H. Park, \u201cDynamic partitioning in a transputer environment\u201d. In SIGMETRICS Conf. Measurement & Modeling of Comput. Syst., pp. 203\u2013213, May 1990.","DOI":"10.1145\/98460.98759"},{"key":"1_CR15","doi-asserted-by":"crossref","unstructured":"A. Dusseau, R. H. Arpaci, and D. E. Culler, \u201cEffective distributed scheduling of parallel workloads\u201d. In SIGMETRICS Conf. Measurement & Modeling of Comput. Syst., pp. 25\u201336, May 1996.","DOI":"10.1145\/233008.233020"},{"issue":"3","key":"1_CR16","doi-asserted-by":"publisher","first-page":"408","DOI":"10.1109\/12.21127","volume":"38","author":"D. L. Eager","year":"1989","unstructured":"D. L. Eager, J. Zahorjan, and E. D. Lazowska, \u201cSpeedup versus efficiency in parallel systems\u201d. IEEE Trans. Comput. 38(3), pp. 408\u2013423, Mar 1989.","journal-title":"IEEE Trans. Comput."},{"key":"1_CR17","doi-asserted-by":"crossref","unstructured":"D. G. Feitelson, \u201cMemory usage in the LANL CM-5 workload\u201d. In Job Scheduling Strategies for Parallel Processing, D. G. Feitelson and L. Rudolph (eds.), Springer Verlag, 1997. Lecture Notes in Computer Science (this volume).","DOI":"10.1007\/3-540-63574-2"},{"key":"1_CR18","doi-asserted-by":"crossref","unstructured":"D. G. Feitelson, \u201cPacking schemes for gang scheduling\u201d. In Job Scheduling Strategies for Parallel Processing, D. G. Feitelson and L. Rudolph (eds.), pp. 89\u2013110, Springer-Verlag, 1996. Lecture Notes in Computer Science Vol. 1162.","DOI":"10.1007\/BFb0022289"},{"key":"1_CR19","unstructured":"D. G. Feitelson, A Survey of Scheduling in Multiprogrammed Parallel Systems. Research Report RC 19790 (87657), IBM T. J. Watson Research Center, Oct 1994."},{"key":"1_CR20","doi-asserted-by":"crossref","unstructured":"D. G. Feitelson and M. A. Jette, \u201cImproved utilization and responsiveness with gang scheduling\u201d. In Job Scheduling Strategies for Parallel Processing, D. G. Feitelson and L. Rudolph (eds.), Springer Verlag, 1997. Lecture Notes in Computer Science (this volume).","DOI":"10.1007\/3-540-63574-2_24"},{"key":"1_CR21","doi-asserted-by":"crossref","unstructured":"D. G. Feitelson and B. Nitzberg, \u201cJob characteristics of a production parallel scientific workload on the NASA Ames iPSC\/860\u201d. In Job Scheduling Strategies for Parallel Processing, D. G. Feitelson and L. Rudolph (eds.), pp. 337\u2013360, Springer-Verlag, 1995. Lecture Notes in Computer Science Vol. 949.","DOI":"10.1007\/3-540-60153-8_38"},{"issue":"2","key":"1_CR22","doi-asserted-by":"crossref","first-page":"135","DOI":"10.1007\/BF02577787","volume":"23","author":"D. G. Feitelson","year":"1995","unstructured":"D. G. Feitelson and L. Rudolph, \u201cCo-scheduling based on runtime identification of activity working sets\u201d. Intl. J. Parallel Programming 23(2), pp. 135\u2013160, Apr 1995.","journal-title":"Intl. J. Parallel Programming"},{"issue":"1","key":"1_CR23","doi-asserted-by":"crossref","first-page":"18","DOI":"10.1006\/jpdc.1996.0064","volume":"35","author":"D. G. Feitelson","year":"1996","unstructured":"D. G. Feitelson and L. Rudolph, \u201cEvaluation of design choices for gang scheduling using distributed hierarchical control\u201d. J. Parallel & Distributed Comput. 35(1), pp. 18\u201334, May 1996.","journal-title":"J. Parallel & Distributed Comput."},{"issue":"4","key":"1_CR24","doi-asserted-by":"crossref","first-page":"306","DOI":"10.1016\/0743-7315(92)90014-E","volume":"16","author":"D. G. Feitelson","year":"1992","unstructured":"D. G. Feitelson and L. Rudolph, \u201cGang scheduling performance benefits for linegrain synchronization\u201d. J. Parallel & Distributed Comput. 16(4), pp. 306\u2013318, Dec 1992.","journal-title":"J. Parallel & Distributed Comput."},{"key":"1_CR25","doi-asserted-by":"crossref","unstructured":"D. G. Feitelson and L. Rudolph, \u201cToward convergence in job schedulers for parallel supercomputers\u201d. In Job Scheduling Strategies for Parallel Processing, D. G. Feitelson and L. Rudolph (eds.), pp. 1\u201326, Springer-Verlag, 1996. Lecture Notes in Computer Science Vol. 1162.","DOI":"10.1007\/BFb0022284"},{"issue":"1","key":"1_CR26","doi-asserted-by":"publisher","first-page":"49","DOI":"10.1016\/0304-3975(94)90152-X","volume":"130","author":"A. Feldmann","year":"1994","unstructured":"A. Feldmann, J. Sgall, and S-H. Teng, \u201cDynamic scheduling on parallel machines\u201d. Theoretical Comput. Sci. 130(1), pp. 49\u201372, Aug 1994.","journal-title":"Theoretical Comput. Sci."},{"key":"1_CR27","unstructured":"H. Franke, P. Pattnaik, and L. Rudolph, \u201cGang scheduling for highly efficient distributed multiprocessor systems\u201d. In 6th Symp. Frontiers Massively Parallel Comput., pp. 1\u20139, Oct 1996."},{"key":"1_CR28","unstructured":"M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman, 1979."},{"issue":"5","key":"1_CR29","doi-asserted-by":"publisher","first-page":"443","DOI":"10.1109\/32.90447","volume":"17","author":"D. Ghosal","year":"1991","unstructured":"D. Ghosal, G. Serazzi, and S. K. Tripathi, \u201cThe processor working set and its use in scheduling multiprocessor systems\u201d. IEEE Trans. Softw. Eng. 17(5), pp. 443\u2013453, May 1991.","journal-title":"IEEE Trans. Softw. Eng."},{"key":"1_CR30","doi-asserted-by":"crossref","unstructured":"R. Gibbons, A Historical Application Profiler for Use by Parallel Schedulers. Master's thesis, Dept. Computer Science, University of Toronto, Dec 1996. Available as Technical Report CSRI-TR 354.","DOI":"10.1007\/3-540-63574-2_16"},{"key":"1_CR31","doi-asserted-by":"crossref","unstructured":"R. Gibbons, \u201cA historical application profiler for use by parallel schedulers\u201d. In Job Scheduling Strategies for Parallel Processing, D. G. Feitelson and L. Rudolph (eds.), Springer Verlag, 1997. Lecture Notes in Computer Science (this volume).","DOI":"10.1007\/3-540-63574-2_16"},{"key":"1_CR32","first-page":"214","volume":"II","author":"B. Gorda","year":"1995","unstructured":"B. Gorda and R. Wolski, \u201cTime sharing massively parallel machines\u201d. In Intl. Conf. Parallel Processing, vol. II, pp. 214\u2013217, Aug 1995.","journal-title":"Intl. Conf. Parallel Processing"},{"issue":"2","key":"1_CR33","doi-asserted-by":"publisher","first-page":"416","DOI":"10.1137\/0117039","volume":"17","author":"R. L. Graham","year":"1969","unstructured":"R. L. Graham, \u201cBounds on multiprocessing timing anomalies\u201d. SIAM J. Applied Mathematics 17(2), pp. 416\u2013429, Mar 1969.","journal-title":"SIAM J. Applied Mathematics"},{"issue":"3","key":"1_CR34","doi-asserted-by":"crossref","first-page":"257","DOI":"10.1006\/jpdc.1994.1058","volume":"21","author":"A. S. Grimshaw","year":"1994","unstructured":"A. S. Grimshaw, J. B. Weissman, E. A. West, and E. C. Loyot, Jr., \u201cMetasystems: an approach combining parallel processing and heterogeneous distributed computing systems\u201d. J. Parallel & Distributed Comput. 21(3), pp. 257\u2013270, Jun 1994.","journal-title":"J. Parallel & Distributed Comput"},{"key":"1_CR35","doi-asserted-by":"crossref","unstructured":"R. L. Henderson, \u201cJob scheduling under the portable batch system\u201d. In Job Scheduling Strategies for Parallel Processing, D. G. Feitelson and L. Rudolph (eds.), pp. 279\u2013294, Springer-Verlag, 1995. Lecture Notes in Computer Science Vol. 949.","DOI":"10.1007\/3-540-60153-8_34"},{"key":"1_CR36","doi-asserted-by":"crossref","unstructured":"A. Hori et al., \u201cTime space sharing scheduling and architectural support\u201d. In Job Scheduling Strategies for Parallel Processing, D. G. Feitelson and L. Rudolph (eds.), pp. 92\u2013105, Springer-Verlag, 1995. Lecture Notes in Computer Science Vol. 949.","DOI":"10.1007\/3-540-60153-8_24"},{"key":"1_CR37","doi-asserted-by":"crossref","unstructured":"S. Hotovy, \u201cWorkload evolution on the Cornell Theory Center IBM SP2\u201d. In Job Scheduling Strategies for Parallel Processing, D. G. Feitelson and L. Rudolph (eds.), pp. 27\u201340, Springer-Verlag, 1996. Lecture Notes in Computer Science Vol. 1162.","DOI":"10.1007\/BFb0022285"},{"key":"1_CR38","doi-asserted-by":"crossref","unstructured":"N. Islam, A. Prodromidis, and M. S. Squillante, \u201cDynamic partitioning in different distributed-memory environments\u201d. In Job Scheduling Strategies for Parallel Processing, D. G. Feitelson and L. Rudolph (eds.), pp. 244\u2013270, Springer-Verlag, 1996. Lecture Notes in Computer Science Vol. 1162.","DOI":"10.1007\/BFb0022297"},{"key":"1_CR39","doi-asserted-by":"crossref","unstructured":"J. Jann, P. Pattnaik, H. Franke, F. Wang, J. Skovira, and J. Riodan, \u201cModeling of workload in mpps\u201d. In Job Scheduling Strategies for Parallel Processing, D. G. Feitelson and L. Rudolph (eds.), Springer Verlag, 1997. Lecture Notes in Computer Science (this volume).","DOI":"10.1007\/3-540-63574-2_18"},{"key":"1_CR40","unstructured":"Job Scheduling Strategies for Parallel Processing, D. G. Feitelson and L. Rudolph (eds.), Springer-Verlag, 1995. Lecture Notes in Computer Science Vol. 949. Job Scheduling Strategies for Parallel Processing, D. G. Feitelson and L. Rudolph (eds.), Springer-Verlag, 1996. Lecture Notes in Computer Science Vol. 11.62. Job Scheduling Strategies for Parallel Processing, D. G. Feitelson and L. Rudolph (eds.), Springer-Verlag, 1997. Lecture Notes in Computer Science (this volume)."},{"issue":"4","key":"1_CR41","doi-asserted-by":"publisher","first-page":"1119","DOI":"10.1137\/0215081","volume":"15","author":"T. Kawaguchi","year":"1986","unstructured":"T. Kawaguchi and S. Kyan, \u201cWorst case bound of an LRF schedule for the mean weighted flow-time problem\u201d. SIAM J. Comput. 15(4), pp. 1119\u20131129, Nov 1986.","journal-title":"SIAM J. Comput."},{"key":"1_CR42","doi-asserted-by":"crossref","unstructured":"H. Kellerer, T. Tautenhahn, and G. J. W\u00f6ginger, \u201cApproximability and nonapproximability results for minimizing total flow time on a single machine\u201d. In 28th Ann. Symp. Theory of Computing, pp. 418\u2013426, 1996.","DOI":"10.1145\/237814.237989"},{"issue":"12","key":"1_CR43","doi-asserted-by":"publisher","first-page":"1572","DOI":"10.1109\/12.214665","volume":"41","author":"R. Krishnamurti","year":"1992","unstructured":"R. Krishnamurti and. E. Ma, \u201cAn approximation algorithm for scheduling tasks on varying partition sizes in partitionable multiprocessor systems\u201d. IEEE Trans. Comput. 41(12), pp. 1572\u20131579, Dec 1992.","journal-title":"IEEE Trans. Comput."},{"key":"1_CR44","doi-asserted-by":"crossref","unstructured":"R. N. Lagerstrom and S. K. Gipp, \u201cPScheD: political scheduling on the CRAY T3E\u201d. In Job Scheduling Strategies for Parallel Processing; D. G. Feitelson and L. Rudolph (eds.), Springer Verlag, 1997. Lecture Notes in Computer Science (this volume).","DOI":"10.1007\/3-540-63574-2_19"},{"key":"1_CR45","doi-asserted-by":"crossref","unstructured":"W. Lee, M. Frank, V. Lee, K. Mackenzie, and L. Rudolph, \u201cImplications of I\/O for gang scheduled workloads\u201d. In Job Scheduling Strategies far Parallel Processing, D. G. Feitelson and L. Rudolph (eds.), Springer Verlag, 1997. Lecture Notes in Computer Science (this volume)","DOI":"10.1007\/3-540-63574-2_23"},{"issue":"2","key":"1_CR46","doi-asserted-by":"crossref","first-page":"145","DOI":"10.1006\/jpdc.1996.0033","volume":"33","author":"C. E. Leiserson","year":"1996","unstructured":"C. E. Leiserson, Z. S. Abuhamdeh, D. C. Douglas, C. R. Feynman, M. N. Ganmukhi, J. V. Hill, W. D. Hillis, B. C. Kuszmaul, M. A. St. Pierre, D. S. Wells, M. C. Wong-Chan, S-W. Yang, and R. Zak, \u201cThe network architecture of the Con nection Machine CM-5\u201d. J. Parallel & Distributed Comput. 33(2), pp. 145\u2013158, Mar 1996.","journal-title":"J. Parallel & Distributed Comput."},{"key":"1_CR47","doi-asserted-by":"crossref","unstructured":"S. Leonardi and D. Raz, \u201cApproximating total flow time on parallel machines\u201d. In 29th Ann. Symp. Theory of Computing, 1997.","DOI":"10.1145\/258533.258562"},{"key":"1_CR48","doi-asserted-by":"crossref","unstructured":"S. T. Leutenegger and M. K. Vernon, \u201cThe performance of multiprogrammed multiprocessor scheduling policies\u201d. In SIGMETRICS Conf. Measurement & Modeling of Comput. Syst., pp. 226\u2013236, May 1990.","DOI":"10.1145\/98460.98761"},{"key":"1_CR49","doi-asserted-by":"crossref","unstructured":"D. Lifka, \u201cThe ANL\/IBM SP scheduling system\u201d. In Job Scheduling Strategies for Parallel Processing, D. G. Feitelson and L. Rudolph (eds.), pp. 295\u2013303, Springer-Verlag, 1995. Lecture Notes in Computer Science Vol. 949.","DOI":"10.1007\/3-540-60153-8_35"},{"key":"1_CR50","unstructured":"W. Ludwig and P. Tiwari, \u201cScheduling malleable and nonmalleable parallel tasks\u201d. In 5th SIAM Symp. Discrete Algorithms, pp. 167\u2013176, Jan 1994."},{"key":"1_CR51","doi-asserted-by":"crossref","unstructured":"C. McCann and J. Zahorjan, \u201cProcessor allocation policies for message passing parallel computers\u201d. In SIGMETRICS Conf. Measurement & Modeling of Comput. Syst., pp. 19\u201332, May 1994.","DOI":"10.1145\/183019.183022"},{"key":"1_CR52","doi-asserted-by":"crossref","unstructured":"C. McCann and J. Zahorjan, \u201cScheduling memory constrained jobs on distributed memory parallel computers\u201d. In SIGMETRICS Conf. Measurement & Modeling of Comput. Syst., pp. 208\u2013219, May 1995.","DOI":"10.1145\/223586.223610"},{"issue":"1","key":"1_CR53","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1287\/mnsc.6.1.1","volume":"6","author":"R. McNaughton","year":"1959","unstructured":"R. McNaughton, \u201cScheduling with deadlines and loss functions\u201d. Management Science 6(1), pp. 1\u201312, Oct 1959.","journal-title":"Management Science"},{"issue":"1","key":"1_CR54","doi-asserted-by":"crossref","first-page":"9","DOI":"10.1109\/88.219855","volume":"1","author":"P. Messina","year":"1993","unstructured":"P. Messina, \u201cThe Concurrent Supercomputing Consortium: year 1\u201d. IEEE Parallel & Distributed Technology 1(1), pp. 9\u201316, Feb 1993.","journal-title":"IEEE Parallel & Distributed Technology"},{"issue":"1","key":"1_CR55","doi-asserted-by":"publisher","first-page":"17","DOI":"10.1016\/0304-3975(94)90151-1","volume":"130","author":"R. Motwani","year":"1994","unstructured":"R. Motwani, S. Phillips, and E. Torng, \u201cNon-clairvoyant scheduling\u201d. Theoretical Comput. Sci. 130(1), pp. 17\u201347, Aug 1994.","journal-title":"Theoretical Comput. Sci."},{"key":"1_CR56","doi-asserted-by":"crossref","unstructured":"V. K. Naik, S. K. Setia, and M. S. Squillante, \u201cPerformance analysis of job scheduling policies in parallel supercomputing environments\u201d. In Supercomputing '93, pp. 824\u2013833, Nov 1993.","DOI":"10.1145\/169627.169848"},{"issue":"4","key":"1_CR57","doi-asserted-by":"publisher","first-page":"532","DOI":"10.1109\/32.4676","volume":"14","author":"R. Nelson","year":"1988","unstructured":"R. Nelson, D. Towsley, and A. N. Tantawi, \u201cPerformance analysis of parallel processing systems\u201d. IEEE Trans. Softw. Eng. 14(4), pp. 532\u2013540, Apr 1988.","journal-title":"IEEE Trans. Softw. Eng."},{"key":"1_CR58","doi-asserted-by":"crossref","unstructured":"T. D. Nguyen, R. Vaswani, and J. Zahorjan, \u201cParallel application characterization for multiprocessor scheduling policy design\u201d. In Job Scheduling Strategies for Parallel Processing, D. G. Feitelson and L. Rudolph (eds.), pp. 175\u2013199, Springer-Verlag, 1996. Lecture Notes in Computer Science Vol. 1162.","DOI":"10.1007\/BFb0022294"},{"key":"1_CR59","doi-asserted-by":"crossref","unstructured":"T. D. Nguyen, R. Vaswani, and J. Zahorjan, \u201cUsing runtime measured workload characteristics in parallel processor scheduling\u201d. In Job Scheduling Strategies for Parallel Processing, D. G. Feitelson and L. Rudolph (eds.), pp. 155\u2013174, Springer-Verlag, 1996. Lecture Notes in Computer Science Vol. 1162.","DOI":"10.1007\/BFb0022293"},{"key":"1_CR60","doi-asserted-by":"crossref","unstructured":"J. D. Padhye and L. Dowdy, \u201cDynamic versus adaptive processor allocation policies for message passing parallel computers: an empirical comparison\u201d. In Job Scheduling Strategies for Parallel Processing, D. G. Feitelson and L. Rudolph (eds.), pp. 224\u2013243, Springer-Verlag, 1996. Lecture Notes in Computer Science Vol. 1162.","DOI":"10.1007\/BFb0022296"},{"key":"1_CR61","doi-asserted-by":"crossref","first-page":"253","DOI":"10.1016\/0166-5316(96)00025-9","volume":"27","author":"E. W. Parsons","year":"1996","unstructured":"E. W. Parsons and K. C. Sevcik, \u201cBenefits of speedup knowledge in memory-constrained multiprocessor scheduling\u201d. Performance Evaluation 27&28, pp. 253\u2013272, Oct 1996.","journal-title":"Performance Evaluation"},{"key":"1_CR62","doi-asserted-by":"crossref","unstructured":"E. W. Parsons and K. C. Sevcik, \u201cCoordinated allocation of memory and processors in multiprocessors\u201d. In SIGMETRICS Conf. Measurement & Modeling of Comput. Syst., pp. 57\u201367, May 1996.","DOI":"10.1145\/233008.233023"},{"key":"1_CR63","doi-asserted-by":"crossref","unstructured":"E. W. Parsons and K. C. Sevcik, \u201cImplementing multiprocessor scheduling disciplines\u201d. In Job Scheduling Strategies for Parallel Processing, D. G. Feitelson and L. Rudolph (eds.), Springer Verlag, 1997. Lecture Notes in Computer Science (this volume).","DOI":"10.1007\/3-540-63574-2_21"},{"key":"1_CR64","doi-asserted-by":"crossref","unstructured":"E. W. Parsons and K. C. Sevcik, \u201cMultiprocessor scheduling for high-variability service time distributions\u201d. In Job Scheduling Strategies for Parallel Processing, D. G. Feitelson and L. Rudolph (eds.), pp. 127\u2013145, Springer-Verlag, 1995. Lecture Notes in Computer Science Vol. 949.","DOI":"10.1007\/3-540-60153-8_26"},{"key":"1_CR65","doi-asserted-by":"crossref","unstructured":"V. G. J. Peris, M. S. Squillante, and V. K. Naik, \u201cAnalysis of the impact of memory in distributed parallel processing systems\u201d. In SIGMETRICS Conf. Measurement & Modeling of Comput. Syst., pp. 5\u201318, May 1994.","DOI":"10.1145\/183018.183021"},{"key":"1_CR66","doi-asserted-by":"crossref","unstructured":"J. Pruyne and M. Livny, \u201cManaging checkpoints for parallel programs\u201d. In Job Scheduling Strategies for Parallel Processing, D. G. Feitelson and L. Rudolph (eds.), pp. 140\u2013154, Springer-Verlag, 1996. Lecture Notes in Computer Science Vol. 1162.","DOI":"10.1007\/BFb0022292"},{"key":"1_CR67","doi-asserted-by":"crossref","unstructured":"J. Pruyne and M. Livny, \u201cParallel processing on dynamic resources with CARMI\u201d. In Job Scheduling Strategies for Parallel Processing, D. G. Feitelson and L. Rudolph (eds.), pp. 259\u2013278, Springer-Verlag, 1995. Lecture Notes in Computer Science Vol. 949.","DOI":"10.1007\/3-540-60153-8_33"},{"issue":"2-3","key":"1_CR68","doi-asserted-by":"publisher","first-page":"141","DOI":"10.1016\/0166-5316(94)90037-X","volume":"19","author":"E. Rosti","year":"1994","unstructured":"E. Rosti, E. Smirni, L. W. Dowdy, G. Serazzi, and B. M. Carlson, \u201cRobust partitioning schemes of multiprocessor systems\u201d. Performance Evaluation 19(2-3), pp. 141\u2013165, Mar 1994.","journal-title":"Performance Evaluation"},{"key":"1_CR69","doi-asserted-by":"crossref","unstructured":"E. Rosti, E. Smirni, G. Serazzi, and L. W. Dowdy, \u201cAnalysis of non-work-conserving processor partitioning policies\u201d. In Job Scheduling Strategies for Parallel Processing, D. G. Feitelson and L. Rudolph (eds.), pp. 165\u2013181, Springer-Verlag, 1995. Lecture Notes in Computer Science Vol. 949.","DOI":"10.1007\/3-540-60153-8_28"},{"issue":"1","key":"1_CR70","doi-asserted-by":"publisher","first-page":"116","DOI":"10.1145\/321921.321934","volume":"23","author":"S. K. Sahni","year":"1976","unstructured":"S. K. Sahni, \u201cAlgorithms for scheduling independent tasks\u201d. J. ACM 23(1), pp. 116\u2013127, Jan 1976.","journal-title":"J. ACM"},{"key":"1_CR71","doi-asserted-by":"crossref","unstructured":"U. Schwiegelshohn, \u201cPreemptive weighted completion time scheduling of parallel jobs\u201d. In 4th European Symp. Algorithms, pp. 39\u201351, Springer-Verlag, Sep 1996. Lecture Notes in Computer Science Vol. 1136.","DOI":"10.1007\/3-540-61680-2_45"},{"key":"1_CR72","unstructured":"U. Schwiegeishohn, W. Ludwig, J. L. Wolf, J. J. Turek, and P. Yu, \u201cSmart SMART bounds for weighted response time scheduling\u201d. SIAM J. Comput. To appear."},{"key":"1_CR73","doi-asserted-by":"crossref","unstructured":"S. K. Setia, \u201cThe interaction between memory allocation and adaptive partitioning in message-passing multicomputers\u201d. In Job Scheduling Strategies for Parallel Processing, D. G. Feitelson and L. Rudolph (eds.), pp. 146\u2013165, Springer-Verlag, 1995. Lecture Notes in Computer Science Vol. 949.","DOI":"10.1007\/3-540-60153-8_27"},{"issue":"4","key":"1_CR74","doi-asserted-by":"crossref","first-page":"401","DOI":"10.1109\/71.273047","volume":"5","author":"S. K. Setia","year":"1994","unstructured":"S. K. Setia, M. S. Squillante, and S. K. Tripathi, \u201cAnalysis of processor allocation in multiprogrammed, distributed-memory parallel processing systems\u201d. IEEE Trans. Parallel & Distributed Syst. 5(4), pp. 401\u2013420, Apr 1994.","journal-title":"IEEE Trans. Parallel & Distributed Syst."},{"key":"1_CR75","doi-asserted-by":"crossref","unstructured":"S. K. Setia, M. S. Squillante, and S. K. Tripathi, \u201cProcessor scheduling on multiprogrammed, distributed memory parallel computers\u201d. In SIGMETRICS Conf. Measurement & Modeling of Comput. Syst., pp. 158\u2013170, May 1993.","DOI":"10.1145\/166962.167002"},{"issue":"2-3","key":"1_CR76","doi-asserted-by":"publisher","first-page":"107","DOI":"10.1016\/0166-5316(94)90036-1","volume":"19","author":"K. C. Sevcik","year":"1994","unstructured":"K. C. Sevcik, \u201cApplication scheduling and processor allocation in multiprogrammed parallel processing systems\u201d. Performance Evaluation 19(2-3), pp. 107\u2013140, Mar 1994.","journal-title":"Performance Evaluation"},{"key":"1_CR77","doi-asserted-by":"crossref","unstructured":"K. C. Sevcik, \u201cCharacterization of parallelism in applications and their use in scheduling\u201d. In SIGMETRICS Conf. Measurement & Modeling of Comput. Syst., pp. 171\u2013180, May 1989.","DOI":"10.1145\/75372.75391"},{"issue":"6","key":"1_CR78","doi-asserted-by":"publisher","first-page":"1313","DOI":"10.1137\/S0097539793248317","volume":"24","author":"D. Shmoys","year":"1995","unstructured":"D. Shmoys, J. Wein, and D. Williamson, \u201cScheduling parallel machines on-line\u201d. SIAM J. Comput. 24(6), pp. 1313\u20131331, Dec 1995.","journal-title":"SIAM J. Comput."},{"key":"1_CR79","doi-asserted-by":"crossref","unstructured":"J. Skovira, W. Chan, H. Zhou, and D. Lifka, \u201cThe EASY \u2014 Load-Leveler API project\u201d. In Job Scheduling Strategies for Parallel Processing, D. G. Feitelson and L. Rudolph (eds.), pp. 41\u201347, Springer-Verlag, 1996. Lecture Notes in Computer Science Vol. 1162.","DOI":"10.1007\/BFb0022286"},{"issue":"2","key":"1_CR80","doi-asserted-by":"publisher","first-page":"202","DOI":"10.1145\/2786.2793","volume":"28","author":"D. D. Sleator","year":"1985","unstructured":"D. D. Sleator and R. E. Tarjan, \u201cAmortized efficiency of list update and paging rules\u201d. Comm. ACM 28(2), pp. 202\u2013208, Feb 1985.","journal-title":"Comm. ACM"},{"key":"1_CR81","first-page":"203","volume":"III","author":"E. Smirni","year":"1995","unstructured":"E. Smirni, E. Rosti, G. Serazzi, L. W. Dowdy, and K. C. Sevcik, \u201cPerformance gains from leaving idle processors in multiprocessor systems\u201d. In Intl. Conf. Parallel Processing, vol. III, pp. 203\u2013210, Aug 1995.","journal-title":"Intl. Conf. Parallel Processing"},{"key":"1_CR82","doi-asserted-by":"crossref","first-page":"59","DOI":"10.1002\/nav.3800030106","volume":"3","author":"W. Smith","year":"1956","unstructured":"W. Smith, \u201cVarious optimizers for single-stage production\u201d. Naval Research Logistics Quarterly 3, pp. 59\u201366, 1956.","journal-title":"Naval Research Logistics Quarterly"},{"key":"1_CR83","doi-asserted-by":"crossref","unstructured":"P. G. Sobalvarro and W. E. Weihl, \u201cDemand-based coscheduling of parallel jobs on multiprogrammed multiprocessors\u201d. In Job Scheduling Strategies for Parallel Processing, D. G. Feitelson and L. Rudolph (eds.), pp. 106\u2013126, Springer-Verlag, 1995. Lecture Notes in Computer Science Vol. 949.","DOI":"10.1007\/3-540-60153-8_25"},{"key":"1_CR84","doi-asserted-by":"crossref","unstructured":"M. S. Squillante, \u201cOn the benefits and limitations of dynamic partitioning in parallel computer systems\u201d. In Job Scheduling Strategies for Parallel Processing, D. G. Feitelson and L. Rudolph (eds.), pp. 219\u2013238, Springer-Verlag, 1995. Lecture Notes in Computer Science Vol. 949.","DOI":"10.1007\/3-540-60153-8_31"},{"key":"1_CR85","doi-asserted-by":"crossref","first-page":"273","DOI":"10.1016\/0166-5316(96)00042-9","volume":"27","author":"M. S. Squillante","year":"1996","unstructured":"M. S. Squillante, F. Wang, and M. Papaefthymiou, \u201cStochastic analysis of gang scheduling in parallel and distributed systems\u201d. Performance Evaluation 27&28, pp. 273\u2013296, Oct 1996.","journal-title":"Performance Evaluation"},{"key":"1_CR86","doi-asserted-by":"crossref","unstructured":"A. Tucker and A. Gupta, \u201cProcess control and scheduling issues for multiprogrammed shared-memory multiprocessors\u201d. In 12th Symp. Operating Systems Principles, pp. 159\u2013166, Dec 1989.","DOI":"10.1145\/74851.74866"},{"key":"1_CR87","doi-asserted-by":"crossref","unstructured":"J. Turek, W. Ludwig, J. L. Wolf, L. Fleischer, P. Tiwari, J. Glasgow, U. Schwiegelshohn, and P. S. Yu, \u201cScheduling parallelizable tasks to minimize average response time\u201d. In 6th Symp. Parallel Algorithms & Architectures, pp. 200\u2013209, Jun 1994.","DOI":"10.1145\/181014.181331"},{"key":"1_CR88","doi-asserted-by":"crossref","unstructured":"J. Turek, J. L. Wolf, and P. S. Yu, \u201cApproximate algorithms for scheduling parallelizable tasks\u201d. In 4th Symp. Parallel Algorithms & Architectures, pp. 323\u2013332, Jun 1992.","DOI":"10.1145\/140901.141909"},{"key":"1_CR89","doi-asserted-by":"crossref","unstructured":"J. J. Turek, U. Schwiegelshohn, J. L. Wolf, and P. Yu, \u201cScheduling parallel tasks to minimize average response time\u201d. In 5th ACM-SIAM Symp. Discrete Algorithms, pp. 112\u2013121, Jan 1994.","DOI":"10.1145\/181014.181331"},{"key":"1_CR90","unstructured":"C. A. Waldspurger and W. E. Weihl, \u201cLottery scheduling: flexible proportional-share resource management\u201d. In 1st Symp. Operating Systems Design & Implementation, pp. 1\u201311, USENIX, Nov 1994."},{"key":"1_CR91","unstructured":"C. A. Waldspurger, Lottery and Stride Scheduling: Flexible Proportional-Share Resource Management. Ph.D. dissertation, Massachusetts Institute of Technology, Technical Report MIT\/LCS\/TR-667, Sep 1995."},{"key":"1_CR92","doi-asserted-by":"crossref","unstructured":"M. Wan, R. Moore, G. Kremenek, and K. Steube, \u201cA batch scheduler for the Intel Paragon with a non-contiguous node allocation algorithm\u201d. In Job Scheduling Strategies for Parallel Processing, D. G. Feitelson and L. Rudolph (eds.), pp. 48\u201364, Springer-Verlag, 1996. Lecture Notes in Computer Science Vol. 1162.","DOI":"10.1007\/BFb0022287"},{"key":"1_CR93","doi-asserted-by":"crossref","unstructured":"F. Wang, H. Franke, M. Papaefthymiou, P. Pattnaik, L. Rudolph, and M. S. Squillante, \u201cA gang scheduling design for multiprogrammed parallel computing environments\u201d. In Job Scheduling Strategies for Parallel Processing, D. G. Feitelson and L. Rudolph (eds.), pp. 111\u2013125, Springer-Verlag, 1996. Lecture Notes in Computer Science Vol. 1162.","DOI":"10.1007\/BFb0022290"},{"key":"1_CR94","doi-asserted-by":"crossref","unstructured":"F. Wang, M. Papaefthymiou, and M. Squillante, \u201cPerformance evaluation of gang scheduling for parallel and distributed multiprogramming\u201d. In Job Scheduling Strategies for Parallel Processing, D. G. Feitelson and L. Rudolph (eds.), Springer Verlag, 1997. Lecture Notes in Computer Science (this volume).","DOI":"10.1007\/3-540-63574-2_26"},{"issue":"2","key":"1_CR95","doi-asserted-by":"publisher","first-page":"281","DOI":"10.1137\/0221021","volume":"21","author":"Q. Wang","year":"1992","unstructured":"Q. Wang and K. H. Cheng, \u201cA heuristic of scheduling parallel tasks and its analysis\u201d. SIAM J. Comput. 21(2), pp. 281\u2013294, Apr 1992.","journal-title":"SIAM J. Comput."},{"key":"1_CR96","doi-asserted-by":"crossref","unstructured":"K. K. Yue and D. J. Lilja, \u201cLoop-level process control: an effective processor allocation policy for multiprogrammed shared-memory multiprocessors\u201d. In Job Scheduling Strategies for Parallel Processing, D. G. Feitelson and L. Rudolph (eds.), pp. 182\u2013199, Springer-Verlag, 1995. Lecture Notes in Computer Science Vol. 949.","DOI":"10.1007\/3-540-60153-8_29"},{"key":"1_CR97","doi-asserted-by":"crossref","unstructured":"J. Zahorjan and C. McCann, \u201cProcessor scheduling in shared memory multiprocessors\u201d. In SIGMETRICS Conf. Measurement & Modeling of Comput. Syst., pp. 214\u2013225, May 1990.","DOI":"10.1145\/98460.98760"}],"container-title":["Lecture Notes in Computer Science","Job Scheduling Strategies for Parallel Processing"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-63574-2_14","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,12,31]],"date-time":"2021-12-31T11:52:15Z","timestamp":1640951535000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-63574-2_14"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1997]]},"ISBN":["9783540635741","9783540695998"],"references-count":97,"URL":"https:\/\/doi.org\/10.1007\/3-540-63574-2_14","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[1997]]},"assertion":[{"value":"12 July 2005","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}