Running a schedule backwards from a horizon $H$ turns a piece processing an operation during $[a, b]$ into one processing it during $[H - b, H - a]$. A job that completes at $C_j$ then starts at $H - C_j$, and a precedence constraint $C_i + l_{ij} \le S_j$ becomes the constraint $C'_j + l_{ij} \le S'_i$ of the reversed relation.

Hence the maximum lateness without release dates and the makespan with release dates are equivalent:

• $L_{\max} \le D$ for due dates $d_j$ exactly if the reversed problem with release dates $r'_j = H - (d_j + D)$, $H = \max_j (d_j + D)$, has makespan at most $H$ (if some $d_j + D$ is negative, or there are no jobs and $D$ is negative, the threshold is $-1$);
• $C_{\max} \le D$ for release dates $r_j$ exactly if the reversed problem without release dates and with due dates $D - r_j$ has maximum lateness at most $0$ (if $D$ is negative or some $r_j$ exceeds $D$, the answer is no, and the reduction asks whether the maximum lateness for due dates $0$ is at most $-1$).

This is shown for the problems of the family with operations that have one operation per job, no restarts, a reversible precedence class, no deadlines, and none of the communication delays, server, forbidden times, transportation delays, no-idle and batch setups, whose meaning changes under reversal. The reversed specification has the reversed precedence class, the release dates or none, and the makespan or the maximum lateness.

A specification $s$ reduces to $t$ by reversal if it is of this kind, and either minimizes the maximum lateness without release dates and its reversal with release dates and the makespan is field by field a special case of $t$, or minimizes the makespan with release dates or none and its reversal without release dates and with the maximum lateness is so. The relation is decidable.

Theorem. A specification that reduces to another by reversal describes a problem whose decision version reduces to that of the other.