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

Article

Algorithms for Special Cases of the Single Machine Total Tardiness Problem and an Application to the Even-Odd Partition Problem

Mathematical and Computer Modelling. 2009. Vol. 49. No. 9-10. P. 2061-2072.
Lazarev A. A., Werner F.

The scheduling problem of minimizing total tardiness on a single machine is known to be NP-hard in the ordinary sense. In this paper, we consider the special case of the problem when the processing times p_j and the due dates d_j of the jobs are oppositely ordered: p_1 >= p_2>=...>=p_n and d_1.