Estimation of the Absolute Error and Polynomial Solvability for a Classical NP-Hard Scheduling Problem
- Autores: Lazarev A.1,2,3,4, Arkhipov D.1
-
Afiliações:
- Trapeznikov Institute of Control Sciences
- National Research University Higher School of Economics
- Faculty of Physics
- Moscow Institute of Physics and Technology (State University)
- Edição: Volume 97, Nº 3 (2018)
- Páginas: 262-265
- Seção: Mathematics
- URL: https://journals.rcsi.science/1064-5624/article/view/225509
- DOI: https://doi.org/10.1134/S1064562418030201
- ID: 225509
Citar
Resumo
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.
Sobre autores
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)
Autor responsável pela correspondência
Email: jobmath@mail.ru
Rússia, Moscow, 117997; Moscow, 101000; Moscow, 119992; Dolgoprudnyi, Moscow oblast, 141700
D. Arkhipov
Trapeznikov Institute of Control Sciences
Email: jobmath@mail.ru
Rússia, Moscow, 117997