|
ИСТИНА |
Войти в систему Регистрация |
ИСТИНА ПсковГУ |
||
Branch-and-bound approach for optima localization in scheduling multiprocessor jobsстатья
Информация о цитировании статьи получена из
Scopus
Статья опубликована в журнале из списка Web of Science и/или Scopus
Дата последнего поиска статьи во внешних источниках: 8 октября 2025 г.
- Авторы: Kononov A., Kononova P., Gordeev A.
- Журнал: International transactions in operational research : a journal of The International Federation of Operational Research Societies
- Том: 27
- Номер: 1
- Год издания: 2020
- Издательство: Blackwell Publishers
- Местоположение издательства: Oxford, UK, England
- Первая страница: 381
- Последняя страница: 393
- DOI: 10.1111/itor.12503
- Аннотация: We consider multiprocessor task scheduling problems with dedicated processors. We determine the tight optima localization intervals for different subproblems of the basic problem. Based on the ideas of a computeraided technique developed by Sevastianov and Tchernykh for shop scheduling problems, we elaborate a similarmethod for the multiprocessor task scheduling problem. Our method allows us to find an upper bound for the length of the optimal schedule in terms of natural lower bound. As a byproduct of our results, a family of linear-time approximation algorithms with a constant ratio performance guarantee is designed for the NP-hard subproblems of the basic problem, and new polynomially solvable classes of problems are found.
- Добавил в систему: Кононов Александр Вениаминович