• A
  • A
  • A
  • ABC
  • ABC
  • ABC
  • А
  • А
  • А
  • А
  • А
Regular version of the site

Article

Transforming a pseudo-polynomial algorithm for the single machine total tardiness maximization problem into a polynomial one

Annals of Operations Research. 2012. Vol. 196. No. 1. P. 247-261.
Gafarov E., Lazarev A. A., Werner F.

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.