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

Book chapter

Special Case of the Single Machine Total Tardiness Problem Is NP-Hard

Lazarev A. A., Gafarov E.

In this paper we show that the special case {\bf B-1} (Lazarev et al., 2004) of the single machine total tardiness problem $1||\sumT_j$ is NP-hard in the ordinary sense. For the case we have constructed pseudo-polynomial algorithm $O(n\sum p_j)$ time.