{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T22:50:16Z","timestamp":1725490216330},"publisher-location":"Berlin, Heidelberg","reference-count":23,"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_34","type":"book-chapter","created":{"date-parts":[[2007,8,29]],"date-time":"2007-08-29T01:17:32Z","timestamp":1188350252000},"page":"398-409","source":"Crossref","is-referenced-by-count":11,"title":["Preemptive Parallel Task Scheduling in O(n) + Poly(m) Time"],"prefix":"10.1007","author":[{"given":"Klaus","family":"Jansen","sequence":"first","affiliation":[]},{"given":"Lorant","family":"Porkolab","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2002,1,29]]},"reference":[{"key":"34_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, Proceedings of the 5th European Symposium on Algorithms (1997), LNCS 1284, 1\u201312."},{"key":"34_CR2","doi-asserted-by":"crossref","unstructured":"A.K. Amoura, E. Bampis, C. Kenyon and Y. Manoussakis, Scheduling independent multiprocessor tasks, manuscript of an extended version of [1], submitted to Algorithmica, 1998.","DOI":"10.1007\/3-540-63397-9_1"},{"key":"34_CR3","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 Olmo and M. Drozdowski, Scheduling multiprocessor tasks on a dynamic configuration of dedicated processors, Annals of Operations Research 58 (1995), 493\u2013517.","journal-title":"Annals of Operations Research"},{"key":"34_CR4","doi-asserted-by":"publisher","first-page":"389","DOI":"10.1109\/TC.1986.1676781","volume":"C-35-5","author":"J. Blazewicz","year":"1986","unstructured":"J. Blazewicz, M. Drabowski and J. Weglarz, Scheduling multiprocessor tasks to minimize schedule length, IEEE Transactions on Computers, C-35-5; (1986), 389\u2013393.","journal-title":"IEEE Transactions on Computers"},{"key":"34_CR5","doi-asserted-by":"publisher","first-page":"81","DOI":"10.1016\/0166-218X(95)00020-R","volume":"65","author":"J. Blazewicz","year":"1996","unstructured":"J. Blazewicz, M. Drozdowski, D. de Werra and J. Weglarz, Deadline scheduling of multiprocessor tasks, Discrete Applied Mathematics 65 (1996), 81\u201396.","journal-title":"Discrete Applied Mathematics"},{"key":"34_CR6","doi-asserted-by":"crossref","unstructured":"J. Chen and A. Miranda, A polynomial time approximation scheme for general multiprocessor job scheduling, Proceedings of the 31st ACM Symposium on the Theory of Computing (1999), 418\u2013427.","DOI":"10.1145\/301250.301363"},{"key":"34_CR7","first-page":"381","volume":"43","author":"M. Drozdowski","year":"1995","unstructured":"M. Drozdowski, On the complexity of multiprocessor task scheduling, Bulletin of the Polish Academy of Sciences, 43 (1995), 381\u2013392.","journal-title":"Bulletin of the Polish Academy of Sciences"},{"key":"34_CR8","doi-asserted-by":"publisher","first-page":"215","DOI":"10.1016\/0377-2217(96)00123-3","volume":"94","author":"M. Drozdowski","year":"1996","unstructured":"M. Drozdowski, Scheduling multiprocessor tasks \u2014 an overview, European Journal on Operations Research, 94 (1996), 215\u2013230.","journal-title":"European Journal on Operations Research"},{"key":"34_CR9","doi-asserted-by":"publisher","first-page":"473","DOI":"10.1137\/0402042","volume":"2","author":"J. Du","year":"1989","unstructured":"J. Du and J. Leung, Complexity of scheduling parallel task systems, SIAM Journal on Discrete Mathematics, 2 (1989), 473\u2013487.","journal-title":"SIAM Journal on Discrete Mathematics"},{"key":"34_CR10","doi-asserted-by":"publisher","first-page":"187","DOI":"10.1006\/jcss.1998.1587","volume":"57","author":"U. Feige","year":"1998","unstructured":"U. Feige and J. Kilian, Zero knowledge and the chromatic number, Journal of Computer and System Sciences, 57 (1998), 187\u2013199.","journal-title":"Journal of Computer and System Sciences"},{"key":"34_CR11","doi-asserted-by":"crossref","unstructured":"A. Feldmann, J. Sgall and S.H. Teng, Dynamic scheduling on parallel machines, Proceedings of the 32nd IEEE Symposium on Foundations of Computer Science (1991), 111\u2013120.","DOI":"10.1109\/SFCS.1991.185355"},{"key":"34_CR12","doi-asserted-by":"crossref","unstructured":"M. Gr\u00f6tschel, L. Lov\u00e1sz and A. Schrijver, Geometric Algorithms and Combinatorial Optimization, Springer Verlag, Berlin, 1988.","DOI":"10.1007\/978-3-642-97881-4"},{"key":"34_CR13","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), 259\u2013272.","journal-title":"Discrete Applied Mathematics"},{"key":"34_CR14","unstructured":"K. Jansen and L. Porkolab, Linear-time approximation schemes for scheduling malleable parallel tasks, Proceedings of the 10th ACM-SIAM Symposium on Discrete Algorithms (1999), 490\u2013498."},{"key":"34_CR15","doi-asserted-by":"crossref","unstructured":"K. Jansen and L. Porkolab, Preemptive scheduling on dedicated processors: applications of fractional graph coloring, Proceedings of the 25th International Symposium on Mathematical Foundations of Computer Science, MFCS 2000, Springer Verlag.","DOI":"10.1007\/3-540-44612-5_40"},{"key":"34_CR16","doi-asserted-by":"crossref","unstructured":"C. Kenyon and E. Remila, Approximate strip packing, Proceedings of the 37th IEEE Symposium on Foundations of Computer Science (1996), 31\u201336.","DOI":"10.1109\/SFCS.1996.548461"},{"key":"34_CR17","unstructured":"W. Ludwig and P. Tiwari, Scheduling malleable and nonmalleable parallel tasks, Proceedings of the 5th ACM-SIAM Symposium on Discrete Algorithms (1994), 167\u2013176."},{"key":"34_CR18","doi-asserted-by":"publisher","first-page":"960","DOI":"10.1145\/185675.306789","volume":"41","author":"C. Lund","year":"1994","unstructured":"C. Lund and M. Yannakakis, On the hardness of approximating minimization problems, Journal of ACM, 41 (1994), 960\u2013981.","journal-title":"Journal of ACM"},{"key":"34_CR19","doi-asserted-by":"publisher","first-page":"153","DOI":"10.1007\/BF01920917","volume":"28","author":"G. Schmidt","year":"1984","unstructured":"G. Schmidt, Scheduling on semi-identical processors, Zeitschrift f\u00fcr Oper. Res. 28 (1984), 153\u2013162.","journal-title":"Zeitschrift f\u00fcr Oper. Res"},{"key":"34_CR20","unstructured":"G. Schmidt, Scheduling with limited machine availability, International Computer Science Institute Technical Report TR-98-036, Berkeley, California, October 1998."},{"key":"34_CR21","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"39","DOI":"10.1007\/3-540-61680-2_45","volume-title":"Preemptive weighted completion time scheduling of parallel jobs","author":"U. Schwiegelshohn","year":"1996","unstructured":"U. Schwiegelshohn, Preemptive weighted completion time scheduling of parallel jobs, Proceedings of the 4th European Symposium of Algorithms (1996), LNCS 1136, 39\u201351."},{"key":"34_CR22","doi-asserted-by":"publisher","first-page":"401","DOI":"10.1137\/S0097539793255801","volume":"26","author":"A. Steinberg","year":"1997","unstructured":"A. Steinberg, A strip-packing algorithm with absolute performance bound two, SIAM Journal on Computing 26 (1997), 401\u2013409.","journal-title":"SIAM Journal on Computing"},{"key":"34_CR23","doi-asserted-by":"crossref","unstructured":"J. Turek, J. Wolf and P. Yu, Approximate algorithms for scheduling parallelizable tasks, Proceedings of the 4th ACM Symposium on Parallel Algorithms and Architectures (1992), 323\u2013332.","DOI":"10.1145\/140901.141909"}],"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_34","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,2]],"date-time":"2019-05-02T17:25:56Z","timestamp":1556817956000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-40996-3_34"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2000]]},"ISBN":["9783540412557","9783540409960"],"references-count":23,"URL":"https:\/\/doi.org\/10.1007\/3-540-40996-3_34","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2000]]}}}