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

• Author: Alexander Kononov,Alexander Gordeev,Polina Kononova
• Date: 01 January 2020
• Published date: 01 January 2020
• DOI: http://doi.org/10.1111/itor.12503

Intl. Trans. in Op. Res. 27 (2020) 381–393

DOI: 10.1111/itor.12503

INTERNATIONAL

TRANSACTIONS

IN OPERATIONAL

RESEARCH

Branch-and-bound approach for optima localization

in scheduling multiprocessor jobs

Alexander Kononova,b, Polina Kononovaa,b and Alexander Gordeeva

aTemporaryResearch Group “Optimization”, Sobolev Institute of Mathematics, 4, Akad. Koptyug Avenue,630090

Novosibirsk, Russia

bDepartment of Mechanics and Mathematics, NovosibirskState University, 2, Pirogova Str., 630090 Novosibirsk, Russia

E-mail: alvenko@math.nsc.ru [Kononov];polik83@ngs.ru [Kononova]; agordeevw@gmail.com [Gordeev]

Received 5 February2017; received in revised form 25 August 2017; accepted 25 August 2017

Abstract

We consider multiprocessor task scheduling problems with dedicated processors. We determine the tight

optima localization intervalsfor different subproblems of the basic problem.Based on the ideas of a computer-

aided technique developed bySevastianov and Tchernykhfor shop scheduling problems, we elaboratea 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:multiprocessor jobs; branch-and-bound algorithm; optima localization

1. Introduction

We consider adjacent single-mode multiprocessor jobs. Set J={J1, ..., Jn}of jobs and set Mof

processors are given. Each job has processing time τjand may require more than one processor

simultaneously. We assume that the set of processors required by a job is given and fixed. Addition-

ally,we assume that processors are the vertices of a given graph G=(M,E)and the required set of

processors must induce a connected subgraphof G.Byμi⊆Mdenotethe set of processors required

by job Ji.LetJAdenote the set of jobs requiring processors in set A,thatis,JA={Ji:μi=A}.

We will say that jobs in set JAare of type A.

A schedule σis an assignment of each job Jito an interval of length τi, such that for any two

conflicting jobs Jiand Jjwith μi∩μj=∅, their intervals do not overlap. It is required to find a

schedule that minimizes the makespan. For the given graph G, we denote the above problem by

(G);OPT stands for the optimum.

C

2017 The Authors.

International Transactionsin Operational Research C

2017 International Federation ofOperational Research Societies

Published by John Wiley & Sons Ltd, 9600 Garsington Road, Oxford OX4 2DQ, UK and 350 Main St, Malden, MA02148,

USA.