{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T23:45:39Z","timestamp":1725493539012},"publisher-location":"Berlin, Heidelberg","reference-count":12,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540422877"},{"type":"electronic","value":"9783540482246"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2001]]},"DOI":"10.1007\/3-540-48224-5_72","type":"book-chapter","created":{"date-parts":[[2007,10,28]],"date-time":"2007-10-28T02:29:04Z","timestamp":1193538544000},"page":"887-897","source":"Crossref","is-referenced-by-count":8,"title":["On the Approximability of Average Completion Time Scheduling under Precedence Constraints"],"prefix":"10.1007","author":[{"given":"Gerhard J.","family":"Woeginger","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2001,7,4]]},"reference":[{"key":"72_CR1","doi-asserted-by":"publisher","first-page":"29","DOI":"10.1016\/S0166-218X(98)00143-7","volume":"98","author":"C. Chekuri","year":"1999","unstructured":"C. Chekuri AND R. Motwani [1999]. Precedence constrained scheduling to minimize sum of weighted completion times on a single machine. Discrete Applied Mathematics 98, 29\u201338.","journal-title":"Discrete Applied Mathematics"},{"key":"72_CR2","doi-asserted-by":"publisher","first-page":"199","DOI":"10.1016\/S0167-6377(99)00056-5","volume":"25","author":"F. Chudak","year":"1999","unstructured":"F. Chudak AND D.S. Hochbaum [1999]. A half-integral linear programming relaxation for scheduling precedence-constrained jobs on a single machine. Operations Research Letters 25, 199\u2013204.","journal-title":"Operations Research Letters"},{"key":"72_CR3","doi-asserted-by":"publisher","first-page":"255","DOI":"10.1016\/0166-218X(90)90104-K","volume":"26","author":"M.E. Dyer","year":"1990","unstructured":"M.E. Dyer AND L.A. Wolsey [1990]. Formulating the single machine sequencing problem with release dates as a mixed integer program. Discrete Applied Mathematics 26, 255\u2013270.","journal-title":"Discrete Applied Mathematics"},{"key":"72_CR4","doi-asserted-by":"publisher","first-page":"281","DOI":"10.1137\/S0895480197330254","volume":"13","author":"M.X. Goemans","year":"2000","unstructured":"M.X. Goemans AND D.P. Williamson [2000]. Two-dimensional Gantt charts and a scheduling algorithm of Lawler. Siam Journal on Discrete Mathematics 13, 281\u2013294.","journal-title":"Siam Journal on Discrete Mathematics"},{"key":"72_CR5","doi-asserted-by":"publisher","first-page":"287","DOI":"10.1016\/S0167-5060(08)70356-X","volume":"5","author":"R.L. Gawler","year":"1979","unstructured":"R.L. Gawler, J.K. Lenstra, AND A.H.G. Rinnooy Kan [1979]. Optimization and approximation in deterministic sequencing and scheduling: A survey. Annals of Discrete Mathematics 5, 287\u2013326.","journal-title":"Annals of Discrete Mathematics"},{"key":"72_CR6","doi-asserted-by":"publisher","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 [1997]. Scheduling to minimize average completion time: Off-line and on-line approximation algorithms. Mathematics of Operations Research 22, 513\u2013544.","journal-title":"Mathematics of Operations Research"},{"key":"72_CR7","doi-asserted-by":"publisher","first-page":"75","DOI":"10.1016\/S0167-5060(08)70323-6","volume":"2","author":"E.L. Lawler","year":"1978","unstructured":"E.L. Lawler [1978]. Sequencing jobs to minimize total weighted completion time subject to precedence constraints. Annals of Discrete Mathematics 2, 75\u201390.","journal-title":"Annals of Discrete Mathematics"},{"key":"72_CR8","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 [1978]. Complexity of scheduling under precedence constraints. Operations Research 26, 22\u201335.","journal-title":"Operations Research"},{"key":"72_CR9","series-title":"Report","volume-title":"Decompositions, network flows, and a precedence constrained single machine scheduling problem","author":"F. Margot","year":"1997","unstructured":"F. Margot, M. Queyranne, AND Y. Wang [1997]. Decompositions, network flows, and a precedence constrained single machine scheduling problem. Report #2000-29, Department of Mathematics, University of Kentucky, Lexington."},{"key":"72_CR10","doi-asserted-by":"crossref","unstructured":"R.H. M\u00f6hring [1989]. Computationally tractable classes of ordered sets. In: I. Rival (ed.) Algorithms and Order, Kluwer Academic Publishers, 105\u2013193.","DOI":"10.1007\/978-94-009-2639-4_4"},{"key":"72_CR11","doi-asserted-by":"crossref","first-page":"78","DOI":"10.1007\/BFb0120909","volume":"13","author":"C.N. Potts","year":"1980","unstructured":"C.N. Potts [1980]. An algorithm for the single machine sequencing problem with precedence constraints. Mathematical Programming Study 13, 78\u201387.","journal-title":"Mathematical Programming Study"},{"key":"72_CR12","doi-asserted-by":"publisher","first-page":"203","DOI":"10.1002\/(SICI)1099-1425(199909\/10)2:5<203::AID-JOS26>3.0.CO;2-5","volume":"2","author":"P. Schuurman","year":"1999","unstructured":"P. Schuurman AND G.J. Woeginger [1999]. Polynomial time approximation algorithms for machine scheduling: Ten open problems. Journal of Scheduling 2, 203\u2013213.","journal-title":"Journal of Scheduling"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-48224-5_72","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,1,17]],"date-time":"2019-01-17T14:34:10Z","timestamp":1547735650000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-48224-5_72"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2001]]},"ISBN":["9783540422877","9783540482246"],"references-count":12,"URL":"https:\/\/doi.org\/10.1007\/3-540-48224-5_72","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2001]]}}}