{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,13]],"date-time":"2026-06-13T10:14:37Z","timestamp":1781345677721,"version":"3.54.1"},"reference-count":33,"publisher":"Springer Science and Business Media LLC","issue":"1-2","license":[{"start":{"date-parts":[[2021,8,11]],"date-time":"2021-08-11T00:00:00Z","timestamp":1628640000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2021,8,11]],"date-time":"2021-08-11T00:00:00Z","timestamp":1628640000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"publisher","award":["JA 612\/20-1"],"award-info":[{"award-number":["JA 612\/20-1"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Math. Program."],"published-print":{"date-parts":[[2022,9]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Integer linear programs of configurations, or configuration IPs, are a classical tool in the design of algorithms for scheduling and packing problems where a set of items has to be placed in multiple target locations. Herein, a configuration describes a possible placement on one of the target locations, and the IP is used to choose suitable configurations covering the items. We give an augmented IP formulation, which we call the module configuration IP. It can be described within the framework of <jats:italic>n<\/jats:italic>-fold integer programming and, therefore, be solved efficiently. As an application, we consider scheduling problems with setup times in which a set of jobs has to be scheduled on a set of identical machines with the objective of minimizing the makespan. For instance, we investigate the case that jobs can be split and scheduled on multiple machines. However, before a part of a job can be processed, an uninterrupted setup depending on the job has to be paid. For both of the variants that jobs can be executed in parallel or not, we obtain an efficient polynomial time approximation scheme (EPTAS) of running time <jats:inline-formula><jats:alternatives><jats:tex-math>$$f(1\/\\varepsilon )\\cdot \\mathrm {poly}(|I|)$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>f<\/mml:mi>\n                    <mml:mo>(<\/mml:mo>\n                    <mml:mn>1<\/mml:mn>\n                    <mml:mo>\/<\/mml:mo>\n                    <mml:mi>\u03b5<\/mml:mi>\n                    <mml:mo>)<\/mml:mo>\n                    <mml:mo>\u00b7<\/mml:mo>\n                    <mml:mi>poly<\/mml:mi>\n                    <mml:mo>(<\/mml:mo>\n                    <mml:mo>|<\/mml:mo>\n                    <mml:mi>I<\/mml:mi>\n                    <mml:mo>|<\/mml:mo>\n                    <mml:mo>)<\/mml:mo>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>. Previously, only constant factor approximations of 5\/3 and <jats:inline-formula><jats:alternatives><jats:tex-math>$$4\/3 + \\varepsilon $$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mn>4<\/mml:mn>\n                    <mml:mo>\/<\/mml:mo>\n                    <mml:mn>3<\/mml:mn>\n                    <mml:mo>+<\/mml:mo>\n                    <mml:mi>\u03b5<\/mml:mi>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>, respectively, were known. Furthermore, we present an EPTAS for a problem where classes of (non-splittable) jobs are given, and a setup has to be paid for each class of jobs being executed on one machine.<\/jats:p>","DOI":"10.1007\/s10107-021-01694-3","type":"journal-article","created":{"date-parts":[[2021,8,11]],"date-time":"2021-08-11T09:03:07Z","timestamp":1628672587000},"page":"367-401","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":12,"title":["Empowering the configuration-IP: new PTAS results for scheduling with setup times"],"prefix":"10.1007","volume":"195","author":[{"given":"Klaus","family":"Jansen","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Kim-Manuel","family":"Klein","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7918-6642","authenticated-orcid":false,"given":"Marten","family":"Maack","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Malin","family":"Rau","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2021,8,11]]},"reference":[{"issue":"2","key":"1694_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). https:\/\/doi.org\/10.1016\/j.ejor.2015.04.004","journal-title":"Eur. J. Oper. Res."},{"issue":"2","key":"1694_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":"1694_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., Cheng, T.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."},{"issue":"1","key":"1694_CR4","doi-asserted-by":"publisher","first-page":"55","DOI":"10.1002\/(SICI)1099-1425(199806)1:1<55::AID-JOS2>3.0.CO;2-J","volume":"1","author":"N Alon","year":"1998","unstructured":"Alon, N., Azar, Y., Woeginger, G.J., Yadid, T.: Approximation schemes for scheduling on parallel machines. J. Sched. 1(1), 55\u201366 (1998)","journal-title":"J. Sched."},{"issue":"6","key":"1694_CR5","doi-asserted-by":"publisher","first-page":"1303","DOI":"10.1137\/0222078","volume":"22","author":"B Chen","year":"1993","unstructured":"Chen, B.: A better heuristic for preemptive parallel machine scheduling with batch setup times. SIAM J. Comput. 22(6), 1303\u20131318 (1993)","journal-title":"SIAM J. Comput."},{"issue":"3","key":"1694_CR6","doi-asserted-by":"publisher","first-page":"299","DOI":"10.1007\/s10951-006-8265-7","volume":"9","author":"B Chen","year":"2006","unstructured":"Chen, B., Ye, Y., Zhang, J.: Lot-sizing scheduling with batch setup times. J. Sched. 9(3), 299\u2013310 (2006)","journal-title":"J. Sched."},{"key":"1694_CR7","unstructured":"Chen, L., Marx, D., Ye, D., Zhang, G.: Parameterized and approximation results for scheduling with a low rank processing time matrix. In: LIPIcs-Leibniz International Proceedings in Informatics, vol. 66. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik (2017)"},{"issue":"1\u20132","key":"1694_CR8","doi-asserted-by":"publisher","first-page":"305","DOI":"10.1007\/s10107-014-0831-8","volume":"154","author":"J Correa","year":"2015","unstructured":"Correa, J., Marchetti-Spaccamela, A., Matuschke, J., Stougie, L., Svensson, O., Verdugo, V., Verschae, J.: 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":"1694_CR9","doi-asserted-by":"publisher","first-page":"469","DOI":"10.1016\/j.orl.2016.04.011","volume":"44","author":"J Correa","year":"2016","unstructured":"Correa, J., 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."},{"key":"1694_CR10","doi-asserted-by":"crossref","unstructured":"Cslovjecsek, J., Eisenbrand, F., Hunkenschr\u00f6der, C., Rohwedder, L., Weismantel, R.: Block-structured integer and linear programming in strongly polynomial and near linear time. In: D. Marx (ed.) Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, SODA 2021, Virtual Conference, January 10\u201313, 2021, pp. 1666\u20131681. SIAM (2021)","DOI":"10.1137\/1.9781611976465.101"},{"key":"1694_CR11","unstructured":"Eisenbrand, F., Hunkenschr\u00f6der, C., Klein, K.: Faster algorithms for integer programs with block structure. In: 45th International Colloquium on Automata, Languages, and Programming, ICALP 2018, July 9\u201313, 2018, Prague, Czech Republic, pp. 49:1\u201349:13 (2018)"},{"key":"1694_CR12","unstructured":"Eisenbrand, F., Hunkenschr\u00f6der, C., Klein, K., Kouteck\u00fd, M., Levin, A., Onn, S.: An algorithmic theory of integer programming. CoRR (2019). http:\/\/arxiv.org\/abs\/abs\/1904.01361"},{"issue":"6","key":"1694_CR13","doi-asserted-by":"publisher","first-page":"849","DOI":"10.1287\/opre.9.6.849","volume":"9","author":"PC Gilmore","year":"1961","unstructured":"Gilmore, P.C., Gomory, R.E.: A linear programming approach to the cutting-stock problem. Oper. Res. 9(6), 849\u2013859 (1961)","journal-title":"Oper. Res."},{"issue":"6","key":"1694_CR14","doi-asserted-by":"publisher","first-page":"38:1","DOI":"10.1145\/3421750","volume":"67","author":"MX Goemans","year":"2020","unstructured":"Goemans, M.X., Rothvoss, T.: Polynomiality for bin packing with a constant number of item types. J. ACM 67(6), 38:1\u201338:21 (2020)","journal-title":"J. ACM"},{"key":"1694_CR15","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s10107-011-0490-y","volume":"137","author":"R Hemmecke","year":"2013","unstructured":"Hemmecke, R., Onn, S., Romanchuk, L.: N-fold integer programming in cubic time. Math. Program. 137, 1\u201317 (2013)","journal-title":"Math. Program."},{"issue":"1","key":"1694_CR16","doi-asserted-by":"publisher","first-page":"144","DOI":"10.1145\/7531.7535","volume":"34","author":"DS Hochbaum","year":"1987","unstructured":"Hochbaum, D.S., Shmoys, D.B.: Using dual approximation algorithms for scheduling problems theoretical and practical results. J. ACM (JACM) 34(1), 144\u2013162 (1987)","journal-title":"J. ACM (JACM)"},{"key":"1694_CR17","unstructured":"Jansen, K., Klein, K., Maack, M., Rau, M.: Empowering the configuration-ip\u2014new PTAS results for scheduling with setups times. CoRR (2018). http:\/\/arxiv.org\/abs\/abs\/1801.06460"},{"key":"1694_CR18","unstructured":"Jansen, K., Klein, K., Maack, M., Rau, M.: Empowering the configuration-ip\u2014new PTAS results for scheduling with setups times. In: 10th Innovations in Theoretical Computer Science Conference, ITCS 2019, January 10\u201312, 2019, San Diego, California, USA, pp. 44:1\u201344:19 (2019)"},{"issue":"4","key":"1694_CR19","doi-asserted-by":"publisher","first-page":"1371","DOI":"10.1287\/moor.2019.1036","volume":"45","author":"K Jansen","year":"2020","unstructured":"Jansen, K., Klein, K., Verschae, J.: Closing the gap for makespan scheduling via sparsification techniques. Math. Oper. Res. 45(4), 1371\u20131392 (2020)","journal-title":"Math. Oper. Res."},{"key":"1694_CR20","doi-asserted-by":"crossref","unstructured":"Jansen, K., Land, F.: Non-preemptive scheduling with setup times: A ptas. In: European Conference on Parallel Processing, pp. 159\u2013170. Springer, Berlin (2016)","DOI":"10.1007\/978-3-319-43659-3_12"},{"issue":"4","key":"1694_CR21","doi-asserted-by":"publisher","first-page":"2282","DOI":"10.1137\/19M1303873","volume":"34","author":"K Jansen","year":"2020","unstructured":"Jansen, K., Lassota, A., Rohwedder, L.: Near-linear time algorithm for n-fold ilps via color coding. SIAM J. Discret. Math. 34(4), 2282\u20132299 (2020)","journal-title":"SIAM J. Discret. Math."},{"issue":"3","key":"1694_CR22","doi-asserted-by":"publisher","first-page":"415","DOI":"10.1287\/moor.12.3.415","volume":"12","author":"R Kannan","year":"1987","unstructured":"Kannan, R.: Minkowski\u2019s convex body theorem and integer programming. Math. Oper. Res. 12(3), 415\u2013440 (1987)","journal-title":"Math. Oper. Res."},{"key":"1694_CR23","first-page":"1","volume":"21","author":"D Knop","year":"2017","unstructured":"Knop, D., Kouteck\u00fd, M.: Scheduling meets n-fold integer programming. J. Sched. 21, 1\u201311 (2017)","journal-title":"J. Sched."},{"key":"1694_CR24","unstructured":"Knop, D., Kouteck\u00fd, M., Levin, A., Mnich, M., Onn, S.: Multitype integer monoid optimization and applications. CoRR abs\/1909.07326 (2019)"},{"issue":"1","key":"1694_CR25","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s10107-019-01402-2","volume":"184","author":"D Knop","year":"2020","unstructured":"Knop, D., Kouteck\u00fd, M., Mnich, M.: Combinatorial n-fold integer programming and applications. Math. Program. 184(1), 1\u201334 (2020)","journal-title":"Math. Program."},{"key":"1694_CR26","unstructured":"Kouteck\u00fd, M., Levin, A., Onn, S.: A parameterized strongly polynomial algorithm for block structured integer programs. In: 45th International Colloquium on Automata, Languages, and Programming, ICALP 2018, July 9\u201313, 2018, Prague, Czech Republic, pp. 85:1\u201385:14 (2018)"},{"issue":"4","key":"1694_CR27","doi-asserted-by":"publisher","first-page":"538","DOI":"10.1287\/moor.8.4.538","volume":"8","author":"HW Lenstra Jr","year":"1983","unstructured":"Lenstra Jr., H.W.: Integer programming with a fixed number of variables. Math. Oper. Res. 8(4), 538\u2013548 (1983)","journal-title":"Math. Oper. Res."},{"key":"1694_CR28","series-title":"MOS-SIAM Series on Optimization","volume-title":"Algebraic and Geometric Ideas in the Theory of Discrete Optimization","author":"JAD Loera","year":"2013","unstructured":"Loera, J.A.D., Hemmecke, R., K\u00f6ppe, M.: Algebraic and Geometric Ideas in the Theory of Discrete Optimization. MOS-SIAM Series on Optimization, vol. 14. SIAM, Philadelphia (2013)"},{"key":"1694_CR29","doi-asserted-by":"crossref","unstructured":"M\u00e4cker, A., Malatyali, M., auf\u00a0der Heide, F.M., Riechers, S.: Non-preemptive scheduling on machines with setup times. In: Workshop on Algorithms and Data Structures, pp. 542\u2013553. Springer, Berlin (2015)","DOI":"10.1007\/978-3-319-21840-3_45"},{"issue":"5","key":"1694_CR30","doi-asserted-by":"publisher","first-page":"981","DOI":"10.1287\/opre.41.5.981","volume":"41","author":"CL Monma","year":"1993","unstructured":"Monma, C.L., Potts, C.N.: Analysis of heuristics for preemptive parallel machine scheduling with batch setup times. Oper. Res. 41(5), 981\u2013993 (1993)","journal-title":"Oper. Res."},{"key":"1694_CR31","series-title":"Zurich Lectures in Advanced Mathematics","doi-asserted-by":"publisher","DOI":"10.4171\/093","volume-title":"Nonlinear Discrete Optimization","author":"S Onn","year":"2010","unstructured":"Onn, S.: Nonlinear Discrete Optimization. Zurich Lectures in Advanced Mathematics. European Mathematical Society, Zurich (2010)"},{"issue":"2","key":"1694_CR32","doi-asserted-by":"publisher","first-page":"119","DOI":"10.1007\/s10951-014-0370-4","volume":"18","author":"F Schalekamp","year":"2015","unstructured":"Schalekamp, F., Sitters, R., Van Der Ster, S., Stougie, L., Verdugo, V., Van Zuylen, A.: Split scheduling with uniform setup times. J. Sched. 18(2), 119\u2013129 (2015)","journal-title":"J. Sched."},{"key":"1694_CR33","unstructured":"Schuurman, P., Woeginger, G.J.: Preemptive scheduling with job-dependent setup times. In: Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms, pp. 759\u2013767. Society for Industrial and Applied Mathematics, Philadelphia (1999)"}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-021-01694-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10107-021-01694-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-021-01694-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,10,21]],"date-time":"2022-10-21T15:30:24Z","timestamp":1666366224000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10107-021-01694-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,8,11]]},"references-count":33,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2022,9]]}},"alternative-id":["1694"],"URL":"https:\/\/doi.org\/10.1007\/s10107-021-01694-3","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"value":"0025-5610","type":"print"},{"value":"1436-4646","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,8,11]]},"assertion":[{"value":"13 August 2019","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"17 June 2021","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"11 August 2021","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}