{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,31]],"date-time":"2025-10-31T07:06:33Z","timestamp":1761894393470,"version":"3.32.0"},"publisher-location":"Berlin, Heidelberg","reference-count":30,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540388753"},{"type":"electronic","value":"9783540388760"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2006]]},"DOI":"10.1007\/11841036_47","type":"book-chapter","created":{"date-parts":[[2006,9,11]],"date-time":"2006-09-11T13:20:54Z","timestamp":1157980854000},"page":"516-527","source":"Crossref","is-referenced-by-count":19,"title":["Approximation in Preemptive Stochastic Online Scheduling"],"prefix":"10.1007","author":[{"given":"Nicole","family":"Megow","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Tjark","family":"Vredeveld","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"47_CR1","doi-asserted-by":"publisher","first-page":"100","DOI":"10.1145\/322234.322242","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. Journal of the ACM\u00a028, 100\u2013113 (1981)","journal-title":"Journal of the ACM"},{"key":"47_CR2","doi-asserted-by":"publisher","first-page":"344","DOI":"10.1016\/S0021-9800(68)80011-0","volume":"5","author":"D. Chazan","year":"1968","unstructured":"Chazan, D., Konheim, A.G., Weiss, B.: A note on time sharing. Journal of Combinatorial Theory\u00a05, 344\u2013369 (1968)","journal-title":"Journal of Combinatorial Theory"},{"key":"47_CR3","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":"47_CR4","doi-asserted-by":"crossref","unstructured":"Chou, M.C., 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 (to appear, 2006)","DOI":"10.1287\/opre.1060.0270"},{"key":"47_CR5","doi-asserted-by":"publisher","first-page":"89","DOI":"10.1017\/S0269964800000991","volume":"3","author":"E.G. Coffman","year":"1989","unstructured":"Coffman, E.G., Hofri, M., Weiss, G.: Scheduling stochastic jobs with a two point distribution on two parallel machines. Probability in the Engineering and Informational Sciences\u00a03, 89\u2013116 (1989)","journal-title":"Probability in the Engineering and Informational Sciences"},{"key":"47_CR6","doi-asserted-by":"crossref","first-page":"148","DOI":"10.1111\/j.2517-6161.1979.tb01068.x","volume":"41","author":"J.C. Gittins","year":"1979","unstructured":"Gittins, J.C.: Bandit processes and dynamic allocation indices. Journal of the Royal Statistical Society, Series B\u00a041, 148\u2013177 (1979)","journal-title":"Journal of the Royal Statistical Society, Series B"},{"key":"47_CR7","volume-title":"Multi-armed Bandit Allocation Indices","author":"J.C. Gittins","year":"1989","unstructured":"Gittins, J.C.: Multi-armed Bandit Allocation Indices. Wiley, New York (1989)"},{"key":"47_CR8","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"},{"issue":"1","key":"47_CR9","doi-asserted-by":"publisher","first-page":"126","DOI":"10.1287\/opre.37.1.126","volume":"37","author":"T. K\u00e4mpke","year":"1989","unstructured":"K\u00e4mpke, T.: Optimal scheduling of jobs with exponential service times on identical parallel processors. Operations Research\u00a037(1), 126\u2013133 (1989)","journal-title":"Operations Research"},{"key":"47_CR10","doi-asserted-by":"publisher","first-page":"70","DOI":"10.1007\/BF01762111","volume":"3","author":"A. Karlin","year":"1988","unstructured":"Karlin, A., Manasse, M., Rudolph, L., Sleator, D.: Competitive snoopy paging. Algorithmica\u00a03, 70\u2013119 (1988)","journal-title":"Algorithmica"},{"key":"47_CR11","first-page":"112","volume":"9","author":"A.G. Konheim","year":"1968","unstructured":"Konheim, A.G.: A note on time sharing with preferred customers. Probability Theory and Related Fields\u00a09, 112\u2013130 (1968)","journal-title":"Probability Theory and Related Fields"},{"key":"47_CR12","doi-asserted-by":"crossref","first-page":"245","DOI":"10.1016\/B978-0-12-566780-7.50020-9","volume-title":"Progress in Combinatorial Optimization","author":"J. Labetoulle","year":"1984","unstructured":"Labetoulle, J., Lawler, E.L., Lenstra, J.K., Rinooy Kan, A.H.G.: Preemptive scheduling of uniform machines subject to release dates. In: Pulleyblank, W.R. (ed.) Progress in Combinatorial Optimization, pp. 245\u2013261. Academic Press, New York (1984)"},{"key":"47_CR13","doi-asserted-by":"publisher","first-page":"243","DOI":"10.1016\/S0167-5060(08)70743-X","volume":"1","author":"J.K. Lenstra","year":"1977","unstructured":"Lenstra, J.K., Rinooy Kan, A.H.G., Brucker, P.: Complexity of machine scheduling problems. Annals of Discrete Mathematics\u00a01, 243\u2013362 (1977)","journal-title":"Annals of Discrete Mathematics"},{"key":"47_CR14","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":"47_CR15","doi-asserted-by":"crossref","unstructured":"Megow, N., Uetz, M., Vredeveld, T.: Models and algorithms for stochastic online scheduling. Mathematics of Operations Research (to appear, 2006)","DOI":"10.1287\/moor.1060.0201"},{"key":"47_CR16","doi-asserted-by":"crossref","unstructured":"Megow, N., Vredeveld, T.: Approximation results for preemptive stochastic online scheduling. Technical Report 8\/2006, Technische Universit\u00e4t Berlin (April 2006)","DOI":"10.1007\/11841036_47"},{"key":"47_CR17","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 Operations Research\u00a028, 193\u2013260 (1984)","journal-title":"ZOR - Zeitschrift f\u00fcr Operations Research"},{"key":"47_CR18","doi-asserted-by":"publisher","first-page":"924","DOI":"10.1145\/331524.331530","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. Journal of the ACM\u00a046, 924\u2013942 (1999)","journal-title":"Journal of the ACM"},{"key":"47_CR19","doi-asserted-by":"publisher","first-page":"559","DOI":"10.1287\/opre.31.3.559","volume":"31","author":"M. Pinedo","year":"1983","unstructured":"Pinedo, M.: Stochastic scheduling with release dates and due dates. Operations Research\u00a031, 559\u2013572 (1983)","journal-title":"Operations Research"},{"key":"47_CR20","volume-title":"Handbook of Scheduling: Algorithms, Models, and Performance Analysis","author":"M. Pinedo","year":"2004","unstructured":"Pinedo, M.: Off-line deterministic scheduling, stochastic scheduling, and online deterministic scheduling: A comparative overview. In: Leung, J. (ed.) Handbook of Scheduling: Algorithms, Models, and Performance Analysis, vol.\u00a038. CRC Press, Boca Raton (2004)"},{"key":"47_CR21","unstructured":"Schulz, A.S.: New old algorithms for stochastic scheduling. In: Albers, S., M\u00f6hring, R.H., Pflug, G.C., Schultz, R. (eds.) Algorithms for Optimization with Incomplete Information, Dagstuhl Seminar Proceedings, vol.\u00a005031 (2005)"},{"key":"47_CR22","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":"47_CR23","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":"47_CR24","doi-asserted-by":"publisher","first-page":"65","DOI":"10.1145\/321796.321803","volume":"21","author":"K.C. Sevcik","year":"1974","unstructured":"Sevcik, K.C.: Scheduling for minimum total loss using service time distributions. Journal of the ACM\u00a021, 65\u201375 (1974)","journal-title":"Journal of the ACM"},{"key":"47_CR25","unstructured":"Sitters, R.A.: Complexity and Approximation in Routing and Scheduling. PhD thesis, Technische Universiteit Eindhoven (2004)"},{"key":"47_CR26","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":"47_CR27","doi-asserted-by":"publisher","first-page":"202","DOI":"10.1145\/2786.2793","volume":"28","author":"D. Sleator","year":"1985","unstructured":"Sleator, D., Tarjan, R.: Amortized efficiency of list update and paging rules. Communications of the ACM\u00a028, 202\u2013208 (1985)","journal-title":"Communications of the ACM"},{"key":"47_CR28","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 Research Logistics Quarterly\u00a03, 59\u201366 (1956)","journal-title":"Naval Research Logistics Quarterly"},{"key":"47_CR29","doi-asserted-by":"publisher","first-page":"167","DOI":"10.2307\/3213926","volume":"19","author":"R.R. Weber","year":"1982","unstructured":"Weber, R.R.: Scheduling jobs with stochastic processing requirements on parallel machines to minimize makespan or flow time. Journal of Applied Probability\u00a019, 167\u2013182 (1982)","journal-title":"Journal of Applied Probability"},{"key":"47_CR30","doi-asserted-by":"publisher","first-page":"827","DOI":"10.2307\/1428135","volume":"27","author":"G. Weiss","year":"1995","unstructured":"Weiss, G.: On almost optimal priority rules for preemptive scheduling of stochastic jobs on parallel machines. Advances in Applied Probability\u00a027, 827\u2013845 (1995)","journal-title":"Advances in Applied Probability"}],"container-title":["Lecture Notes in Computer Science","Algorithms \u2013 ESA 2006"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11841036_47.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,10]],"date-time":"2025-01-10T20:33:01Z","timestamp":1736541181000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11841036_47"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006]]},"ISBN":["9783540388753","9783540388760"],"references-count":30,"URL":"https:\/\/doi.org\/10.1007\/11841036_47","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2006]]}}}