Abstract
We study the problem of non-preemptively scheduling n jobs, each job j with a release time \(t_j\), a deadline \(d_j\), and a processing time \(p_j\), on m parallel identical machines. Cieliebak et al. (2004) considered the two constraints \(|d_j-t_j|\le \lambda {}p_j\) and \(|d_j-t_j|\le p_j +\sigma \) and showed the problem to be NP-hard for any \(\lambda >1\) and for any \(\sigma \ge 2\). We complement their results by parameterized complexity studies: we show that, for any \(\lambda >1\), the problem remains weakly NP-hard even for \(m=2\) and strongly W[1]-hard parameterized by m. We present a pseudo-polynomial-time algorithm for constant m and \(\lambda \) and a fixed-parameter tractability result for the parameter m combined with \(\sigma \).
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Notes
The results of Kononov et al. (2012) were obtained in context of a multivariate complexity analysis framework described by Sevastianov (2005), which is independent of the framework of parameterized complexity theory considered in our work: it allows for systematic classification of problems as polynomial-time solvable or NP-hard given concrete constraints on a set of instance parameters. It is plausible that this framework is applicable to classify problems as FPT or W[1]-hard as well.
References
van Bevern, R. (2014). Towards optimal and expressive kernelization for \(d\)-hitting set. Algorithmica, 70(1), 129–147.
van Bevern, R., Chen, J., Hüffner, F., Kratsch, S., Talmon, N., & Woeginger, G. J. (2015a). Approximability and parameterized complexity of multicover by \(c\)-intervals. Information Processing Letters, 115(10), 744–749.
van Bevern, R., Mnich, M., Niedermeier, R., & Weller, M. (2015b). Interval scheduling and colorful independent sets. Journal of Scheduling, 18(5), 449–469.
Bodlaender, H. L., & Fellows, M. R. (1995). W[2]-hardness of precedence constrained \(k\)-processor scheduling. Operations Research Letters, 18(2), 93–97.
Chen, L., Megow, N., & Schewior, K. (2016). An \(O(\log m)\)-competitive algorithm for online machine minimization. In Proceedings of the 27th annual ACM-SIAM symposium on discrete algorithms (SODA’16), pp. 155–163. SIAM.
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’04), pp. 81–90.
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–222). Berlin: Springer. doi:10.1007/1-4020-8141-3_18.
Cygan, M., Fomin, F. V., Kowalik, L., Lokshtanov, D., Marx, D., Pilipczuk, M., et al. (2015). Parameterized algorithms. Berlin: Springer.
Downey, R. G., & Fellows, M. R. (2013). Fundamentals of parameterized complexity. Berlin: Springer.
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–566.
Fellows, M. R., & McCartin, C. (2003). On the parametric complexity of schedules to minimize tardy tasks. Theoretical Computer Science, 298(2), 317–324.
Flum, J., & Grohe, M. (2006). Parameterized complexity theory. Berlin: Springer.
Garey, M. R., & Johnson, D. S. (1979). Computers and intractability: A guide to the theory of NP-completeness. Newyork, NY: Freeman.
Halldórsson, 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–146). Springer.
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’15), Leibniz International Proceedings in Informatics (LIPIcs), (Vol. 43, pp. 55–65). Schloss Dagstuhl–Leibniz-Zentrum für Informatik.
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–49.
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–543.
Kononov, A., Sevastyanov, S., & Sviridenko, M. (2012). A complete 4-parametric complexity classification of short shop scheduling problems. Journal of Scheduling, 15(4), 427–446.
Malucelli, F., & Nicoloso, S. (2007). Shiftable intervals. Annals of Operations Research, 150(1), 137–157.
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.
Mnich, M., & Wiese, A. (2015). Scheduling and fixed-parameter tractability. Mathematical Programming, 154(1–2), 533–562.
Niedermeier, R. (2010). Reflections on multivariate algorithmics and problem parameterization. In Proceedings of the 27th international symposium on theoretical aspects of computer science (STACS’10). Leibniz International Proceedings in Informatics (LIPIcs) (Vol.5, pp. 17–32). Schloss Dagstuhl-Leibniz-Zentrum für Informatik.
Niedermeier, R. (2006). Invitation to fixed-parameter algorithms. Oxford: Oxford University Press.
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–448). Schloss Dagstuhl-Leibniz-Zentrumfür Informatik.
Sevastianov, S. V. (2005). An introduction to multi-parameter complexity analysis of discrete problems. European Journal of Operational Research, 165(2), 387–397.
Author information
Authors and Affiliations
Corresponding author
Additional information
René van Bevern is supported by Grant 16-31-60007 mol_a_dk of the Russian Foundation for Basic Research (RFBR).
Ondřej Suchý is supported by Grant 14-13017P of the Czech Science Foundation.
Rights and permissions
About this article
Cite this article
van Bevern, R., Niedermeier, R. & Suchý, O. A parameterized complexity view on non-preemptively scheduling interval-constrained jobs: few machines, small looseness, and small slack. J Sched 20, 255–265 (2017). https://doi.org/10.1007/s10951-016-0478-9
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10951-016-0478-9