Abstract
We consider scheduling on identical and unrelated parallel machines with job assignment restrictions. These problems are NP-hard and they do not admit polynomial time approximation algorithms with approximation ratios smaller than 1.5 unless P = NP. However, if we impose limitations on the set of machines that can process a job, the problem sometimes becomes easier in the sense that algorithms with approximation ratios better than 1.5 exist. We introduce three graphs, based on the assignment restrictions and study the computational complexity of the scheduling problem with respect to structural properties of these graphs, in particular their tree- and rankwidth. We identify cases that admit polynomial time approximation schemes or FPT algorithms, generalizing and extending previous results in this area.
This work was partially supported by the DAAD (Deutscher Akademischer Austauschdienst) and by the German Research Foundation (DFG) project JA 612/15-1.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
References
Szeider, S.: On fixed-parameter tractable parameterizations of SAT. In: Giunchiglia, E., Tacchella, A. (eds.) SAT 2003. LNCS, vol. 2919, pp. 188–202. Springer, Heidelberg (2004). doi:10.1007/978-3-540-24605-3_15
Samer, M., Szeider, S.: Constraint satisfaction with bounded treewidth revisited. J. Comput. Syst. Sci. 76(2), 103–114 (2010)
Lenstra, J.K., Shmoys, D.B., Tardos, É.: Approximation algorithms for scheduling unrelated parallel machines. Math. Program. 46(1–3), 259–271 (1990)
Horowitz, E., Sahni, S.: Exact and approximate algorithms for scheduling nonidentical processors. J. ACM (JACM) 23(2), 317–327 (1976)
Ebenlendr, T., Krčál, M., Sgall, J.: Graph balancing: a special case of scheduling unrelated parallel machines. Algorithmica 68(1), 62–80 (2014)
Lee, K., Leung, J.Y.T., Pinedo, M.L.: A note on graph balancing problems with restrictions. Inf. Process. Lett. 110(1), 24–29 (2009)
Asahiro, Y., Miyano, E., Ono, H.: Graph classes and the complexity of the graph orientation minimizing the maximum weighted outdegree. Discret. Appl. Math. 159(7), 498–508 (2011)
Ou, J., Leung, J.Y.T., Li, C.L.: Scheduling parallel machines with inclusive processing set restrictions. Naval Res. Logist. (NRL) 55(4), 328–338 (2008)
Epstein, L., Levin, A.: Scheduling with processing set restrictions: PTAS results for several variants. Int. J. Prod. Econ. 133(2), 586–595 (2011)
Muratore, G., Schwarz, U.M., Woeginger, G.J.: Parallel machine scheduling with nested job assignment restrictions. Oper. Res. Lett. 38(1), 47–50 (2010)
Mnich, M., Wiese, A.: Scheduling and fixed-parameter tractability. Math. Program. 154(1–2), 533–562 (2015)
Knop, D., Kouteckỳ, M.: Scheduling meets n-fold integer programming. arXiv preprint arXiv:1603.02611 [cs.DS] (2016)
Szeider, S.: Not so easy problems for tree decomposable graphs. In: International Conference on Discrete Mathematics (2008)
Giakoumakis, V., Vanherpe, J.M.: Linear time recognition of weak bisplit graphs. Electron. Notes Discret. Math. 5, 138–141 (2000)
Jansen, K., Maack, M., Solis-Oba, R.: Structural parameters for scheduling with assignment restrictions. arXiv preprint arXiv:1701.07242 [cs.DS] (2017)
Bodlaender, H.L.: A partial k-arboretum of graphs with bounded treewidth. Theoret. Comput. Sci. 209(1), 1–45 (1998)
Bodlaender, H.L.: A linear-time algorithm for finding tree-decompositions of small treewidth. SIAM J. Comput. 25(6), 1305–1317 (1996)
Arnborg, S., Corneil, D.G., Proskurowski, A.: Complexity of finding embeddings in a k-tree. SIAM J. Algebraic Discret. Methods 8(2), 277–284 (1987)
Hlinenỳ, P., Oum, S.I.: Finding branch-decompositions and rank-decompositions. SIAM J. Comput. 38(3), 1012–1032 (2008)
Kolaitis, P.G., Vardi, M.Y.: Conjunctive-query containment and constraint satisfaction. J. Comput. Syst. Sci. 61, 302–332 (1998)
Acknowledgements
The Rounding Lemma in the presented form was formulated by Lars Rohwedder and Kevin Prohn as part of a student project.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2017 Springer International Publishing AG
About this paper
Cite this paper
Jansen, K., Maack, M., Solis-Oba, R. (2017). Structural Parameters for Scheduling with Assignment Restrictions. In: Fotakis, D., Pagourtzis, A., Paschos, V. (eds) Algorithms and Complexity. CIAC 2017. Lecture Notes in Computer Science(), vol 10236. Springer, Cham. https://doi.org/10.1007/978-3-319-57586-5_30
Download citation
DOI: https://doi.org/10.1007/978-3-319-57586-5_30
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-57585-8
Online ISBN: 978-3-319-57586-5
eBook Packages: Computer ScienceComputer Science (R0)