{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,1]],"date-time":"2026-08-01T04:15:32Z","timestamp":1785557732212,"version":"3.56.0"},"reference-count":35,"publisher":"Springer Science and Business Media LLC","issue":"5","license":[{"start":{"date-parts":[[2017,11,15]],"date-time":"2017-11-15T00:00:00Z","timestamp":1510704000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/100007543","name":"Grantov\u00e1 Agentura, Univerzita Karlova","doi-asserted-by":"crossref","award":["1784214"],"award-info":[{"award-number":["1784214"]}],"id":[{"id":"10.13039\/100007543","id-type":"DOI","asserted-by":"crossref"}]},{"name":"Grantov\u00e1 Agentura \u010c(esk\u00e9 Republiky (CZ)","award":["17-09142S"],"award-info":[{"award-number":["17-09142S"]}]},{"name":"Grantov\u00e1 Agentura \u010c(esk\u00e9 Republiky (CZ)","award":["P202\/12\/G061"],"award-info":[{"award-number":["P202\/12\/G061"]}]},{"DOI":"10.13039\/100007543","name":"Grantov\u00e1 Agentura, Univerzita Karlova","doi-asserted-by":"publisher","award":["338216"],"award-info":[{"award-number":["338216"]}],"id":[{"id":"10.13039\/100007543","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100007397","name":"Univerzita Karlova v Praze","doi-asserted-by":"publisher","award":["SVV-2017-260452"],"award-info":[{"award-number":["SVV-2017-260452"]}],"id":[{"id":"10.13039\/100007397","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Sched"],"published-print":{"date-parts":[[2018,10]]},"DOI":"10.1007\/s10951-017-0550-0","type":"journal-article","created":{"date-parts":[[2017,11,15]],"date-time":"2017-11-15T14:19:07Z","timestamp":1510755547000},"page":"493-503","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":50,"title":["Scheduling meets n-fold integer programming"],"prefix":"10.1007","volume":"21","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-2588-5709","authenticated-orcid":false,"given":"Du\u0161an","family":"Knop","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Martin","family":"Kouteck\u00fd","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2017,11,15]]},"reference":[{"issue":"2","key":"550_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. (2015). The third comprehensive survey on scheduling problems with setup times\/costs. European Journal of Operational Research, 246(2), 345\u2013378. https:\/\/doi.org\/10.1016\/j.ejor.2015.04.004 .","journal-title":"European Journal of Operational Research"},{"issue":"1","key":"550_CR2","doi-asserted-by":"publisher","first-page":"78","DOI":"10.1007\/s10878-009-9276-z","volume":"22","author":"Y Asahiro","year":"2011","unstructured":"Asahiro, Y., Jansson, J., Miyano, E., Ono, H., & Zenmyo, K. (2011). Approximation algorithms for the graph orientation minimizing the maximum weighted outdegree. Journal of Combinatorial Optimization, 22(1), 78\u201396. https:\/\/doi.org\/10.1007\/s10878-009-9276-z .","journal-title":"Journal of Combinatorial Optimization"},{"key":"550_CR3","doi-asserted-by":"crossref","DOI":"10.1137\/1.9781611972290","volume-title":"Semidefinite optimization and convex algebraic geometry","author":"G Blekherman","year":"2012","unstructured":"Blekherman, G., Parrilo, P. A., & Thomas, R. R. (2012). Semidefinite optimization and convex algebraic geometry. Philadelphia: SIAM."},{"issue":"2","key":"550_CR4","doi-asserted-by":"publisher","first-page":"93","DOI":"10.1016\/0167-6377(95)00031-9","volume":"18","author":"HL Bodlaender","year":"1995","unstructured":"Bodlaender, H. L., & Fellows, M. R. (1995). W[2]-hardness of precedence constrained k-processor scheduling. Operations Research Letter, 18(2), 93\u201397. https:\/\/doi.org\/10.1016\/0167-6377(95)00031-9 .","journal-title":"Operations Research Letter"},{"issue":"7","key":"550_CR5","doi-asserted-by":"publisher","first-page":"382","DOI":"10.1145\/361011.361064","volume":"17","author":"J Bruno","year":"1974","unstructured":"Bruno, J., Coffman, E. G, Jr., & Sethi, R. (1974). Scheduling independent tasks to reduce mean finishing time. Communications of the ACM, 17(7), 382\u2013387. https:\/\/doi.org\/10.1145\/361011.361064 .","journal-title":"Communications of the ACM"},{"key":"550_CR6","unstructured":"Chen, L., Marx, D., Ye, D., & Zhang, G. (2017). Parameterized and approximation results for scheduling with a low rank processing time matrix. In LIPIcs-Leibniz international proceedings in informatics (Vol.\u00a066). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik."},{"key":"550_CR7","unstructured":"Demaine, E.D., Hajiaghayi, M., Marx, D. (eds.) (2009). Parameterized complexity and approximation algorithms. Dagstuhl seminar proceedings (Vol. 09511), 13.12.2009\u201317.12.2009, Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, Germany http:\/\/drops.dagstuhl.de\/portals\/09511\/ ."},{"key":"550_CR8","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4471-5559-1","volume-title":"Fundamentals of parameterized complexity. Texts in computer science","author":"RG Downey","year":"2013","unstructured":"Downey, R. G., & Fellows, M. R. (2013). Fundamentals of parameterized complexity. Texts in computer science. Berlin: Springer."},{"issue":"298","key":"550_CR9","doi-asserted-by":"publisher","first-page":"317","DOI":"10.1016\/S0304-3975(02)00811-3","volume":"2","author":"MR Fellows","year":"2003","unstructured":"Fellows, M. R., & McCartin, C. (2003). On the parametric complexity of schedules to minimize tardy tasks. Theoretical Computer Science, 2(298), 317\u2013324. https:\/\/doi.org\/10.1016\/S0304-3975(02)00811-3 .","journal-title":"Theoretical Computer Science"},{"key":"550_CR10","unstructured":"Garey, M. R., & Johnson, D. S. (1979) Computers and intractability: A guide to the theory of np-completeness"},{"key":"550_CR11","doi-asserted-by":"publisher","unstructured":"Goemans, M., & Williamson, D. P. (2000). Two-dimensional Gantt charts and a scheduling algorithm of Lawler. SIAM Journal on Discrete Mathematics, 13(3), 281\u2013294. https:\/\/doi.org\/10.1137\/S0895480197330254 , http:\/\/epubs.siam.org\/sam-bin\/dbq\/article\/33025 .","DOI":"10.1137\/S0895480197330254"},{"key":"550_CR12","doi-asserted-by":"publisher","unstructured":"Halld\u00f3rsson, M.M., & Karlsson, R.K. (2006). Strip graphs: Recognition and scheduling. In WG 2006 (pp. 137\u2013146). https:\/\/doi.org\/10.1007\/11917496_13 .","DOI":"10.1007\/11917496_13"},{"issue":"1\u20132","key":"550_CR13","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s10107-013-0638-z","volume":"145","author":"R Hemmecke","year":"2014","unstructured":"Hemmecke, R., K\u00f6ppe, M., & Weismantel, R. (2014). Graver basis and proximity techniques for block-structured separable convex integer minimization problems. Mathematical Programming, 145(1\u20132), 1\u201318. https:\/\/doi.org\/10.1007\/s10107-013-0638-z .","journal-title":"Mathematical Programming"},{"issue":"1\u20132","key":"550_CR14","doi-asserted-by":"publisher","first-page":"325","DOI":"10.1007\/s10107-011-0490-y","volume":"137","author":"R Hemmecke","year":"2013","unstructured":"Hemmecke, R., Onn, S., & Romanchuk, L. (2013). n-fold integer programming in cubic time. Mathematical Programming, 137(1\u20132), 325\u2013341. https:\/\/doi.org\/10.1007\/s10107-011-0490-y .","journal-title":"Mathematical Programming"},{"key":"550_CR15","doi-asserted-by":"publisher","first-page":"55","DOI":"10.4230\/LIPIcs.IPEC.2015.55","volume":"2015","author":"D Hermelin","year":"2015","unstructured":"Hermelin, D., Kubitza, J., Shabtay, D., Talmon, N., & Woeginger, G. J. (2015). Scheduling two competing agents when one agent has significantly fewer jobs. IPEC, 2015, 55\u201365. https:\/\/doi.org\/10.4230\/LIPIcs.IPEC.2015.55 .","journal-title":"IPEC"},{"issue":"1","key":"550_CR16","doi-asserted-by":"crossref","first-page":"69","DOI":"10.1016\/j.disopt.2012.11.003","volume":"10","author":"R Hildebrand","year":"2013","unstructured":"Hildebrand, R., & K\u00f6ppe, M. (2013). A new Lenstra-type algorithm for quasiconvex polynomial integer minimization with complexity $$2^{O(n{\\rm log}n)}$$ 2 O ( n log n ) . Discrete Optimization, 10(1), 69\u201384.","journal-title":"Discrete Optimization"},{"issue":"4","key":"550_CR17","doi-asserted-by":"publisher","first-page":"843","DOI":"10.1145\/96559.96597","volume":"37","author":"DS Hochbaum","year":"1990","unstructured":"Hochbaum, D. S., & Shanthikumar, J. G. (1990). Convex separable optimization is not much harder than linear optimization. Journal of the ACM, 37(4), 843\u2013862. https:\/\/doi.org\/10.1145\/96559.96597 .","journal-title":"Journal of the ACM"},{"issue":"3","key":"550_CR18","doi-asserted-by":"publisher","first-page":"846","DOI":"10.1287\/opre.21.3.846","volume":"21","author":"WA Horn","year":"1973","unstructured":"Horn, W. A. (1973). Technical note\u2014Minimizing average flow time with parallel machines. Operations Research, 21(3), 846\u2013847. https:\/\/doi.org\/10.1287\/opre.21.3.846 .","journal-title":"Operations Research"},{"issue":"1","key":"550_CR19","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":"2","key":"550_CR20","doi-asserted-by":"crossref","first-page":"207","DOI":"10.1007\/PL00009496","volume":"23","author":"L Khachiyan","year":"2000","unstructured":"Khachiyan, L., & Porkolab, L. (2000). Integer optimization on convex semialgebraic sets. Discrete & Computational Geometry, 23(2), 207\u2013224.","journal-title":"Discrete & Computational Geometry"},{"key":"550_CR21","unstructured":"Knop, D., Kouteck\u1ef3, M., & Mnich, M. (2017) Voting and bribing in single-exponential time. In 34th symposium on theoretical aspects of computer science."},{"issue":"4","key":"550_CR22","doi-asserted-by":"publisher","first-page":"427","DOI":"10.1007\/s10951-011-0243-z","volume":"15","author":"AV Kononov","year":"2012","unstructured":"Kononov, A. V., Sevastyanov, S., & Sviridenko, M. (2012). A complete 4-parametric complexity classification of short shop scheduling problems. Journal of Scheduling, 15(4), 427\u2013446. https:\/\/doi.org\/10.1007\/s10951-011-0243-z .","journal-title":"Journal of Scheduling"},{"key":"550_CR23","doi-asserted-by":"crossref","first-page":"445","DOI":"10.1016\/S0927-0507(05)80189-6","volume":"4","author":"EL Lawler","year":"1993","unstructured":"Lawler, E. L., Lenstra, J. K., Kan, A. H. R., & Shmoys, D. B. (1993). Sequencing and scheduling: Algorithms and complexity. Handbooks in operations research and management science, 4, 445\u2013522.","journal-title":"Handbooks in operations research and management science"},{"issue":"4","key":"550_CR24","doi-asserted-by":"crossref","first-page":"538","DOI":"10.1287\/moor.8.4.538","volume":"8","author":"HW Lenstra Jr","year":"1983","unstructured":"Lenstra, H. W, Jr. (1983). Integer programming with a fixed number of variables. Mathematics of Operations Research, 8(4), 538\u2013548.","journal-title":"Mathematics of Operations Research"},{"key":"550_CR25","volume-title":"Algebraic and geometric ideas in the theory of discrete optimization. MOS-SIAM series on optimization","author":"JAD Loera","year":"2013","unstructured":"Loera, J. A. D., Hemmecke, R., & K\u00f6ppe, M. (2013). Algebraic and geometric ideas in the theory of discrete optimization. MOS-SIAM series on optimization (Vol. 14). Philadelphia: SIAM."},{"issue":"2","key":"550_CR26","doi-asserted-by":"publisher","first-page":"67","DOI":"10.4230\/DagRep.1.2.67","volume":"1","author":"D Marx","year":"2011","unstructured":"Marx, D. (2011). Packing and scheduling algorithms for information and communication services (dagstuhl seminar 11091). Dagstuhl Reports, 1(2), 67\u201393. https:\/\/doi.org\/10.4230\/DagRep.1.2.67 .","journal-title":"Dagstuhl Reports"},{"issue":"1","key":"550_CR27","doi-asserted-by":"publisher","first-page":"533","DOI":"10.1007\/s10107-014-0830-9","volume":"154","author":"M Mnich","year":"2014","unstructured":"Mnich, M., & Wiese, A. (2014). Scheduling and fixed-parameter tractability. Mathematical Programming, 154(1), 533\u2013562. https:\/\/doi.org\/10.1007\/s10107-014-0830-9 .","journal-title":"Mathematical Programming"},{"key":"550_CR28","doi-asserted-by":"crossref","unstructured":"Onn, S. (2010). Nonlinear discrete optimization. Zurich Lectures in Advanced Mathematics: European Mathematical Society.","DOI":"10.4171\/093"},{"issue":"4","key":"550_CR29","doi-asserted-by":"publisher","first-page":"2277","DOI":"10.1137\/151004227","volume":"29","author":"S Onn","year":"2015","unstructured":"Onn, S., & Sarrabezolles, P. (2015). Huge unimodular $$n$$ n -fold programs. SIAM Journal on Discrete Mathematics, 29(4), 2277\u20132283. https:\/\/doi.org\/10.1137\/151004227 .","journal-title":"SIAM Journal on Discrete Mathematics"},{"key":"550_CR30","doi-asserted-by":"publisher","unstructured":"Potts, C. N., & Strusevich, V. A. (2009). Fifty years of scheduling: A survey of milestones. Journal of the Operational Research Society, 60(1), S41\u2013S68. https:\/\/doi.org\/10.1057\/jors.2009.2 .","DOI":"10.1057\/jors.2009.2"},{"key":"550_CR31","doi-asserted-by":"publisher","unstructured":"Sitters, R. (2005). Complexity of preemptive minsum scheduling on unrelated parallel machines. Journal of Algorithms, 57(1), 37\u201348. https:\/\/doi.org\/10.1016\/j.jalgor.2004.06.011 .","DOI":"10.1016\/j.jalgor.2004.06.011"},{"key":"550_CR32","doi-asserted-by":"crossref","unstructured":"van Bevern, R., Bredereck, R., Bulteau, L., Komusiewicz, C., Talmon, N., & Woeginger, G.J. (2016). Precedence-constrained scheduling problems parameterized by partial order width. In Proceedings of the 9th international conference on discrete optimization and operations research, DOOR 2016, Vladivostok, Russia, September 19\u201323, 2016, pp. 105\u2013120.","DOI":"10.1007\/978-3-319-44914-2_9"},{"issue":"5","key":"550_CR33","doi-asserted-by":"publisher","first-page":"449","DOI":"10.1007\/s10951-014-0398-5","volume":"18","author":"R Bevern van","year":"2015","unstructured":"van Bevern, R., Mnich, M., Niedermeier, R., & Weller, M. (2015a). Interval scheduling and colorful independent sets. Journal of Scheduling, 18(5), 449\u2013469. https:\/\/doi.org\/10.1007\/s10951-014-0398-5 .","journal-title":"Journal of Scheduling"},{"key":"550_CR34","doi-asserted-by":"crossref","unstructured":"van Bevern, R., Niedermeier, R., & Such\u00fd, O. (2015b). A parameterized complexity view on non-preemptively scheduling interval-constrained jobs: Few machines, small looseness, and small slack. CoRR arXiv:1508.01657 .","DOI":"10.1007\/s10951-016-0478-9"},{"key":"550_CR35","doi-asserted-by":"publisher","first-page":"73","DOI":"10.1007\/978-3-319-34171-2_6","volume":"2016","author":"R Bevern van","year":"2016","unstructured":"van Bevern, R., & Pyatkin, A. V. (2016). Completing partial schedules for open shop with unit processing times and routing. CSR, 2016, 73\u201387. https:\/\/doi.org\/10.1007\/978-3-319-34171-2_6 .","journal-title":"CSR"}],"container-title":["Journal of Scheduling"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10951-017-0550-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10951-017-0550-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10951-017-0550-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,10,6]],"date-time":"2019-10-06T01:49:47Z","timestamp":1570326587000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10951-017-0550-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,11,15]]},"references-count":35,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2018,10]]}},"alternative-id":["550"],"URL":"https:\/\/doi.org\/10.1007\/s10951-017-0550-0","relation":{},"ISSN":["1094-6136","1099-1425"],"issn-type":[{"value":"1094-6136","type":"print"},{"value":"1099-1425","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,11,15]]}}}