Branch-and-bound approach for optima localization in scheduling multiprocessor jobs

Результат исследования: Научные публикации в периодических изданияхстатья

Аннотация

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 computer-aided technique developed by Sevastianov and Tchernykh for shop scheduling problems, we elaborate a similar method 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.

Язык оригиналаанглийский
Страницы (с-по)381-393
Число страниц13
ЖурналInternational Transactions in Operational Research
Том27
Номер выпуска1
DOI
СостояниеОпубликовано - 1 янв 2020

Fingerprint Подробные сведения о темах исследования «Branch-and-bound approach for optima localization in scheduling multiprocessor jobs». Вместе они формируют уникальный семантический отпечаток (fingerprint).

  • Цитировать