{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,12]],"date-time":"2026-09-12T19:11:19Z","timestamp":1789240279883,"version":"build-2803163510"},"reference-count":28,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2008,1,4]],"date-time":"2008-01-04T00:00:00Z","timestamp":1199404800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Math. Program."],"published-print":{"date-parts":[[2009,6]]},"DOI":"10.1007\/s10107-007-0204-7","type":"journal-article","created":{"date-parts":[[2008,1,3]],"date-time":"2008-01-03T15:21:53Z","timestamp":1199373713000},"page":"109-136","source":"Crossref","is-referenced-by-count":37,"title":["LP-based online scheduling: from single to parallel machines"],"prefix":"10.1007","volume":"119","author":[{"given":"Jos\u00e9 R.","family":"Correa","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Michael R.","family":"Wagner","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2008,1,4]]},"reference":[{"key":"204_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":"204_CR2","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1145\/944618.944621","volume":"7","author":"S. Albers","year":"2002","unstructured":"Albers S. and Schr\u00f6der B. (2002). An experimental study of online scheduling algorithms. J. Exp. Algorithmics 7: 3","journal-title":"J. Exp. Algorithmics"},{"key":"204_CR3","doi-asserted-by":"crossref","first-page":"686","DOI":"10.1287\/moor.1040.0092","volume":"29","author":"E.J. Anderson","year":"2004","unstructured":"Anderson E.J. and Potts C.N. (2004). On-line scheduling of a single machine to minimize total weighted completion time. Math. Oper. Res. 29: 686\u2013697","journal-title":"Math. Oper. Res."},{"key":"204_CR4","first-page":"646","volume-title":"Improved scheduling algorithms for minsum criteria,\u201d in Automata, Languages and Programming (ICALP), LNCS, vol. 1099","author":"S. Chakrabarti","year":"1996","unstructured":"Chakrabarti S., Phillips C., Schulz A.S., Shmoys D.B., Stein C. and Wein J. (1996). Improved scheduling algorithms for minsum criteria,\u201d in Automata, Languages and Programming (ICALP), LNCS, vol. 1099. Springer, Heidelberg, pp 646\u2013657"},{"key":"204_CR5","doi-asserted-by":"crossref","first-page":"146","DOI":"10.1137\/S0097539797327180","volume":"31","author":"C. Chekuri","year":"2001","unstructured":"Chekuri C., Motwani R., Natarajan B. and Stein C. (2001). Approximation techniques for average completion time scheduling. SIAM J. Comput. 31: 146\u2013166","journal-title":"SIAM J. Comput."},{"key":"204_CR6","doi-asserted-by":"crossref","first-page":"137","DOI":"10.1007\/s10107-005-0588-1","volume":"106","author":"M.C. Chou","year":"2006","unstructured":"Chou M.C., Queyranne M. and Simchi-Levi D. (2006). The asymptotic performance ratio of an on-line algorithm for uniform parallel machine scheduling with release dates. Math. Program. 106: 137\u2013157","journal-title":"Math. Program."},{"key":"204_CR7","unstructured":"Sousa, J.P.: Time Indexed Formulations of Non-Preemptive Single-Machine Scheduling Problems. PhD thesis, Universit\u00e9 Catholique de Louvain (1989)"},{"key":"204_CR8","doi-asserted-by":"crossref","first-page":"268","DOI":"10.1287\/mnsc.11.2.268","volume":"11","author":"W.L. Eastman","year":"1964","unstructured":"Eastman W.L., Even S. and Isaacs I.M. (1964). Bounds for the optimal scheduling of n jobs on m processors. Manage. Sci. 11: 268\u2013279","journal-title":"Manage. Sci."},{"key":"204_CR9","doi-asserted-by":"crossref","unstructured":"Goemans, M.X.: A supermodular relaxation for scheduling with release dates. In: Proceedings of the 5th Integer Programming and Combinatorial Optimization Conference (IPCO), LNCS, vol. 1084, pp. 288\u2013300. Springer, Heidelberg (1996)","DOI":"10.1007\/3-540-61310-2_22"},{"key":"204_CR10","unstructured":"Goemans, M.X.: Improved approximation algorithms for scheduling with release dates. In: Proceedings of the 8th Annual ACM\u2013SIAM Symposium on Discrete Algorithms (SODA), New Orleans, LA, 1997. ACM, New York, 1997, pp. 591\u2013598 (1997)"},{"key":"204_CR11","doi-asserted-by":"crossref","first-page":"165","DOI":"10.1137\/S089548019936223X","volume":"15","author":"M. Goemans","year":"2002","unstructured":"Goemans M., Queyranne M., Schulz A.S., Skutella M. and Wang Y. (2002). Single machine scheduling with release dates. SIAM J. Discrete Math. 15: 165\u2013192","journal-title":"SIAM J. Discrete Math."},{"key":"204_CR12","doi-asserted-by":"crossref","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. and Rinnooy Kan A.H.G. (1979). Optimization and approximation in deterministic sequencing and scheduling: a survey. Ann. Discrete Math. 5: 287\u2013326","journal-title":"Ann. Discrete Math."},{"key":"204_CR13","doi-asserted-by":"crossref","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. and Wein J. (1997). Scheduling to minimize average completion time: off-line and on-line approximation algorithms. Math. Oper. Res. 22: 513\u2013544","journal-title":"Math. Oper. Res."},{"key":"204_CR14","doi-asserted-by":"crossref","unstructured":"Hall, L.A., Shmoys, D.B., Wein, J.: Scheduling to minimize average completion time: off-line and on-line approximation algorithms. In: Proceedings of the 7th Annual ACM\u2013SIAM Symposium on Discrete Algorithms, pp. 142\u2013151 (1997)","DOI":"10.1287\/moor.22.3.513"},{"key":"204_CR15","doi-asserted-by":"crossref","unstructured":"Hoogeveen, J.A., Vestjens, A.P.A.: Optimal on-line algorithms for single-machine scheduling. In: Proceedings of the 5th Integer Programming and Combinatorial Optimization Conference (IPCO), LNCS, vol. 1084, pp. 404\u2013414. Springer, Heidelberg (1996)","DOI":"10.1007\/3-540-61310-2_30"},{"key":"204_CR16","doi-asserted-by":"crossref","unstructured":"Kov\u00e1cs, A., Beck, J.C.: A global constraint for total weighted completion time. In: Proceedings of the 4th International Conference on Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems (LNCS 4510), Brussels, pp. 112\u2013126. Springer, Heidelberg (2007)","DOI":"10.1007\/978-3-540-72397-4_9"},{"key":"204_CR17","doi-asserted-by":"crossref","first-page":"485","DOI":"10.1016\/j.orl.2003.11.008","volume":"32","author":"N. Megow","year":"2004","unstructured":"Megow N. and Schulz A.S. (2004). On-line scheduling to minimize average completion time revisited. Oper. Res. Lett 32: 485\u2013490","journal-title":"Oper. Res. Lett"},{"key":"204_CR18","first-page":"199","volume":"82","author":"C. Phillips","year":"1998","unstructured":"Phillips C., Stein C. and Wein J. (1998). Minimizing average completion time in the presence of release dates. Math. Program. 82: 199\u2013223","journal-title":"Math. Program."},{"key":"204_CR19","doi-asserted-by":"crossref","first-page":"123","DOI":"10.1287\/ijoc.1030.0055","volume":"17","author":"M.W.P. Savelsbergh","year":"2005","unstructured":"Savelsbergh M.W.P., Uma R.N. and Wein J. (2005). An experimental study of LP-based approximation algorithms for scheduling problems. INFORMS J. Comput. 17: 123\u2013136","journal-title":"INFORMS J. Comput."},{"key":"204_CR20","volume-title":"Algorithms for Optimization with Incomplete Information, Dagstuhl Seminar Proceedings 05031","author":"A.S. Schulz","year":"2005","unstructured":"Schulz A.S. (2005). New old algorithms for stochastic scheduling. In: Albers, S., M\u00f6hring, R.H., Pflug, G.C. and Schultz, R. (eds) Algorithms for Optimization with Incomplete Information, Dagstuhl Seminar Proceedings 05031, Schloss Dagstuhl, Germany"},{"key":"204_CR21","doi-asserted-by":"crossref","first-page":"450","DOI":"10.1137\/S0895480199357078","volume":"15","author":"A.S. Schulz","year":"2002","unstructured":"Schulz A.S. and Skutella M. (2002). Scheduling unrelated machines by randomized rounding. SIAM J. Discrete Math. 15: 450\u2013469","journal-title":"SIAM J. Discrete Math."},{"key":"204_CR22","doi-asserted-by":"crossref","first-page":"121","DOI":"10.1002\/jos.93","volume":"5","author":"A.S. Schulz","year":"2002","unstructured":"Schulz A.S. and Skutella M. (2002). The power of \u03b1-points in preemptive single machine scheduling. J. Sched. 5: 121\u2013133","journal-title":"J. Sched."},{"key":"204_CR23","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":"204_CR24","unstructured":"Sitters, R.: Complexity and approximation in routing and scheduling. PhD Thesis, Eindhoven University of Technology, The Netherlands (2004)"},{"key":"204_CR25","doi-asserted-by":"crossref","unstructured":"Skutella, M.: List scheduling in order of \u03b1-points on a single machine. Lecture Notes in Computer Science, vol. 3484, pp. 250\u2013291 (2006)","DOI":"10.1007\/11671541_9"},{"key":"204_CR26","doi-asserted-by":"crossref","first-page":"59","DOI":"10.1002\/nav.3800030106","volume":"3","author":"W.E. Smith","year":"1956","unstructured":"Smith W.E. (1956). Various optimizers for single-stage production. Nav. Res. Logist. Q. 3: 59\u201366","journal-title":"Nav. Res. Logist. Q."},{"key":"204_CR27","doi-asserted-by":"crossref","first-page":"89","DOI":"10.1016\/S0167-6377(01)00115-8","volume":"30","author":"L. Stougie","year":"2002","unstructured":"Stougie L. and Vestjens A.P.A. (2002). Randomized algorithms for on-line scheduling problems: how low can\u2019t you go?. Oper. Res. Lett. 30: 89\u201396","journal-title":"Oper. Res. Lett."},{"key":"204_CR28","unstructured":"Vestjens, A.P.A.: Online machine scheduling. PhD Thesis, Eindhoven University of Technology, The Netherlands (1997)"}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-007-0204-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10107-007-0204-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-007-0204-7","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,29]],"date-time":"2019-05-29T09:50:05Z","timestamp":1559123405000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10107-007-0204-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,1,4]]},"references-count":28,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2009,6]]}},"alternative-id":["204"],"URL":"https:\/\/doi.org\/10.1007\/s10107-007-0204-7","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"value":"0025-5610","type":"print"},{"value":"1436-4646","type":"electronic"}],"subject":[],"published":{"date-parts":[[2008,1,4]]}}}