{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T18:05:08Z","timestamp":1725559508037},"publisher-location":"Berlin, Heidelberg","reference-count":53,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540322122"},{"type":"electronic","value":"9783540322139"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2006]]},"DOI":"10.1007\/11671541_9","type":"book-chapter","created":{"date-parts":[[2006,1,23]],"date-time":"2006-01-23T07:04:36Z","timestamp":1137999876000},"page":"250-291","source":"Crossref","is-referenced-by-count":6,"title":["List Scheduling in Order of \u03b1-Points on a Single Machine"],"prefix":"10.1007","author":[{"given":"Martin","family":"Skutella","sequence":"first","affiliation":[]}],"member":"297","reference":[{"key":"9_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, New York City, NY, pp. 32\u201343 (1999)","DOI":"10.1109\/SFFCS.1999.814574"},{"key":"9_CR2","unstructured":"van den Akker, J.M.: LP\u2013Based Solution Methods for Single\u2013Machine Scheduling Problems. PhD thesis, Eindhoven University of Technology, Eindhoven, The Netherlands (1994)"},{"key":"9_CR3","doi-asserted-by":"publisher","first-page":"686","DOI":"10.1287\/moor.1040.0092","volume":"29","author":"E.J. Anderson","year":"2004","unstructured":"Anderson, E.J., Potts, C.N.: On-line scheduling of a single machine to minimize total weighted completion time. Mathematics of Operations Research\u00a029, 686\u2013697 (2004)","journal-title":"Mathematics of Operations Research"},{"key":"9_CR4","volume-title":"Introduction to Sequencing and Scheduling","author":"K.R. Baker","year":"1974","unstructured":"Baker, K.R.: Introduction to Sequencing and Scheduling. John Wiley & Sons, New York (1974)"},{"key":"9_CR5","doi-asserted-by":"publisher","first-page":"27","DOI":"10.1016\/S0166-218X(00)00308-5","volume":"112","author":"C.C.B. Cavalcante","year":"2001","unstructured":"Cavalcante, C.C.B., de Souza, C.C., Savelsbergh, M.W.P., Wang, Y., Wolsey, L.A.: Scheduling projects with labor constraints. Discrete Applied Mathematics\u00a0112, 27\u201352 (2001)","journal-title":"Discrete Applied Mathematics"},{"key":"9_CR6","doi-asserted-by":"crossref","unstructured":"Chakrabarti, S., Muthukrishnan, S.: Resource scheduling for parallel database and scientific applications. In: Proceedings of the 8th Annual ACM Symposium on Parallel Algorithms and Architectures, Padua, Italy, pp. 329\u2013335 (1996)","DOI":"10.1145\/237502.237577"},{"key":"9_CR7","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.S., Shmoys, D.B., Stein, C., Wein, J.: Improved scheduling algorithms for minsum criteria. In: Meyer auf der Heide, F., Monien, B. (eds.) ICALP 1996. LNCS, vol.\u00a01099, pp. 646\u2013657. Springer, Heidelberg (1996)"},{"key":"9_CR8","doi-asserted-by":"publisher","first-page":"729","DOI":"10.1287\/opre.46.5.729","volume":"46","author":"L.M.A. Chan","year":"1998","unstructured":"Chan, L.M.A., Muriel, A., Simchi-Levi, D.: Parallel machine scheduling, linear programming and list scheduling heuristics. Operations Research\u00a046, 729\u2013741 (1998)","journal-title":"Operations Research"},{"key":"9_CR9","doi-asserted-by":"crossref","unstructured":"Chekuri, C.S., Johnson, R., Motwani, R., Natarajan, B., Rau, B.R., Schlansker, M.: Profile\u2013driven instruction level parallel scheduling with applications to super blocks. In: Proceedings of the 29th Annual International Symposium on Microarchitecture, Paris, France, pp. 58\u201367 (1996)","DOI":"10.1109\/MICRO.1996.566450"},{"key":"9_CR10","doi-asserted-by":"publisher","first-page":"29","DOI":"10.1016\/S0166-218X(98)00143-7","volume":"98","author":"C.S. Chekuri","year":"1999","unstructured":"Chekuri, C.S., Motwani, R.: Precedence constrained scheduling to minimize weighted completion time on a single machine. Discrete Applied Mathematics\u00a098, 29\u201338 (1999)","journal-title":"Discrete Applied Mathematics"},{"key":"9_CR11","doi-asserted-by":"publisher","first-page":"146","DOI":"10.1137\/S0097539797327180","volume":"31","author":"C.S. Chekuri","year":"2001","unstructured":"Chekuri, C.S., 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":"9_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"283","DOI":"10.1007\/978-3-540-25960-2_22","volume-title":"Integer Programming and Combinatorial Optimization","author":"J.R. Correa","year":"2004","unstructured":"Correa, J.R., Schulz, A.S.: Single machine scheduling with precedence constraints. In: Bienstock, D., Nemhauser, G.L. (eds.) IPCO 2004. LNCS, vol.\u00a03064, pp. 283\u2013297. Springer, Heidelberg (2004)"},{"key":"9_CR13","doi-asserted-by":"publisher","first-page":"255","DOI":"10.1016\/0166-218X(90)90104-K","volume":"26","author":"M.E. Dyer","year":"1990","unstructured":"Dyer, M.E., Wolsey, L.A.: Formulating the single machine sequencing problem with release dates as a mixed integer program. Discrete Applied Mathematics\u00a026, 255\u2013270 (1990)","journal-title":"Discrete Applied Mathematics"},{"key":"9_CR14","doi-asserted-by":"publisher","first-page":"439","DOI":"10.1016\/S0304-3975(02)00488-7","volume":"299","author":"L. Epstein","year":"2003","unstructured":"Epstein, L., van Stee, R.: Lower bounds for on-line single machine scheduling. Theoretical Computer Science\u00a0299, 439\u2013450 (2003)","journal-title":"Theoretical Computer Science"},{"key":"9_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"288","DOI":"10.1007\/3-540-61310-2_22","volume-title":"Integer Programming and Combinatorial Optimization","author":"M.X. Goemans","year":"1996","unstructured":"Goemans, M.X.: A supermodular relaxation for scheduling with release dates. In: Cunningham, W.H., Queyranne, M., McCormick, S.T. (eds.) IPCO 1996. LNCS, vol.\u00a01084, pp. 288\u2013300. Springer, Heidelberg (1996)"},{"key":"9_CR16","unstructured":"Goemans, M.X.: Improved approximation algorithms for scheduling with release dates. In: Proceedings of the 8th Annual ACM\u2013SIAM Symposium on Discrete Algorithms, New Orleans, LA, pp. 591\u2013598 (1997)"},{"key":"9_CR17","doi-asserted-by":"publisher","first-page":"165","DOI":"10.1137\/S089548019936223X","volume":"15","author":"M.X. Goemans","year":"2002","unstructured":"Goemans, M.X., Queyranne, M., Schulz, A.S., 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":"9_CR18","doi-asserted-by":"publisher","first-page":"149","DOI":"10.1016\/S0167-6377(00)00024-9","volume":"26","author":"M.X. Goemans","year":"2000","unstructured":"Goemans, M.X., Wein, J., Williamson, D.P.: A 1.47-approximation algorithm for a preemptive single-machine scheduling problem. Operations Research Letters\u00a026, 149\u2013154 (2000)","journal-title":"Operations Research Letters"},{"key":"9_CR19","doi-asserted-by":"publisher","first-page":"281","DOI":"10.1137\/S0895480197330254","volume":"13","author":"M.X. Goemans","year":"2000","unstructured":"Goemans, M.X., Williamson, D.P.: Two-dimensional Gantt charts and a scheduling algorithm of Lawler. SIAM Journal on Discrete Mathematics\u00a013, 281\u2013294 (2000)","journal-title":"SIAM Journal on Discrete Mathematics"},{"key":"9_CR20","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"},{"key":"9_CR21","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":"9_CR22","unstructured":"Hall, L.A., Shmoys, D.B., Wein, J.: Scheduling to minimize average completion time: Off-line and on-line algorithms. In: Proceedings of the 7th Annual ACM\u2013SIAM Symposium on Discrete Algorithms, Atlanta, GA, pp. 142\u2013151 (1996)"},{"key":"9_CR23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"404","DOI":"10.1007\/3-540-61310-2_30","volume-title":"Integer Programming and Combinatorial Optimization","author":"J.A. Hoogeveen","year":"1996","unstructured":"Hoogeveen, J.A., Vestjens, A.P.A.: Optimal on-line algorithms for single-machine scheduling. In: Cunningham, W.H., Queyranne, M., McCormick, S.T. (eds.) IPCO 1996. LNCS, vol.\u00a01084, pp. 404\u2013414. Springer, Heidelberg (1996)"},{"key":"9_CR24","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., Rinnooy 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":"9_CR25","doi-asserted-by":"publisher","first-page":"981","DOI":"10.1287\/opre.51.6.981.24912","volume":"51","author":"F. Margot","year":"2003","unstructured":"Margot, F., Queyranne, M., Wang, Y.: Decomposition, network flows and a precedence constrained single machine scheduling problem. Operations Research\u00a051, 981\u2013992 (2003)","journal-title":"Operations Research"},{"key":"9_CR26","doi-asserted-by":"publisher","first-page":"330","DOI":"10.1287\/mnsc.49.3.330.12737","volume":"49","author":"R.H. M\u00f6hring","year":"2003","unstructured":"M\u00f6hring, R.H., Schulz, A.S., Stork, F., Uetz, M.: Solving project scheduling problems by minimum cut computations. Management Science\u00a049, 330\u2013350 (2003)","journal-title":"Management Science"},{"key":"9_CR27","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":"9_CR28","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511814075","volume-title":"Randomized Algorithms","author":"R. Motwani","year":"1995","unstructured":"Motwani, R., Raghavan, P.: Randomized Algorithms. Cambridge University Press, Cambridge (1995)"},{"key":"9_CR29","first-page":"199","volume":"82","author":"C. Phillips","year":"1998","unstructured":"Phillips, C., Stein, C., Wein, J.: Minimizing average completion time in the presence of release dates. Mathematical Programming\u00a082, 199\u2013223 (1998)","journal-title":"Mathematical Programming"},{"key":"9_CR30","doi-asserted-by":"crossref","first-page":"78","DOI":"10.1007\/BFb0120909","volume":"13","author":"C.N. Potts","year":"1980","unstructured":"Potts, C.N.: An algorithm for the single machine sequencing problem with precedence constraints. Mathematical Programming Studies\u00a013, 78\u201387 (1980)","journal-title":"Mathematical Programming Studies"},{"key":"9_CR31","doi-asserted-by":"publisher","first-page":"263","DOI":"10.1007\/BF01581271","volume":"58","author":"M. Queyranne","year":"1993","unstructured":"Queyranne, M.: Structure of a simple scheduling polyhedron. Mathematical Programming\u00a058, 263\u2013285 (1993)","journal-title":"Mathematical Programming"},{"key":"9_CR32","unstructured":"Savelsbergh, M.W.P., Uma, R.N., Wein, J.M.: An experimental study of LP-based approximation algorithms for scheduling problems. In: Proceedings of the 9th Annual ACM\u2013SIAM Symposium on Discrete Algorithms, San Francisco, CA, pp. 453\u2013462 (1998)"},{"key":"9_CR33","unstructured":"Schulz, A.S.: Polytopes and scheduling. PhD thesis, TU Berlin, Germany (1996)"},{"key":"9_CR34","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":"9_CR35","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"119","DOI":"10.1007\/3-540-63248-4_11","volume-title":"Randomization and Approximation Techniques in Computer Science","author":"A.S. Schulz","year":"1997","unstructured":"Schulz, A.S., Skutella, M.: Random-based scheduling: New approximations and LP lower bounds. In: Rolim, J.D.P. (ed.) RANDOM 1997. LNCS, vol.\u00a01269, pp. 119\u2013133. Springer, Heidelberg (1997)"},{"key":"9_CR36","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":"9_CR37","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":"9_CR38","doi-asserted-by":"publisher","first-page":"203","DOI":"10.1002\/(SICI)1099-1425(199909\/10)2:5<203::AID-JOS26>3.0.CO;2-5","volume":"2","author":"P. Schuurman","year":"1999","unstructured":"Schuurman, P., Woeginger, G.J.: Polynomial time approximation algorithms for machine scheduling: Ten open problems. Journal of Scheduling\u00a02, 203\u2013213 (1999)","journal-title":"Journal of Scheduling"},{"key":"9_CR39","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"196","DOI":"10.1007\/BFb0029570","volume-title":"Online Algorithms","author":"J. Sgall","year":"1998","unstructured":"Sgall, J.: On-line scheduling \u2014 a survey. In: Fiat, A. (ed.) Dagstuhl Seminar 1996. LNCS, vol.\u00a01442, pp. 196\u2013231. Springer, Heidelberg (1998)"},{"key":"9_CR40","doi-asserted-by":"publisher","first-page":"461","DOI":"10.1007\/BF01585178","volume":"62","author":"D.B. Shmoys","year":"1993","unstructured":"Shmoys, D.B., Tardos, \u00c9.: An approximation algorithm for the generalized assignment problem. Mathematical Programming\u00a062, 461\u2013474 (1993)","journal-title":"Mathematical Programming"},{"key":"9_CR41","doi-asserted-by":"publisher","first-page":"283","DOI":"10.1287\/opre.23.2.283","volume":"23","author":"J.B. Sidney","year":"1975","unstructured":"Sidney, J.B.: Decomposition algorithms for single-machine sequencing with precedence relations and deferral costs. Operations Research\u00a023, 283\u2013298 (1975)","journal-title":"Operations Research"},{"key":"9_CR42","unstructured":"Skutella, M.: Approximation and randomization in scheduling. PhD thesis, Technische Universit\u00e4t Berlin, Germany (1998)"},{"key":"9_CR43","unstructured":"Skutella, M., Uetz, M.: Scheduling precedence-constrained jobs with stochastic processing times on parallel machines. In: Proceedings of the 12th Annual ACM\u2013SIAM Symposium on Discrete Algorithms, Washington, DC, pp. 589\u2013590 (2001)"},{"key":"9_CR44","doi-asserted-by":"crossref","unstructured":"Skutella, M., Uetz, M.: Stochastic machine scheduling with precedence constraints. SIAM Journal on Computing (2005) (to appear)","DOI":"10.1137\/S0097539702415007"},{"key":"9_CR45","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 and Logistics Quarterly\u00a03, 59\u201366 (1956)","journal-title":"Naval Research and Logistics Quarterly"},{"key":"9_CR46","unstructured":"Sousa, J.P.: Time indexed formulations of non-preemptive single-machine scheduling problems. PhD thesis, Universit\u00e9 Catholique de Louvain (1989)"},{"key":"9_CR47","doi-asserted-by":"publisher","first-page":"115","DOI":"10.1016\/S0167-6377(97)00025-4","volume":"21","author":"C. Stein","year":"1997","unstructured":"Stein, C., Wein, J.: On the existence of schedules that are near-optimal for both makespan and total weighted completion time. Operations Research Letters\u00a021, 115\u2013122 (1997)","journal-title":"Operations Research Letters"},{"key":"9_CR48","doi-asserted-by":"publisher","first-page":"89","DOI":"10.1016\/S0167-6377(01)00115-8","volume":"30","author":"L. Stougie","year":"2002","unstructured":"Stougie, L., Vestjens, A.P.A.: Randomized algorithms for on-line scheduling problems: How low can\u2019t you go? Operations Research Letters\u00a030, 89\u201396 (2002)","journal-title":"Operations Research Letters"},{"key":"9_CR49","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"394","DOI":"10.1007\/3-540-69346-7_30","volume-title":"Integer Programming and Combinatorial Optimization","author":"R.N. Uma","year":"1998","unstructured":"Uma, R.N., Wein, J.M.: On the relationship between combinatorial and LP-based approaches to NP-hard scheduling problems. In: Bixby, R.E., Boyd, E.A., R\u00edos-Mercado, R.Z. (eds.) IPCO 1998. LNCS, vol.\u00a01412, pp. 394\u2013408. Springer, Heidelberg (1998)"},{"key":"9_CR50","unstructured":"Vestjens, A.P.A.: On-line machine scheduling. PhD thesis, Eindhoven University of Technology, The Netherlands (1997)"},{"key":"9_CR51","doi-asserted-by":"publisher","first-page":"237","DOI":"10.1016\/S0166-218X(02)00427-4","volume":"131","author":"G.J. Woeginger","year":"2003","unstructured":"Woeginger, G.J.: On the approximability of average completion time scheduling under precedence constraints. Discrete Applied Mathematics\u00a0131, 237\u2013252 (2003)","journal-title":"Discrete Applied Mathematics"},{"key":"#cr-split#-9_CR52.1","unstructured":"Wolsey, L.A.: Mixed integer programming formulations for production planning and scheduling problems (1985);"},{"key":"#cr-split#-9_CR52.2","unstructured":"Invited talk at the 12th International Symposium on Mathematical Programming. MIT, Cambridge"}],"container-title":["Lecture Notes in Computer Science","Efficient Approximation and Online Algorithms"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11671541_9.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T03:14:31Z","timestamp":1619493271000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11671541_9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006]]},"ISBN":["9783540322122","9783540322139"],"references-count":53,"URL":"https:\/\/doi.org\/10.1007\/11671541_9","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2006]]}}}