Consider the problems assembled from arbitrary constraint modules over a kernel and the completion-time objectives.

Some relations between objectives hold for decision versions only. Let $D$ be an integer.

• The makespan is at most $D$ exactly if no job is late for the common due date $D$: $C_{\max} \le D$ if and only if $\sum_j U_j \le 0$. For negative $D$ both sides are made false: the due date is $0$ and the threshold $-1$.
• The maximum lateness is at most $D$ exactly if no job is tardy for the due dates $d_j + D$: $L_{\max} \le D$ if and only if $\sum_j T_j \le 0$. If some $d_j + D$ is negative, or there are no jobs and $D$ is negative, the left side is false and the threshold is $-1$.
• The maximum lateness is at most $D$ exactly if no job is late for the due dates $d_j + D$: $L_{\max} \le D$ if and only if $\sum_j U_j \le 0$, with the same treatment of negative due dates.
• Flow time is tardiness for the due dates $d_j = r_j$: $\sum_j w_j F_j$ and $\sum_j w_j T_j$ with these due dates are the same cost, weighted or not.
• If every job completes no earlier than its release date in every feasible schedule, the maximum flow time is the maximum lateness for the due dates $d_j = r_j$.
• If every job completes no earlier than its release date in every feasible schedule, then $\sum_j w_j F_j = \sum_j w_j C_j - \sum_j w_j r_j$, so $\sum_j w_j C_j \le D$ if and only if $\sum_j w_j F_j \le D - \sum_j w_j r_j$; likewise without weights.

In all cases the kernel instance, the data of the constraint modules and the schedule are unchanged.

A specification $s$ reduces to a specification $t$ if $s$ is field by field a special case of $t$, possibly after replacing the makespan or maximum lateness of $s$ by the number of late jobs or by the total tardiness, or the total flow time of $s$, weighted or not, by the total tardiness. It reduces to $t$ through flow time if it is so after replacing the total completion time of $s$ by the total flow time, weighted or not, or the maximum flow time by the maximum lateness. Both relations are decidable.

Theorem. The equivalences hold. If the constraint modules are sound and $s$ reduces to $t$, then the decision version of the problem of $s$ reduces to that of the problem of $t$; the same holds for reductions through flow time if release dates are respected.

Theorem. Every reduction obtained from these steps and a field-wise comparison is in place: it keeps the kernel instance and every invariant parameter of a constraint field, and changes only the due dates and the threshold.