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

Full description

Saved in:
Bibliographic Details
Published in:International transactions in operational research 2020-01, Vol.27 (1), p.381-393
Main Authors: Kononov, Alexander, Kononova, Polina, Gordeev, Alexander
Format: Article
Language:English
Subjects:
Algorithms
branch‐and‐bound algorithm
Job shops
Localization
Lower bounds
Multiprocessing
multiprocessor jobs
Operations research
optima localization
Production scheduling
Schedules
Scheduling
Task scheduling
Upper bounds
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:0969-6016
1475-3995
DOI:10.1111/itor.12503