On unrelated machines every processing time is finite, and the problems on unrelated machines have no machine sets. A machine on which job $j$ may not run is instead encoded by a processing time too long for every schedule within the threshold. Four relations of the Scheduling Zoo rest on this encoding; each maps an instance with machine sets $M_j$ and threshold $D$ to an instance on unrelated machines with the same jobs, machines and times $p_{ij}$ for $i \in M_j$, and a long time for $i \notin M_j$.

• $P \mid M_j \mid C_{\max}$ to $R \mid\mid C_{\max}$ and $Q \mid M_j \mid \sum C_j$ to $R \mid\mid \sum C_j$: the time $D + 1$. A job on a machine outside its set completes after $D$, so a schedule within the threshold uses only the machines of the sets, and it is a schedule of the instance with machine sets of the same cost. A job without a machine in its set makes both instances infeasible within the threshold.
• $P \mid M_j \mid \sum w_jC_j$ to $R \mid\mid \sum w_jC_j$: the time $D + 1$ again. A job of positive weight on a machine outside its set costs more than $D$; a job of weight $0$ costs nothing anywhere and is moved to the end of a machine of its set. An instance with a job whose set is empty is mapped to a threshold that no schedule meets.
• $P \mid M_j \mid \sum w_jZ_j$ to $R \mid\mid \sum w_jZ_j$: the time $d_j + 1$, so a job outside its set is never just in time; such jobs are moved to the end of a machine of their set, which makes no just-in-time job late. An instance with a job whose set is empty is mapped to a threshold that no schedule meets.

Theorem. The decision version of each of the four problems with machine sets reduces to that of the problem on unrelated machines, with the same numbers of jobs and machines.

The reduction is computed on the standard words: a program reads the word of an instance with machine sets and its threshold and writes the word of the unrelated instance and its threshold, in polynomial time and with numbers at most one more than those it reads. So hardness goes up along the four relations.

Theorem. Along each of the four relations, NP-hardness and strong NP-hardness on the standard reading go from the problem with machine sets to the problem on unrelated machines, and so does W[t]-hardness for the number of machines.