Fixed Parameter Tractability of Scheduling Problems

We consider a single machine scheduling problem with n jobs. Each job has a processing time, a due date and a weight. The objective is to minimize the weighted number of late jobs. (This is a generalization of the classical knapsack problem.) This problem is well-known to be NP-Hard in the ordinary sense and a pseudo-polynomial time algorithm as well as a FPTAS are available for this problem. We show under which conditions this problem become tractable when the numbers of different due dates, different processing times, and different weights are bounded.

We use the theory of Fixed Parameter Complexity to determine the tractability of the problem as a function of how many different values its parameters may take. We discuss the differences between polynomial algorithms which are “good” and polynomial algorithms which are “very good”. We describe the hierarchy of complexity classes in Parameterized Complexity Theory and then we show under which conditions on the bounds on the numbers of different values of the parameters the problem considered fits in the various different classes.