Theorem 12. Let $I$ be an instance whose due dates are day-independent, so that client $j$ has one due date $d_j$ on every day. Order the clients by due date and process them in that order, carrying as state, for every day, the time at which that day's machine becomes free. Serving a client on a set of days requires that on each of those days the machine be free early enough for its job to be completed at its due date, and leaves the machine of each of those days free from that due date onwards. The instance admits a $k$-fair schedule if and only if the program, started with every machine free from time $0$ and applied to the clients in due-date order, can serve every client on $k$ days.

Processing the clients in due-date order is what makes the state sufficient: a client considered later has a due date at least as large, so the only thing a decision about the earlier clients can leave behind that matters is how late each machine is occupied. For a constant number $m$ of days the number of reachable states is polynomial, and the program decides the problem in polynomial time.