Paper Info
Title
Distributionally robust scheduling algorithms for total flow time minimization on parallel machines using norm regularizations
Abstract
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 l(p) norm. The main question we ask and answer is whether the particular choice of the used l(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 l(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 l(1) case. Furthermore, for instances with dependent durations of the jobs, we propose computationally efficient formulation and an algorithm that uses l(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. (C) 2022 Elsevier B.V. All rights reserved.
Year
DOI
Venue
2022
10.1016/j.ejor.2022.01.002
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH
Keywords
DocType
Volume
Scheduling, Distributionally robust optimization, Uncertain processing time, Total flow time, Computational complexity
Journal
302
Issue
ISSN
Citations 
2
0377-2217
0
PageRank 
References 
Authors
0.34
0
3
Name
Order
Citations
PageRank
Antonin Novak172.86
Andrzej Gnatowski200.34
sůcha přemysl37413.96