A note on reverse scheduling with maximum lateness objective

The inverse and reverse counterparts of the single‐machine scheduling problem $1\mid \mid L_{\max }$ are studied in [2], in which the complexity classification is provided for various combinations of adjustable parameters (due dates and processing times) and for five different types of norm: ${\ell }_1,{\ell }_2,{\ell }_{\mathrm{\infty }},{\ell }_H^{\Sigma }$ , and ${\ell }_H^{\max }$ . It appears that the $O(n^2)$ ‐time algorithm for the reverse problem with adjustable due dates contains a flaw. In this note, we present the structural properties of the reverse model, establishing a link with the forward scheduling problem with due dates and deadlines. For the four norms ${\ell }_1,{\ell }_{\mathrm{\infty }},{\ell }_H^{\Sigma }$ , and ${\ell }_H^{\max }$ , the complexity results are derived based on the properties of the corresponding forward problems, while the case of the norm ${\ell }_2$ is treated separately. As a by‐product, we resolve an open question on the complexity of problem $1\mid \mid \sum {\alpha }_j{T}_j^2$ .