Theorem 7. The problem $1 \mid \mathrm{rep},\, p_{i,j} = p \mid \min_j \sum_i Z_{i,j}$ is NP-hard for $k = 1$ and $m = 3$.

Let $\varphi$ be a [2,3]-bounded 3-SAT formula with $n$ variables, $\ell$ clauses of two literals and $q$ clauses of three literals. Build an instance with three days and the clients: three dummies; two clients $x_v^1, x_v^0$ per variable $v$; and one client per occurrence of a literal in a clause. Every processing time is $2$, so two jobs of a day conflict exactly when their due dates differ by at most one, and the whole construction is a matter of placing due dates on a line, three times.

On the first day the due dates are $2$ for the three dummies, $2v+5$ for both clients of variable $v$, $2n+2j+7$ for both clients of the $j$-th clause of two literals, and $2n+2\ell+2j+9$ for all three clients of the $j$-th clause of three literals. Clients sharing a due date conflict and nothing else does, so the first day admits one client out of each group: one dummy, one of $x_v^1 / x_v^0$ — this is the truth assignment — and one client of every clause. On the second day the dummies, the variable clients and the clients of the clauses of two literals all have the due date $2$, so they are pairwise conflicting, while the clients of the $j$-th clause of three literals sit alone at $3j+6$; since a dummy runs on every day, the second day is a dead end for everything but one client of each clause of three literals. On the third day $x_v^1$ sits at $10v+6$ and $x_v^0$ at $10v+11$, while an occurrence of the literal $v$ sits at $10v+5$ or $10v+7$ and an occurrence of $\lnot v$ at $10v+10$ or $10v+12$, according to which of its at most two occurrences it is. So on the third day a client of an occurrence conflicts with exactly the variable client that falsifies its literal, and with nothing else.

The three dummies conflict with each other on all three days, so a $1$-fair schedule runs exactly one of them on each day. This is what forces the selection on the first day and makes the second day a dead end, and a client of an occurrence can then be served only on the third day — which is possible exactly when the assignment selected on the first day makes its literal true.