{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,8,21]],"date-time":"2025-08-21T18:10:32Z","timestamp":1755799832689},"publisher-location":"Berlin, Heidelberg","reference-count":28,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540850960"},{"type":"electronic","value":"9783540850977"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/978-3-540-85097-7_42","type":"book-chapter","created":{"date-parts":[[2008,8,19]],"date-time":"2008-08-19T03:18:26Z","timestamp":1219115906000},"page":"448-457","source":"Crossref","is-referenced-by-count":10,"title":["Stochastic Online Scheduling Revisited"],"prefix":"10.1007","author":[{"given":"Andreas S.","family":"Schulz","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"42_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, pp. 32\u201343 (1999)","DOI":"10.1109\/SFFCS.1999.814574"},{"key":"42_CR2","volume-title":"Online Computation and Competitive Analysis","author":"A. Borodin","year":"1998","unstructured":"Borodin, A., El-Yaniv, R.: Online Computation and Competitive Analysis. Cambridge University Press, Cambridge (1998)"},{"key":"42_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., Shmoys, D., Stein, C., Wein, J.: Improved scheduling algorithms for minsum criteria. In: auf der Heide, F., Monien, B. (eds.) ICALP 1996. LNCS, vol.\u00a01099, pp. 646\u2013657. Springer, Heidelberg (1996)"},{"key":"42_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":"42_CR5","doi-asserted-by":"publisher","first-page":"464","DOI":"10.1287\/opre.1060.0270","volume":"54","author":"M. Chou","year":"2006","unstructured":"Chou, M., Liu, H., Queyranne, M., Simchi-Levi, D.: On the asymptotic optimality of a simple on-line algorithm for the stochastic single-machine weighted completion time problem and its extensions. Operations Research\u00a054, 464\u2013474 (2006)","journal-title":"Operations Research"},{"key":"42_CR6","doi-asserted-by":"publisher","first-page":"137","DOI":"10.1007\/s10107-005-0588-1","volume":"106","author":"M. Chou","year":"2006","unstructured":"Chou, M., Queyranne, M., Simchi-Levi, D.: The asymptotic performance ratio of an on-line algorithm for uniform parallel machine scheduling with release dates. Mathematical Programming\u00a0106, 137\u2013157 (2006)","journal-title":"Mathematical Programming"},{"key":"42_CR7","doi-asserted-by":"crossref","unstructured":"Correa, J., Wagner, M.: LP-based online scheduling: From single to parallel machines. Mathematical Programming (in press, 2008)","DOI":"10.1007\/s10107-007-0204-7"},{"key":"42_CR8","doi-asserted-by":"publisher","first-page":"165","DOI":"10.1137\/S089548019936223X","volume":"15","author":"M. Goemans","year":"2002","unstructured":"Goemans, M., Queyranne, M., Schulz, A., 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":"42_CR9","doi-asserted-by":"publisher","first-page":"513","DOI":"10.1287\/moor.22.3.513","volume":"22","author":"L. Hall","year":"1997","unstructured":"Hall, L., Schulz, A., Shmoys, D., 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":"42_CR10","unstructured":"Hall, W., Wellner, J.: Mean residual life. In: Cs\u00f6rg\u00f6, M., Dawson, D., Rao, J., Saleh, A.E. (eds.) Proceedings of the International Symposium on Statistics and Related Topics, pp. 169\u2013184 (1981)"},{"key":"42_CR11","doi-asserted-by":"publisher","first-page":"430","DOI":"10.2307\/3214267","volume":"24","author":"T. K\u00e4mpke","year":"1987","unstructured":"K\u00e4mpke, T.: On the optimality of static priority policies in stochastic scheduling on parallel machines. Journal of Applied Probability\u00a024, 430\u2013448 (1987)","journal-title":"Journal of Applied Probability"},{"key":"42_CR12","doi-asserted-by":"publisher","first-page":"343","DOI":"10.1016\/S0167-5060(08)70743-X","volume":"1","author":"J. Lenstra","year":"1977","unstructured":"Lenstra, J., Rinnooy Kan, A., Brucker, P.: Complexity of machine scheduling problems. Annals of Discrete Mathematics\u00a01, 343\u2013362 (1977)","journal-title":"Annals of Discrete Mathematics"},{"key":"42_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.: On-line scheduling to minimize average completion time revisited. Operations Research Letters\u00a032, 485\u2013490 (2004)","journal-title":"Operations Research Letters"},{"key":"42_CR14","doi-asserted-by":"publisher","first-page":"513","DOI":"10.1287\/moor.1060.0201","volume":"31","author":"N. Megow","year":"2006","unstructured":"Megow, N., Uetz, M., Vredeveld, T.: Models and algorithms for stochastic online scheduling. Mathematics of Operations Research\u00a031, 513\u2013525 (2006)","journal-title":"Mathematics of Operations Research"},{"key":"42_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"516","DOI":"10.1007\/11841036_47","volume-title":"Algorithms \u2013 ESA 2006","author":"N. Megow","year":"2006","unstructured":"Megow, N., Vredeveld, T.: Approximation results for preemptive stochastic online scheduling. In: Azar, Y., Erlebach, T. (eds.) ESA 2006. LNCS, vol.\u00a04168, pp. 516\u2013527. Springer, Heidelberg (2006)"},{"key":"42_CR16","doi-asserted-by":"publisher","first-page":"193","DOI":"10.1007\/BF01919323","volume":"28","author":"R. M\u00f6hring","year":"1984","unstructured":"M\u00f6hring, R., Radermacher, F., Weiss, G.: Stochastic scheduling problems I: General strategies. Zeitschrift f\u00fcr Operations Research\u00a028, 193\u2013260 (1984)","journal-title":"Zeitschrift f\u00fcr Operations Research"},{"key":"42_CR17","doi-asserted-by":"publisher","first-page":"924","DOI":"10.1145\/331524.331530","volume":"46","author":"R. M\u00f6hring","year":"1999","unstructured":"M\u00f6hring, R., Schulz, A., Uetz, M.: Approximation in stochastic scheduling: The power of LP-based priority policies. Journal of the ACM\u00a046, 924\u2013942 (1999)","journal-title":"Journal of the ACM"},{"key":"42_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"307","DOI":"10.1007\/3-540-59408-6_60","volume-title":"Integer Programming and Combinatorial Optimization","author":"M. Queyranne","year":"1995","unstructured":"Queyranne, M., Schulz, A.: Scheduling unit jobs with compatible release dates on parallel machines with nonstationary speeds. In: Balas, E., Clausen, J. (eds.) IPCO 1995. LNCS, vol.\u00a0920, pp. 307\u2013320. Springer, Heidelberg (1995)"},{"key":"42_CR19","first-page":"703","volume":"12","author":"M. Rothkopf","year":"1966","unstructured":"Rothkopf, M.: Scheduling with random service times. Management Science\u00a012, 703\u2013713 (1966)","journal-title":"Management Science"},{"key":"42_CR20","doi-asserted-by":"publisher","first-page":"121","DOI":"10.1002\/jos.93","volume":"5","author":"A. Schulz","year":"2002","unstructured":"Schulz, A., Skutella, M.: The power of \u03b1-points in preemptive single machine scheduling. Journal of Scheduling\u00a05, 121\u2013133 (2002a)","journal-title":"Journal of Scheduling"},{"key":"42_CR21","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 Journal on Discrete Mathematics\u00a015, 450\u2013469 (2002b)","journal-title":"SIAM Journal on Discrete Mathematics"},{"key":"42_CR22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"196","DOI":"10.1007\/BFb0029570","volume-title":"Online Algorithms: The State of the Art","author":"J. Sgall","year":"1998","unstructured":"Sgall, J.: On-line scheduling. In: Fiat, A., Woeginger, G. (eds.) Online Algorithms: The State of the Art. LNCS, vol.\u00a01442, ch. 9, pp. 196\u2013231. Springer, Heidelberg (1998)"},{"key":"42_CR23","doi-asserted-by":"publisher","first-page":"788","DOI":"10.1137\/S0097539702415007","volume":"34","author":"M. Skutella","year":"2005","unstructured":"Skutella, M., Uetz, M.: Stochastic machine scheduling with precedence constraints. SIAM Journal on Computing\u00a034, 788\u2013802 (2005)","journal-title":"SIAM Journal on Computing"},{"key":"42_CR24","unstructured":"Sousa, J.: Time Indexed Formulations of Non-Preemptive Single-Machine Scheduling Problems. Ph.D. thesis, Universit\u00e9 Catholique de Louvain, Belgium (1989)"},{"key":"42_CR25","series-title":"CBMS-NSF Regional Conference Series in Applied Mathematics","volume-title":"Ten Lectures on the Probabilistic Method","author":"J. Spencer","year":"1987","unstructured":"Spencer, J.: Ten Lectures on the Probabilistic Method. CBMS-NSF Regional Conference Series in Applied Mathematics, vol.\u00a052. SIAM, Philadelphia (1987)"},{"key":"42_CR26","doi-asserted-by":"publisher","first-page":"841","DOI":"10.2307\/3214023","volume":"23","author":"R. Weber","year":"1986","unstructured":"Weber, R., Varaiya, P., Walrand, J.: Scheduling jobs with stochastically ordered processing times on parallel machines to minimize expected flowtime. Journal of Applied Probability\u00a023, 841\u2013847 (1986)","journal-title":"Journal of Applied Probability"},{"key":"42_CR27","doi-asserted-by":"publisher","first-page":"195","DOI":"10.1007\/BF02248591","volume":"26","author":"G. Weiss","year":"1990","unstructured":"Weiss, G.: Approximation results in parallel machines stochastic scheduling. Annals of Operations Research\u00a026, 195\u2013242 (1990)","journal-title":"Annals of Operations Research"},{"key":"42_CR28","doi-asserted-by":"publisher","first-page":"187","DOI":"10.2307\/3212936","volume":"17","author":"G. Weiss","year":"1980","unstructured":"Weiss, G., Pinedo, M.: Scheduling tasks with exponential service times on nonidentical processors to minimize various cost functions. Journal of Applied Probability\u00a017, 187\u2013202 (1980)","journal-title":"Journal of Applied Probability"}],"container-title":["Lecture Notes in Computer Science","Combinatorial Optimization and Applications"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-85097-7_42.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,23]],"date-time":"2020-11-23T21:21:56Z","timestamp":1606166516000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-85097-7_42"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540850960","9783540850977"],"references-count":28,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-85097-7_42","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[]}}