{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,30]],"date-time":"2025-06-30T11:27:46Z","timestamp":1751282866722},"publisher-location":"Berlin, Heidelberg","reference-count":22,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540616801"},{"type":"electronic","value":"9783540706670"}],"license":[{"start":{"date-parts":[[1996,1,1]],"date-time":"1996-01-01T00:00:00Z","timestamp":820454400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1996]]},"DOI":"10.1007\/3-540-61680-2_48","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T17:12:02Z","timestamp":1330276322000},"page":"76-90","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":13,"title":["Scheduling jobs with communication delays: Using infeasible solutions for approximation"],"prefix":"10.1007","author":[{"given":"Rolf H.","family":"M\u00f6hring","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Markus W.","family":"Sch\u00e4ffter","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Andreas S.","family":"Schulz","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,6,6]]},"reference":[{"key":"7_CR1","unstructured":"P. Chr\u00e9tienne and C. Picouleau, Scheduling with communication delays: a survey, Scheduling Theory and its Applications (P. Chr\u00e9tienne, E. G. Coffman Jr, J. K. Lenstra, and Z. Liu, eds.), John Wiley & Sons, 1995, pp. 65\u201390."},{"key":"7_CR2","doi-asserted-by":"crossref","first-page":"646","DOI":"10.1007\/3-540-61440-0_166","volume-title":"Automata, Languages and Programming","author":"Soumen Chakrabarti","year":"1996","unstructured":"S. Chakrabarti, C. A. Phillips, A. S. Schulz, D. B. Shmoys, C. Stein, and J. Wein, Improved scheduling algorithms for minsum criteria, 1996, To appear in Springer Lecture Notes in Computer Science, Proceedings of the 23rd ICALP Conference."},{"key":"7_CR3","unstructured":"M. X. Goemans and J. Kleinberg, An improved approximation ratio for the minimum latency problem, Proceedings of the 7th ACM-SIAM Symposium on Discrete Algorithms, 1996."},{"key":"7_CR4","volume-title":"Algorithms and Combinatorics, vol. 2","author":"M. Gr\u00f6tschel","year":"1988","unstructured":"M. Gr\u00f6tschel, L. Lov\u00e1sz, and A. Schrijver, Geometric Algorithms and Combinatorial Optimization, Algorithms and Combinatorics, vol. 2, Springer, Berlin, 1988."},{"key":"7_CR5","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 Tech. J. 45 (1966), 1563\u20131581.","journal-title":"Bell System Tech. J."},{"key":"7_CR6","unstructured":"C. Hanen and A. Munier, An approximation algorithm for scheduling dependent tasks on m processors with small communication delays, Preprint, Laboratoire Informatique Th\u00e9orique et Programmation, Institut Blaise Pascal, Universit\u00e9 Pierre et Marie Curie, 1995."},{"key":"7_CR7","volume-title":"Preprint 516\/1996","author":"L. A. Hall","year":"1996","unstructured":"L. A. Hall, A. S. Schulz, D. B. Shmoys, and J. Wein, Scheduling to minimize average completion time: Off-line and on-line approximation algorithms, Preprint 516\/1996, Department of Mathematics, University of Technology, Berlin, Germany, 1996, submitted. Available from ftp:\/\/ftp.math.tu-berlin.de\/pub\/Preprints\/combi\/Report-516-1996.ps.Z."},{"key":"7_CR8","unstructured":"L. A. Hall, D. B. Shmoys, and J. Wein, Scheduling to minimize average completion time: Off-line and on-line algorithms, Proceedings of the 7th ACM-SIAM Symposium on Discrete Algorithms, 1996, pp. 142\u2013151."},{"key":"7_CR9","doi-asserted-by":"crossref","first-page":"129","DOI":"10.1016\/0167-6377(94)90024-8","volume":"16","author":"J. A. Hoogeveen","year":"1994","unstructured":"J. A. Hoogeveen, B. Veltman, and J. K. Lenstra, Three, four, five, six, or the complexity of scheduling with communication delays, Operations Research Letters 16 (1994), 129\u2013137.","journal-title":"Operations Research Letters"},{"key":"7_CR10","unstructured":"E. L. Lawler, Scheduling trees on multiprocessors with unit communication delays, Presented at the First Workshop on Models and Algorithms for Planning and Scheduling Problems, unpublished manuscript, June 1993."},{"key":"7_CR11","doi-asserted-by":"crossref","first-page":"157","DOI":"10.1006\/jagm.1996.0007","volume":"20","author":"J. K. Lenstra","year":"1996","unstructured":"J. K. Lenstra, M. Veldhorst, and B. Veltman, The complexity of scheduling trees with communication delays, Journal of Algorithms 20 (1996), 157\u2013173.","journal-title":"Journal of Algorithms"},{"key":"7_CR12","volume-title":"Preprint 871","author":"A. Munier","year":"1993","unstructured":"A. Munier and J.-C. K\u00f6nig, A heuristic for a scheduling problem with communication delays, Preprint 871, Laboratoire de Recherche en informatique, Universit\u00e9 de Paris, France, 1993, to appear in Operations Research, 1996."},{"key":"7_CR13","series-title":"Nato Advanced Study Institutes Series","doi-asserted-by":"crossref","first-page":"105","DOI":"10.1007\/978-94-009-2639-4_4","volume-title":"Algorithms and Order","author":"R. H. M\u00f6hring","year":"1989","unstructured":"R. H. M\u00f6hring, Computationally tractable classes of ordered sets, Algorithms and Order (I. Rival, ed.), Nato Advanced Study Institutes Series, D. Reidel Publishing Company, Dordrecht, 1989, pp. 105\u2013193."},{"key":"7_CR14","volume-title":"Preprint No. 506\/1996","author":"R. H. M\u00f6hring","year":"1996","unstructured":"R. H. M\u00f6hring and M. W. Sch\u00e4ffter, A simple approximation algorithm for scheduling forests with unit processing times and zero-one communication delays, Preprint No. 506\/1996, University of Technology, Berlin, 1996, ftp:\/\/ftp.math.tuberlin.de\/pub\/Preprints\/combi\/Report-506-1995.ps.Z."},{"key":"7_CR15","volume-title":"Preprint 517\/1996","author":"R. H. M\u00f6hring","year":"1996","unstructured":"R. H. M\u00f6hring, M. W. Sch\u00e4ffter, and A. S. Schulz, Scheduling jobs with communication delays: Using infeasible solutions for approximation, Preprint 517\/1996, Department of Mathematics, University of Technology, Berlin, Germany, 1996."},{"key":"7_CR16","doi-asserted-by":"crossref","first-page":"331","DOI":"10.1016\/0166-218X(94)00063-J","volume":"60","author":"C. Picouleau","year":"1995","unstructured":"C. Picouleau, New complexity results on scheduling with small communication delays, Discrete Applied Mathematics 60 (1995), 331\u2013342.","journal-title":"Discrete Applied Mathematics"},{"key":"7_CR17","first-page":"86","volume-title":"Lecture Notes in Computer Science, no. 955","author":"C. Phillips","year":"1995","unstructured":"C. Phillips, C. Stein, and J. Wein, Scheduling jobs that arrive over time, Proceedings of the Fourth Workshop on Algorithms and Data Structures (Berlin), Lecture Notes in Computer Science, no. 955, Springer, Berlin, 1995, pp. 86\u201397."},{"key":"7_CR18","doi-asserted-by":"crossref","first-page":"55","DOI":"10.1016\/0166-218X(87)90042-4","volume":"18","author":"V. J. Rayward-Smith","year":"1987","unstructured":"V. J. Rayward-Smith, UET scheduling with unit interprocessor communication delays, Discrete Applied Math. 18 (1987), 55\u201371.","journal-title":"Discrete Applied Math."},{"key":"7_CR19","volume-title":"Ph.D. thesis","author":"A. S. Schulz","year":"1995","unstructured":"A. S. Schulz, Polytopes and scheduling, Ph.D. thesis, University of Technology, Berlin, Germany, 1995."},{"key":"7_CR20","series-title":"Lecture Notes in Computer Science, no. 1084","doi-asserted-by":"crossref","first-page":"301","DOI":"10.1007\/3-540-61310-2_23","volume-title":"Integer Programming and Combinatorial Optimization (Berlin)","author":"A. S. Schulz","year":"1996","unstructured":"A. S. Schulz, Scheduling to minimize total weighted completion time: Performance guarantees of LP-based heuristics and lower bounds, Integer Programming and Combinatorial Optimization (Berlin) (W. H. Cunningham, S. T. McCormick, and M. Queyranne, eds.), Lecture Notes in Computer Science, no. 1084, Springer, Berlin, 1996, Proceedings of the 5th International IPCO Conference, pp. 301\u2013315."},{"key":"7_CR21","unstructured":"J. Verriet, Scheduling UET, UCT dags with release dates and deadlines, Preprint No. UU-CS-1995-31, Utrecht University, Department of Computer Science, 1995."},{"key":"7_CR22","doi-asserted-by":"publisher","first-page":"173","DOI":"10.1016\/0167-8191(90)90056-F","volume":"16","author":"B. Veltman","year":"1990","unstructured":"B. Veltman, B. Lageweg, and J. K. Lenstra, Multiprocessor scheduling with commmunication delays, Parallel Computing 16 (1990), 173\u2013182.","journal-title":"Parallel Computing"}],"container-title":["Lecture Notes in Computer Science","Algorithms \u2014 ESA '96"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-61680-2_48","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,1,8]],"date-time":"2020-01-08T21:06:41Z","timestamp":1578517601000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-61680-2_48"}},"subtitle":["Extended abstract"],"short-title":[],"issued":{"date-parts":[[1996]]},"ISBN":["9783540616801","9783540706670"],"references-count":22,"URL":"https:\/\/doi.org\/10.1007\/3-540-61680-2_48","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1996]]},"assertion":[{"value":"6 June 2005","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}