{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,11]],"date-time":"2025-02-11T20:40:35Z","timestamp":1739306435271,"version":"3.37.0"},"publisher-location":"Berlin, Heidelberg","reference-count":27,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642036842"},{"type":"electronic","value":"9783642036859"}],"license":[{"start":{"date-parts":[[2009,1,1]],"date-time":"2009-01-01T00:00:00Z","timestamp":1230768000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2009]]},"DOI":"10.1007\/978-3-642-03685-9_7","type":"book-chapter","created":{"date-parts":[[2009,8,21]],"date-time":"2009-08-21T02:39:51Z","timestamp":1250822391000},"page":"84-97","source":"Crossref","is-referenced-by-count":4,"title":["The Power of Preemption on Unrelated Machines and Applications to Scheduling Orders"],"prefix":"10.1007","author":[{"given":"Jos\u00e9 R.","family":"Correa","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Martin","family":"Skutella","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jos\u00e9","family":"Verschae","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"7_CR1","doi-asserted-by":"crossref","unstructured":"Afrati, F., Bampis, E., Chekuri, C., Karger, D., Kenyon, C., Khanna, S., Milis, I., Queyranne, M., Skutella, M., Stein, C., Sviridenko, M.: Approximation schemes for minimizing average weighted completion time with release dates. In: Proceedings of the 40th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pp. 32\u201343 (1999)","DOI":"10.1109\/SFFCS.1999.814574"},{"key":"7_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"28","DOI":"10.1007\/11841036_6","volume-title":"Algorithms \u2013 ESA 2006","author":"C. Amb\u00fchl","year":"2006","unstructured":"Amb\u00fchl, C., Mastrolilli, M.: Single Machine Precedence Constrained Scheduling is a Vertex Cover Problem. In: Azar, Y., Erlebach, T. (eds.) ESA 2006. LNCS, vol.\u00a04168, pp. 28\u201339. Springer, Heidelberg (2006)"},{"key":"7_CR3","doi-asserted-by":"crossref","unstructured":"Amb\u00fchl, C., Mastrolilli, M., Svensson, O.: Inapproximability Results for Sparsest Cut, Optimal Linear Arrangement, and Precedence Constrained Scheduling. In: Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pp. 329\u2013337 (2007)","DOI":"10.1109\/FOCS.2007.4389504"},{"key":"7_CR4","doi-asserted-by":"publisher","first-page":"993","DOI":"10.1137\/S0097539795283292","volume":"27","author":"R. Canetti","year":"1998","unstructured":"Canetti, R., Irani, S.: Bounding the Power of Preemption in Randomized Scheduling. SIAM J. Computing\u00a027, 993\u20131015 (1998)","journal-title":"SIAM J. Computing"},{"key":"7_CR5","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 times on a single machine. Discrete Applied Mathematics\u00a098, 29\u201338 (1999)","journal-title":"Discrete Applied Mathematics"},{"key":"7_CR6","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. Oper. Res. Let.\u00a025, 199\u2013204 (1999)","journal-title":"Oper. Res. Let."},{"key":"7_CR7","doi-asserted-by":"publisher","first-page":"1005","DOI":"10.1287\/moor.1050.0158","volume":"30","author":"J.R. Correa","year":"2005","unstructured":"Correa, J.R., Schulz, A.S.: Single Machine Scheduling with Precedence Constraints. Math. Oper. Res.\u00a030, 1005\u20131021 (2005)","journal-title":"Math. Oper. Res."},{"key":"7_CR8","doi-asserted-by":"publisher","first-page":"255","DOI":"10.1016\/0166-218X(90)90104-K","volume":"26","author":"M.E. Dyer","year":"1999","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 (1999)","journal-title":"Discrete Applied Mathematics"},{"key":"7_CR9","doi-asserted-by":"publisher","first-page":"1563","DOI":"10.1002\/j.1538-7305.1966.tb01709.x","volume":"45","author":"R.L. Graham","year":"1966","unstructured":"Graham, R.L.: Bounds for certain multiprocessing anomalies. Bell Systems Technical Journal\u00a045, 1563\u20131581 (1966)","journal-title":"Bell Systems Technical Journal"},{"key":"7_CR10","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. Math. Oper. Res.\u00a022, 513\u2013544 (1997)","journal-title":"Math. Oper. Res."},{"key":"7_CR11","doi-asserted-by":"publisher","first-page":"144","DOI":"10.1145\/7531.7535","volume":"34","author":"D. Hochbaum","year":"1987","unstructured":"Hochbaum, D., Shmoys, D.: Using dual approximation algorithm for scheduling problems: Theoretical and practical results. J. ACM\u00a034, 144\u2013162 (1987)","journal-title":"J. ACM"},{"key":"7_CR12","doi-asserted-by":"publisher","first-page":"157","DOI":"10.1287\/ijoc.13.2.157.10520","volume":"13","author":"H. Hoogeveen","year":"2001","unstructured":"Hoogeveen, H., Schuurman, P., Woeginger, G.J.: Non-approximability results for scheduling problems with minsum criteria. INFORMS J. Computing\u00a013, 157\u2013168 (2001)","journal-title":"INFORMS J. Computing"},{"key":"7_CR13","doi-asserted-by":"publisher","first-page":"612","DOI":"10.1145\/322092.322101","volume":"25","author":"E.L. Lawler","year":"1978","unstructured":"Lawler, E.L., Labetoulle, J.: On Preemptive Scheduling of Unrelated Parallel Processors by Linear Programming. J. ACM\u00a025, 612\u2013619 (1978)","journal-title":"J. ACM"},{"key":"7_CR14","doi-asserted-by":"publisher","first-page":"445","DOI":"10.1016\/S0927-0507(05)80189-6","volume-title":"Logistics of Production and Inventory, Handbooks in Oper. Res. and Management Science","author":"E.L. Lawler","year":"1993","unstructured":"Lawler, E.L., Lenstra, J.K., Rinnooy Kan, A.H.G., Shmoys, D.B.: Sequencing and scheduling: Algorithms and complexity. In: Graves, S.C., Rinnooy Kan, A.H.G., Zipkin, P.H. (eds.) Logistics of Production and Inventory, Handbooks in Oper. Res. and Management Science, vol.\u00a04, pp. 445\u2013522. North-Holland, Amsterdam (1993)"},{"key":"7_CR15","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 constrains. Operations Research\u00a026, 22\u201335 (1978)","journal-title":"Operations Research"},{"key":"7_CR16","doi-asserted-by":"publisher","first-page":"259","DOI":"10.1007\/BF01585745","volume":"46","author":"J.K. Lenstra","year":"1990","unstructured":"Lenstra, J.K., Shmoys, D.B., Tardos, E.: Approximation algorithms for scheduling unrelated parallel machines. Mathematical Programming\u00a046, 259\u2013271 (1990)","journal-title":"Mathematical Programming"},{"key":"7_CR17","doi-asserted-by":"publisher","first-page":"243","DOI":"10.1002\/nav.20138","volume":"53","author":"J. Leung","year":"2006","unstructured":"Leung, J., Li, H., Pinedo, M.: Approximation algorithm for minimizing total weighted completion time of orders on identical parallel machines. Naval Research Logistics\u00a053, 243\u2013260 (2006)","journal-title":"Naval Research Logistics"},{"key":"7_CR18","doi-asserted-by":"publisher","first-page":"119","DOI":"10.1016\/j.ipl.2007.03.002","volume":"103","author":"J. Leung","year":"2007","unstructured":"Leung, J., Li, H., Pinedo, M., Zhang, J.: Minimizing Total Weighted Completion Time when Scheduling Orders in a Flexible Environment with Uniform Machines. Information Processing Letters\u00a0103, 119\u2013129 (2007)","journal-title":"Information Processing Letters"},{"key":"7_CR19","doi-asserted-by":"publisher","first-page":"945","DOI":"10.1016\/j.dam.2006.09.012","volume":"155","author":"J. Leung","year":"2007","unstructured":"Leung, J., Li, H., Pinedo, M.: Scheduling orders for multiple product types to minimize total weighted completion time. Discrete Applied Mathematics\u00a0155, 945\u2013970 (2007)","journal-title":"Discrete Applied Mathematics"},{"key":"7_CR20","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":"7_CR21","doi-asserted-by":"publisher","first-page":"651","DOI":"10.1007\/s00453-001-0098-3","volume":"32","author":"H. Shachnai","year":"2002","unstructured":"Shachnai, H., Tamir, T.: Multiprocessor Scheduling with Machine Allotment and Parallelism Constraints. Algorithmica\u00a032, 651\u2013678 (2002)","journal-title":"Algorithmica"},{"key":"7_CR22","doi-asserted-by":"publisher","first-page":"450","DOI":"10.1137\/S0895480199357078","volume":"15","author":"A. Schulz","year":"2002","unstructured":"Schulz, A., Skutella, M.: Scheduling unrelated machines by randomized rounding. SIAM J. Discrete Math.\u00a015, 450\u2013469 (2002)","journal-title":"SIAM J. Discrete Math."},{"key":"7_CR23","doi-asserted-by":"publisher","first-page":"561","DOI":"10.1007\/BF01585178","volume":"62","author":"D.B. Shmoys","year":"1993","unstructured":"Shmoys, D.B., Tardos, E.: An approximation algorithm for the generalized assignment problem. Mathematical Programming\u00a062, 561\u2013574 (1993)","journal-title":"Mathematical Programming"},{"key":"7_CR24","doi-asserted-by":"publisher","first-page":"63","DOI":"10.1287\/moor.25.1.63.15212","volume":"25","author":"M. Skutella","year":"2000","unstructured":"Skutella, M., Woeginger, G.J.: Minimizing the total weighted completion time on identical parallel machines. Math. Oper. Res.\u00a025, 63\u201375 (2000)","journal-title":"Math. Oper. Res."},{"key":"7_CR25","doi-asserted-by":"publisher","first-page":"206","DOI":"10.1145\/375827.375840","volume":"48","author":"M. Skutella","year":"2001","unstructured":"Skutella, M.: Convex quadratic and semidefinite programming relaxations in scheduling. J. ACM\u00a048, 206\u2013242 (2001)","journal-title":"J. ACM"},{"key":"7_CR26","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 Logics Quarterly\u00a03, 59\u201366 (1956)","journal-title":"Naval Research Logics Quarterly"},{"key":"7_CR27","unstructured":"Verschae, J.: Approximation algorithms for scheduling orders on parallel machines. Mathematical engineering thesis. Universidad de Chile, Santiago, Chile (2008)"}],"container-title":["Lecture Notes in Computer Science","Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-03685-9_7","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,2,11]],"date-time":"2025-02-11T20:24:10Z","timestamp":1739305450000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-03685-9_7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009]]},"ISBN":["9783642036842","9783642036859"],"references-count":27,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-03685-9_7","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2009]]}}}