Theorem 1. The problem $1 \mid \mathrm{rep} \mid \min_j \sum_i Z_{i,j}$ is solvable in polynomial time when $k \in \{0,\, m-1,\, m\}$. For every fixed pair $(m,k)$ with $0<k<m-1$, the problem is NP-hard.

The three tractable values are settled separately: $k = 0$ and $k = m$ by inspection of the instance, and $k = m-1$ by a reduction to 2-satisfiability. Hardness holds already for every fixed pair $(m, k)$ with $m \ge 3$ and $0 < k < m-1$; it is obtained for $(3,1)$ from a satisfiability problem of bounded occurrence and lifted to all other pairs by two constructions adding one day at a time.

Let $I$ be an instance with $n$ clients and $m$ days. The day $i$ conflict graph of $I$ is the graph on the $n$ clients in which two clients are adjacent if their jobs of day $i$ conflict. The overall conflict graph of $I$ is the graph on the $n$ clients in which two clients are adjacent if their jobs conflict on at least one day; its edge set is the union of the edge sets of the $m$ daily graphs.

A day's conflict graph is the intersection graph of that day's $n$ intervals, so it is an interval graph. The observation the results of the source rest on is that a set of clients can be served on day $i$ exactly when it is an independent set of the day $i$ conflict graph: a schedule is feasible if and only if each of its days is independent in that day's graph.

The treewidth $\tau$ of the overall conflict graph is the structural parameter measured in the last section of the source, and it is the archive's treewidth.

A tree decomposition of a graph is a tree whose nodes carry bags of vertices such that every vertex and every edge lies in a bag and the nodes whose bags contain a fixed vertex form a connected subtree; its width is the largest bag size minus one. It is nice if its nodes are of four kinds: a leaf, an introduce node whose bag is the bag of its single child plus one vertex, a forget node whose bag is the bag of its single child minus one vertex, and a join node with two children whose bags equal its own.

Bodlaender's theorem. For every constant $w$ one can decide in linear time whether a graph has treewidth at most $w$, and if so construct a tree decomposition of width at most $w$; the dependence on $w$ is $2^{O(w^3)}$. Kloks' construction turns any tree decomposition of width $w$ into a nice one of the same width in time linear in the size of the decomposition, so the same holds for nice decompositions.

Bodlaender, "A linear-time algorithm for finding tree-decompositions of small treewidth", SIAM Journal on Computing 25 (1996) 1305–1317; Kloks, "Treewidth: Computations and Approximations", Lecture Notes in Computer Science 842, Springer 1994. Cited by Heeger–Hermelin–Itzhaki–Molter–Shabtay for Theorem 4's second bullet.

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.

Corollary 8. The problem $1 \mid \mathrm{rep},\, p_{i,j} = p_j \mid \min_j \sum_i Z_{i,j}$ is NP-hard whenever $m \ge 3$ and $0 < k < m-1$.

Two constructions lift hardness from one pair $(m, k)$ to the next. Adding a single day on which no two jobs conflict raises the attainable fairness by exactly one, so hardness for $(m, k)$ gives hardness for $(m+1, k+1)$: every client is served on the new day, and on the old days nothing has changed. Adding one day together with one new client raises the number of days at $k = 1$: the new client's job blocks every job on each of the old days, and on the new day all jobs coincide, so a $1$-fair schedule must serve the new client on the new day and is otherwise a $1$-fair schedule of the old instance. Together with the base case $(m, k) = (3, 1)$ these two steps reach every pair with $m \ge 3$ and $0 < k < m-1$.

Both constructions give the new day the processing times of the first day, so an instance with day-independent processing times is sent to one with day-independent processing times, which is what makes the corollary a statement about that restriction.