Fixed-parameter tractability analysis and scheduling are two core domains of combinatorial optimization which led to deep understanding of many important algorithmic questions. However, even though fixed-parameter algorithms are appealing for many reasons, no such algorithms are known for many fundamental scheduling problems. In this paper we present the first fixed-parameter algorithms for classical scheduling problems such as makespan minimization, scheduling with job-dependent cost functions-one important example being weighted flow time-and scheduling with rejection. To this end, we identify crucial parameters that determine the problems' complexity. In particular, we manage to cope with the problem complexity stemming from numeric input values, such as job processing times, which is usually a core bottleneck in the design of fixed-parameter algorithms. We complement our algorithms with W[1]-hardness results showing that for smaller sets of parameters the respective problems do not allow FPT-algorithms. In particular, our positive and negative results for scheduling with rejection explore a research direction proposed by D 'aniel Marx. We hope that our contribution yields a new and fresh perspective on scheduling and fixed-parameter algorithms and will lead to further fruitful interdisciplinary research connecting these two areas.
It is shown that the Precedence Constrained K-Processor Scheduling problem is hard for the parameterized complexity class W[2]. This means that there does not exist a constant c, such that for all fixed K, the Precedence Constrained K-Processor Scheduling problem can be solved in O(n^c) time, unless an unlikely collapse occurs in the parameterized complexity hierarchy. That is, if the problem can be solved in polynomial time for each fixed K, then it is likely that the degree of the running time polynomial must increase as the number of processors K increases. Given a set T of tasks, each of unit length and having an individual deadline d(t) ∈ Z+, a set of precedence constraints on T, and a positive integer k ≤ |T|, we can ask "Is there a one-processor schedule for T that obeys the precedence constraints and contains no more than k late tasks?" This is a well-known NP-complete problem.We might also inquire "Is there a one-processor schedule for T that obeys the precedence constraints and contains at least k tasks that are on time i.e. no more than |T| - k late tasks?"Within the framework of classical complexity theory, these two questions are merely different instances of the same problem. Within the recently developed framework of parameterized complexity theory, however, they give rise to two separate problems that may be studied independently of one another.We investigate these problems from the parameterized point of view. We show that, in the general case, both these problems are hard for the parameterized complexity class W[1].In contrast, in the case where the set of precedence constraints can be modelled by a partial order of bounded width, we show that both these problems are fixed parameter tractable. 