{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,22]],"date-time":"2026-08-22T08:00:15Z","timestamp":1787385615523,"version":"build-2736575974"},"publisher-location":"Berlin, Heidelberg","reference-count":38,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540645900","type":"print"},{"value":"9783540693468","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1998]]},"DOI":"10.1007\/3-540-69346-7_28","type":"book-chapter","created":{"date-parts":[[2007,8,2]],"date-time":"2007-08-02T11:51:29Z","timestamp":1186055489000},"page":"367-382","source":"Crossref","is-referenced-by-count":26,"title":["Approximation Bounds for a General Class of Precedence Constrained Parallel Machine Scheduling Problems"],"prefix":"10.1007","author":[{"given":"Alix","family":"Munier","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Maurice","family":"Queyranne","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Andreas S.","family":"Schulz","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[1998,6,18]]},"reference":[{"key":"28_CR1","first-page":"1","volume":"75","author":"A. Arnim von","year":"1996","unstructured":"A. von Arnim, R. Schrader, and Y. Wang. The permutahedron of N-sparse posets. Mathematical Programming, 75:1\u201318, 1996.","journal-title":"Mathematical Programming"},{"key":"28_CR2","doi-asserted-by":"publisher","first-page":"179","DOI":"10.1016\/S0166-218X(96)00044-3","volume":"72","author":"A. Arnim von","year":"1997","unstructured":"A. von Arnim and A. S. Schulz. Facets of the generalized permutahedron of a poset. Discrete Applied Mathematics, 72:179\u2013192, 1997.","journal-title":"Discrete Applied Mathematics"},{"key":"28_CR3","doi-asserted-by":"crossref","first-page":"94","DOI":"10.1287\/mnsc.41.1.94","volume":"41","author":"E. Balas","year":"1995","unstructured":"E. Balas, J. K. Lenstra, and A. Vazacopoulos. The one machine problem with delayed precedence constraints and its use in job-shop scheduling. Management Science, 41:94\u2013109, 1995.","journal-title":"Management Science"},{"key":"28_CR4","doi-asserted-by":"publisher","first-page":"201","DOI":"10.1007\/BF02283745","volume":"16","author":"M. Bartusch","year":"1988","unstructured":"M. Bartusch, R. H. M\u00f6hring, and F. J. Radermacher. Scheduling project networks with resource constraints and time windows. Annals of Operations Research, 16:201\u2013240, 1988.","journal-title":"Annals of Operations Research"},{"key":"28_CR5","doi-asserted-by":"publisher","first-page":"57","DOI":"10.1145\/59287.59291","volume":"11","author":"D. Bernstein","year":"1989","unstructured":"D. Bernstein and I. Gertner. Scheduling expressions on a pipelined processor with a maximum delay of one cycle. ACM Transactions on Programming Languages and Systems, 11:57\u201366, 1989.","journal-title":"ACM Transactions on Programming Languages and Systems"},{"key":"28_CR6","doi-asserted-by":"publisher","first-page":"308","DOI":"10.1109\/TC.1980.1675569","volume":"C-29","author":"J. Bruno","year":"1980","unstructured":"J. Bruno, J. W. Jones, and K. So. Deterministic scheduling with pipelined processors. IEEE Transactions on Computers, C-29:308\u2013316, 1980.","journal-title":"IEEE Transactions on Computers"},{"key":"28_CR7","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"646","DOI":"10.1007\/3-540-61440-0_166","volume-title":"Automata, Languages and Programming","author":"S. 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. In F. Meyer auf der Heide and B. Monien, editors, Automata, Languages and Programming, LNCS, Vol. 1099, pages 646\u2013657. Springer, Berlin, 1996."},{"key":"28_CR8","unstructured":"C. S. Chekuri, R. Motwani, B. Natarajan, and C. Stein. Approximation techniques for average completion time scheduling. In Proceedings of the 8th ACM-SIAM Symposium on Discrete Algorithms, pages 609\u2013618, 1997."},{"key":"28_CR9","unstructured":"P. Chr\u00e9tienne and C. Picouleau. Scheduling with communication delays: A survey. In P. Chr\u00e9tienne, E. G. Coffman Jr., J. K. Lenstra, and Z. Liu, editors, Scheduling Theory and its Applications, chapter 4, pages 65\u201390. John Wiley & Sons, 1995."},{"key":"28_CR10","unstructured":"F. A. Chudak and D. B. Shmoys. Approximation algorithms for precedence-constrained scheduling problems on parallel machines that run at different speeds. In Proceedings of the 8th ACM-SIAM Symposium on Discrete Algorithms, pages 581\u2013590, 1997."},{"key":"28_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":"28_CR12","unstructured":"M. X. Goemans. Improved approximation algorithms for scheduling with release dates. In Proceedings of the 8th ACM-SIAM Symposium on Discrete Algorithms, pages 591\u2013598, 1997."},{"key":"28_CR13","unstructured":"M. X. Goemans, M. Queyranne, A. S. Schulz, M. Skutella, and Y. Wang. Single machine scheduling with release dates. Working paper, 1997."},{"key":"28_CR14","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:1563\u20131581, 1966.","journal-title":"Bell System Tech. J."},{"key":"28_CR15","doi-asserted-by":"publisher","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. Annals of Discrete Mathematics, 5:287\u2013326, 1979.","journal-title":"Annals of Discrete Mathematics"},{"key":"28_CR16","doi-asserted-by":"crossref","first-page":"513","DOI":"10.1287\/moor.22.3.513","volume":"22","author":"L. A. Hall","year":"1997","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. Mathematics of Operations Research, 22:513\u2013544, 1997.","journal-title":"Mathematics of Operations Research"},{"key":"28_CR17","unstructured":"W. Herroelen and E. Demeulemeester. Recent advances in branch-and-bound procedures for resource-constrained project scheduling problems. In P. Chr\u00e9tienne, E. G. Coffman Jr., J. K. Lenstra, and Z. Liu, editors, Scheduling Theory and its Applications, chapter 12, pages 259\u2013276. John Wiley & Sons, 1995."},{"key":"28_CR18","series-title":"Lect Notes Comput Sci","first-page":"344","volume-title":"Proceedings of the 6th International IPCO Conference","author":"J. A. Hoogeveen","year":"1998","unstructured":"J. A. Hoogeveen, P. Schuurman, and G. J. Woeginger. Non-approximability results for scheduling problems with minsum criteria. In R. E. Bixby, E. A. Boyd, and R. Z. R\u00edos-Mercado, editors, Proceedings of the 6th International IPCO Conference, LNCS, Vol. 1412, pages 344\u2013357. Springer, 1998. This volume."},{"key":"28_CR19","doi-asserted-by":"publisher","first-page":"129","DOI":"10.1016\/0167-6377(94)90024-8","volume":"3","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, 3:129\u2013137, 1994.","journal-title":"Operations Research Letters"},{"key":"28_CR20","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/0304-3975(80)90002-X","volume":"12","author":"J. M. Jaffe","year":"1980","unstructured":"J. M. Jaffe. Efficient scheduling of tasks without full use of processor resources. Theoretical Computer Science, 12:1\u201317, 1980.","journal-title":"Theoretical Computer Science"},{"key":"28_CR21","series-title":"Technical Report","volume-title":"Pipeline scheduling: A survey","author":"E. Lawler","year":"1987","unstructured":"E. Lawler, J. K. Lenstra, C. Martel, B. Simons, and L. Stockmeyer. Pipeline scheduling: A survey. Technical Report RJ 5738 (57717), IBM Research Division, San Jose, California, 1987."},{"key":"28_CR22","doi-asserted-by":"crossref","first-page":"445","DOI":"10.1016\/S0927-0507(05)80189-6","volume-title":"Logistics of Production and Inventory, Handbooks in Operations Research and Management Science","author":"E. L. Lawler","year":"1993","unstructured":"E. L. Lawler, J. K. Lenstra, A. H. G. Rinnooy Kan, and D. B. Shmoys. Sequencing and scheduling: Algorithms and complexity. In S. C. Graves, A. H. G. Rinnooy Kan, and P. H. Zipkin, editors, Logistics of Production and Inventory, Handbooks in Operations Research and Management Science, Vol. 4, chapter 9, pages 445\u2013522. North-Holland, Amsterdam, The Netherlands, 1993."},{"key":"28_CR23","doi-asserted-by":"crossref","first-page":"22","DOI":"10.1287\/opre.26.1.22","volume":"26","author":"J. K. Lenstra","year":"1978","unstructured":"J. K. Lenstra and A. H. G. Rinnooy Kan. Complexity of scheduling under precedence constraints. Operations Research, 26:22\u201335, 1978.","journal-title":"Operations Research"},{"key":"28_CR24","doi-asserted-by":"publisher","first-page":"650","DOI":"10.1137\/0213040","volume":"13","author":"J. Y.-T. Leung","year":"1984","unstructured":"J. Y.-T. Leung, O. Vornberger, and J. Witthoff. On some variants of the bandwidth minimization problem. SIAM J. Computing, 13:650\u2013667, 1984.","journal-title":"SIAM J. Computing"},{"key":"28_CR25","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"76","DOI":"10.1007\/3-540-61680-2_48","volume-title":"Algorithms-ESA\u201996","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. In J. Diaz and M. Serna, editors, Algorithms-ESA\u201996, LNCS, Vol. 1136, pages 76\u201390. Springer, Berlin, 1996."},{"key":"28_CR26","doi-asserted-by":"crossref","first-page":"145","DOI":"10.1287\/opre.45.1.145","volume":"45","author":"A. Munier","year":"1997","unstructured":"A. Munier and J.-C. K\u00f6nig. A heuristic for a scheduling problem with communication delays. Operations Research, 45:145\u2013147, 1997.","journal-title":"Operations Research"},{"key":"28_CR27","volume-title":"Approximation bounds for a general class of precedence constrained parallel machine scheduling problems","author":"A. Munier","year":"1998","unstructured":"A. Munier, M. Queyranne, and A. S. Schulz. Approximation bounds for a general class of precedence constrained parallel machine scheduling problems. Preprint 584\/1998, Department of Mathematics, Technical University of Berlin, Berlin, Germany, 1998. \n                    ftp:\/\/ftp.math.tu-berlin.de\/pub\/Preprints\/combi\/\n                    \n                   Report-584-1998.ps.Z"},{"key":"28_CR28","doi-asserted-by":"crossref","unstructured":"K. W. Palem and B. Simons. Scheduling time critical instructions on RISC machines. In Proceedings of the 17th Annual Symposium on Principles of Programming Languages, pages 270\u2013280, 1990.","DOI":"10.1145\/96709.96737"},{"key":"28_CR29","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"86","DOI":"10.1007\/3-540-60220-8_53","volume-title":"Proceedings of the Fourth Workshop on Algorithms and Data Structures","author":"C. Phillips","year":"1995","unstructured":"C. Phillips, C. Stein, and J. Wein. Scheduling jobs that arrive over time. In Proceedings of the Fourth Workshop on Algorithms and Data Structures, LNCS, Vol. 955, pages 86\u201397. Springer, Berlin, 1995."},{"key":"28_CR30","doi-asserted-by":"publisher","first-page":"263","DOI":"10.1007\/BF01581271","volume":"58","author":"M. Queyranne","year":"1993","unstructured":"M. Queyranne. Structure of a simple scheduling polyhedron. Mathematical Programming, 58:263\u2013285, 1993.","journal-title":"Mathematical Programming"},{"key":"28_CR31","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1287\/moor.16.1.1","volume":"16","author":"M. Queyranne","year":"1991","unstructured":"M. Queyranne and Y. Wang. Single-machine scheduling polyhedra with precedence constraints. Mathematics of Operations Research, 16:1\u201320, 1991.","journal-title":"Mathematics of Operations Research"},{"key":"28_CR32","doi-asserted-by":"publisher","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 Mathematics, 18:55\u201371, 1987.","journal-title":"Discrete Applied Mathematics"},{"key":"28_CR33","volume-title":"Polytopes and Scheduling","author":"A. S. Schulz","year":"1996","unstructured":"A. S. Schulz. Polytopes and Scheduling. PhD thesis, Technical University of Berlin, Berlin, Germany, 1996."},{"key":"28_CR34","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"301","DOI":"10.1007\/3-540-61310-2_23","volume-title":"Integer Programming and Combinatorial Optimization","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. In W. H. Cunningham, S. T. McCormick, and M. Queyranne, editors, Integer Programming and Combinatorial Optimization, LNCS, Vol. 1084, pages 301\u2013315. Springer, Berlin, 1996."},{"key":"28_CR35","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"119","DOI":"10.1007\/3-540-63248-4_11","volume-title":"Randomization and Approximation Techniques in Computer Science","author":"A. S. Schulz","year":"1997","unstructured":"A. S. Schulz and M. Skutella. Random-based scheduling: New approximations and LP lower bounds. In J. Rolim, editor, Randomization and Approximation Techniques in Computer Science, LNCS, Vol. 1269, pages 119\u2013133. Springer, Berlin, 1997."},{"key":"28_CR36","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"416","DOI":"10.1007\/3-540-63397-9_32","volume-title":"Algorithms \u2014 ESA\u201997","author":"A. S. Schulz","year":"1997","unstructured":"A. S. Schulz and M. Skutella. Scheduling-LPs bear probabilities: Randomized approximations for min-sum criteria. In R. Burkard and G. Woeginger, editors, Algorithms \u2014 ESA\u201997, LNCS, Vol. 1284, pages 416\u2013429. Springer, Berlin, 1997."},{"key":"28_CR37","doi-asserted-by":"publisher","first-page":"87","DOI":"10.1016\/0167-6377(94)90064-7","volume":"16","author":"E. D. Wikum","year":"1994","unstructured":"E. D. Wikum, D. C. Llewellyn, and G. L. Nemhauser. One-machine generalized precedence constrained scheduling problems. Operations Research Letters, 16:87\u201389, 1994.","journal-title":"Operations Research Letters"},{"key":"28_CR38","volume-title":"Invited Talk at the 12th International Symposium on Mathematical Programming","author":"L. A. Wolsey","year":"1985","unstructured":"L. A. Wolsey, August 1985. Invited Talk at the 12th International Symposium on Mathematical Programming, MIT, Cambridge."}],"container-title":["Lecture Notes in Computer Science","Integer Programming and Combinatorial Optimization"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-69346-7_28","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,2,17]],"date-time":"2019-02-17T17:41:28Z","timestamp":1550425288000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-69346-7_28"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1998]]},"ISBN":["9783540645900","9783540693468"],"references-count":38,"URL":"https:\/\/doi.org\/10.1007\/3-540-69346-7_28","relation":{},"ISSN":["0302-9743"],"issn-type":[{"value":"0302-9743","type":"print"}],"subject":[],"published":{"date-parts":[[1998]]}}}