16561

Автор(ы): 

Коренев П. С. (ИПУ РАН, Лаборатория 41)
Лазарев А. А. (ИПУ РАН, Лаборатория 68)

Автор(ов): 

2

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

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

Доклад

Название: 

An Approximation Scheme for the 1|r_j|\sum T_j Scheduling Problem with Guaranteed Absolute Error

ISBN/ISSN: 

9789081409940

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

  • 13th International Conference on Project Management and Scheduling (Leuven, April 1-4, 2012)

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

  • Proceedings of the 13th International Conference on Project Management and Scheduling (Leuven, Belgium, 2012)

Город: 

  • Leuven, Belgium

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

  • KATHOLIEKE UNIVERSITEIT LEUVEN

Год издания: 

2012

Страницы: 

195-198
Аннотация
In the paper, we consider the NP-hard total tardiness minimization on a single machine scheduling problem. We propose a metric for that problem and present a new polynomial approximation scheme based on search for the polynomially solvable instance which has a minimal distance in the metric from an initial instance.

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

Коренев П.С., Лазарев А.А. An Approximation Scheme for the 1|r_j|\sum T_j Scheduling Problem with Guaranteed Absolute Error / Proceedings of the 13th International Conference on Project Management and Scheduling (Leuven, Belgium, 2012). Leuven, Belgium: KATHOLIEKE UNIVERSITEIT LEUVEN, 2012. С. 195-198.