{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,11,11]],"date-time":"2026-11-11T06:31:25Z","timestamp":1794378685486,"version":"4.9.0"},"publisher-location":"Berlin, Heidelberg","reference-count":20,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540245742","type":"print"},{"value":"9783540318330","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2005]]},"DOI":"10.1007\/11389811_15","type":"book-chapter","created":{"date-parts":[[2010,7,2]],"date-time":"2010-07-02T14:11:05Z","timestamp":1278079865000},"page":"167-180","source":"Crossref","is-referenced-by-count":5,"title":["Stochastic Online Scheduling on Parallel Machines"],"prefix":"10.1007","author":[{"given":"Nicole","family":"Megow","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Marc","family":"Uetz","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Tjark","family":"Vredeveld","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","reference":[{"key":"15_CR1","first-page":"100","volume":"28","author":"J.L. Bruno","year":"1981","unstructured":"Bruno, J.L., Downey, P.J., Frederickson, G.N.: Sequencing tasks with exponential service times to minimize the expected flowtime or makespan. J.\u00a0ACM\u00a028, 100\u2013113 (1981)","journal-title":"J.\u00a0ACM"},{"key":"15_CR2","doi-asserted-by":"crossref","unstructured":"Chakrabarti, S., Muthukrishnan, S.: Resource scheduling for parallel database and scientific applications. In: Proc. 8th Ann. ACM Symp. on Parallel Algorithms and Architectures, Padua, Italy, pp. 329\u2013335 (1996)","DOI":"10.1145\/237502.237577"},{"key":"15_CR3","doi-asserted-by":"crossref","unstructured":"Chekuri, C., Johnson, R., Motwani, R., Natarajan, B., Rau, B., Schlansker, M.: An analysis of profile-driven instruction level parallel scheduling with application to super blocks. In: Proc. 29th IEEE\/ACM Int. Symp. on Microarchitecture, Paris, France, pp. 58\u201369 (1996)","DOI":"10.1109\/MICRO.1996.566450"},{"key":"15_CR4","volume-title":"Deterministic and Stochastic Scheduling","year":"1982","unstructured":"Dempster, M.A.H., Lenstra, J.K., Rinnooy Kan, A.H.G. (eds.): Deterministic and Stochastic Scheduling. D.\u00a0Reidel Publishing Company, Dordrecht (1982)"},{"key":"15_CR5","doi-asserted-by":"publisher","first-page":"268","DOI":"10.1287\/mnsc.11.2.268","volume":"11","author":"W. Eastman","year":"1964","unstructured":"Eastman, W., Even, S., Isaacs, I.: Bounds for the optimal scheduling of n jobs on m processors. Mgmt.\u00a0Sci.\u00a011, 268\u2013279 (1964)","journal-title":"Mgmt.\u00a0Sci."},{"key":"15_CR6","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. Ann.\u00a0Discr.\u00a0Math.\u00a05, 287\u2013326 (1979)","journal-title":"Ann.\u00a0Discr.\u00a0Math."},{"key":"15_CR7","first-page":"169","volume-title":"Proc. Int. Symp. on Statistics and Related Topics","author":"W.J. Hall","year":"1981","unstructured":"Hall, W.J., Wellner, J.A.: Mean residual life. In: Cs\u00f6rg\u00f6, M., Dawson, D.A., Rao, J.N.K., Saleh, A.K.M.E. (eds.) Proc. Int. Symp. on Statistics and Related Topics, Ottawa, ON, pp. 169\u2013184. North-Holland, Amsterdam (1981)"},{"key":"15_CR8","doi-asserted-by":"publisher","first-page":"300","DOI":"10.1137\/S0097539796299540","volume":"30","author":"E. Koutsoupias","year":"2000","unstructured":"Koutsoupias, E., Papadimitriou, C.H.: Beyond competitive analysis. SIAM J.\u00a0Comp.\u00a030, 300\u2013317 (2000)","journal-title":"SIAM J.\u00a0Comp."},{"issue":"5","key":"15_CR9","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. Oper.\u00a0Res.\u00a0Lett.\u00a032(5), 485\u2013490 (2004)","journal-title":"Oper.\u00a0Res.\u00a0Lett."},{"key":"15_CR10","first-page":"193","volume":"28","author":"R.H. M\u00f6hring","year":"1984","unstructured":"M\u00f6hring, R.H., Radermacher, F.J., Weiss, G.: Stochastic scheduling problems I: General strategies. ZOR - Zeitschrift f\u00fcr Oper.\u00a0Res.\u00a028, 193\u2013260 (1984)","journal-title":"ZOR - Zeitschrift f\u00fcr Oper.\u00a0Res."},{"key":"15_CR11","first-page":"924","volume":"46","author":"R.H. M\u00f6hring","year":"1999","unstructured":"M\u00f6hring, R.H., Schulz, A.S., Uetz, M.: Approximation in stochastic scheduling: the power of LP-based priority policies. J.\u00a0ACM\u00a046, 924\u2013942 (1999)","journal-title":"J.\u00a0ACM"},{"key":"15_CR12","first-page":"703","volume":"12","author":"M.H. Rothkopf","year":"1966","unstructured":"Rothkopf, M.H.: Scheduling with random service times. Mgmt. Sci.\u00a012, 703\u2013713 (1966)","journal-title":"Mgmt. Sci."},{"key":"15_CR13","doi-asserted-by":"crossref","unstructured":"Scharbrodt, M., Schickinger, T., Steger, A.: A new average case analysis for completion time scheduling. In: Proc. 34th Ann. ACM Symp. on the Theory of Computing, Montr\u00e9al, QB, pp. 170\u2013178 (2002)","DOI":"10.1145\/509907.509936"},{"key":"15_CR14","unstructured":"Skutella, M., Uetz, M.: Scheduling precedence-constrained jobs with stochastic processing times on parallel machines. In: Proc. 12th Ann. ACM-SIAM Symp. on Discrete Algorithms, Washington, DC, pp. 589\u2013590 (2001)"},{"key":"15_CR15","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1002\/nav.3800030106","volume":"3","author":"W. Smith","year":"1956","unstructured":"Smith, W.: Various optimizers for single-stage production. Naval Res.\u00a0Log.\u00a03, 59\u201366 (1956)","journal-title":"Naval Res.\u00a0Log."},{"key":"15_CR16","doi-asserted-by":"crossref","unstructured":"Souza-Offermatt, A., Steger, A.: The expected competitive ratio for weighted completion time scheduling. In: Proc. 21st Symp. on Theoretical Aspects of Computer Science, Montpellier, France (2004) (to appear)","DOI":"10.1007\/978-3-540-24749-4_54"},{"key":"15_CR17","unstructured":"Uetz, M.: Algorithms for Deterministic and Stochastic Scheduling. PhD thesis, Cuvillier Verlag, G\u00f6ttingen, Germany (2002)"},{"key":"15_CR18","first-page":"195","volume":"26","author":"G. Weiss","year":"1990","unstructured":"Weiss, G.: Approximation results in parallel machines stochastic scheduling. Ann.\u00a0Oper.\u00a0Res.\u00a026, 195\u2013242 (1990)","journal-title":"Ann.\u00a0Oper.\u00a0Res."},{"key":"15_CR19","first-page":"255","volume":"17","author":"G. Weiss","year":"1992","unstructured":"Weiss, G.: Turnpike optimality of Smith\u2019s rule in parallel machines stochastic scheduling. Math.\u00a0Oper.\u00a0Res.\u00a017, 255\u2013270 (1992)","journal-title":"Math.\u00a0Oper.\u00a0Res."},{"key":"15_CR20","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 non-identical processors to minimize various cost functions. J.\u00a0Appl.\u00a0Prob.\u00a017, 187\u2013202 (1980)","journal-title":"J.\u00a0Appl.\u00a0Prob."}],"container-title":["Lecture Notes in Computer Science","Approximation and Online Algorithms"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11389811_15.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T14:50:45Z","timestamp":1605624645000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11389811_15"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005]]},"ISBN":["9783540245742","9783540318330"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/11389811_15","relation":{"is-part-of":[{"id-type":"doi","id":"https:\/\/doi.org\/10.1007\/b106130","asserted-by":"object"}]},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2005]]}}}