4465

Автор(ы): 

Автор(ов): 

2

Параметры публикации

Тип публикации: 

Доклад

Название: 

Algorithms for Single Machine Total Tardiness Problem 1 | Σ Tj

Наименование конференции: 

  • International Conference on Operations Research, -- Karlsruhe, Germany, 2006

Город: 

  • Karlsruhe

Издательство: 

  • -

Год издания: 

2006

Страницы: 

-
Аннотация
We have proofed that the special case {\bf B-1} of the problemwhen $d_{max}-d_{min} \leq p_{min}$ is NP-hard in the ordinarysense. We have proposed a polynomial scheme of reduction fromNP-complete {\bf Partition Problem} to the special case {\bf B-1}of the problem $1\mid\,\mid\sum T_j$. For this case apseudo-polynomial algorithm with run time $O(n\sum p_j)$ and exactalgorithm for $p_j \notin Z$ have been constructed. Therefore wecan decide the {\bf Partition Problem} when parameters are notinteger.

Библиографическая ссылка: 

Гафаров Е.Р., Лазарев А.А. Algorithms for Single Machine Total Tardiness Problem 1 | Σ Tj / . Karlsruhe: -, 2006. С. -.