|
ИСТИНА |
Войти в систему Регистрация |
ИПМех РАН |
||
Estimation of the Absolute Error and Polynomial Solvability for a Classical NP-Hard Scheduling Problemстатья
Информация о цитировании статьи получена из
Web of Science,
Scopus
Статья опубликована в журнале из списка Web of Science и/или Scopus
Дата последнего поиска статьи во внешних источниках: 7 сентября 2018 г.
- Авторы: Лазарев А.А., Архипов Д.И.
- Журнал: Doklady Mathematics
- Том: 97
- Номер: 3
- Год издания: 2018
- Издательство: Maik Nauka/Interperiodica Publishing
- Местоположение издательства: Russian Federation
- Первая страница: 262
- Последняя страница: 265
- DOI: 10.1134/S1064562418030201
- Аннотация: 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.
- Добавил в систему: Лазарев Александр Алексеевич
Прикрепленные файлы
| № | Имя | Описание | Имя файла | Размер | Добавлен |
|---|---|---|---|---|---|
| 1. | Doklady_mathematics_2018.pdf | Doklady_mathematics_2018.pdf | 196,2 КБ | 6 сентября 2018 [Lazarev] | |
| 2. | 30984-47055.pdf | 30984-47055.pdf | 196,2 КБ | 6 сентября 2018 [Lazarev] |