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

Отпечаток

Scheduling
Approximation algorithms
Byproducts
Branch-and-bound
Localization
Performance ratio
NP-hard
Upper bound
By-products
Schedule
Lower bounds
Guarantee

Цитировать

@article{2c10139924a246f8a0a5df9f0a1ec985,
title = "Branch-and-bound approach for optima localization in scheduling multiprocessor jobs",
abstract = "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.",
keywords = "branch-and-bound algorithm, multiprocessor jobs, optima localization",
author = "Alexander Kononov and Polina Kononova and Alexander Gordeev",
year = "2020",
month = "1",
day = "1",
doi = "10.1111/itor.12503",
language = "English",
volume = "27",
pages = "381--393",
journal = "International Transactions in Operational Research",
issn = "0969-6016",
number = "1",

}

Branch-and-bound approach for optima localization in scheduling multiprocessor jobs. / Kononov, Alexander; Kononova, Polina; Gordeev, Alexander.

В: International Transactions in Operational Research, Том 27, № 1, 01.01.2020, стр. 381-393.

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

TY - JOUR

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

AU - Kononov, Alexander

AU - Kononova, Polina

AU - Gordeev, Alexander

PY - 2020/1/1

Y1 - 2020/1/1

N2 - 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.

AB - 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.

KW - branch-and-bound algorithm

KW - multiprocessor jobs

KW - optima localization

UR - http://www.scopus.com/inward/record.url?scp=85070223396&partnerID=8YFLogxK

U2 - 10.1111/itor.12503

DO - 10.1111/itor.12503

M3 - Article

AN - SCOPUS:85070223396

VL - 27

SP - 381

EP - 393

JO - International Transactions in Operational Research

JF - International Transactions in Operational Research

SN - 0969-6016

IS - 1

ER -