{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T18:57:12Z","timestamp":1725562632908},"publisher-location":"Berlin, Heidelberg","reference-count":26,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540221135"},{"type":"electronic","value":"9783540259602"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2004]]},"DOI":"10.1007\/978-3-540-25960-2_22","type":"book-chapter","created":{"date-parts":[[2010,8,8]],"date-time":"2010-08-08T23:21:46Z","timestamp":1281309706000},"page":"283-297","source":"Crossref","is-referenced-by-count":3,"title":["Single Machine Scheduling with Precedence Constraints"],"prefix":"10.1007","author":[{"given":"Jos\u00e9 R.","family":"Correa","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Andreas S.","family":"Schulz","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"22_CR1","doi-asserted-by":"crossref","first-page":"179","DOI":"10.1007\/BFb0121051","volume":"24","author":"E. Balas","year":"1985","unstructured":"Balas, E.: On the facial structure of scheduling polyhedra. Mathematical Programming Study\u00a024, 179\u2013218 (1985)","journal-title":"Mathematical Programming Study"},{"key":"22_CR2","doi-asserted-by":"publisher","first-page":"29","DOI":"10.1016\/S0166-218X(98)00143-7","volume":"98","author":"C. Chekuri","year":"1999","unstructured":"Chekuri, C., Motwani, R.: Precedence constrained scheduling to minimize sum of weighted completion time on a single machine. Discrete Applied Mathematics\u00a098, 29\u201338 (1999)","journal-title":"Discrete Applied Mathematics"},{"key":"22_CR3","doi-asserted-by":"publisher","first-page":"199","DOI":"10.1016\/S0167-6377(99)00056-5","volume":"25","author":"F. Chudak","year":"1999","unstructured":"Chudak, F., Hochbaum, D.S.: A half-integral linear programming relaxation for scheduling precedence-constrained jobs on a single machine. Operations Research Letters\u00a025, 199\u2013204 (1999)","journal-title":"Operations Research Letters"},{"key":"22_CR4","doi-asserted-by":"publisher","first-page":"255","DOI":"10.1016\/0166-218X(90)90104-K","volume":"26","author":"M.E. Dyer","year":"1990","unstructured":"Dyer, M.E., Wolsey, L.A.: Formulating the single machine sequencing problem with release dates as a mixed integer program. Discrete Applied Mathematics\u00a026, 255\u2013270 (1990)","journal-title":"Discrete Applied Mathematics"},{"key":"22_CR5","doi-asserted-by":"publisher","first-page":"268","DOI":"10.1287\/mnsc.11.2.268","volume":"11","author":"W.L. Eastman","year":"1964","unstructured":"Eastman, W.L., Even, S., Isaacs, I.M.: Bounds for the optimal scheduling of n jobs on m processors. Management Science\u00a011, 268\u2013279 (1964)","journal-title":"Management Science"},{"key":"22_CR6","doi-asserted-by":"publisher","first-page":"281","DOI":"10.1137\/S0895480197330254","volume":"13","author":"M.X. Goemans","year":"2000","unstructured":"Goemans, M.X., Williamson, D.P.: Two dimensional Gantt charts and a scheduling algorithm of Lawler. SIAM Journal on Discrete Mathematics\u00a013, 281\u2013294 (2000)","journal-title":"SIAM Journal on Discrete Mathematics"},{"key":"22_CR7","doi-asserted-by":"publisher","first-page":"287","DOI":"10.1016\/S0167-5060(08)70356-X","volume":"5","author":"R.L. Graham","year":"1979","unstructured":"Graham, R.L., Lawler, E.L., Lenstra, J.K., Rinnooy Kan, A.H.G.: Optimization and approximation in deterministic sequencing and scheduling: A survey. Annals of Discrete Mathematics\u00a05, 287\u2013326 (1979)","journal-title":"Annals of Discrete Mathematics"},{"key":"22_CR8","unstructured":"Hall, L.A., Shmoys, D.B., Wein, J.: Scheduling to minimize average completion time: Off-line and on-line algorithms. In: Proceedings of the 7th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 142\u2013151 (1996)"},{"key":"22_CR9","doi-asserted-by":"publisher","first-page":"513","DOI":"10.1287\/moor.22.3.513","volume":"22","author":"L.A. Hall","year":"1997","unstructured":"Hall, L.A., Schulz, A.S., Shmoys, D.B., Wein, J.: Scheduling to minimize average completion time: Off-line and on-line approximation algorithms. Mathematics of Operations Research\u00a022, 513\u2013544 (1997)","journal-title":"Mathematics of Operations Research"},{"key":"22_CR10","doi-asserted-by":"publisher","first-page":"243","DOI":"10.1016\/0166-218X(83)90080-X","volume":"6","author":"D.S. Hochbaum","year":"1983","unstructured":"Hochbaum, D.S.: Efficient bounds for the stable set, vertex cover and set packing problems. Discrete Applied Mathematics\u00a06, 243\u2013254 (1983)","journal-title":"Discrete Applied Mathematics"},{"key":"22_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"612","DOI":"10.1007\/3-540-45749-6_54","volume-title":"Algorithms - ESA 2002","author":"S. Kolliopoulos","year":"2002","unstructured":"Kolliopoulos, S., Steiner, G.: Partially-ordered knapsack and applications to scheduling. In: M\u00f6hring, R.H., Raman, R. (eds.) ESA 2002. LNCS, vol.\u00a02461, pp. 612\u2013624. Springer, Heidelberg (2002)"},{"key":"22_CR12","doi-asserted-by":"publisher","first-page":"75","DOI":"10.1016\/S0167-5060(08)70323-6","volume":"2","author":"E.L. Lawler","year":"1978","unstructured":"Lawler, E.L.: Sequencing jobs to minimize total weighted completion time subject to precedence constraints. Annals of Discrete Mathematics\u00a02, 75\u201390 (1978)","journal-title":"Annals of Discrete Mathematics"},{"key":"22_CR13","doi-asserted-by":"publisher","first-page":"22","DOI":"10.1287\/opre.26.1.22","volume":"26","author":"J.K. Lenstra","year":"1978","unstructured":"Lenstra, J.K., Rinnooy Kan, A.H.G.: Complexity of scheduling under precedence constraints. Operations Research\u00a026, 22\u201335 (1978)","journal-title":"Operations Research"},{"key":"22_CR14","doi-asserted-by":"publisher","first-page":"981","DOI":"10.1287\/opre.51.6.981.24912","volume":"51","author":"F. Margot","year":"2003","unstructured":"Margot, F., Queyranne, M., Wang, Y.: Decompositions, network flows, and a precedence constrained single-machine scheduling problem. Operations Research\u00a051, 981\u2013992 (2003)","journal-title":"Operations Research"},{"key":"22_CR15","doi-asserted-by":"publisher","first-page":"232","DOI":"10.1007\/BF01580444","volume":"8","author":"G.L. Nemhauser","year":"1978","unstructured":"Nemhauser, G.L., Trotter, L.E.: Vertex packing: Structural properties and algorithms. Mathematical Programming\u00a08, 232\u2013248 (1978)","journal-title":"Mathematical Programming"},{"key":"22_CR16","doi-asserted-by":"publisher","first-page":"1268","DOI":"10.1287\/mnsc.22.11.1268","volume":"22","author":"J.C. Picard","year":"1976","unstructured":"Picard, J.C.: Maximum closure of a graph and applications to combinatorial problems. Management Science\u00a022, 1268\u20131272 (1976)","journal-title":"Management Science"},{"key":"22_CR17","doi-asserted-by":"crossref","first-page":"78","DOI":"10.1007\/BFb0120909","volume":"13","author":"C.N. Potts","year":"1980","unstructured":"Potts, C.N.: An algorithm for the single machine sequencing problem with precedence constraints. Mathematical Programming Study\u00a013, 78\u201387 (1980)","journal-title":"Mathematical Programming Study"},{"key":"22_CR18","doi-asserted-by":"publisher","first-page":"263","DOI":"10.1007\/BF01581271","volume":"58","author":"M. Queyranne","year":"1993","unstructured":"Queyranne, M.: Structure of a simple scheduling polyhedron. Mathematical Programming\u00a058, 263\u2013285 (1993)","journal-title":"Mathematical Programming"},{"key":"22_CR19","unstructured":"Queyranne, M., Schulz, A.S.: Polyhedral approaches to machine scheduling. Technical Report 408, Department of Mathematics, Technische Universit\u00e4t Berlin, Germany (1994)"},{"key":"22_CR20","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1287\/moor.16.1.1","volume":"16","author":"M. Queyranne","year":"1991","unstructured":"Queyranne, M., Wang, Y.: Single-machine scheduling polyhedra with precedence constraints. Mathematics of Operations Research\u00a016, 1\u201320 (1991)","journal-title":"Mathematics of Operations Research"},{"key":"22_CR21","series-title":"Lecture Notes in Computer Science","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":"Schulz, A.S.: Scheduling to minimize total weighted completion time: Performance guarantees of LP-based heuristics and lower bounds. In: Cunningham, W.H., Queyranne, M., McCormick, S.T. (eds.) IPCO 1996. LNCS, vol.\u00a01084, pp. 301\u2013315. Springer, Heidelberg (1996)"},{"key":"22_CR22","doi-asserted-by":"publisher","first-page":"283","DOI":"10.1287\/opre.23.2.283","volume":"23","author":"J.B. Sidney","year":"1975","unstructured":"Sidney, J.B.: Decomposition algorithms for single machine scheduling with precedence relations and deferral costs. Operations Research\u00a023, 283\u2013298 (1975)","journal-title":"Operations Research"},{"key":"22_CR23","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1002\/nav.3800030106","volume":"3","author":"W.E. Smith","year":"1956","unstructured":"Smith, W.E.: Various optimizers for single-stage production. Naval Research and Logistics Quarterly\u00a03, 59\u201366 (1956)","journal-title":"Naval Research and Logistics Quarterly"},{"key":"22_CR24","doi-asserted-by":"publisher","first-page":"237","DOI":"10.1016\/S0166-218X(02)00427-4","volume":"131","author":"G.J. Woeginer","year":"2003","unstructured":"Woeginer, G.J.: On the approximability of average completion time scheduling under precedence constraints. Discrete Applied Mathematics\u00a0131, 237\u2013252 (2003)","journal-title":"Discrete Applied Mathematics"},{"key":"22_CR25","unstructured":"Wolsey, L.A.: Mixed integer programming formulations for production planning and scheduling problems. Invited talk at the 12th International Symposium on Mathematical Programming, MIT, Cambridge (1985)"},{"key":"22_CR26","first-page":"473","volume-title":"Economic Decision-Making: Games, Econometrics and Optimisation","author":"L.A. Wolsey","year":"1990","unstructured":"Wolsey, L.A.: Formulating single machine scheduling problems with precedence constraints. In: Gabszewic, J.J., Richard, J.F., Wolsey, L.A. (eds.) Economic Decision-Making: Games, Econometrics and Optimisation, pp. 473\u2013484. North-Holland, Amsterdam (1990)"}],"container-title":["Lecture Notes in Computer Science","Integer Programming and Combinatorial Optimization"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-25960-2_22.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,5,3]],"date-time":"2021-05-03T03:19:44Z","timestamp":1620011984000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-25960-2_22"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2004]]},"ISBN":["9783540221135","9783540259602"],"references-count":26,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-25960-2_22","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2004]]}}}