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

Research output: Contribution to journalArticle


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.

Original languageEnglish
Pages (from-to)381-393
Number of pages13
JournalInternational Transactions in Operational Research
Issue number1
Publication statusPublished - 1 Jan 2020



  • branch-and-bound algorithm
  • multiprocessor jobs
  • optima localization

Cite this