{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T18:36:48Z","timestamp":1725561408280},"publisher-location":"Berlin, Heidelberg","reference-count":29,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540206958"},{"type":"electronic","value":"9783540245872"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2003]]},"DOI":"10.1007\/978-3-540-24587-2_34","type":"book-chapter","created":{"date-parts":[[2010,7,29]],"date-time":"2010-07-29T08:59:19Z","timestamp":1280393959000},"page":"319-328","source":"Crossref","is-referenced-by-count":4,"title":["On Minimizing Average Weighted Completion Time: A PTAS for the Job Shop Problem with Release Dates"],"prefix":"10.1007","author":[{"given":"Aleksei V.","family":"Fishkin","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Klaus","family":"Jansen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Monaldo","family":"Mastrolilli","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"34_CR1","doi-asserted-by":"crossref","unstructured":"Afrati, F., Bampis, E., Chekuri, C., Karger, D., Kenyon, C., Khanna, S., Millis, I., Queyranne, M., Skutella, M., Stein, C., Sviridenko, M.: Approximation schemes for minimizing average weighted completion time with release dates. In: Proceedings 40th IEEE Symposium on Foundations of Computer Science, pp. 32\u201343 (1999)","DOI":"10.1109\/SFFCS.1999.814574"},{"key":"34_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"454","DOI":"10.1007\/3-540-44450-5_37","volume-title":"FST TCS 2000: Foundations of Software Technology and Theoretical Science","author":"F. Afrati","year":"2000","unstructured":"Afrati, F., Bampis, E., Fishkin, A.V., Jansen, K., Kenyon, C.: Scheduling to minimize the average completion time of dedicated tasks. In: Kapoor, S., Prasad, S. (eds.) FST TCS 2000. LNCS, vol.\u00a01974, pp. 454\u2013464. Springer, Heidelberg (2000)"},{"key":"34_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"432","DOI":"10.1007\/3-540-44669-9_50","volume-title":"Fundamentals of Computation Theory","author":"F. Afrati","year":"2001","unstructured":"Afrati, F., Milis, I.: Designing PTASs for MIN-SUM scheduling problems. In: Freivalds, R. (ed.) FCT 2001. LNCS, vol.\u00a02138, pp. 432\u2013444. Springer, Heidelberg (2001)"},{"key":"34_CR4","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.A., 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":"34_CR5","unstructured":"Chekuri, C.: Approximation algorithms for scheduling problems. PhD thesis, Department of Computer Science, Stanford University (1998)"},{"key":"34_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"848","DOI":"10.1007\/3-540-48224-5_69","volume-title":"Automata, Languages and Programming","author":"C. Chekuri","year":"2001","unstructured":"Chekuri, C., Khanna, S.: A PTAS for minimizing weighted completion time on uniformly related machines. In: Orejas, F., Spirakis, P.G., van Leeuwen, J. (eds.) ICALP 2001. LNCS, vol.\u00a02076, pp. 848\u2013861. Springer, Heidelberg (2001)"},{"key":"34_CR7","unstructured":"Chekuri, C., Motwani, R., Natarajan, B., Stein, C.: Approximation techniques for average completion time scheduling. In: Proceedings of 8th Annual ACM-SIAM Symposium on discrete Algorithms, pp. 609\u2013618 (1997)"},{"key":"34_CR8","first-page":"21","volume-title":"Chapter A review of machine scheduling: complexity, algorithms and approximability","author":"B. Chen","year":"1998","unstructured":"Chen, B., Potts, C.N., Woeginger, G.J.: Handbook of combinatorial optimization. In: Du, D.-Z., Paradalos, P.M. (eds.) Chapter A review of machine scheduling: complexity, algorithms and approximability, pp. 21\u2013169. Kluwer, Dordrecht (1998)"},{"key":"34_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"206","DOI":"10.1007\/3-540-44676-1_17","volume-title":"Proceedings 9th Annual European Symposium","author":"A.V. Fishkin","year":"2001","unstructured":"Fishkin, A.V., Jansen, K., Mastrolilli, M.: Grouping techniques for scheduling problems: Simpler and faster. In: Proceedings 9th Annual European Symposium, Arhus. LNCS, vol.\u00a02161, pp. 206\u2013217. Springer, Heidelberg (2001)"},{"key":"34_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"875","DOI":"10.1007\/3-540-48224-5_71","volume-title":"Proceedings 28th International Colloquium on Automata, Languages and Programming","author":"A.V. Fishkin","year":"2001","unstructured":"Fishkin, A.V., Jansen, K., Porkolab, L.: On minimizing average weighted completion time of multiprocessor tasks with release dates. In: Proceedings 28th International Colloquium on Automata, Languages and Programming, Crete. LNCS, vol.\u00a02076, pp. 875\u2013886. Springer, Heidelberg (2001)"},{"key":"34_CR11","volume-title":"Computers and intractability: A guide to the theory of NP-completeness","author":"M.R. Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and intractability: A guide to the theory of NP-completeness. Freeman, San Francisco (1979)"},{"key":"34_CR12","doi-asserted-by":"publisher","first-page":"117","DOI":"10.1287\/moor.1.2.117","volume":"1","author":"M.R. Garey","year":"1976","unstructured":"Garey, M.R., Johnson, D.S., Sethi, R.: The complexity of flowshop and jobshop scheduling. Mathematics of Operation Research\u00a01, 117\u2013129 (1976)","journal-title":"Mathematics of Operation Research"},{"key":"34_CR13","unstructured":"Goldberg, L.A., Paterson, M., Srinivasan, A., Sweedyk, E.: Better approximation guarantees for job-shop scheduling. In: Proceedings 8th Symposium on Discrete Algorithms, pp. 599\u2013608 (1997)"},{"key":"34_CR14","doi-asserted-by":"publisher","first-page":"36","DOI":"10.1287\/opre.26.1.36","volume":"26","author":"T. Gonzales","year":"1978","unstructured":"Gonzales, T., Sahni, S.: Flowshop and jobshop schedules: Complexity and approximation. Operations Research\u00a026, 36\u201352 (1978)","journal-title":"Operations Research"},{"key":"34_CR15","doi-asserted-by":"crossref","unstructured":"Graham, R.L., Lawler, E.L., Lenstra, J.K., Rinnooy Kan, A.H.G.: Optimization and approximation in deterministic scheduling: A survey. Annals of Discrete Mathematics, 287\u2013326 (1979)","DOI":"10.1016\/S0167-5060(08)70356-X"},{"key":"34_CR16","doi-asserted-by":"crossref","unstructured":"Hall, L.A., Schulz, A.S., Shmoys, D.B., Wein, J.: Scheduling to minimize average time: Off-line and on-line algorithm. Mathematics of Operation Research, 513\u2013544 (1997)","DOI":"10.1287\/moor.22.3.513"},{"key":"34_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"353","DOI":"10.1007\/3-540-69346-7_27","volume-title":"Integer Programming and Combinatorial Optimization","author":"H. Hoogeveen","year":"1998","unstructured":"Hoogeveen, H., Schuurman, P., Weoginger, G.: Non-approximability results for scheduling problems with minsum criteria. In: Bixby, R.E., Boyd, E.A., R\u00edos-Mercado, R.Z. (eds.) IPCO 1998. LNCS, vol.\u00a01412, pp. 353\u2013366. Springer, Heidelberg (1998)"},{"key":"34_CR18","doi-asserted-by":"crossref","unstructured":"Jansen, K., Solis-Oba, R., Sviridenko, M.: Makespan minimization in job shops: A polynomial time approximation scheme. In: Proceedings 31st Annual ACM Symposium on Theory of Computing, pp. 394\u2013399, Atlanta (1999) (To appear in SIAM Journal on Discrete Mathematics)","DOI":"10.1145\/301250.301351"},{"key":"34_CR19","series-title":"Handbooks in Operation Research and Management Science, chapter Sequencing and scheduling: Algorithms and complexity","doi-asserted-by":"publisher","first-page":"445","DOI":"10.1016\/S0927-0507(05)80189-6","volume-title":"Logistics of Production and Inventory","author":"E.L. Lawler","year":"1993","unstructured":"Lawler, E.L., Lenstra, J.K., Rinnooy Kan, A.H.G., Shmoys, D.B.: Logistics of Production and Inventory. Handbooks in Operation Research and Management Science, chapter Sequencing and scheduling: Algorithms and complexity, vol.\u00a04, pp. 445\u2013522. North-Holland, Amsterdam (1993)"},{"key":"34_CR20","unstructured":"Queyranne, M., Sviridenko, M.: New and improved algorithms for minsum shop scheduling. In: Proceedings 11th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 871\u2013878 (2000)"},{"key":"34_CR21","unstructured":"Schulz, A.S.: Polytopes and scheduling. PhD thesis, Technical University of Berlin, Germany (1996)"},{"key":"34_CR22","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":"34_CR23","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":"2000","unstructured":"Schuurman, P., Woeginger, G.J.: Polynomial time approximation algorithms for machine scheduling: Ten open problems. Journal of Scheduling\u00a02, 203\u2013213 (2000)","journal-title":"Journal of Scheduling"},{"key":"34_CR24","unstructured":"Schuurman, P., Woeginger, G.J.: Approximation schemes \u2013 a tutorial. To appear in the book Lectures on Scheduling, edited by Moehring, R.H., Potts, C.N., Schulz, A.S., Woeginger, G.J., Wolsey, L.A. (2002)"},{"key":"34_CR25","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"15","DOI":"10.1007\/BFb0053960","volume-title":"Approximation Algorithms for Combinatorial Optimization","author":"D.B. Shmoys","year":"1998","unstructured":"Shmoys, D.B.: Using linear programming in the design and analysis of approximation algorithms: Two illustrative examples. In: Jansen, K., Rolim, J.D.P. (eds.) APPROX 1998. LNCS, vol.\u00a01444, pp. 15\u201332. Springer, Heidelberg (1998)"},{"key":"34_CR26","doi-asserted-by":"publisher","first-page":"617","DOI":"10.1137\/S009753979222676X","volume":"23","author":"D.B. Shmoys","year":"1994","unstructured":"Shmoys, D.B., Stein, C., Wein, J.: Improved approximation algorithms for shop scheduling problems. SIAM Journal of Computing\u00a023, 617\u2013632 (1994)","journal-title":"SIAM Journal of Computing"},{"key":"34_CR27","unstructured":"Skutella, M.: Approximation and randomization in scheduling. PhD thesis, Technical University of Berlin, Germany (1998)"},{"key":"34_CR28","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 Logistic Quarterly\u00a03, 59\u201366 (1956)","journal-title":"Naval Research Logistic Quarterly"},{"key":"34_CR29","unstructured":"Torng, E., Uthaisombut, P.: Lower bounds for SRPT-subsequence algorithms for non-preemptive scheduling. In: Proceedings 10th ACM-SIAM Symposium on Discrete Algorithms, pp. 973\u2013974 (1999)"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Computation"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-24587-2_34","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,3,17]],"date-time":"2019-03-17T13:54:27Z","timestamp":1552830867000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-24587-2_34"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2003]]},"ISBN":["9783540206958","9783540245872"],"references-count":29,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-24587-2_34","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2003]]}}}