Estimation of the Absolute Error and Polynomial Solvability for a Classical NP-Hard Scheduling Problem
- Авторы: Lazarev A.1,2,3,4, Arkhipov D.1
-
Учреждения:
- Trapeznikov Institute of Control Sciences
- National Research University Higher School of Economics
- Faculty of Physics
- Moscow Institute of Physics and Technology (State University)
- Выпуск: Том 97, № 3 (2018)
- Страницы: 262-265
- Раздел: Mathematics
- URL: https://journals.rcsi.science/1064-5624/article/view/225509
- DOI: https://doi.org/10.1134/S1064562418030201
- ID: 225509
Цитировать
Аннотация
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.
Об авторах
A. Lazarev
Trapeznikov Institute of Control Sciences; National Research University Higher School of Economics; Faculty of Physics; Moscow Institute of Physics and Technology (State University)
Автор, ответственный за переписку.
Email: jobmath@mail.ru
Россия, Moscow, 117997; Moscow, 101000; Moscow, 119992; Dolgoprudnyi, Moscow oblast, 141700
D. Arkhipov
Trapeznikov Institute of Control Sciences
Email: jobmath@mail.ru
Россия, Moscow, 117997