Premium
Branch‐and‐bound approach for optima localization in scheduling multiprocessor jobs
Author(s) -
Koov Alexander,
Koova Polina,
Gordeev Alexander
Publication year - 2020
Publication title -
international transactions in operational research
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.032
H-Index - 52
eISSN - 1475-3995
pISSN - 0969-6016
DOI - 10.1111/itor.12503
Subject(s) - multiprocessor scheduling , multiprocessing , computer science , scheduling (production processes) , mathematical optimization , upper and lower bounds , job shop scheduling , schedule , parallel computing , branch and bound , algorithm , mathematics , flow shop scheduling , mathematical analysis , operating system
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.