A note on reverse scheduling with maximum lateness objective

The inverse and reverse counterparts of the single-machine scheduling problem \(1||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 _{\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 _{\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||\sum \alpha _{j}T_{j}^{2}\).