15146

Автор(ы): 

Гафаров Е. Р. (ИПУ РАН, Лаборатория 68)
Лазарев А. А. (ИПУ РАН, Лаборатория 68)
Werner F. (?)

Автор(ов): 

3

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

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

Статья в журнале/сборнике

Название: 

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

ISBN/ISSN: 

0254-5330

Наименование источника: 

  • Annals of Operations Research

Обозначение и номер тома: 

DOI 10.1007/s10479-011-1055-4

Город: 

  • Berlin

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

  • Springer Verlag

Год издания: 

2012

Страницы: 

1-17 DOI 10.1007/s10479-011-1055-4
Аннотация
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

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

Гафаров Е.Р., Лазарев А.А., Werner F. Transforming a pseudo-polynomial algorithm for the single machine total tardiness maximization problem into a polynomial one // Annals of Operations Research. 2012. DOI 10.1007/s10479-011-1055-4. С. 1-17 DOI 10.1007/s10479-011-1055-4.