A metric for total tardiness minimization
- Authors: Lazarev A.A.1,2,3,4, Korenev P.S.1,2, Sologub A.A.1,2
-
Affiliations:
- Trapeznikov Institute of Control Sciences
- Lomonosov State University
- Moscow Institute of Physics and Technology
- Higher School of Economics (National Research University)
- Issue: Vol 78, No 4 (2017)
- Pages: 732-740
- Section: Large Scale Systems Control
- URL: https://journals.rcsi.science/0005-1179/article/view/150585
- DOI: https://doi.org/10.1134/S0005117917040142
- ID: 150585
Cite item
Abstract
In this paper we consider the NP-hard 1|rj|ΣTj scheduling problem, suggesting a polynomial algorithm to find its approximate solution with the guaranteed absolute error. The algorithm employs a metric introduced in the parameter space. In addition, we study the possible application of such an approach to other scheduling problems.
About the authors
A. A. Lazarev
Trapeznikov Institute of Control Sciences; Lomonosov State University; Moscow Institute of Physics and Technology; Higher School of Economics (National Research University)
Author for correspondence.
Email: jobmath@mail.ru
Russian Federation, Moscow; Moscow; Moscow; Moscow
P. S. Korenev
Trapeznikov Institute of Control Sciences; Lomonosov State University
Email: jobmath@mail.ru
Russian Federation, Moscow; Moscow
A. A. Sologub
Trapeznikov Institute of Control Sciences; Lomonosov State University
Email: jobmath@mail.ru
Russian Federation, Moscow; Moscow