{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T22:50:19Z","timestamp":1725490219719},"publisher-location":"Berlin, Heidelberg","reference-count":19,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540412557"},{"type":"electronic","value":"9783540409960"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2000]]},"DOI":"10.1007\/3-540-40996-3_6","type":"book-chapter","created":{"date-parts":[[2007,8,29]],"date-time":"2007-08-29T01:17:32Z","timestamp":1188350252000},"page":"60-71","source":"Crossref","is-referenced-by-count":3,"title":["A Simple Linear-Time Approximation Algorithm for Multi-processor Job Scheduling on Four Processors"],"prefix":"10.1007","author":[{"given":"Jingui","family":"Huang","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jianer","family":"Chen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Songqiao","family":"Chen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2002,1,29]]},"reference":[{"key":"6_CR1","series-title":"Lect Notes Comput Sci","first-page":"1","volume-title":"Scheduling independent multiprocessor tasks","author":"A. K. Amoura","year":"1997","unstructured":"A. K. Amoura, E. Bampis, C. Kenyon, and Y. Manoussakis, Scheduling independent multiprocessor tasks, Proc. 5th Ann. European Symposium on Algorithms,Lecture Notes in Computer Science 1284, (1997), pp. 1\u201312."},{"key":"6_CR2","doi-asserted-by":"publisher","first-page":"493","DOI":"10.1007\/BF02057160","volume":"58","author":"L. Bianco","year":"1995","unstructured":"L. Bianco, J. Blazewicz, P. Dell\u2019Olmo, and M. Drozdowski, Schedulingmultiprocessor tasks on a dynamic configuration of dedicated processors, Annalsof Operations Research 58, (1995), pp. 493\u2013517.","journal-title":"Annalsof Operations Research"},{"key":"6_CR3","doi-asserted-by":"publisher","first-page":"275","DOI":"10.1016\/0020-0190(92)90172-R","volume":"41","author":"J. Blazewicz","year":"1992","unstructured":"J. Blazewicz, P. Dell\u2019Olmo, M. Drozdowski, and M. Speranza, Scheduling multiprocessor tasks on the three dedicated processors, Information Processing Letters 41, (1992), pp. 275\u2013280.","journal-title":"Information Processing Letters"},{"key":"6_CR4","doi-asserted-by":"publisher","first-page":"275","DOI":"10.1016\/0020-0190(92)90172-R","volume":"41","author":"J. Blazewicz","year":"1992","unstructured":"J. Blazewicz, P. Dell\u2019Olmo, M. Drozdowski, and M. Speranza, Corrigendum to \u201cScheduling multiprocessor tasks on the three dedicated processors,Information Processing Letters 41, (1992), pp. 275\u2013280.\u201d Information Processing Letters 49, (1994), pp. 269-270.","journal-title":"Information Processing Letters"},{"key":"6_CR5","doi-asserted-by":"publisher","first-page":"389","DOI":"10.1109\/TC.1986.1676781","volume":"35","author":"J. Blazewicz","year":"1986","unstructured":"J. Blazewicz, M. Drozdowski, and J. Weglarz, Scheduling multiprocessor tasks to minimize scheduling length, IEEE Transactions on Computers 35, (1986), pp. 389\u2013393.","journal-title":"IEEE Transactions on Computers"},{"key":"6_CR6","first-page":"89","volume":"13","author":"J. Blazewicz","year":"1994","unstructured":"J. Blazewicz, W. Drozdowski, and J. Weglarz, Scheduling multiprocessor tasks \u2014 a survey, International Journal of Microcomputer Applications 13, (1994), pp. 89\u201397.","journal-title":"International Journal of Microcomputer Applications"},{"key":"6_CR7","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1002\/(SICI)1520-6750(199902)46:1<57::AID-NAV4>3.0.CO;2-H","volume":"46","author":"J. Chen","year":"1999","unstructured":"J. Chen and C.-Y. Lee, General multiprocessor tasks scheduling, Naval Research Logistics 46, (1999), pp. 59\u201374.","journal-title":"Naval Research Logistics"},{"doi-asserted-by":"crossref","unstructured":"J. Chen and A. Miranda, A polynomial time approximation scheme for general multiprocessor job scheduling, Proc. 31st Annual ACM Symposium on Theory of Computing (STOC\u201999), (1999), pp. 418\u2013427. Final version to appear in SIAM J. Comput.","key":"6_CR8","DOI":"10.1145\/301250.301363"},{"key":"6_CR9","doi-asserted-by":"publisher","first-page":"67","DOI":"10.1016\/S0012-365X(97)84781-4","volume":"164","author":"P. Dell\u2019Olmo","year":"1997","unstructured":"P. Dell\u2019Olmo, M. G. Speranza, Zs. Tuza, Efficiency and effectiveness of normal schedules on three dedicated processors, Discrete Mathematics 164, (1997), pp. 67\u201379.","journal-title":"Discrete Mathematics"},{"key":"6_CR10","doi-asserted-by":"publisher","first-page":"592","DOI":"10.1287\/opre.37.4.592","volume":"37","author":"G. Dobson","year":"1989","unstructured":"G. Dobson and U. Karmarkar, Simultaneous resource scheduling to minimize weighted flow times, Operations Research 37, (1989), pp. 592\u2013600.","journal-title":"Operations Research"},{"key":"6_CR11","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"M. R. Garey","year":"1979","unstructured":"M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, Freeman, San Francisco, 1979."},{"key":"6_CR12","doi-asserted-by":"publisher","first-page":"49","DOI":"10.1016\/0166-218X(94)00160-F","volume":"61","author":"M. X. Goemans","year":"1995","unstructured":"M. X. Goemans, An approximation algorithm for scheduling on three dedicated machines, Discrete Applied Mathematics 61, (1995), pp. 49\u201359.","journal-title":"Discrete Applied Mathematics"},{"key":"6_CR13","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":"R. L. Graham, Bounds for certain multiprocessing anomalies, Bell System Technical Journal 45, (1966), pp. 1563\u20131581.","journal-title":"Bell System Technical Journal"},{"unstructured":"L. A. Hall, Approximation algorithms for scheduling, in D. S. Hochbaum, ed., Approximation algorithms for NP-hard problems, PWS Publishing Company, 1997, pp. 1\u201345.","key":"6_CR14"},{"key":"6_CR15","doi-asserted-by":"publisher","first-page":"259","DOI":"10.1016\/0166-218X(94)90012-4","volume":"55","author":"J. A. Hoogeveen","year":"1994","unstructured":"J. A. Hoogeveen, S. L. van de Velde, and B. Veltman, Complexity of scheduling multiprocessor tasks with prespecified processor allocations, Discrete Applied Mathematics 55, (1994), pp. 259\u2013272.","journal-title":"Discrete Applied Mathematics"},{"key":"6_CR16","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"110","DOI":"10.1007\/3-540-48447-7_13","volume-title":"General multiprocessor task scheduling: approximate solutions in linear time","author":"K. Jansen","year":"1999","unstructured":"K. Jansen and L. Porkolab, General multiprocessor task scheduling: approximate solutions in linear time, Lecture Notes in Computer Science 1663 (WADS\u201999), (1999), pp. 110\u2013121."},{"key":"6_CR17","doi-asserted-by":"publisher","first-page":"869","DOI":"10.1109\/TC.1985.1676647","volume":"34","author":"H. Krawczyk","year":"1985","unstructured":"H. Krawczyk and M. Kubale, An approximation algorithm for diagnostic test scheduling in multicomputer systems, IEEE Transactions on Computers 34, (1985), pp. 869\u2013872.","journal-title":"IEEE Transactions on Computers"},{"unstructured":"C.-Y. Lee and X. Cai, Scheduling multiprocessor tasks without prespecified processor allocations, IIE Transactions, to appear.","key":"6_CR18"},{"key":"6_CR19","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1023\/A:1018909801944","volume":"70","author":"C.-Y. Lee","year":"1997","unstructured":"C.-Y. Lee, L. Lei, and M. Pinedo, Current trends in deterministic scheduling, Annals of Operations Research 70, (1997), pp. 1\u201342.","journal-title":"Annals of Operations Research"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Computation"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-40996-3_6","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,2]],"date-time":"2019-05-02T17:26:07Z","timestamp":1556817967000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-40996-3_6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2000]]},"ISBN":["9783540412557","9783540409960"],"references-count":19,"URL":"https:\/\/doi.org\/10.1007\/3-540-40996-3_6","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2000]]}}}