• A
  • A
  • A
  • АБB
  • АБB
  • АБB
  • А
  • А
  • А
  • А
  • А
Обычная версия сайта

Глава

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.