A New Structural Parameter on Single Machine Scheduling with Release Dates and Deadlines

In this paper we study the single machine scheduling problem with release dates, deadlines and precedence relations where the objective is to minimize the makespan. This is a well-known strongly NP-hard scheduling problem [18]. We analyze the problem from the parameterized complexity point of view. We propose parameter \(q\) which is the maximum number of time windows \([r_j, d_j)\) that can strictly include a time window \([r_i, d_i)\) on both ends. We show that problems \(1|prec, r_j, d_j|C_{max}\) and \(1|prec, r_j|L_{max}\) are fixed-parameter tractable parameterized by \(q\) . We use a dynamic programming approach and define a new dominance rule, which we call the weak earliest deadline rule. This rule narrows down the number of relevant scheduling prefixes enough to complete the search via a fixed-parameter tractable number of dynamic programming states.