{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,30]],"date-time":"2026-04-30T04:21:14Z","timestamp":1777522874295,"version":"3.51.4"},"reference-count":39,"publisher":"Springer Science and Business Media LLC","issue":"5","license":[{"start":{"date-parts":[[2006,10,1]],"date-time":"2006-10-01T00:00:00Z","timestamp":1159660800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J Sched"],"published-print":{"date-parts":[[2006,10]]},"DOI":"10.1007\/s10951-006-8497-6","type":"journal-article","created":{"date-parts":[[2006,6,16]],"date-time":"2006-06-16T07:47:07Z","timestamp":1150444027000},"page":"433-452","source":"Crossref","is-referenced-by-count":63,"title":["Scheduling parallel jobs to minimize the makespan"],"prefix":"10.1007","volume":"9","author":[{"given":"Berit","family":"Johannes","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"8497_CR1","doi-asserted-by":"crossref","first-page":"459","DOI":"10.1137\/S0097539797324874","volume":"29","author":"S. Albers","year":"1999","unstructured":"Albers, S. \u201cBetter bounds for online scheduling,\u201d SIAM Journal on Computing, 29, 459\u2013473 (1999).","journal-title":"SIAM Journal on Computing"},{"key":"8497_CR2","doi-asserted-by":"crossref","unstructured":"Amoura, A. K., E. Bampis, C. Kenyon, and Y. Manoussakis, \u201cScheduling independent multiprocessor tasks,\u201d in R. Burkard and G. Woeginger (eds.), Algorithms\u2013ESA\u201997, Lecture Notes in Computer Science 1284, Springer, Berlin, 1997, pp. 1\u201312 .","DOI":"10.1007\/3-540-63397-9_1"},{"key":"8497_CR3","doi-asserted-by":"crossref","first-page":"846","DOI":"10.1137\/0209064","volume":"9","author":"B. S. Baker","year":"1980","unstructured":"Baker, B. S., E. G. Coffman, Jr., and R. L. Rivest, \u201c Orthogonal packings in two dimensions,\u201d SIAM Journal on Computing, 9, 846\u2013855 (1980).","journal-title":"SIAM Journal on Computing"},{"key":"8497_CR4","doi-asserted-by":"crossref","first-page":"389","DOI":"10.1109\/TC.1986.1676781","volume":"35","author":"J. Ba\u017cewicz","year":"1986","unstructured":"Ba\u017cewicz, J., M. Drabowski, and J. Weglarz, \u201cScheduling multiprocessor tasks to minimize schedule length,\u201d IEEE Transactions on Computers, 35, 389\u2013393 (1986).","journal-title":"IEEE Transactions on Computers"},{"key":"8497_CR5","doi-asserted-by":"crossref","first-page":"165","DOI":"10.1016\/S0167-6377(97)00040-0","volume":"21","author":"B. Chen","year":"1997","unstructured":"Chen, B. and A. P. A. Vestjens, \u201cScheduling on identical machines: How good is LPT in an on-line setting?,\u201dOperations Research Letters, 21, 165\u2013169 (1997).","journal-title":"Operations Research Letters"},{"key":"8497_CR6","doi-asserted-by":"crossref","unstructured":"Chen, J. and A. Miranda, \u201cA polynomial time approximation scheme for general multiprocessor job scheduling,\u201d in Proceedings of the 31st Annual ACM Symposium on Theory of Computing, 1999, pp. 418\u2013427 .","DOI":"10.1145\/301250.301363"},{"key":"8497_CR7","doi-asserted-by":"crossref","first-page":"808","DOI":"10.1137\/0209062","volume":"9","author":"E. G. Coffman Jr.","year":"1980","unstructured":"Coffman, E. G., Jr. M. R. Garey., D. S. Johnson, and R. E. Tarjan, \u201cPerformance bounds for level-oriented two-dimensional packing algorithms,\u201d SIAM Journal on Computing, 9, 808\u2013826 (1980).","journal-title":"SIAM Journal on Computing"},{"key":"8497_CR8","unstructured":"Drozdowski, M., \u201cOn complexity of multiprocessor task scheduling,\u201d Bulletin of the Polish Academy of Sciences, Technical Sciences, 43, 437\u2013445 (1994)."},{"key":"8497_CR9","doi-asserted-by":"crossref","first-page":"215","DOI":"10.1016\/0377-2217(96)00123-3","volume":"64","author":"M. Drozdowski","year":"1996","unstructured":"Drozdowski, M., \u201cScheduling multiprocessor tasks\u2013an overview,\u201d European Journal of Operational Research, 64, 215\u2013230 (1996).","journal-title":"European Journal of Operational Research"},{"key":"8497_CR10","doi-asserted-by":"crossref","first-page":"473","DOI":"10.1137\/0402042","volume":"2","author":"J. Du","year":"1989","unstructured":"Du, J. and J. Y.-T. Leung, \u201cComplexity of scheduling parallel task systems,\u201d SIAM Journal of Discrete Mathematics, 2, 473\u2013487 (1989).","journal-title":"SIAM Journal of Discrete Mathematics"},{"key":"8497_CR11","unstructured":"Feitelson, D. G., \u201cA survey of scheduling in multiprogrammed parallel systems,\u201d Research Report RC 19790 (87657), IBM T. J. Watson Research Center, Oct. 1994, revised Aug. 1997."},{"key":"8497_CR12","doi-asserted-by":"crossref","unstructured":"Feitelson, D. G., L. Rudolph, U. Schwiegelshohn, K. C. Sevcik, and P. Wong, \u201cTheory and practice in parallel job scheduling,\u201d in D. G. Feitelson and L. Rudolph (eds.), Job Scheduling Strategies for Parallel Processing, Lecture Notes in Computer Science 1291, Springer, Berlin, 1997, pp. 1\u201334,.","DOI":"10.1007\/3-540-63574-2_14"},{"key":"8497_CR13","doi-asserted-by":"crossref","first-page":"49","DOI":"10.1016\/0304-3975(94)90152-X","volume":"130","author":"A. Feldmann","year":"1994","unstructured":"Feldmann, A., J. Sgall, and S.-H. Teng,\u201c Dynamic scheduling on parallel machines,\u201d Theoretical Computer Science, 130, 49\u201372 (1994).","journal-title":"Theoretical Computer Science"},{"key":"8497_CR14","doi-asserted-by":"crossref","first-page":"343","DOI":"10.1002\/1099-1425(200011\/12)3:6<343::AID-JOS54>3.0.CO;2-2","volume":"3","author":"R. Fleischer","year":"2000","unstructured":"Fleischer, R. and M. Wahl, \u201cOn-line scheduling revisited,\u201d Journal of Scheduling, 3, 343\u2013353 (2000).","journal-title":"Journal of Scheduling"},{"key":"8497_CR15","doi-asserted-by":"crossref","first-page":"187","DOI":"10.1137\/0204015","volume":"4","author":"M. R. Garey","year":"1975","unstructured":"Garey, M. R. and R. L. Graham, \u201cBounds for multiprocessor scheduling with resource constraints,\u201d SIAM Journal on Computing, 4, 187\u2013200 (1975).","journal-title":"SIAM Journal on Computing"},{"key":"8497_CR16","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"M. R. Garey","year":"1979","unstructured":"Garey, M. R. and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, Freeman, San Francisco, CA. 1979."},{"key":"8497_CR17","doi-asserted-by":"crossref","first-page":"571","DOI":"10.1137\/0210042","volume":"10","author":"I. Golan","year":"1981","unstructured":"Golan, I., \u201cPerformance bounds for orthogonal oriented two-dimensional packing algorithms,\u201d SIAM Journal on Computing, 10, 571\u2013582 (1981).","journal-title":"SIAM Journal on Computing"},{"key":"8497_CR18","doi-asserted-by":"crossref","first-page":"287","DOI":"10.1145\/322186.322194","volume":"27","author":"T. F. Gonzalez","year":"1980","unstructured":"Gonzalez, T. F. and D. B. Johnson, \u201cA new algorithm for preemptive scheduling of trees,\u201d Journal of the Association for Computing Machinery, 27, 287\u2013312 (1980).","journal-title":"Journal of the Association for Computing Machinery"},{"key":"8497_CR19","doi-asserted-by":"crossref","first-page":"1563","DOI":"10.1002\/j.1538-7305.1966.tb01709.x","volume":"45","author":"R. L. Graham","year":"1966","unstructured":"Graham, R. L., \u201cBounds for certain multiprocessing anomalies,\u201d Bell System Technical Journal, 45, 1563\u20131581 (1966).","journal-title":"Bell System Technical Journal"},{"key":"8497_CR20","doi-asserted-by":"crossref","first-page":"416","DOI":"10.1137\/0117039","volume":"17","author":"R. L. Graham","year":"1969","unstructured":"Graham, R. L., \u201cBounds on multiprocessing timing anomalies,\u201d SIAM Journal of Applied Mathematics, 17, 416\u2013426 (1969).","journal-title":"SIAM Journal of Applied Mathematics"},{"key":"8497_CR21","doi-asserted-by":"crossref","first-page":"287","DOI":"10.1016\/S0167-5060(08)70356-X","volume":"5","author":"R. L. Graham","year":"1979","unstructured":"Graham, R. L., E. L. Lawler, J. K. Lenstra, and A. H. G. Rinnooy Kan, \u201cOptimization and approximation in deterministic sequencing and scheduling: A survey,\u201d Annals of Discrete Mathematics, 5, 287\u2013326 (1979).","journal-title":"Annals of Discrete Mathematics"},{"key":"8497_CR22","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0196-6774(84)90035-X","volume":"5","author":"D. Gusfield","year":"1984","unstructured":"Gusfield, D., \u201cBounds for naive multiple machine scheduling with release times and deadlines,\u201d Journal of Algorithms, 5, 1\u20136 (1984).","journal-title":"Journal of Algorithms"},{"key":"8497_CR23","doi-asserted-by":"crossref","unstructured":"Hall, L. A. and D. B. Shmoys, \u201cApproximation schemes for constrained scheduling problems,\u201d in Proceedings of the 30th Annual IEEE Symposium on Foundations of Computer Science, 1989 pp. 134\u2013139.","DOI":"10.1109\/SFCS.1989.63468"},{"key":"8497_CR24","doi-asserted-by":"crossref","first-page":"144","DOI":"10.1145\/7531.7535","volume":"34","author":"D. S. Hochbaum","year":"1987","unstructured":"Hochbaum, D. S., and Shmoys, D. B., \u201cUsing dual approximation algorithms for scheduling problems: Theoretical and practical results,\u201d Journal of the Association for Computing Machinery, 34, 144\u2013162 (1987).","journal-title":"Journal of the Association for Computing Machinery"},{"key":"8497_CR25","doi-asserted-by":"crossref","first-page":"177","DOI":"10.1002\/nav.3800210113","volume":"21","author":"W. A. Horn","year":"1974","unstructured":"Horn, W. A., \u201cSome simple machine scheduling algorithms,\u201d Naval Research Logistics Quarterly, 21, 177\u2013185 (1974).","journal-title":"Naval Research Logistics Quarterly"},{"key":"8497_CR26","unstructured":"Jansen, K. and L. Porkolab, \u201cLinear-time approximation schemes for scheduling malleable parallel tasks,\u201d in Proceedings of the 10th Annual ACM-SIAM Symposium on Discrete Algorithms, 1999, pp. 490\u2013498."},{"key":"8497_CR27","doi-asserted-by":"crossref","unstructured":"Jansen, K. and L. Porkolab, \u201cPreemptive parallel task scheduling in O(n) + poly(m) time,\u201d in D. T. Lee and S.-H. Teng (eds.), Algorithms and Computation, Lecture Notes in Computer Science 1969, Springer, Berlin, 2000, pp. 398\u2013409.","DOI":"10.1007\/3-540-40996-3_34"},{"key":"8497_CR28","unstructured":"Johannes, B., Obere und untere Schranken f\u00fcr die G\u00fcte von Heuristiken und Relaxierungen im Maschinen Scheduling, Diplomarbeit, Institut f\u00fcr Mathematik, Technische Universit\u00e4t Berlin, Germany, June 2001; partly published in B. Johannes, Scheduling parallel jobs to minimize makespan, Technical Report 723\/2001, Institut f\u00fcr Mathematik, Technische Universit\u00e4t Berlin, Germany."},{"key":"8497_CR29","doi-asserted-by":"crossref","unstructured":"Kenyon, C. and E. Remila, \u201cApproximative strip packing,\u201d in Proceedings of the 37th IEEE Symposium on Foundations of Computer Science, 1996, pp. 31\u201336.","DOI":"10.1109\/SFCS.1996.548461"},{"key":"8497_CR30","first-page":"155","volume":"3","author":"K. Li","year":"1999","unstructured":"Li, K., \u201cAnalysis of an approximation algorithm for scheduling independent parallel tasks,\u201d Discrete Mathematics and Theoretical Computer Science, 3, 1999, 155\u2013166.","journal-title":"Discrete Mathematics and Theoretical Computer Science"},{"key":"8497_CR31","unstructured":"Ludwig, W., and P. Tiwari, \u201cScheduling malleable and nonmalleable tasks,\u201d in Proceedings of the 5th ACM-SIAM Symposium on Discrete Algorithms, 1994, pp. 167\u2013176."},{"key":"8497_CR32","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1287\/mnsc.6.1.1","volume":"6","author":"R. McNaughton","year":"1959","unstructured":"McNaughton, R., \u201cScheduling with deadlines and loss functions,\u201d Management Science, 6, 1\u201312 (1959).","journal-title":"Management Science"},{"key":"8497_CR33","unstructured":"Mu\u2019alem, A. W. and D. G. Feitelson, \u201cPreemptive bicriteria scheduling for parallel jobs: Off-line and on-line algorithms. Technical Report 99-36,\u201d Leibniz Center for Research in Computer Science, Hebrew University, Jerusalem, Israel, Dec. 1999."},{"key":"8497_CR34","doi-asserted-by":"crossref","unstructured":"Naroska, E. and U. Schwiegelshohn, \u201cOn an online scheduling problem for parallel jobs,\u201d Information Processing Letters, 81, 297\u2013304 (2002).","DOI":"10.1016\/S0020-0190(01)00241-1"},{"key":"8497_CR35","doi-asserted-by":"crossref","unstructured":"Sgall, J., \u201cOn-line scheduling,\u201d in A. Fiat and G. J. Woeginger (eds.), Online Algorithms, Lecture Notes in Computer Science 1442, Springer, Berlin, 1998, pp. 197\u2013231.","DOI":"10.1007\/BFb0029570"},{"key":"8497_CR36","doi-asserted-by":"crossref","first-page":"1313","DOI":"10.1137\/S0097539793248317","volume":"24","author":"D. B. Shmoys","year":"1995","unstructured":"Shmoys, D. B., J. Wein, and D. P. Williamson, \u201cScheduling parallel machines on-line,\u201d SIAM Journal on Computing, 24, 1313\u20131331 (1995).","journal-title":"SIAM Journal on Computing"},{"key":"8497_CR37","doi-asserted-by":"crossref","first-page":"37","DOI":"10.1016\/0020-0190(80)90121-0","volume":"10","author":"D. Sleator","year":"1980","unstructured":"Sleator, D., \u201cA 2.5 times optimal algorithm for packing in two dimensions,\u201d Information Processing Letters, 10, 37\u201340 (1980).","journal-title":"Information Processing Letters"},{"key":"8497_CR38","doi-asserted-by":"crossref","first-page":"401","DOI":"10.1137\/S0097539793255801","volume":"26","author":"A. Steinberg","year":"1997","unstructured":"Steinberg, A., \u201cA strip-packing algorithm with absolute performance bound 2,\u201dSIAM Journal on Computing, 26, 401\u2013409 (1997).","journal-title":"SIAM Journal on Computing"},{"key":"8497_CR39","doi-asserted-by":"crossref","unstructured":"Turek, J., J. L. Wolf, and P. S. Yu, \u201cApproximate algorithms for scheduling parallelizable tasks,\u201d in Proceedings of the 4th ACM Symposium on Parallel Algorithms and Architectures, 1992, pp. 323\u2013332.","DOI":"10.1145\/140901.141909"}],"container-title":["Journal of Scheduling"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10951-006-8497-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10951-006-8497-6\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10951-006-8497-6","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,9]],"date-time":"2025-01-09T11:34:11Z","timestamp":1736422451000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10951-006-8497-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006,10]]},"references-count":39,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2006,10]]}},"alternative-id":["8497"],"URL":"https:\/\/doi.org\/10.1007\/s10951-006-8497-6","relation":{},"ISSN":["1094-6136","1099-1425"],"issn-type":[{"value":"1094-6136","type":"print"},{"value":"1099-1425","type":"electronic"}],"subject":[],"published":{"date-parts":[[2006,10]]}}}