{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,16]],"date-time":"2026-03-16T10:20:48Z","timestamp":1773656448402,"version":"3.50.1"},"reference-count":22,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[1995,12,1]],"date-time":"1995-12-01T00:00:00Z","timestamp":817776000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Ann Oper Res"],"published-print":{"date-parts":[[1995,12]]},"DOI":"10.1007\/bf02099688","type":"journal-article","created":{"date-parts":[[2005,9,12]],"date-time":"2005-09-12T20:03:31Z","timestamp":1126555411000},"page":"13-27","source":"Crossref","is-referenced-by-count":26,"title":["Shop scheduling problems with multiprocessor tasks on dedicated processors"],"prefix":"10.1007","volume":"57","author":[{"given":"Peter","family":"Brucker","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Andreas","family":"Kr\u00e4mer","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"BF02099688_CR1","doi-asserted-by":"crossref","first-page":"109","DOI":"10.1016\/0020-0190(93)90054-D","volume":"46","author":"L. Bianco","year":"1993","unstructured":"L. Bianco, J. Bla\u017cewicz, P. Dell'Olmo and M. Drozdowski, Preemptive scheduling of multiprocessor tasks on the dedicated processor system subject to minimal lateness, Inf. Proc. Lett. 46(1993)109\u2013113.","journal-title":"Inf. Proc. Lett."},{"key":"BF02099688_CR2","doi-asserted-by":"crossref","first-page":"959","DOI":"10.1002\/1520-6750(199412)41:7<959::AID-NAV3220410708>3.0.CO;2-K","volume":"41","author":"L. Bianco","year":"1994","unstructured":"L. Bianco, P. Dell'Olmo and M.G. Speranza, Nonpreemptive scheduling of independent tasks with prespecified processor allocation, Naval Res. Log. 41(1994)959\u2013971.","journal-title":"Naval Res. Log."},{"key":"BF02099688_CR3","doi-asserted-by":"crossref","first-page":"275","DOI":"10.1016\/0020-0190(92)90172-R","volume":"41","author":"J. Bla\u017cewicz","year":"1992","unstructured":"J. Bla\u017cewicz, P. Dell'Olmo, M. Drozdowski and M.G. Speranza, Scheduling multiprocessor tasks on three dedicated processors, Inf. Proc. Lett. 41(1992)275\u2013280.","journal-title":"Inf. Proc. Lett."},{"key":"BF02099688_CR4","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-662-00074-8","volume-title":"Scheduling in Computer and Manufacturing Systems","author":"J. Bla\u017cewicz","year":"1993","unstructured":"J. Bla\u017cewicz, K. Ecker, G. Schmidt and J. Weglarz,Scheduling in Computer and Manufacturing Systems (Springer, Berlin, 1993)."},{"key":"BF02099688_CR5","doi-asserted-by":"crossref","first-page":"353","DOI":"10.1007\/BF02276919","volume":"40","author":"P. Brucker","year":"1988","unstructured":"P. Brucker, An efficient algorithm for the job-shop problem with two jobs, Computing 40(1988)353\u2013359.","journal-title":"Computing"},{"key":"BF02099688_CR6","doi-asserted-by":"crossref","first-page":"5","DOI":"10.1007\/BF01719698","volume":"16","author":"P. Brucker","year":"1994","unstructured":"P. Brucker, A polynomial algorithm for the two machine job-shop scheduling problem with a fixed number of jobs, Operations Research Spektrum 16(1994)5\u20137.","journal-title":"Operations Research Spektrum"},{"key":"BF02099688_CR7","doi-asserted-by":"crossref","first-page":"59","DOI":"10.1007\/BF01415528","volume":"37","author":"P. Brucker","year":"1993","unstructured":"P. Brucker, B. Jurisch and M. Jurisch, Open shop problems with unit time operations, Zeits. Oper. Res. 37(1993)59\u201373.","journal-title":"Zeits. Oper. Res."},{"key":"BF02099688_CR8","doi-asserted-by":"crossref","first-page":"117","DOI":"10.1137\/0211009","volume":"11","author":"H.N. Gabow","year":"1982","unstructured":"H.N. Gabow and O. Kariv, Algorithms for edge colouring bipartite graphs and multigraphs, SIAM J. Comp. 11(1982)117\u2013129.","journal-title":"SIAM J. Comp."},{"key":"BF02099688_CR9","doi-asserted-by":"crossref","first-page":"499","DOI":"10.1145\/322077.322090","volume":"25","author":"M.R. Garey","year":"1978","unstructured":"M.R. Garey and D.S. Johnson, Strong NP-completeness results: motivation, examples and implications, J. ACM 25(1978)499\u2013508.","journal-title":"J. ACM"},{"key":"BF02099688_CR10","volume-title":"Computers and Intractability","author":"M.R. Garey","year":"1979","unstructured":"M.R. Garey and D.S. Johnson,Computers and Intractability (Freemann, San Francisco, 1979)."},{"key":"BF02099688_CR11","doi-asserted-by":"crossref","first-page":"665","DOI":"10.1145\/321978.321985","volume":"23","author":"T. Gonzales","year":"1976","unstructured":"T. Gonzales and S. Sahni, Open shop scheduling to minimize finish time, J. ACM 23(1976)665\u2013679.","journal-title":"J. ACM"},{"key":"BF02099688_CR12","doi-asserted-by":"crossref","first-page":"36","DOI":"10.1287\/opre.26.1.36","volume":"26","author":"T. Gonzales","year":"1978","unstructured":"T. Gonzales and S. Sahni, Flowshop and jobshop schedules: complexity and approximation, Oper. Res. 26(1978)36\u201352.","journal-title":"Oper. Res."},{"key":"BF02099688_CR13","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, Ann. Discr. Math. 5(1979)287\u2013326.","journal-title":"Ann. Discr. Math."},{"key":"BF02099688_CR14","unstructured":"J.A. Hoogeveen, S.L. van de Velde and B. Veltman, Complexity of scheduling multiprocessor tasks with prespecified processor allocation, Discr. Appl. Math. (1992), to appear."},{"key":"BF02099688_CR15","doi-asserted-by":"crossref","first-page":"201","DOI":"10.1002\/nav.3800030307","volume":"3","author":"J.R. Jackson","year":"1956","unstructured":"J.R. Jackson, An extension of Johnson's results on job lot scheduling, Naval Res. Log. Quart. 3(1956)201\u2013203.","journal-title":"Naval Res. Log. Quart."},{"key":"BF02099688_CR16","doi-asserted-by":"crossref","first-page":"61","DOI":"10.1002\/nav.3800010110","volume":"1","author":"S.M. Johnson","year":"1954","unstructured":"S.M. Johnson, Optimal two- and three stage production schedules with setup times included, Naval Res. Log. Quart. 1(1954)61\u201368.","journal-title":"Naval Res. Log. Quart."},{"key":"BF02099688_CR17","unstructured":"M. Kubale, Preemptive scheduling of two-processor tasks on dedicated processors, Zeszyty Naukowe Politechnik: Slaskiej, Seria: Automatyka Z. 100, No. 1082(1990)145\u2013153, in polish."},{"key":"BF02099688_CR18","doi-asserted-by":"crossref","unstructured":"W. Kubiak, S. Sehti and C. Sriskandarajah, An efficient algorithm for a job shop problem, Ann. Oper. Res. (1995), this volume.","DOI":"10.1007\/BF02099698"},{"key":"BF02099688_CR19","doi-asserted-by":"crossref","first-page":"538","DOI":"10.1287\/moor.8.4.538","volume":"8","author":"H.W. Lenstra Jr.","year":"1983","unstructured":"H.W. Lenstra, Jr., Integer programming with a fixed number of variables, Math. Oper. Res. 8(1983)538\u2013548.","journal-title":"Math. Oper. Res."},{"key":"BF02099688_CR20","unstructured":"Y.N. Sotskov and N.V. Shakhlevich, NP-hardness of shop-scheduling problems with three jobs, to appear in Discr. Appl. Math. (1993)."},{"key":"BF02099688_CR21","first-page":"109","volume":"2","author":"V.G. Timkowskiy","year":"1985","unstructured":"V.G. Timkowskiy, Polynomial-time algorithm for the Lenstra-Rinnooy Kan two-machine scheduling problem, Kibernetika 2(1985)109\u2013111, in Russian.","journal-title":"Kibernetika"},{"key":"BF02099688_CR22","doi-asserted-by":"crossref","first-page":"173","DOI":"10.1016\/0167-8191(90)90056-F","volume":"16","author":"B. Veltman","year":"1990","unstructured":"B. Veltman, B.J. Lageweg and J.K. Lenstra, Multiprocessor scheduling with communication delays, Parallel Comp. 16(1990)173\u2013182.","journal-title":"Parallel Comp."}],"container-title":["Annals of Operations Research"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF02099688.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF02099688\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF02099688","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,14]],"date-time":"2019-05-14T00:41:15Z","timestamp":1557794475000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF02099688"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1995,12]]},"references-count":22,"journal-issue":{"issue":"1","published-print":{"date-parts":[[1995,12]]}},"alternative-id":["BF02099688"],"URL":"https:\/\/doi.org\/10.1007\/bf02099688","relation":{},"ISSN":["0254-5330","1572-9338"],"issn-type":[{"value":"0254-5330","type":"print"},{"value":"1572-9338","type":"electronic"}],"subject":[],"published":{"date-parts":[[1995,12]]}}}