Email this article Minimization of the maximal lateness for a single machine
- Authors: Lazarev A.A.1,2,3,4, Arkhipov D.I.1
-
Affiliations:
- Trapeznikov Institute of Control Sciences
- National Research University Higher School of Economics
- Lomonosov State University
- Moscow Physical and Technical Institute
- Issue: Vol 77, No 4 (2016)
- Pages: 656-671
- Section: Intellectual Control Systems
- URL: https://ogarev-online.ru/0005-1179/article/view/150305
- DOI: https://doi.org/10.1134/S000511791604010X
- ID: 150305
Cite item
Open Access
Access granted
Subscription Access
Abstract
Consideration was given to the classical NP-hard problem 1|rj|Lmax of the scheduling theory. An algorithm to determine the optimal schedule of processing n jobs where the job parameters satisfy a system of linear constraints was presented. The polynomially solvable area of the problem 1|rj|Lmax was expanded. An algorithm was described to construct a Pareto-optimal set of schedules by the criteria Lmax and Cmax for complexity of O(n3logn) operations.
About the authors
A. A. Lazarev
Trapeznikov Institute of Control Sciences; National Research University Higher School of Economics; Lomonosov State University; Moscow Physical and Technical Institute
Author for correspondence.
Email: jobmath@mail.ru
Russian Federation, Moscow; Moscow; Moscow; Dolgoprudnyi
D. I. Arkhipov
Trapeznikov Institute of Control Sciences
Email: jobmath@mail.ru
Russian Federation, Moscow
Supplementary files
