{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,11]],"date-time":"2024-09-11T14:29:46Z","timestamp":1726064986669},"publisher-location":"Cham","reference-count":21,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783030389185"},{"type":"electronic","value":"9783030389192"}],"license":[{"start":{"date-parts":[[2020,1,1]],"date-time":"2020-01-01T00:00:00Z","timestamp":1577836800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2020]]},"DOI":"10.1007\/978-3-030-38919-2_8","type":"book-chapter","created":{"date-parts":[[2020,1,16]],"date-time":"2020-01-16T17:03:18Z","timestamp":1579194198000},"page":"88-100","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Approximating Weighted Completion Time for Order Scheduling with Setup Times"],"prefix":"10.1007","author":[{"given":"Alexander","family":"M\u00e4cker","sequence":"first","affiliation":[]},{"given":"Friedhelm","family":"Meyer auf der Heide","sequence":"additional","affiliation":[]},{"given":"Simon","family":"Pukrop","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2020,1,17]]},"reference":[{"issue":"2","key":"8_CR1","doi-asserted-by":"publisher","first-page":"345","DOI":"10.1016\/j.ejor.2015.04.004","volume":"246","author":"A Allahverdi","year":"2015","unstructured":"Allahverdi, A.: The third comprehensive survey on scheduling problems with setup times\/costs. Eur. J. Oper. Res. 246(2), 345\u2013378 (2015)","journal-title":"Eur. J. Oper. Res."},{"issue":"2","key":"8_CR2","doi-asserted-by":"publisher","first-page":"219","DOI":"10.1016\/S0305-0483(98)00042-5","volume":"27","author":"A Allahverdi","year":"1999","unstructured":"Allahverdi, A., Gupta, J.N., Aldowaisan, T.: A review of scheduling research involving setup considerations. Omega 27(2), 219\u2013239 (1999)","journal-title":"Omega"},{"issue":"3","key":"8_CR3","doi-asserted-by":"publisher","first-page":"985","DOI":"10.1016\/j.ejor.2006.06.060","volume":"187","author":"A Allahverdi","year":"2008","unstructured":"Allahverdi, A., Ng, C.T., Cheng, T.C.E., Kovalyov, M.Y.: A survey of scheduling problems with setup times or costs. Eur. J. Oper. Res. 187(3), 985\u20131032 (2008)","journal-title":"Eur. J. Oper. Res."},{"key":"8_CR4","doi-asserted-by":"crossref","unstructured":"Bansal, N., Khot, S.: Optimal long code test with one free bit. In: Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pp. 453\u2013462. IEEE (2009)","DOI":"10.1109\/FOCS.2009.23"},{"issue":"1\u20132","key":"8_CR5","doi-asserted-by":"publisher","first-page":"29","DOI":"10.1016\/S0166-218X(98)00143-7","volume":"98","author":"C Chekuri","year":"1999","unstructured":"Chekuri, C., Motwani, R.: Precedence constrained scheduling to minimize sum of weighted completion times on a single machine. Discrete Appl. Math. 98(1\u20132), 29\u201338 (1999)","journal-title":"Discrete Appl. Math."},{"issue":"1\u20132","key":"8_CR6","doi-asserted-by":"publisher","first-page":"305","DOI":"10.1007\/s10107-014-0831-8","volume":"154","author":"JR Correa","year":"2015","unstructured":"Correa, J.R., et al.: Strong LP formulations for scheduling splittable jobs on unrelated machines. Math. Program. 154(1\u20132), 305\u2013328 (2015)","journal-title":"Math. Program."},{"issue":"4","key":"8_CR7","doi-asserted-by":"publisher","first-page":"469","DOI":"10.1016\/j.orl.2016.04.011","volume":"44","author":"JR Correa","year":"2016","unstructured":"Correa, J.R., Verdugo, V., Verschae, J.: Splitting versus setup trade-offs for scheduling to minimize weighted completion time. Oper. Res. Lett. 44(4), 469\u2013473 (2016)","journal-title":"Oper. Res. Lett."},{"issue":"5","key":"8_CR8","doi-asserted-by":"publisher","first-page":"719","DOI":"10.1016\/j.dam.2007.08.010","volume":"156","author":"S Divakaran","year":"2008","unstructured":"Divakaran, S., Saks, M.E.: Approximation algorithms for problems in scheduling with set-ups. Discrete Appl. Math. 156(5), 719\u2013729 (2008)","journal-title":"Discrete Appl. Math."},{"key":"8_CR9","doi-asserted-by":"publisher","first-page":"87","DOI":"10.1023\/A:1018959420252","volume":"92","author":"AE Gerodimos","year":"1999","unstructured":"Gerodimos, A.E., Glass, C.A., Potts, C.N., Tautenhahn, T.: Scheduling multi-operation jobs on a single machine. Ann. OR 92, 87\u2013105 (1999)","journal-title":"Ann. OR"},{"issue":"3","key":"8_CR10","doi-asserted-by":"publisher","first-page":"513","DOI":"10.1287\/moor.22.3.513","volume":"22","author":"LA 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. Math. Oper. Res. 22(3), 513\u2013544 (1997)","journal-title":"Math. Oper. Res."},{"key":"8_CR11","doi-asserted-by":"crossref","unstructured":"Happe, M., Meyer auf der Heide, F., Kling, P., Platzner, M., Plessl, C.: On-the-fly computing: a novel paradigm for individualized IT services. In: Proceedings of the 16th IEEE International Symposium on Object\/Component\/Service-Oriented Real-Time Distributed Computing (ISORC), pp. 1\u201310. IEEE Computer Society (2013)","DOI":"10.1109\/ISORC.2013.6913232"},{"key":"8_CR12","unstructured":"Jansen, K., Klein, K., Maack, M., Rau, M.: Empowering the configuration-IP-new PTAS results for scheduling with setups times. In: Proceedings of the 10th Innovations in Theoretical Computer Science Conference (ITCS). LIPIcs, vol. 124, pp. 1\u201319. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik (2019)"},{"key":"8_CR13","doi-asserted-by":"crossref","unstructured":"Jansen, K., Maack, M., M\u00e4cker, A.: Scheduling on (un-)related machines with setup times. In: Proceedings of the 2019 IEEE International Parallel and Distributed Processing Symposium (IPDPS), pp. 145\u2013154. IEEE Computer Society (2019)","DOI":"10.1109\/IPDPS.2019.00025"},{"key":"8_CR14","doi-asserted-by":"publisher","first-page":"75","DOI":"10.1016\/S0167-5060(08)70323-6","volume":"2","author":"EL Lawler","year":"1978","unstructured":"Lawler, E.L.: Sequencing jobs to minimize total weighted completion time subject to precedence constraints. Ann. Discrete Math. 2, 75\u201390 (1978)","journal-title":"Ann. Discrete Math."},{"issue":"1","key":"8_CR15","doi-asserted-by":"publisher","first-page":"22","DOI":"10.1287\/opre.26.1.22","volume":"26","author":"JK Lenstra","year":"1978","unstructured":"Lenstra, J.K., Kan, A.H.G.R.: Complexity of scheduling under precedence constraints. Oper. Res. 26(1), 22\u201335 (1978)","journal-title":"Oper. Res."},{"key":"8_CR16","doi-asserted-by":"publisher","first-page":"37","DOI":"10.1007\/0-387-27744-7_3","volume-title":"Multidisciplinary Scheduling: Theory and Applications","author":"JY Leung","year":"2005","unstructured":"Leung, J.Y., Li, H., Pinedo, M.: Order scheduling models: an overview. In: Kendall, G., Burke, E.K., Petrovic, S., Gendreau, M. (eds.) Multidisciplinary Scheduling: Theory and Applications, pp. 37\u201353. Springer, Boston (2005). https:\/\/doi.org\/10.1007\/0-387-27744-7_3"},{"key":"8_CR17","doi-asserted-by":"crossref","unstructured":"M\u00e4cker, A., Meyer auf der Heide, F., Pukrop, S.: Approximating weighted completion time for order scheduling with setup times. arXiv e-prints arXiv:1910.08360 , October 2019","DOI":"10.1007\/978-3-030-38919-2_8"},{"issue":"5","key":"8_CR18","doi-asserted-by":"publisher","first-page":"798","DOI":"10.1287\/opre.37.5.798","volume":"37","author":"CL Monma","year":"1989","unstructured":"Monma, C.L., Potts, C.N.: On the complexity of scheduling with batch setup times. Oper. Res. 37(5), 798\u2013804 (1989)","journal-title":"Oper. Res."},{"issue":"4","key":"8_CR19","doi-asserted-by":"publisher","first-page":"187","DOI":"10.1016\/S0020-0190(01)00274-5","volume":"82","author":"CT Ng","year":"2002","unstructured":"Ng, C.T., Cheng, T.C.E., Yuan, J.J.: Strong NP-hardness of the single machine multi-operation jobs total completion time scheduling problem. Inf. Process. Lett. 82(4), 187\u2013191 (2002)","journal-title":"Inf. Process. Lett."},{"issue":"1\u20132","key":"8_CR20","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1002\/nav.3800030106","volume":"3","author":"WE Smith","year":"1956","unstructured":"Smith, W.E.: Various optimizers for single-stage production. Naval Res. Logistics Q. 3(1\u20132), 59\u201366 (1956)","journal-title":"Naval Res. Logistics Q."},{"issue":"1","key":"8_CR21","doi-asserted-by":"publisher","first-page":"237","DOI":"10.1016\/S0166-218X(02)00427-4","volume":"131","author":"GJ Woeginger","year":"2003","unstructured":"Woeginger, G.J.: On the approximability of average completion time scheduling under precedence constraints. Discrete Appl. Math. 131(1), 237\u2013252 (2003)","journal-title":"Discrete Appl. Math."}],"container-title":["Lecture Notes in Computer Science","SOFSEM 2020: Theory and Practice of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-030-38919-2_8","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,2,22]],"date-time":"2021-02-22T12:42:25Z","timestamp":1613997745000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-030-38919-2_8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020]]},"ISBN":["9783030389185","9783030389192"],"references-count":21,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-38919-2_8","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2020]]},"assertion":[{"value":"17 January 2020","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"SOFSEM","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Current Trends in Theory and Practice of Informatics","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Limassol","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Cyprus","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2020","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"20 January 2020","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"24 January 2020","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"46","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"sofsem2020","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"http:\/\/cyprusconferences.org\/sofsem2020\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Single-blind","order":1,"name":"type","label":"Type","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Easychair","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"125","order":3,"name":"number_of_submissions_sent_for_review","label":"Number of Submissions Sent for Review","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"40","order":4,"name":"number_of_full_papers_accepted","label":"Number of Full Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"17","order":5,"name":"number_of_short_papers_accepted","label":"Number of Short Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"32% - The value is computed by the equation \"Number of Full Papers Accepted \/ Number of Submissions Sent for Review * 100\" and then rounded to a whole number.","order":6,"name":"acceptance_rate_of_full_papers","label":"Acceptance Rate of Full Papers","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"2.9","order":7,"name":"average_number_of_reviews_per_paper","label":"Average Number of Reviews per Paper","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"3.8","order":8,"name":"average_number_of_papers_per_reviewer","label":"Average Number of Papers per Reviewer","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Yes","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}}]}}