{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,22]],"date-time":"2026-03-22T21:46:35Z","timestamp":1774215995581,"version":"3.50.1"},"reference-count":25,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2016,4,8]],"date-time":"2016-04-08T00:00:00Z","timestamp":1460073600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100001824","name":"Grantov\u00e1 Agentura \u010cesk\u00e9 Republiky","doi-asserted-by":"publisher","award":["14-13017P"],"award-info":[{"award-number":["14-13017P"]}],"id":[{"id":"10.13039\/501100001824","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100002261","name":"Russian Foundation for Basic Research","doi-asserted-by":"publisher","award":["16-31-60007 mol_a_dk"],"award-info":[{"award-number":["16-31-60007 mol_a_dk"]}],"id":[{"id":"10.13039\/501100002261","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Sched"],"published-print":{"date-parts":[[2017,6]]},"DOI":"10.1007\/s10951-016-0478-9","type":"journal-article","created":{"date-parts":[[2016,4,8]],"date-time":"2016-04-08T16:47:04Z","timestamp":1460134024000},"page":"255-265","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":24,"title":["A parameterized complexity view on non-preemptively scheduling interval-constrained jobs: few machines, small looseness, and small slack"],"prefix":"10.1007","volume":"20","author":[{"given":"Ren\u00e9","family":"van Bevern","sequence":"first","affiliation":[]},{"given":"Rolf","family":"Niedermeier","sequence":"additional","affiliation":[]},{"given":"Ond\u0159ej","family":"Such\u00fd","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2016,4,8]]},"reference":[{"issue":"1","key":"478_CR1","first-page":"129","volume":"70","author":"R Bevern van","year":"2014","unstructured":"van Bevern, R. (2014). Towards optimal and expressive kernelization for $$d$$ d -hitting set. Algorithmica, 70(1), 129\u2013147.","journal-title":"Algorithmica"},{"issue":"10","key":"478_CR2","doi-asserted-by":"publisher","first-page":"744","DOI":"10.1016\/j.ipl.2015.03.004","volume":"115","author":"R Bevern van","year":"2015","unstructured":"van Bevern, R., Chen, J., H\u00fcffner, F., Kratsch, S., Talmon, N., & Woeginger, G. J. (2015a). Approximability and parameterized complexity of multicover by $$c$$ c -intervals. Information Processing Letters, 115(10), 744\u2013749.","journal-title":"Information Processing Letters"},{"issue":"5","key":"478_CR3","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. (2015b). Interval scheduling and colorful independent sets. Journal of Scheduling, 18(5), 449\u2013469.","journal-title":"Journal of Scheduling"},{"issue":"2","key":"478_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$$ k -processor scheduling. Operations Research Letters, 18(2), 93\u201397.","journal-title":"Operations Research Letters"},{"key":"478_CR5","doi-asserted-by":"crossref","unstructured":"Chen, L., Megow, N., & Schewior, K. (2016). An $$O(\\log m)$$ O ( log m ) -competitive algorithm for online machine minimization. In Proceedings of the 27th annual ACM-SIAM symposium on discrete algorithms (SODA\u201916), pp. 155\u2013163. SIAM.","DOI":"10.1137\/1.9781611974331.ch12"},{"key":"478_CR6","doi-asserted-by":"publisher","unstructured":"Chuzhoy, J., Guha S., Khanna, S., & Naor, J. (2004). Machine minimization for scheduling jobs with interval constraints. In Proceedings of the 45th annual symposium on foundations of computer science (FOCS\u201904), pp. 81\u201390.","DOI":"10.1109\/FOCS.2004.38"},{"key":"478_CR7","doi-asserted-by":"publisher","unstructured":"Cieliebak, M., Erlebach, T., Hennecke, F., Weber, B., & Widmayer, P. (2004). Scheduling with release times and deadlines on a minimum number of machines. In J.-J. Levy, E. W. Mayr, J. C. Mitchel (Eds.), Exploring new frontiers of theoretical informatics, IFIP international federation for information processing (Vol. 155, pp. 209\u2013222). Berlin: Springer. doi: 10.1007\/1-4020-8141-3_18 .","DOI":"10.1007\/1-4020-8141-3_18"},{"key":"478_CR8","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-21275-3","volume-title":"Parameterized algorithms","author":"M Cygan","year":"2015","unstructured":"Cygan, M., Fomin, F. V., Kowalik, L., Lokshtanov, D., Marx, D., Pilipczuk, M., et al. (2015). Parameterized algorithms. Berlin: Springer."},{"key":"478_CR9","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4471-5559-1","volume-title":"Fundamentals of parameterized complexity","author":"RG Downey","year":"2013","unstructured":"Downey, R. G., & Fellows, M. R. (2013). Fundamentals of parameterized complexity. Berlin: Springer."},{"issue":"3","key":"478_CR10","doi-asserted-by":"publisher","first-page":"541","DOI":"10.1016\/j.ejc.2012.04.008","volume":"34","author":"MR Fellows","year":"2013","unstructured":"Fellows, M. R., Jansen, B. M. P., & Rosamond, F. A. (2013). Towards fully multivariate algorithmics: Parameter ecology and the deconstruction of computational complexity. European Journal of Combinatorics, 34(3), 541\u2013566.","journal-title":"European Journal of Combinatorics"},{"issue":"2","key":"478_CR11","doi-asserted-by":"publisher","first-page":"317","DOI":"10.1016\/S0304-3975(02)00811-3","volume":"298","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, 298(2), 317\u2013324.","journal-title":"Theoretical Computer Science"},{"key":"478_CR12","volume-title":"Parameterized complexity theory","author":"J Flum","year":"2006","unstructured":"Flum, J., & Grohe, M. (2006). Parameterized complexity theory. Berlin: Springer."},{"key":"478_CR13","unstructured":"Garey, M. R., & Johnson, D. S. (1979). Computers and intractability: A guide to the theory of NP-completeness. Newyork, NY: Freeman."},{"key":"478_CR14","doi-asserted-by":"publisher","unstructured":"Halld\u00f3rsson, M. M., & Karlsson, R. K. (2006). Strip graphs: Recognition and scheduling. In Proceedings of the 32nd international workshop on graph-theoretic concepts in computer science. LNCS (Vol. 4271, pp. 137\u2013146). Springer.","DOI":"10.1007\/11917496_13"},{"key":"478_CR15","unstructured":"Hermelin, D., Kubitza, J. M., Shabtay, D., Talmon, N., & Woeginger, G. (2015). Scheduling two competing agents when one agent has significantly fewer jobs. In Proceedings of the 10th international symposium on parameterized and exact computation (IPEC\u201915), Leibniz International Proceedings in Informatics (LIPIcs), (Vol.\u00a043, pp. 55\u201365). Schloss Dagstuhl\u2013Leibniz-Zentrum f\u00fcr Informatik."},{"issue":"1","key":"478_CR16","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.","journal-title":"Journal of Computer and System Sciences"},{"issue":"5","key":"478_CR17","doi-asserted-by":"publisher","first-page":"530","DOI":"10.1002\/nav.20231","volume":"54","author":"AWJ Kolen","year":"2007","unstructured":"Kolen, A. W. J., Lenstra, J. K., Papadimitriou, C. H., & Spieksma, F. C. R. (2007). Interval scheduling: A survey. Naval Research Logistics, 54(5), 530\u2013543.","journal-title":"Naval Research Logistics"},{"issue":"4","key":"478_CR18","doi-asserted-by":"publisher","first-page":"427","DOI":"10.1007\/s10951-011-0243-z","volume":"15","author":"A Kononov","year":"2012","unstructured":"Kononov, A., Sevastyanov, S., & Sviridenko, M. (2012). A complete 4-parametric complexity classification of short shop scheduling problems. Journal of Scheduling, 15(4), 427\u2013446.","journal-title":"Journal of Scheduling"},{"issue":"1","key":"478_CR19","doi-asserted-by":"publisher","first-page":"137","DOI":"10.1007\/s10479-006-0161-1","volume":"150","author":"F Malucelli","year":"2007","unstructured":"Malucelli, F., & Nicoloso, S. (2007). Shiftable intervals. Annals of Operations Research, 150(1), 137\u2013157.","journal-title":"Annals of Operations Research"},{"key":"478_CR20","doi-asserted-by":"publisher","unstructured":"Marx, D. (2011). Fixed-parameter tractable scheduling problems. In Packing and scheduling algorithms for information and communication services (Dagstuhl Seminar 11091). doi: 10.4230\/DagRep.1.2.67 .","DOI":"10.4230\/DagRep.1.2.67"},{"issue":"1\u20132","key":"478_CR21","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.","journal-title":"Mathematical Programming"},{"key":"478_CR22","unstructured":"Niedermeier, R. (2010). Reflections on multivariate algorithmics and problem parameterization. In Proceedings of the 27th international symposium on theoretical aspects of computer science (STACS\u201910). Leibniz International Proceedings in Informatics (LIPIcs) (Vol.5, pp. 17\u201332). Schloss Dagstuhl-Leibniz-Zentrum f\u00fcr Informatik."},{"key":"478_CR23","doi-asserted-by":"publisher","DOI":"10.1093\/acprof:oso\/9780198566076.001.0001","volume-title":"Invitation to fixed-parameter algorithms","author":"R Niedermeier","year":"2006","unstructured":"Niedermeier, R. (2006). Invitation to fixed-parameter algorithms. Oxford: Oxford University Press."},{"key":"478_CR24","unstructured":"Saha, B. (2013). Renting a cloud. In Annual conference on foundations of software technology and theoretical computer science (FSTTCS) 2013. Leibniz International Proceedings in Informatics (LIPIcs) (Vol. 24, pp. 437\u2013448). Schloss Dagstuhl-Leibniz-Zentrumf\u00fcr Informatik."},{"issue":"2","key":"478_CR25","doi-asserted-by":"publisher","first-page":"387","DOI":"10.1016\/j.ejor.2004.04.009","volume":"165","author":"SV Sevastianov","year":"2005","unstructured":"Sevastianov, S. V. (2005). An introduction to multi-parameter complexity analysis of discrete problems. European Journal of Operational Research, 165(2), 387\u2013397.","journal-title":"European Journal of Operational Research"}],"container-title":["Journal of Scheduling"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10951-016-0478-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10951-016-0478-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10951-016-0478-9","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10951-016-0478-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,9,6]],"date-time":"2019-09-06T06:53:43Z","timestamp":1567752823000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10951-016-0478-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,4,8]]},"references-count":25,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2017,6]]}},"alternative-id":["478"],"URL":"https:\/\/doi.org\/10.1007\/s10951-016-0478-9","relation":{},"ISSN":["1094-6136","1099-1425"],"issn-type":[{"value":"1094-6136","type":"print"},{"value":"1099-1425","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,4,8]]}}}