nach oben

Journal of Scheduling

Erschienen in:

08.04.2016

A parameterized complexity view on non-preemptively scheduling interval-constrained jobs: few machines, small looseness, and small slack

verfasst von: René van Bevern, Rolf Niedermeier, Ondřej Suchý

Erschienen in: Journal of Scheduling | Ausgabe 3/2017

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

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 \).

Vorheriger Artikel The local–global conjecture for scheduling with non-linear cost

Nächster Artikel Optimal scheduling of contract algorithms with soft deadlines

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

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.

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.CrossRef

van Bevern, R., Mnich, M., Niedermeier, R., & Weller, M. (2015b). Interval scheduling and colorful independent sets. Journal of Scheduling, 18(5), 449–469.CrossRef

Bodlaender, H. L., & Fellows, M. R. (1995). W[2]-hardness of precedence constrained \(k\)-processor scheduling. Operations Research Letters, 18(2), 93–97.CrossRef

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.CrossRef

Downey, R. G., & Fellows, M. R. (2013). Fundamentals of parameterized complexity. Berlin: Springer.CrossRef

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.CrossRef

Fellows, M. R., & McCartin, C. (2003). On the parametric complexity of schedules to minimize tardy tasks. Theoretical Computer Science, 298(2), 317–324.CrossRef

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.CrossRef

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.CrossRef

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.CrossRef

Malucelli, F., & Nicoloso, S. (2007). Shiftable intervals. Annals of Operations Research, 150(1), 137–157.CrossRef

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.CrossRef

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.CrossRef

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.CrossRef

Titel: A parameterized complexity view on non-preemptively scheduling interval-constrained jobs: few machines, small looseness, and small slack
verfasst von: René van Bevern
Rolf Niedermeier
Ondřej Suchý
Publikationsdatum: 08.04.2016
Verlag: Springer US
Erschienen in: Journal of Scheduling / Ausgabe 3/2017
Print ISSN: 1094-6136
Elektronische ISSN: 1099-1425
DOI: https://doi.org/10.1007/s10951-016-0478-9

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Weitere Artikel der Ausgabe 3/2017

A greedy approximation algorithm for minimum-gap scheduling

The local–global conjecture for scheduling with non-linear cost

The equivalence of two classical list scheduling algorithms for dependent typed tasks with release dates, due dates and precedence delays

Continuous-time production, distribution and financial planning with periodic liquidity balancing

Optimal scheduling of contract algorithms with soft deadlines

Two-machine flowshop scheduling with three-operation jobs subject to a fixed job sequence

Premium Partner