On the Fine-grained Parameterized Complexity of Partial Scheduling to Minimize the Makespan.

We study a natural variant of scheduling that we call : in this variant an instance of a scheduling problem along with an integer  is given and one seeks an optimal schedule where not all, but only jobs, have to be processed. Specifically, we aim to determine the fine-grained parameterized complexity of partial scheduling problems parameterized by for all variants of scheduling problems that minimize the makespan and involve unit/arbitrary processing times, identical/unrelated parallel machines, release/due dates, and precedence constraints. That is, we investigate whether algorithms with runtimes of the type or exist for a function that is as small as possible.