Distributionally robust scheduling algorithms for total flow time minimization on parallel machines using norm regularizations

Result code in IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21230%2F22%3A00354299" target="_blank" >RIV/68407700:21230/22:00354299 - isvavai.cz</a>

Alternative codes found

RIV/68407700:21730/22:00354299

Result on the web

<a href="https://doi.org/10.1016/j.ejor.2022.01.002" target="_blank" >https://doi.org/10.1016/j.ejor.2022.01.002</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1016/j.ejor.2022.01.002" target="_blank" >10.1016/j.ejor.2022.01.002</a>

Result language

angličtina

Original language name

Distributionally robust scheduling algorithms for total flow time minimization on parallel machines using norm regularizations

Original language description

In this paper, we study a distributionally robust parallel machines scheduling problem, minimizing the total flow time criterion. The distribution of uncertain processing times is subject to ambiguity belonging to a set of distributions with constrained mean and covariance. We show that the problem can be cast as a deterministic optimization problem, with the objective function composed of an expectation and a regularization term given as an ℓp norm. The main question we ask and answer is whether the particular choice of the used ℓp norm affects the computational complexity of the problem and the robustness of its solution. We prove that if durations of the jobs are independent, the solution in terms of any ℓp norm can be solved in a pseudopolynomial time, by the reduction to a non-linear bipartite matching problem. We also show an efficient, polynomial-time algorithm for ℓ1 case. Furthermore, for instances with dependent durations of the jobs, we propose computationally efficient formulation and an algorithm that uses ℓ1 norm. Moreover, we identify a class of covariance matrices admitting a faster, polynomial-time algorithm. The computational experiments show that the proposed algorithms provide solutions with a similar quality to the existing algorithms while having significantly better computational complexities.

Czech name

—

Czech description

—

Type

J_imp - Article in a specialist periodical, which is included in the Web of Science database

CEP classification

—

OECD FORD branch

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Project

<a href="/en/project/GA22-31670S" target="_blank" >GA22-31670S: Scheduling Tests in Medical Laboratories: Reduction of Turn-Around Time</a><br>

Continuities

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Publication year

2022

Confidentiality

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Name of the periodical

European Journal of Operational Research

ISSN

0377-2217

e-ISSN

1872-6860

Volume of the periodical

302

Issue of the periodical within the volume

2

Country of publishing house

NL - THE KINGDOM OF THE NETHERLANDS

Number of pages

18

Pages from-to

438-455

UT code for WoS article

000829764400003

EID of the result in the Scopus database

2-s2.0-85124263563