{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,23]],"date-time":"2025-02-23T05:15:54Z","timestamp":1740287754559,"version":"3.37.3"},"publisher-location":"Berlin, Heidelberg","reference-count":20,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540261995"},{"type":"electronic","value":"9783540321026"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2005]]},"DOI":"10.1007\/11496915_15","type":"book-chapter","created":{"date-parts":[[2010,7,14]],"date-time":"2010-07-14T16:40:39Z","timestamp":1279125639000},"page":"196-209","source":"Crossref","is-referenced-by-count":10,"title":["LP-Based Online Scheduling: From Single to Parallel Machines"],"prefix":"10.1007","author":[{"given":"Jos\u00e9 R.","family":"Correa","sequence":"first","affiliation":[]},{"given":"Michael R.","family":"Wagner","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"15_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 IEEE Symposium on Foundations of Computer Science (FOCS), pp. 32\u201343 (1999)","DOI":"10.1109\/SFFCS.1999.814574"},{"key":"15_CR2","doi-asserted-by":"publisher","first-page":"686","DOI":"10.1287\/moor.1040.0092","volume":"29","author":"E.J. Anderson","year":"2004","unstructured":"Anderson, E.J., Potts, C.N.: On-line scheduling of a single machine to minimize total weighted completion time. Mathematics of Operations Research\u00a029, 686\u2013697 (2004)","journal-title":"Mathematics of Operations Research"},{"key":"15_CR3","series-title":"Lecture Notes in Computer Science","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":"Chakrabarti, S., Phillips, C., Schulz, A.S., Shmoys, D.B., Stein, C., Wein, J.: Improved scheduling algorithms for minsum criteria. In: Meyer auf der Heide, F., Monien, B. (eds.) ICALP 1996. LNCS, vol.\u00a01099, pp. 646\u2013657. Springer, Heidelberg (1996)"},{"key":"15_CR4","doi-asserted-by":"publisher","first-page":"146","DOI":"10.1137\/S0097539797327180","volume":"31","author":"C. Chekuri","year":"2001","unstructured":"Chekuri, C., Motwani, R., Natarajan, B., Stein, C.: Approximation techniques for average completion time scheduling. SIAM Journal on Computing\u00a031, 146\u2013166 (2001)","journal-title":"SIAM Journal on Computing"},{"key":"15_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"45","DOI":"10.1007\/3-540-45535-3_4","volume-title":"Integer Programming and Combinatorial Optimization","author":"C.M. Chou","year":"2001","unstructured":"Chou, C.M., Queyranne, M., Simchi-Levi, D.: The asymptotic performance ratio of an on-line algorithm for uniform parallel machine scheduling with release dates. In: Aardal, K., Gerards, B. (eds.) IPCO 2001. LNCS, vol.\u00a02081, pp. 45\u201359. Springer, Heidelberg (2001)"},{"key":"15_CR6","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":"15_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"288","DOI":"10.1007\/3-540-61310-2_22","volume-title":"Proceedings of the 5th Integer Programming and Combinatorial Optimization Conference (IPCO)","author":"M.X. Goemans","year":"1996","unstructured":"Goemans, M.X.: A supermodular relaxation for scheduling with release dates. In: IPCO 1996. LNCS, vol.\u00a01084, pp. 288\u2013300. Springer, Heidelberg (1996)"},{"key":"15_CR8","unstructured":"Goemans, M.X.: Improved approximation algorithms for scheduling with release dates. In: Proceedings of the 8th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 591\u2013598 (1997)"},{"key":"15_CR9","doi-asserted-by":"publisher","first-page":"165","DOI":"10.1137\/S089548019936223X","volume":"15","author":"M.X. Goemans","year":"2002","unstructured":"Goemans, M.X., Queyranne, M., Schulz, A.S., Skutella, M., Wang, Y.: Single machine scheduling with release dates. SIAM Journal on Discrete Mathematics\u00a015, 165\u2013192 (2002)","journal-title":"SIAM Journal on Discrete Mathematics"},{"key":"15_CR10","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":"15_CR11","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":"15_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"404","DOI":"10.1007\/3-540-61310-2_30","volume-title":"Proceedings of the 5th Integer Programming and Combinatorial Optimization Conference (IPCO)","author":"J.A. Hoogeveen","year":"1996","unstructured":"Hoogeveen, J.A., Vestjens, A.P.A.: Optimal on-line algorithms for single-machine scheduling. In: IPCO 1996. LNCS, vol.\u00a01084, pp. 404\u2013414. Springer, Heidelberg (1996)"},{"key":"15_CR13","doi-asserted-by":"publisher","first-page":"485","DOI":"10.1016\/j.orl.2003.11.008","volume":"32","author":"N. Megow","year":"2004","unstructured":"Megow, N., Schulz, A.S.: On-line scheduling to minimize average completion time revisited. Operations Research Letters\u00a032, 485\u2013490 (2004)","journal-title":"Operations Research Letters"},{"key":"15_CR14","first-page":"199","volume":"82","author":"C. Phillips","year":"1998","unstructured":"Phillips, C., Stein, C., Wein, J.: Minimizing average completion time in the presence of release dates. Mathematical Programming\u00a082, 199\u2013223 (1998)","journal-title":"Mathematical Programming"},{"key":"15_CR15","doi-asserted-by":"publisher","first-page":"450","DOI":"10.1137\/S0895480199357078","volume":"15","author":"A.S. Schulz","year":"2002","unstructured":"Schulz, A.S., Skutella, M.: Scheduling unrelated machines by randomized rounding. SIAM Journal on Discrete Mathematics\u00a015, 450\u2013469 (2002)","journal-title":"SIAM Journal on Discrete Mathematics"},{"key":"15_CR16","doi-asserted-by":"publisher","first-page":"121","DOI":"10.1002\/jos.93","volume":"5","author":"A.S. Schulz","year":"2002","unstructured":"Schulz, A.S., Skutella, M.: The power of \u03b1-points in preemptive single machine scheduling. Journal of Scheduling\u00a05, 121\u2013133 (2002)","journal-title":"Journal of Scheduling"},{"key":"15_CR17","doi-asserted-by":"crossref","unstructured":"Seiden, S.: A guessing game and randomized online algorithms. In: Proceedings of the 32nd ACM Symposium on Theory of Computing, pp. 592\u2013601 (2000)","DOI":"10.1145\/335305.335385"},{"key":"15_CR18","unstructured":"Sitters, R.: Complexity and approximation in routing and scheduling. Ph.D. Thesis, Eindhoven University of Technology, Netherlands (2004)"},{"key":"15_CR19","doi-asserted-by":"publisher","first-page":"89","DOI":"10.1016\/S0167-6377(01)00115-8","volume":"30","author":"L. Stougie","year":"2002","unstructured":"Stougie, L., Vestjens, A.P.A.: Randomized algorithms for on-line scheduling problems: how low can\u2019t you go? Operations Research Letters\u00a030, 89\u201396 (2002)","journal-title":"Operations Research Letters"},{"key":"15_CR20","unstructured":"Vestjens, A.P.A.: Online machine scheduling. Ph.D. Thesis, Eindhoven University of Technology, Netherlands (1997)"}],"container-title":["Lecture Notes in Computer Science","Integer Programming and Combinatorial Optimization"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11496915_15.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,2,22]],"date-time":"2025-02-22T22:24:14Z","timestamp":1740263054000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11496915_15"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005]]},"ISBN":["9783540261995","9783540321026"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/11496915_15","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2005]]}}}