Отправить статью по E-mail Minimization of the maximal lateness for a single machine
- Авторы: Lazarev A.A.1,2,3,4, Arkhipov D.I.1
-
Учреждения:
- Trapeznikov Institute of Control Sciences
- National Research University Higher School of Economics
- Lomonosov State University
- Moscow Physical and Technical Institute
- Выпуск: Том 77, № 4 (2016)
- Страницы: 656-671
- Раздел: Intellectual Control Systems
- URL: https://ogarev-online.ru/0005-1179/article/view/150305
- DOI: https://doi.org/10.1134/S000511791604010X
- ID: 150305
Цитировать
Открытый доступ
Доступ предоставлен
Только для подписчиков
Аннотация
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.
Ключевые слова
Об авторах
A. Lazarev
Trapeznikov Institute of Control Sciences; National Research University Higher School of Economics; Lomonosov State University; Moscow Physical and Technical Institute
Автор, ответственный за переписку.
Email: jobmath@mail.ru
Россия, Moscow; Moscow; Moscow; Dolgoprudnyi
D. Arkhipov
Trapeznikov Institute of Control Sciences
Email: jobmath@mail.ru
Россия, Moscow
Дополнительные файлы
