{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T19:29:35Z","timestamp":1725564575186},"publisher-location":"Berlin, Heidelberg","reference-count":27,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540212362"},{"type":"electronic","value":"9783540247494"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2004]]},"DOI":"10.1007\/978-3-540-24749-4_54","type":"book-chapter","created":{"date-parts":[[2010,9,8]],"date-time":"2010-09-08T15:01:54Z","timestamp":1283958114000},"page":"620-631","source":"Crossref","is-referenced-by-count":7,"title":["The Expected Competitive Ratio for Weighted Completion Time Scheduling"],"prefix":"10.1007","author":[{"given":"Alexander","family":"Souza","sequence":"first","affiliation":[]},{"given":"Angelika","family":"Steger","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"54_CR1","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)"},{"issue":"1","key":"54_CR2","doi-asserted-by":"publisher","first-page":"100","DOI":"10.1145\/322234.322242","volume":"28","author":"J. Bruno","year":"1981","unstructured":"Bruno, J., Downey, P., Frederickson, G.N.: Sequencing Tasks with Exponential Service Times to Minimize the Expected Flow Time or Makespan. Journal of the ACM\u00a028(1), 100\u2013113 (1981)","journal-title":"Journal of the ACM"},{"key":"54_CR3","doi-asserted-by":"publisher","first-page":"382","DOI":"10.1145\/361011.361064","volume":"17","author":"E.C. Bruno Jr.","year":"1974","unstructured":"Bruno Jr., E.C., Sethi, R.: Scheduling independent tasks to reduce mean finishing time. Communications of the ACM\u00a017, 382\u2013387 (1974)","journal-title":"Communications of the ACM"},{"issue":"3","key":"54_CR4","doi-asserted-by":"publisher","first-page":"548","DOI":"10.1287\/opre.33.3.548","volume":"33","author":"E.G. Coffman Jr.","year":"1985","unstructured":"Coffman Jr., E.G., Gilbert, E.N.: On the Expected Relative Performance of List Scheduling. Operations Research\u00a033(3), 548\u2013561 (1985)","journal-title":"Operations Research"},{"key":"54_CR5","volume-title":"Theory of Scheduling","author":"R.W. Conway","year":"1967","unstructured":"Conway, R.W., Maxwell, W.L., Miller, L.W.: Theory of Scheduling. Addison\u2013Wesley Publishing Company, Reading (1967)"},{"key":"54_CR6","volume-title":"Statistical Reliability Theory","author":"I.R. Gertsbakh","year":"1989","unstructured":"Gertsbakh, I.R.: Statistical Reliability Theory. Marcel Dekker, Inc., New York (1989)"},{"key":"54_CR7","volume-title":"Computers and Intractability \u2013 A Guide to the Theory of NP-Completeness","author":"M.R. Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability \u2013 A Guide to the Theory of NP-Completeness. Freeman, San Francisco (1979)"},{"key":"54_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 theory: a survey. Annals of Discrete Mathematics\u00a05, 287\u2013326 (1979)","journal-title":"Annals of Discrete Mathematics"},{"key":"54_CR9","doi-asserted-by":"publisher","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., 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":"54_CR10","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"},{"issue":"4","key":"54_CR11","doi-asserted-by":"publisher","first-page":"1119","DOI":"10.1137\/0215081","volume":"15","author":"T. Kawaguchi","year":"1986","unstructured":"Kawaguchi, T., Kyan, S.: Worst Case Bound of an LRF Schedule for the Mean Weighted Flow-Time Problem. SIAM Journal on Computing\u00a015(4), 1119\u20131129 (1986)","journal-title":"SIAM Journal on Computing"},{"key":"54_CR12","doi-asserted-by":"crossref","unstructured":"Koutsoupias, E., Papadimitriou, C.: Beyond Competitive Analysis. In: Proceedings of the 35th Annual Symposium on Foundations of Computer Science (FOCS 1994), pp. 394\u2013400 (1994)","DOI":"10.1109\/SFCS.1994.365677"},{"key":"54_CR13","doi-asserted-by":"publisher","first-page":"924","DOI":"10.1145\/331524.331530","volume":"46","author":"R.H. M\u00f6ring","year":"1999","unstructured":"M\u00f6ring, R.H., Schulz, A.S., Uetz, M.: Approximation in Stochastic Scheduling: The Power of LP-based Priority Rules. Journal of the ACM\u00a046, 924\u2013942 (1999)","journal-title":"Journal of the ACM"},{"key":"54_CR14","volume-title":"Scheduling \u2013 Theory, Algorithms, and Systems","author":"M. Pinedo","year":"1995","unstructured":"Pinedo, M.: Scheduling \u2013 Theory, Algorithms, and Systems. Prentice-Hall, Englewood Cliffs (1995)"},{"key":"54_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"86","DOI":"10.1007\/3-540-60220-8_53","volume-title":"Algorithms and Data Structures","author":"C. Phillips","year":"1995","unstructured":"Phillips, C., Stein, C., Wein, J.: Scheduling Jobs That Arrive Over Time. In: Sack, J.-R., Akl, S.G., Dehne, F., Santoro, N. (eds.) WADS 1995. LNCS, vol.\u00a0955, pp. 86\u201397. Springer, Heidelberg (1995)"},{"key":"54_CR16","first-page":"199","volume":"82","author":"C.A. Phillips","year":"1998","unstructured":"Phillips, C.A., Stein, C., Wein, J.: Minimizing average completion time in the presence of release dates. Mathematical Programming\u00a082, 199\u2013223 (1998)","journal-title":"Mathematical Programming"},{"issue":"4","key":"54_CR17","doi-asserted-by":"publisher","first-page":"867","DOI":"10.1137\/0144062","volume":"44","author":"M. Pinedo","year":"1984","unstructured":"Pinedo, M., Weber, R.: Inequalities and bounds in stochastic shop scheduling. SIAM Journal on Applied Mathematics\u00a044(4), 867\u2013879 (1984)","journal-title":"SIAM Journal on Applied Mathematics"},{"key":"54_CR18","doi-asserted-by":"publisher","first-page":"707","DOI":"10.1287\/mnsc.12.9.707","volume":"12","author":"M.H. Rothkopf","year":"1966","unstructured":"Rothkopf, M.H.: Scheduling with Random Service Times. Management Science\u00a012, 707\u2013713 (1966)","journal-title":"Management Science"},{"key":"54_CR19","doi-asserted-by":"publisher","first-page":"116","DOI":"10.1145\/321921.321934","volume":"23","author":"S.K. Sahni","year":"1976","unstructured":"Sahni, S.K.: Algorithms for Scheduling Independent Tasks. Journal of the ACM\u00a023, 116\u2013127 (1976)","journal-title":"Journal of the ACM"},{"key":"54_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"301","DOI":"10.1007\/3-540-61310-2_23","volume-title":"Integer Programming and Combinatorial Optimization","author":"A.S. Schulz","year":"1996","unstructured":"Schulz, A.S.: Scheduling to Minimize Total Weighted Completion Time: Performance Guarantees of LP-Based Heuristics and Lower Bounds. In: Cunningham, W.H., Queyranne, M., McCormick, S.T. (eds.) IPCO 1996. LNCS, vol.\u00a01084, pp. 301\u2013315. Springer, Heidelberg (1996)"},{"key":"54_CR21","doi-asserted-by":"crossref","unstructured":"Skutella, M.: Semidefinite relaxations for parallel machine scheduling. In: Proceedings of the 39th Annual Symposium on Foundations of Computer Science (FOCS 1998), pp. 472\u2013481 (1998)","DOI":"10.1109\/SFCS.1998.743498"},{"key":"54_CR22","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1002\/nav.3800030106","volume":"3","author":"W.E. Smith","year":"1956","unstructured":"Smith, W.E.: Various Optimizers for Single Stage Production. Naval Research Logistics Quarterly\u00a03, 59\u201366 (1956)","journal-title":"Naval Research Logistics Quarterly"},{"key":"54_CR23","doi-asserted-by":"crossref","unstructured":"Schickinger, T., Scharbrodt, M., Steger, A.: A new average case analysis for completion time scheduling. In: Proceedings of the 34th Annual ACM Symposium on Theory of Computing (STOC 2002), pp. 170\u2013178 (2002)","DOI":"10.1145\/509935.509936"},{"key":"54_CR24","doi-asserted-by":"crossref","unstructured":"Schickinger, T., Scharbrodt, M., Steger, A.: A new average case analysis for completion time scheduling. Journal of the ACM (2003) (accepted)","DOI":"10.1145\/509935.509936"},{"key":"54_CR25","doi-asserted-by":"crossref","unstructured":"Skutella, M., Woeginger, G.J.: A PTAS for minimizing the total weighted completion time on identical parallel machines. Mathematics of Operations Research\u00a025 (2000)","DOI":"10.1287\/moor.25.1.63.15212"},{"key":"54_CR26","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. Journal of Applied Probability\u00a017, 187\u2013202 (1980)","journal-title":"Journal of Applied Probability"},{"key":"54_CR27","doi-asserted-by":"publisher","first-page":"841","DOI":"10.2307\/3214023","volume":"23","author":"R.R. Weber","year":"1986","unstructured":"Weber, R.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"}],"container-title":["Lecture Notes in Computer Science","STACS 2004"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-24749-4_54","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,6,4]],"date-time":"2019-06-04T01:32:34Z","timestamp":1559611954000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-24749-4_54"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2004]]},"ISBN":["9783540212362","9783540247494"],"references-count":27,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-24749-4_54","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2004]]}}}