47055

Автор(ы): 

Автор(ов): 

2

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

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

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

Название: 

Estimation of the Absolute Error and Polynomial Solvability for a Classical NP-Hard Scheduling Problem

ISBN/ISSN: 

1064-5624

DOI: 

10.1134/S1064562418030201

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

  • Doklady Mathematics

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

Vol. 97, No 3

Город: 

  • Москва

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

  • Pleiades Publishing

Год издания: 

2018

Страницы: 

262-265
Аннотация
A method for finding an approximate solution for NP-hard scheduling problems is proposed. The example of the classical NP-hard in the strong sense problem of minimizing the maximum lateness of job processing with a single machine shows how a metric introduced on the instance space of the problem and polynomially solvable areas can be used to find an approximate solution with a guaranteed absolute error. The method is evaluated theoretically and experimentally and is compared with the ED-heuristic. Additionally, for the problem under consideration, we propose a numerical characteristic of polynomial unsolvability, namely, an upper bound for the guaranteed absolute error for each equivalence class of the instance space.

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

Лазарев А.А., Архипов Д.И. Estimation of the Absolute Error and Polynomial Solvability for a Classical NP-Hard Scheduling Problem / Doklady Mathematics. М.: Pleiades Publishing, 2018. Vol. 97, No 3. С. 262-265.

Публикация имеет версию на другом языке: 

Да

Связь с публикацией: