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

Kód výsledku v 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>

Nalezeny alternativní kódy

RIV/68407700:21730/22:00354299

Výsledek na webu

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

Jazyk výsledku

angličtina

Název v původním jazyce

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

Popis výsledku v původním jazyce

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.

Název v anglickém jazyce

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

Popis výsledku anglicky

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.

Druh

J_imp - Článek v periodiku v databázi Web of Science

CEP obor

—

OECD FORD obor

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

Projekt

<a href="/cs/project/GA22-31670S" target="_blank" >GA22-31670S: Rozvrhování prováděných testů ve zdravotnických laboratořích: zkrácení doby dodání výsledku</a><br>

Návaznosti

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

Rok uplatnění

2022

Kód důvěrnosti údajů

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

Název periodika

European Journal of Operational Research

ISSN

0377-2217

e-ISSN

1872-6860

Svazek periodika

302

Číslo periodika v rámci svazku

2

Stát vydavatele periodika

NL - Nizozemsko

Počet stran výsledku

18

Strana od-do

438-455

Kód UT WoS článku

000829764400003

EID výsledku v databázi Scopus

2-s2.0-85124263563