{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,28]],"date-time":"2025-11-28T12:11:35Z","timestamp":1764331895771,"version":"3.38.0"},"reference-count":33,"publisher":"Springer Science and Business Media LLC","issue":"3","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Comput Sci Res Dev"],"published-print":{"date-parts":[[2012,8]]},"DOI":"10.1007\/s00450-011-0153-5","type":"journal-article","created":{"date-parts":[[2011,4,5]],"date-time":"2011-04-05T17:41:23Z","timestamp":1302025283000},"page":"181-187","source":"Crossref","is-referenced-by-count":11,"title":["Stochastic online scheduling"],"prefix":"10.1007","volume":"27","author":[{"given":"Tjark","family":"Vredeveld","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2011,4,6]]},"reference":[{"key":"153_CR1","unstructured":"Becchetti L, Marchetti-Spaccamela A, Sch\u00e4fer G, Vredeveld T (2006) On scheduling stochastic jobs to minimize the expected total flow time. Unpublished manuscript"},{"key":"153_CR2","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-540-24804-0","volume-title":"Scheduling algorithms","author":"P Brucker","year":"2004","unstructured":"Brucker P (2004) Scheduling algorithms, 4th edn. Springer, Berlin","edition":"4"},{"key":"153_CR3","doi-asserted-by":"crossref","first-page":"329","DOI":"10.1145\/237502.237577","volume-title":"Proceedings of the 8th annual ACM symposium on parallel algorithms and architectures (SPAA)","author":"S Chakrabarti","year":"1996","unstructured":"Chakrabarti S, Muthukrishnan S (1996) Resource scheduling for parallel database and scientific applications. In: Proceedings of the 8th annual ACM symposium on parallel algorithms and architectures (SPAA), pp 329\u2013335"},{"key":"153_CR4","doi-asserted-by":"crossref","first-page":"344","DOI":"10.1016\/S0021-9800(68)80011-0","volume":"5","author":"D Chazan","year":"1968","unstructured":"Chazan D, Konheim AG, Weiss B (1968) A note on time sharing. J Comb Theory 5:344\u2013369","journal-title":"J Comb Theory"},{"key":"153_CR5","doi-asserted-by":"crossref","first-page":"58","DOI":"10.1109\/MICRO.1996.566450","volume-title":"Proceedings 29th IEEE\/ACM int. symp. on microarchitecture","author":"C Chekuri","year":"1996","unstructured":"Chekuri C, Johnson R, Motwani R, Natarajan B, Rau B, Schlansker M (1996) An analysis of profile-driven instruction level parallel scheduling with application to super blocks. In: Proceedings 29th IEEE\/ACM int. symp. on microarchitecture, Paris, France, pp 58\u201369"},{"key":"153_CR6","doi-asserted-by":"crossref","first-page":"525","DOI":"10.1080\/07408170600941623","volume":"39","author":"G Chen","year":"2007","unstructured":"Chen G, Shen Z-JM (2007) Probabilistic asymptotic analysis of stochastic online scheduling problems. IIE Trans 39:525\u2013538","journal-title":"IIE Trans"},{"issue":"3","key":"153_CR7","doi-asserted-by":"crossref","first-page":"464","DOI":"10.1287\/opre.1060.0270","volume":"54","author":"C-FM Chou","year":"2006","unstructured":"Chou C-FM, Liu H, Queyranne M, Simchi-Levi D (2006) On the asymptotic optimality of a simple on-line algorithm for the stochastic single machine weighted completion time problem and its extensions. Oper Res 54(3):464\u2013474","journal-title":"Oper Res"},{"key":"153_CR8","doi-asserted-by":"crossref","first-page":"109","DOI":"10.1007\/s10107-007-0204-7","volume":"119","author":"J Correa","year":"2009","unstructured":"Correa J, Wagner M (2009) LP-based online scheduling: from single to parallel machines. Math Program 119:109\u2013136","journal-title":"Math Program"},{"key":"153_CR9","unstructured":"Dean BC (2005) Approximation algorithms for stochastic scheduling problems. PhD thesis, Massachusetts Institute of Technology"},{"key":"153_CR10","series-title":"Lecture notes in computer science","doi-asserted-by":"crossref","first-page":"123","DOI":"10.1007\/978-3-540-24592-6_10","volume-title":"Proceedings of the first international workshop on approximation and online algorithms, WAOA 2003","author":"T Erlebach","year":"2004","unstructured":"Erlebach T, K\u00e4\u00e4b V, M\u00f6hring RH (2004) Scheduling AND\/OR-networks on identical parallel machines. In: Jansen K, Solis-Oba R (eds) Proceedings of the first international workshop on approximation and online algorithms, WAOA 2003. Lecture notes in computer science, Budapest, Hungary, vol 2909. Springer, Berlin, pp 123\u2013136"},{"issue":"4","key":"153_CR11","doi-asserted-by":"crossref","first-page":"393","DOI":"10.1023\/A:1009794729459","volume":"1","author":"A Feldmann","year":"1998","unstructured":"Feldmann A, Kao M-Y, Sgall J, Teng S-H (1998) Optimal online scheduling of parallel jobs with dependencies. J Comb Optim 1(4):393\u2013411","journal-title":"J Comb Optim"},{"key":"153_CR12","doi-asserted-by":"crossref","first-page":"148","DOI":"10.1111\/j.2517-6161.1979.tb01068.x","volume":"41","author":"JC Gittins","year":"1979","unstructured":"Gittins JC (1979) Bandit processes and dynamic allocation indices. J R Stat Soc, Ser B 41:148\u2013177","journal-title":"J R Stat Soc, Ser B"},{"key":"153_CR13","volume-title":"Multi-armed bandit allocation indices","author":"JC Gittins","year":"1989","unstructured":"Gittins JC (1989) Multi-armed bandit allocation indices. Wiley, New York"},{"key":"153_CR14","first-page":"591","volume-title":"Proceedings of the 8th ACM-SIAM symposium on discrete algorithms","author":"MX Goemans","year":"1997","unstructured":"Goemans MX (1997) Improved approximation algorithms for scheduling with release dates. In: Proceedings of the 8th ACM-SIAM symposium on discrete algorithms, New Orleans, LA, USA, pp 591\u2013598"},{"key":"153_CR15","doi-asserted-by":"crossref","first-page":"165","DOI":"10.1137\/S089548019936223X","volume":"15","author":"MX Goemans","year":"2002","unstructured":"Goemans MX, Queyranne M, Schulz AS, Skutella M, Wang Y (2002) Single machine scheduling with release dates. SIAM J Discrete Math 15:165\u2013192","journal-title":"SIAM J Discrete Math"},{"key":"153_CR16","first-page":"112","volume":"9","author":"AG Konheim","year":"1968","unstructured":"Konheim AG (1968) A note on time sharing with preferred customers. Probab Theory Relat Fields 9:112\u2013130","journal-title":"Probab Theory Relat Fields"},{"key":"153_CR17","doi-asserted-by":"crossref","DOI":"10.1201\/9780203489802","volume-title":"Handbook of scheduling: algorithms, models, and performance analysis","author":"JY-T Leung","year":"2004","unstructured":"Leung JY-T (2004) Handbook of scheduling: algorithms, models, and performance analysis. Chapman & Hall, London"},{"issue":"5","key":"153_CR18","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, Schulz AS (2004) On-line scheduling to minimize average completion time revisited. Oper Res Lett 32(5):485\u2013490","journal-title":"Oper Res Lett"},{"issue":"3","key":"153_CR19","doi-asserted-by":"crossref","first-page":"513","DOI":"10.1287\/moor.1060.0201","volume":"31","author":"N Megow","year":"2006","unstructured":"Megow N, Uetz M, Vredeveld T (2006) Models and algorithms for stochastic online scheduling. Math Oper Res 31(3):513\u2013525","journal-title":"Math Oper Res"},{"key":"153_CR20","series-title":"Lecture notes in computer science","doi-asserted-by":"crossref","first-page":"516","DOI":"10.1007\/11841036_47","volume-title":"Proceedings of 14th European symposium on algorithms","author":"N Megow","year":"2006","unstructured":"Megow N, Vredeveld T (2006) Approximation in preemptive stochastic online scheduling. In: Azar Y, Erlebach T (eds) Proceedings of 14th European symposium on algorithms. Lecture notes in computer science, Zurich, Switzerland, vol 4168. Springer, Berlin, pp 516\u2013527"},{"key":"153_CR21","unstructured":"Megow N, Vredeveld T (2007) Stochastic online scheduling with precedence constraints. Technical report 029-2007, Technische Universit\u00e4t Berlin"},{"key":"153_CR22","first-page":"193","volume":"28","author":"RH M\u00f6hring","year":"1984","unstructured":"M\u00f6hring RH, Radermacher FJ, Weiss G (1984) Stochastic scheduling problems I: General strategies. Z Oper-Res 28:193\u2013260","journal-title":"Z Oper-Res"},{"key":"153_CR23","doi-asserted-by":"crossref","first-page":"924","DOI":"10.1145\/331524.331530","volume":"46","author":"RH M\u00f6hring","year":"1999","unstructured":"M\u00f6hring RH, Schulz AS, Uetz M (1999) Approximation in stochastic scheduling: the power of LP-based priority policies. J ACM 46:924\u2013942","journal-title":"J ACM"},{"key":"153_CR24","volume-title":"Scheduling: theory, algorithms, and systems","author":"M Pinedo","year":"2002","unstructured":"Pinedo M (2002) Scheduling: theory, algorithms, and systems, 3rd edn. Springer, Berlin","edition":"3"},{"key":"153_CR25","volume-title":"Handbook of scheduling: algorithms, models, and performance analysis, chap. 38","author":"M Pinedo","year":"2004","unstructured":"Pinedo M (2004) Off-line deterministic scheduling, stochastic scheduling, and online deterministic scheduling: a comparative overview. In: Leung JY-T (ed) Handbook of scheduling: algorithms, models, and performance analysis, chap. 38, Chapman & Hall, London"},{"key":"153_CR26","volume-title":"Handbook of scheduling: algorithms, models, and performance analysis, chap. 15","author":"KR Pruhs","year":"2004","unstructured":"Pruhs KR, Sgall J, Torng E (2004) Online scheduling. In: Leung JY-T (ed) Handbook of scheduling: algorithms, models, and performance analysis, chap. 15, Chapman & Hall, London"},{"key":"153_CR27","first-page":"703","volume":"12","author":"MH Rothkopf","year":"1966","unstructured":"Rothkopf MH (1966) Scheduling with random service times. Manag Sci 12:703\u2013713","journal-title":"Manag Sci"},{"key":"153_CR28","series-title":"Lecture notes in computer science","doi-asserted-by":"crossref","first-page":"448","DOI":"10.1007\/978-3-540-85097-7_42","volume-title":"Combinatorial optimization and applications (COCOA)","author":"A Schulz","year":"2008","unstructured":"Schulz A (2008) Stochastic online scheduling revisited. In: Yang B, Du D-Z, Wang C (eds) Combinatorial optimization and applications (COCOA). Lecture notes in computer science, vol 5165, pp 448\u2013457"},{"key":"153_CR29","doi-asserted-by":"crossref","first-page":"65","DOI":"10.1145\/321796.321803","volume":"21","author":"KC Sevcik","year":"1974","unstructured":"Sevcik KC (1974) Scheduling for minimum total loss using service time distributions. J ACM 21:65\u201375","journal-title":"J ACM"},{"key":"153_CR30","doi-asserted-by":"crossref","first-page":"59","DOI":"10.1002\/nav.3800030106","volume":"3","author":"WE Smith","year":"1956","unstructured":"Smith WE (1956) Various optimizers for single-stage production. Nav Res Logist Q 3:59\u201366","journal-title":"Nav Res Logist Q"},{"key":"153_CR31","unstructured":"Sousa J (1989) Time indexed formulations of non-preemptive single-machine scheduling problems. PhD thesis, Universit\u00e9 Catholique de Louvain"},{"key":"153_CR32","volume-title":"Algorithms for deterministic and stochastic scheduling","author":"M Uetz","year":"2002","unstructured":"Uetz M (2002) Algorithms for deterministic and stochastic scheduling. Cuvillier Verlag, G\u00f6ttingen"},{"key":"153_CR33","doi-asserted-by":"crossref","first-page":"827","DOI":"10.2307\/1428135","volume":"27","author":"G Weiss","year":"1995","unstructured":"Weiss G (1995) On almost optimal priority rules for preemptive scheduling of stochastic jobs on parallel machines. Adv Appl Probab 27:827\u2013845","journal-title":"Adv Appl Probab"}],"container-title":["Computer Science - Research and Development"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/www.springerlink.com\/index\/pdf\/10.1007\/s00450-011-0153-5","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,4]],"date-time":"2025-03-04T21:55:31Z","timestamp":1741125331000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00450-011-0153-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,4,6]]},"references-count":33,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2012,8]]}},"alternative-id":["153"],"URL":"https:\/\/doi.org\/10.1007\/s00450-011-0153-5","relation":{},"ISSN":["1865-2034","1865-2042"],"issn-type":[{"type":"print","value":"1865-2034"},{"type":"electronic","value":"1865-2042"}],"subject":[],"published":{"date-parts":[[2011,4,6]]}}}