We consider the problem of maximizing total tardiness on a single machine,
where the first job starts at time zero and idle times between the processing of jobs are not allowed. We present a modification of an exact pseudo-polynomial algorithm based on a graphical approach, which has a polynomial running time. This result settles the complexity
status of the problem under consideration which was open
E.R. Gafarov, A.A. Lazarev and F. Werner (2012), Transforming a pseudo-polynomial algorithm for the single machine total tardiness maximization problem into a polynomial one. Annals of Operations Research, 196 (1), 247-261. (journal impact factor 2018: 2.284). Q1