Standard

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

In: International Transactions in Operational Research, Vol. 27, No. 1, 01.01.2020, p. 381-393.

Research output: Contribution to journal › Article › peer-review

Harvard

Kononov, A, Kononova, P & Gordeev, A 2020, 'Branch-and-bound approach for optima localization in scheduling multiprocessor jobs', International Transactions in Operational Research, vol. 27, no. 1, pp. 381-393. https://doi.org/10.1111/itor.12503

APA

Kononov, A., Kononova, P., & Gordeev, A. (2020). Branch-and-bound approach for optima localization in scheduling multiprocessor jobs. International Transactions in Operational Research, 27(1), 381-393. https://doi.org/10.1111/itor.12503

Vancouver

Kononov A, Kononova P, Gordeev A. Branch-and-bound approach for optima localization in scheduling multiprocessor jobs. International Transactions in Operational Research. 2020 Jan 1;27(1):381-393. doi: 10.1111/itor.12503

Author

Kononov, Alexander ; Kononova, Polina ; Gordeev, Alexander. / Branch-and-bound approach for optima localization in scheduling multiprocessor jobs. In: International Transactions in Operational Research. 2020 ; Vol. 27, No. 1. pp. 381-393.

BibTeX

@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",
note = "Publisher Copyright: {\textcopyright} 2017 The Authors. International Transactions in Operational Research {\textcopyright} 2017 International Federation of Operational Research Societies Copyright: Copyright 2019 Elsevier B.V., All rights reserved.",
year = "2020",
month = jan,
day = "1",
doi = "10.1111/itor.12503",
language = "English",
volume = "27",
pages = "381--393",
journal = "International Transactions in Operational Research",
issn = "0969-6016",
publisher = "Blackwell Publishing",
number = "1",

}

RIS

TY - JOUR

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

AU - Kononov, Alexander

AU - Kononova, Polina

AU - Gordeev, Alexander

N1 - Publisher Copyright: © 2017 The Authors. International Transactions in Operational Research © 2017 International Federation of Operational Research Societies Copyright: Copyright 2019 Elsevier B.V., All rights reserved.

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 -

ID: 21239932