Structural parameters for scheduling with assignment restrictions

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 a graph framework based on the assignment restrictions and study the computational complexity of the scheduling problem with respect to structural properties of the resulting graphs, in particular, their tree- and cliquewidth. We identify cases that admit polynomial time approximation schemes or FPT algorithms generalizing and extending previous results in this area.

Authors

• Klaus Jansen
• Marten Maack
• Roberto Solis-Oba

Keywords

• Scheduling
• Approximation
• Approximation scheme
• FPT algorithm
• Treewidth
• Cliquewidth