{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,25]],"date-time":"2026-04-25T11:08:12Z","timestamp":1777115292901,"version":"3.51.4"},"reference-count":32,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2025,1,30]],"date-time":"2025-01-30T00:00:00Z","timestamp":1738195200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2025,1,30]],"date-time":"2025-01-30T00:00:00Z","timestamp":1738195200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/100007397","name":"Univerzita Karlova v Praze","doi-asserted-by":"publisher","award":["UNCE 24\/SCI\/008"],"award-info":[{"award-number":["UNCE 24\/SCI\/008"]}],"id":[{"id":"10.13039\/100007397","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"publisher","award":["Wo758\/11-1"],"award-info":[{"award-number":["Wo758\/11-1"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001824","name":"Grantov\u00e1 Agentura Cesk\u00e9 Republiky","doi-asserted-by":"publisher","award":["22-22997\u00a0S"],"award-info":[{"award-number":["22-22997\u00a0S"]}],"id":[{"id":"10.13039\/501100001824","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Sched"],"published-print":{"date-parts":[[2025,2]]},"abstract":"<jats:title>Abstract<\/jats:title>\n          <jats:p>The task of scheduling jobs to machines while minimizing the total makespan, the sum of weighted completion times, or a norm of the load vector are among the oldest and most fundamental tasks in combinatorial optimization. Since all of these problems are in general -hard, much attention has been given to the regime where there is only a small number <jats:italic>k<\/jats:italic> of job types, but possibly the number of jobs <jats:italic>n<\/jats:italic> is large; this is the few job types, high-multiplicity regime. Despite many positive results, the hardness boundary of this regime was not understood until now. We show that makespan minimization on uniformly related machines (<jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>$$Q|HM|C_{\\max }$$<\/jats:tex-math>\n                <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mrow>\n                      <mml:mi>Q<\/mml:mi>\n                      <mml:mo>|<\/mml:mo>\n                      <mml:mi>H<\/mml:mi>\n                      <mml:mi>M<\/mml:mi>\n                      <mml:mo>|<\/mml:mo>\n                    <\/mml:mrow>\n                    <mml:msub>\n                      <mml:mi>C<\/mml:mi>\n                      <mml:mo>max<\/mml:mo>\n                    <\/mml:msub>\n                  <\/mml:mrow>\n                <\/mml:math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula>) is -hard already with 6 job types, and that the related <jats:sc>Cutting Stock<\/jats:sc> problem is -hard already with 8 item types. For the more general unrelated machines model (<jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>$$R|HM|C_{\\max }$$<\/jats:tex-math>\n                <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mrow>\n                      <mml:mi>R<\/mml:mi>\n                      <mml:mo>|<\/mml:mo>\n                      <mml:mi>H<\/mml:mi>\n                      <mml:mi>M<\/mml:mi>\n                      <mml:mo>|<\/mml:mo>\n                    <\/mml:mrow>\n                    <mml:msub>\n                      <mml:mi>C<\/mml:mi>\n                      <mml:mo>max<\/mml:mo>\n                    <\/mml:msub>\n                  <\/mml:mrow>\n                <\/mml:math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula>), we show that if the largest job size <jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>$$p_{\\max }$$<\/jats:tex-math>\n                <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:msub>\n                    <mml:mi>p<\/mml:mi>\n                    <mml:mo>max<\/mml:mo>\n                  <\/mml:msub>\n                <\/mml:math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula> or the number of jobs <jats:italic>n<\/jats:italic> is polynomially bounded in the instance size\u00a0|<jats:italic>I<\/jats:italic>|, there are algorithms with complexity <jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>$$|I|^{{{\\,\\mathrm{\\textrm{poly}}\\,}}(k)}$$<\/jats:tex-math>\n                <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:msup>\n                    <mml:mrow>\n                      <mml:mo>|<\/mml:mo>\n                      <mml:mi>I<\/mml:mi>\n                      <mml:mo>|<\/mml:mo>\n                    <\/mml:mrow>\n                    <mml:mrow>\n                      <mml:mrow>\n                        <mml:mspace\/>\n                        <mml:mtext>poly<\/mml:mtext>\n                        <mml:mspace\/>\n                      <\/mml:mrow>\n                      <mml:mo>(<\/mml:mo>\n                      <mml:mi>k<\/mml:mi>\n                      <mml:mo>)<\/mml:mo>\n                    <\/mml:mrow>\n                  <\/mml:msup>\n                <\/mml:math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula>. Our main result is that this is unlikely to be improved because <jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>$$Q||C_{\\max }$$<\/jats:tex-math>\n                <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mrow>\n                      <mml:mi>Q<\/mml:mi>\n                      <mml:mo>|<\/mml:mo>\n                      <mml:mo>|<\/mml:mo>\n                    <\/mml:mrow>\n                    <mml:msub>\n                      <mml:mi>C<\/mml:mi>\n                      <mml:mo>max<\/mml:mo>\n                    <\/mml:msub>\n                  <\/mml:mrow>\n                <\/mml:math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula> is <jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>$$\\mathsf {W[1]}$$<\/jats:tex-math>\n                <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>W<\/mml:mi>\n                    <mml:mo>[<\/mml:mo>\n                    <mml:mn>1<\/mml:mn>\n                    <mml:mo>]<\/mml:mo>\n                  <\/mml:mrow>\n                <\/mml:math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula>-hard parameterized by <jats:italic>k<\/jats:italic> already when <jats:italic>n<\/jats:italic>, <jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>$$p_{\\max }$$<\/jats:tex-math>\n                <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:msub>\n                    <mml:mi>p<\/mml:mi>\n                    <mml:mo>max<\/mml:mo>\n                  <\/mml:msub>\n                <\/mml:math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula>, and the numbers describing the machine speeds are polynomial in\u00a0|<jats:italic>I<\/jats:italic>|; the same holds for <jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>$$R||C_{\\max }$$<\/jats:tex-math>\n                <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mrow>\n                      <mml:mi>R<\/mml:mi>\n                      <mml:mo>|<\/mml:mo>\n                      <mml:mo>|<\/mml:mo>\n                    <\/mml:mrow>\n                    <mml:msub>\n                      <mml:mi>C<\/mml:mi>\n                      <mml:mo>max<\/mml:mo>\n                    <\/mml:msub>\n                  <\/mml:mrow>\n                <\/mml:math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula> (without machine speeds) when the job sizes matrix has rank\u00a02. Our positive and negative results also extend to the objectives <jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>$$\\ell _2$$<\/jats:tex-math>\n                <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:msub>\n                    <mml:mi>\u2113<\/mml:mi>\n                    <mml:mn>2<\/mml:mn>\n                  <\/mml:msub>\n                <\/mml:math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula>-norm minimization of the load vector and, partially, sum of weighted completion times <jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>$$\\sum w_j C_j$$<\/jats:tex-math>\n                <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mo>\u2211<\/mml:mo>\n                    <mml:msub>\n                      <mml:mi>w<\/mml:mi>\n                      <mml:mi>j<\/mml:mi>\n                    <\/mml:msub>\n                    <mml:msub>\n                      <mml:mi>C<\/mml:mi>\n                      <mml:mi>j<\/mml:mi>\n                    <\/mml:msub>\n                  <\/mml:mrow>\n                <\/mml:math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula>. Along the way, we answer affirmatively the question whether makespan minimization on identical machines (<jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>$$P||C_{\\max }$$<\/jats:tex-math>\n                <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mrow>\n                      <mml:mi>P<\/mml:mi>\n                      <mml:mo>|<\/mml:mo>\n                      <mml:mo>|<\/mml:mo>\n                    <\/mml:mrow>\n                    <mml:msub>\n                      <mml:mi>C<\/mml:mi>\n                      <mml:mo>max<\/mml:mo>\n                    <\/mml:msub>\n                  <\/mml:mrow>\n                <\/mml:math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula>) is fixed-parameter tractable parameterized by <jats:italic>k<\/jats:italic>, extending our understanding of this fundamental problem. Together with our hardness results for <jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>$$Q||C_{\\max }$$<\/jats:tex-math>\n                <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mrow>\n                      <mml:mi>Q<\/mml:mi>\n                      <mml:mo>|<\/mml:mo>\n                      <mml:mo>|<\/mml:mo>\n                    <\/mml:mrow>\n                    <mml:msub>\n                      <mml:mi>C<\/mml:mi>\n                      <mml:mo>max<\/mml:mo>\n                    <\/mml:msub>\n                  <\/mml:mrow>\n                <\/mml:math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula>, this implies that the complexity of <jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>$$P|HM|C_{\\max }$$<\/jats:tex-math>\n                <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mrow>\n                      <mml:mi>P<\/mml:mi>\n                      <mml:mo>|<\/mml:mo>\n                      <mml:mi>H<\/mml:mi>\n                      <mml:mi>M<\/mml:mi>\n                      <mml:mo>|<\/mml:mo>\n                    <\/mml:mrow>\n                    <mml:msub>\n                      <mml:mi>C<\/mml:mi>\n                      <mml:mo>max<\/mml:mo>\n                    <\/mml:msub>\n                  <\/mml:mrow>\n                <\/mml:math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula> is the only remaining open case.<\/jats:p>","DOI":"10.1007\/s10951-024-00827-8","type":"journal-article","created":{"date-parts":[[2025,1,30]],"date-time":"2025-01-30T18:29:59Z","timestamp":1738261799000},"page":"139-156","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Complexity of scheduling few types of jobs on related and unrelated machines"],"prefix":"10.1007","volume":"28","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-7846-0053","authenticated-orcid":false,"given":"Martin","family":"Kouteck\u00fd","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7398-718X","authenticated-orcid":false,"given":"Johannes","family":"Zink","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2025,1,30]]},"reference":[{"issue":"3","key":"827_CR1","doi-asserted-by":"publisher","first-page":"2152","DOI":"10.1137\/17M1162792","volume":"28","author":"I Aliev","year":"2018","unstructured":"Aliev, I., Loera, J. A. D., Eisenbrand, F., Oertel, T., & Weismantel, R. (2018). The support of integer optimal solutions. SIAM Journal on Optimization, 28(3), 2152\u20132157. https:\/\/doi.org\/10.1137\/17M1162792","journal-title":"SIAM Journal on Optimization"},{"key":"827_CR2","doi-asserted-by":"publisher","unstructured":"Berndt, S., Jansen, K., & Klein, K. (2021). New bounds for the vertices of the integer hull. In: Proc. SOSA 2021, pp. 25\u201336. SIAM, Philadelphia. https:\/\/doi.org\/10.1137\/1.9781611976496.3","DOI":"10.1137\/1.9781611976496.3"},{"key":"827_CR3","doi-asserted-by":"publisher","unstructured":"Bhaskara, A., Krishnaswamy, R., Talwar, K., & Wieder, U. (2013). Minimum makespan scheduling with low rank processing times. In: Proc. SODA 2013, pp. 937\u2013947. SIAM, Philadelphia. https:\/\/doi.org\/10.1137\/1.9781611973105.67","DOI":"10.1137\/1.9781611973105.67"},{"key":"827_CR4","doi-asserted-by":"publisher","unstructured":"Chen, L., Marx, D., Ye, D., & Zhang, G. (2017). Parameterized and approximation results for scheduling with a low rank processing time matrix. In: Proc. STACS 2017. LIPIcs, vol. 66, pp. 22\u201312214. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, Dagstuhl. https:\/\/doi.org\/10.4230\/LIPIcs.STACS.2017.22","DOI":"10.4230\/LIPIcs.STACS.2017.22"},{"key":"827_CR5","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.jcss.2018.03.005","volume":"96","author":"L Chen","year":"2018","unstructured":"Chen, L., Jansen, K., & Zhang, G. (2018). On the optimality of exact and approximation algorithms for scheduling problems. Journal of Computer and System Sciences, 96, 1\u201332. https:\/\/doi.org\/10.1016\/j.jcss.2018.03.005","journal-title":"Journal of Computer and System Sciences"},{"key":"827_CR6","doi-asserted-by":"publisher","unstructured":"Conforti, M., Cornu\u00e9jols, G., & Zambelli, G. (2014). Integer Programming. Graduate Texts in Mathematics, vol. 271. Springer, Cham. https:\/\/doi.org\/10.1007\/978-3-319-11008-0","DOI":"10.1007\/978-3-319-11008-0"},{"key":"827_CR7","doi-asserted-by":"publisher","unstructured":"Cslovjecsek, J., Eisenbrand, F., Hunkenschr\u00f6der, C., Rohwedder, L., & Weismantel, R. (2021). Block-structured integer and linear programming in strongly polynomial and near linear time. In Proc. SODA 2021, pp 1666\u20131681. SIAM, Philadelphia. https:\/\/doi.org\/10.1137\/1.9781611976465.101","DOI":"10.1137\/1.9781611976465.101"},{"key":"827_CR8","doi-asserted-by":"publisher","unstructured":"Cygan, M., Fomin, F., Kowalik, L., Lokshtanov, D., Marx, D., Pilipczuk, M., Pilipczuk, M., & Saurabh, S. (2015). Parameterized algorithms. Springer. https:\/\/doi.org\/10.1007\/978-3-319-21275-3","DOI":"10.1007\/978-3-319-21275-3"},{"key":"827_CR9","unstructured":"Eisenbrand, F., Hunkenschr\u00f6der, C., Klein, K., Kouteck\u00fd, M., Levin, A., & Onn, S. (2019). An algorithmic theory of integer programming. CoRR arXiv:1904.01361 preprint"},{"issue":"1","key":"827_CR10","doi-asserted-by":"publisher","first-page":"49","DOI":"10.1007\/bf02579200","volume":"7","author":"A Frank","year":"1987","unstructured":"Frank, A., & Tardos, \u00c9. (1987). An application of simultaneous diophantine approximation in combinatorial optimization. Combinatorica, 7(1), 49\u201365. https:\/\/doi.org\/10.1007\/bf02579200","journal-title":"Combinatorica"},{"issue":"6","key":"827_CR11","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. (1961). A linear programming approach to the cutting-stock problem. Operations Research, 9(6), 849\u2013859. https:\/\/doi.org\/10.1287\/opre.9.6.849","journal-title":"Operations Research"},{"key":"827_CR12","doi-asserted-by":"publisher","unstructured":"Goemans, M.X., & Rothvo\u00df, T. (2014). Polynomiality for bin packing with a constant number of item types. In: Proc. SODA 2014, pp. 830\u2013839. SIAM, Philadelphia. https:\/\/doi.org\/10.1137\/1.9781611973402.61","DOI":"10.1137\/1.9781611973402.61"},{"issue":"6","key":"827_CR13","doi-asserted-by":"publisher","first-page":"38","DOI":"10.1137\/1.9781611973402.61","volume":"67","author":"MX Goemans","year":"2020","unstructured":"Goemans, M. X., & Rothvo\u00df, T. (2020). Polynomiality for bin packing with a constant number of item types. Journal of the ACM, 67(6), 38\u201313821. https:\/\/doi.org\/10.1137\/1.9781611973402.61","journal-title":"Journal of the ACM"},{"key":"827_CR14","unstructured":"Hermelin, D., Mnich, M., & Omlor, S. (2019). Single machine batch scheduling to minimize the weighted number of tardy jobs. CoRR arXiv:1911.12350. preprint"},{"issue":"1","key":"827_CR15","doi-asserted-by":"publisher","first-page":"271","DOI":"10.1007\/s10479-018-2852-9","volume":"298","author":"D Hermelin","year":"2021","unstructured":"Hermelin, D., Karhi, S., Pinedo, M., & Shabtay, D. (2021). New algorithms for minimizing the weighted number of tardy jobs on a single machine. Annals of Operations Research, 298(1), 271\u2013287. https:\/\/doi.org\/10.1007\/s10479-018-2852-9","journal-title":"Annals of Operations Research"},{"issue":"1","key":"827_CR16","doi-asserted-by":"publisher","first-page":"67","DOI":"10.1016\/j.ejor.2018.07.038","volume":"273","author":"D Hermelin","year":"2019","unstructured":"Hermelin, D., Pinedo, M., Shabtay, D., & Talmon, N. (2019). On the parameterized tractability of single machine scheduling with rejection. European Journal of Operational Research, 273(1), 67\u201373. https:\/\/doi.org\/10.1016\/j.ejor.2018.07.038","journal-title":"European Journal of Operational Research"},{"key":"827_CR17","doi-asserted-by":"publisher","unstructured":"Jansen, K. (2017). New algorithmic results for bin packing and scheduling. In: Proc. CIAC 2017, pp. 10\u201315. Springer, Cham. https:\/\/doi.org\/10.1007\/978-3-319-57586-5_2","DOI":"10.1007\/978-3-319-57586-5_2"},{"key":"827_CR18","doi-asserted-by":"publisher","unstructured":"Jansen, K., Klein, K.-M., Maack, M., & Rau, M. (2018). Empowering the configuration-IP-new PTAS results for scheduling with setups times. In: Proc. ITCS 2019, pp. 44\u201314419. Schloss Dagstuhl \u2013 Leibniz-Zentrum f\u00fcr Informatik, Dagstuhl. https:\/\/doi.org\/10.1007\/s10107-021-01694-3","DOI":"10.1007\/s10107-021-01694-3"},{"key":"827_CR19","doi-asserted-by":"publisher","unstructured":"Jansen, K., Lassota, A., & Maack, M. (2020). Approximation algorithms for scheduling with class constraints. In: Proc. SPAA 2020, pp. 349\u2013357. ACM, New York. https:\/\/doi.org\/10.1145\/3350755.3400247","DOI":"10.1145\/3350755.3400247"},{"issue":"4","key":"827_CR20","doi-asserted-by":"publisher","first-page":"1498","DOI":"10.1137\/1.9781611974782.103","volume":"45","author":"K Jansen","year":"2020","unstructured":"Jansen, K., & Klein, K. (2020). About the structure of the integer cone and its application to bin packing. Mathematics of Operations Research, 45(4), 1498\u20131511. https:\/\/doi.org\/10.1137\/1.9781611974782.103","journal-title":"Mathematics of Operations Research"},{"issue":"1","key":"827_CR21","doi-asserted-by":"publisher","first-page":"39","DOI":"10.1016\/j.jcss.2012.04.004","volume":"79","author":"K Jansen","year":"2013","unstructured":"Jansen, K., Kratsch, S., Marx, D., & Schlotter, I. (2013). Bin packing with fixed number of bins revisited. Journal of Computer and System Sciences, 79(1), 39\u201349. https:\/\/doi.org\/10.1016\/j.jcss.2012.04.004","journal-title":"Journal of Computer and System Sciences"},{"issue":"4","key":"827_CR22","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. (2020). Near-linear time algorithm for $$n$$-fold ILPs via color coding. SIAM Journal on Discrete Mathematics, 34(4), 2282\u20132299. https:\/\/doi.org\/10.1137\/19M1303873","journal-title":"SIAM Journal on Discrete Mathematics"},{"key":"827_CR23","doi-asserted-by":"publisher","unstructured":"Knop, D., & Kouteck\u00fd, M. (2022). Scheduling kernels via configuration LP. In: Proc. ESA 2022, pp. 73\u201317315. Schloss Dagstuhl \u2013 Leibniz-Zentrum f\u00fcr Informatik, Dagstuhl. https:\/\/doi.org\/10.4230\/LIPIcs.ESA.2022.73","DOI":"10.4230\/LIPIcs.ESA.2022.73"},{"key":"827_CR24","unstructured":"Knop, D., Kouteck\u00fd, M., Levin, A., Mnich, M., & Onn, S. (2019). Multitype integer monoid optimization and applications. CoRR arXiv:1909.07326. preprint"},{"issue":"5","key":"827_CR25","doi-asserted-by":"publisher","first-page":"493","DOI":"10.1007\/s10951-017-0550-0","volume":"21","author":"D Knop","year":"2018","unstructured":"Knop, D., & Kouteck\u00fd, M. (2018). Scheduling meets $$n$$-fold integer programming. Journal of Scheduling, 21(5), 493\u2013503. https:\/\/doi.org\/10.1007\/s10951-017-0550-0","journal-title":"Journal of Scheduling"},{"issue":"1","key":"827_CR26","doi-asserted-by":"publisher","first-page":"199","DOI":"10.1007\/S10107-022-01882-9","volume":"200","author":"D Knop","year":"2023","unstructured":"Knop, D., Kouteck\u00fd, M., Levin, A., Mnich, M., & Onn, S. (2023). High-multiplicity n-fold IP via configuration LP. Mathematical programming, 200(1), 199\u2013227. https:\/\/doi.org\/10.1007\/S10107-022-01882-9","journal-title":"Mathematical programming"},{"key":"827_CR27","doi-asserted-by":"publisher","unstructured":"Lawler, E., Lenstra, J.K., Kan, A.R., & Shmoys, D. (1993). Sequencing and scheduling: Algorithms and complexity. In: Graves, S.C., Rinnooy Kan, A.H.G., Zipkin, P.H. (eds.) Logistics of Production and Inventory. Handbooks in Operations Research and Management Science, vol. 4, pp. 445\u2013522. North-Holland, Amsterdam. https:\/\/doi.org\/10.1016\/S0927-0507(05)80189-6","DOI":"10.1016\/S0927-0507(05)80189-6"},{"key":"827_CR28","doi-asserted-by":"publisher","unstructured":"Levin, A. (2022). Approximation schemes for the generalized extensible bin packing problem. Algorithmica, 84(2), 325\u2013343. https:\/\/doi.org\/10.1007\/s00453-021-00895-8","DOI":"10.1007\/s00453-021-00895-8"},{"issue":"1","key":"827_CR29","doi-asserted-by":"publisher","first-page":"31","DOI":"10.1287\/moor.26.1.31.10590","volume":"26","author":"T McCormick","year":"2001","unstructured":"McCormick, T., Smallwood, S., & Spieksma, F. (2001). A polynomial algorithm for multiprocessor scheduling with two job lengths. Mathematics of Operations Research, 26(1), 31\u201349. https:\/\/doi.org\/10.1287\/moor.26.1.31.10590","journal-title":"Mathematics of Operations Research"},{"key":"827_CR30","doi-asserted-by":"publisher","first-page":"254","DOI":"10.1016\/j.cor.2018.07.020","volume":"100","author":"M Mnich","year":"2018","unstructured":"Mnich, M., & Bevern, R. (2018). Parameterized complexity of machine scheduling: 15 open problems. Computers and Operations Research, 100, 254\u2013261. https:\/\/doi.org\/10.1016\/j.cor.2018.07.020","journal-title":"Computers and Operations Research"},{"issue":"1\u20132","key":"827_CR31","doi-asserted-by":"publisher","first-page":"533","DOI":"10.1007\/s10107-014-0830-9","volume":"154","author":"M Mnich","year":"2015","unstructured":"Mnich, M., & Wiese, A. (2015). Scheduling and fixed-parameter tractability. Mathematical Programming, 154(1\u20132), 533\u2013562. https:\/\/doi.org\/10.1007\/s10107-014-0830-9","journal-title":"Mathematical Programming"},{"key":"827_CR32","doi-asserted-by":"publisher","unstructured":"Smith, W. E. (1956). Various optimizers for single-stage production. Naval Research Logistics Quarterly, 3(1\u20132), 59\u201366. https:\/\/doi.org\/10.1002\/nav.3800030106","DOI":"10.1002\/nav.3800030106"}],"container-title":["Journal of Scheduling"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10951-024-00827-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10951-024-00827-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10951-024-00827-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,4,1]],"date-time":"2025-04-01T06:08:55Z","timestamp":1743487735000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10951-024-00827-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,1,30]]},"references-count":32,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2025,2]]}},"alternative-id":["827"],"URL":"https:\/\/doi.org\/10.1007\/s10951-024-00827-8","relation":{},"ISSN":["1094-6136","1099-1425"],"issn-type":[{"value":"1094-6136","type":"print"},{"value":"1099-1425","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,1,30]]},"assertion":[{"value":"13 October 2024","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"30 January 2025","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}