{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,5]],"date-time":"2026-05-05T07:21:29Z","timestamp":1777965689618,"version":"3.51.4"},"reference-count":21,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[1999,7,1]],"date-time":"1999-07-01T00:00:00Z","timestamp":930787200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[1999,7,1]],"date-time":"1999-07-01T00:00:00Z","timestamp":930787200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Journal of Combinatorial Optimization"],"published-print":{"date-parts":[[1999,7]]},"DOI":"10.1023\/a:1009817206440","type":"journal-article","created":{"date-parts":[[2002,12,22]],"date-time":"2002-12-22T23:53:29Z","timestamp":1040601209000},"page":"73-88","source":"Crossref","is-referenced-by-count":13,"title":["Analysis of the List Scheduling Algorithm for Precedence Constrained Parallel Tasks"],"prefix":"10.1007","volume":"3","author":[{"given":"Keqin","family":"Li","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"211420_CR1","doi-asserted-by":"crossref","first-page":"207","DOI":"10.1007\/BF00264439","volume":"18","author":"D.J. Brown","year":"1982","unstructured":"D.J. Brown, B.S. Baker, and H.P. Katseff, \"Lower bounds for on-line two-dimensional packing algorithms,\" Acta Informatica, vol. 18, pp. 207-225, 1982.","journal-title":"Acta Informatica"},{"key":"211420_CR2","doi-asserted-by":"crossref","first-page":"215","DOI":"10.1016\/0377-2217(96)00123-3","volume":"94","author":"M. Drozdowski","year":"1996","unstructured":"M. Drozdowski, \"Scheduling multiprocessor tasks-An overview,\" European Journal of Operational Research, vol. 94, pp. 215-230, 1996.","journal-title":"European Journal of Operational Research"},{"key":"211420_CR3","unstructured":"M.R. Garey and D.S. Johnson, Computers and Intractability-A Guide to the Theory of NP-Completeness. W.H. Freeman, 1979."},{"key":"211420_CR4","doi-asserted-by":"crossref","first-page":"416","DOI":"10.1137\/0117039","volume":"2","author":"R.L. Graham","year":"1969","unstructured":"R.L. Graham, \"Bounds on multiprocessing timing anomalies,\" SIAM J. Appl. Math., vol. 2, pp. 416-429, 1969.","journal-title":"SIAM J. Appl. Math."},{"key":"211420_CR5","doi-asserted-by":"crossref","first-page":"287","DOI":"10.1016\/S0167-5060(08)70356-X","volume":"5","author":"R.L. Graham","year":"1979","unstructured":"R.L. Graham, E.L. Lawler, J.K. Lenstra, and A.H.G. Rinnooy Kan, \"Optimization and approximation in deterministic sequencing and scheduling: A survey,\" Annals of Discrete Mathematics, vol. 5, pp. 287-326, 1979.","journal-title":"Annals of Discrete Mathematics"},{"key":"211420_CR6","volume-title":"Approximation Algorithms for NP-Hard Problems","year":"1997","unstructured":"D.S. Hochbaum, Ed., Approximation Algorithms for NP-Hard Problems, PWS Publishing, Boston, MA, 1997."},{"key":"211420_CR7","doi-asserted-by":"crossref","first-page":"144","DOI":"10.1145\/7531.7535","volume":"34","author":"D.S. Hochbaum","year":"1987","unstructured":"D.S. Hochbaum and D.B. Shmoys, \"Using dual approximation algorithms for scheduling problems: Practical and theoretical results,\" Journal of the ACM, vol. 34, pp. 144-162, 1987.","journal-title":"Journal of the ACM"},{"key":"211420_CR8","doi-asserted-by":"crossref","first-page":"879","DOI":"10.1109\/71.298216","volume":"5","author":"K.K. Jain","year":"1994","unstructured":"K.K. Jain and V. Rajaraman, \"Lower and upper bounds on time for multiprocessor optimal schedules,\" IEEE Transactions on Parallel and Distributed Systems, vol. 5, pp. 879-886, 1994.","journal-title":"IEEE Transactions on Parallel and Distributed Systems"},{"key":"211420_CR9","doi-asserted-by":"crossref","first-page":"299","DOI":"10.1137\/0203025","volume":"3","author":"D.S. Johnson","year":"1974","unstructured":"D.S. Johnson et al., \"Worst-case performance bounds for simple one-dimensional packing algorithms,\" SIAM Journal on Computing, vol. 3, pp. 299-325, 1974.","journal-title":"SIAM Journal on Computing"},{"key":"211420_CR10","doi-asserted-by":"crossref","unstructured":"N. Karmarkar and R.M. Karp, \"An efficient approximation scheme for the one-dimensional bin packing problem,\" in Proceedings of the 23rd Annual Symposium on Foundations of Computer Science, 1982, pp. 312-320.","DOI":"10.1109\/SFCS.1982.61"},{"key":"211420_CR11","doi-asserted-by":"crossref","first-page":"22","DOI":"10.1287\/opre.26.1.22","volume":"26","author":"J.K. Lenstra","year":"1978","unstructured":"J.K. Lenstra and A.H.G. Rinnooy Kan, \"Complexity of scheduling under precedence constraints,\" Operations Research, vol. 26, pp. 22-25, 1978.","journal-title":"Operations Research"},{"key":"211420_CR12","unstructured":"K. Li, \"An approximation algorithm for scheduling independent parallel tasks and its analysis,\" in Proceedings of the 8th International Conference on Parallel and Distributed Computing Systems, 1995, pp. 634-639."},{"key":"211420_CR13","first-page":"630","volume":"465","author":"K. Li","year":"1997","unstructured":"K. Li, \"Stochastic bounds for parallel program execution times with processor constraints,\" IEEE Transactions on Computers, vol. 46, no. 5, pp. 630-636, 1997a.","journal-title":"IEEE Transactions on Computers"},{"key":"211420_CR14","unstructured":"K. Li, \"Worst-case performance analysis of the list scheduling algorithm for precedence constrained parallel tasks,\" in Proceedings of the 9th International Conference on Parallel and Distributed Computing and Systems, 1997b; pp. 249-252."},{"key":"211420_CR15","unstructured":"K. Li and Y. Pan, \"On scheduling precedence constrained parallel tasks on multiprocessors I: Limitations of list scheduling strategies,\" in Proceedings of International Conference on Modelling and Simulation, 1996a, pp. 63-66."},{"key":"211420_CR16","unstructured":"K. Li and Y. Pan, \"On scheduling precedence constrained parallel tasks on multiprocessors II: Performance analysis of a heuristic algorithm,\" in Proceedings of International Conference on Modelling and Simulation, 1996b, pp. 67-71."},{"key":"211420_CR17","unstructured":"K. Li and Y. Pan, \"On scheduling precedence constrained parallel tasks on multiprocessors III: An efficient heuristic for wide task graphs,\" in Proceedings of International Conference on Modelling and Simulation, 1996c, pp. 72-75."},{"key":"211420_CR18","doi-asserted-by":"crossref","first-page":"189","DOI":"10.1287\/opre.29.1.189","volume":"29","author":"E.L. Lloyd","year":"1981","unstructured":"E.L. Lloyd, \"Concurrent task systems,\" Operations Research, vol. 29, pp. 189-201, 1981.","journal-title":"Operations Research"},{"key":"211420_CR19","doi-asserted-by":"crossref","unstructured":"J. Turek et al., \"Scheduling parallelizable tasks to minimize average response time,\" in Proceedings of the 6th Annual ACM Symposium on Parallel Algorithms and Architectures, 1994, pp. 200-209.","DOI":"10.1145\/181014.181331"},{"key":"211420_CR20","doi-asserted-by":"crossref","first-page":"384","DOI":"10.1016\/S0022-0000(75)80008-0","volume":"10","author":"J.D. Ullman","year":"1975","unstructured":"J.D. Ullman, \"NP-complete scheduling problems,\" Journal of Computer and System Science, vol. 10, pp. 384-393, 1975.","journal-title":"Journal of Computer and System Science"},{"key":"211420_CR21","doi-asserted-by":"crossref","first-page":"281","DOI":"10.1137\/0221021","volume":"21","author":"Q. Wang","year":"1992","unstructured":"Q. Wang and K.H. Cheng, \"A heuristic of scheduling parallel tasks and its analysis,\" SIAM Journal on Computing, vol. 21, pp. 281-294, 1992.","journal-title":"SIAM Journal on Computing"}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1023\/A:1009817206440.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1023\/A:1009817206440\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1023\/A:1009817206440.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,30]],"date-time":"2025-06-30T11:10:08Z","timestamp":1751281808000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1023\/A:1009817206440"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1999,7]]},"references-count":21,"journal-issue":{"issue":"1","published-print":{"date-parts":[[1999,7]]}},"alternative-id":["211420"],"URL":"https:\/\/doi.org\/10.1023\/a:1009817206440","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"value":"1382-6905","type":"print"},{"value":"1573-2886","type":"electronic"}],"subject":[],"published":{"date-parts":[[1999,7]]}}}