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

Research output: Contribution to journalArticle

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.

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

    Fingerprint

Keywords

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

Cite this