69957

Автор(ы): 

Автор(ов): 

3

Параметры публикации

Тип публикации: 

Тезисы доклада

Название: 

Метрический подход для задач на быстродействие

ISBN/ISSN: 

978-5-907366-47-3

Наименование конференции: 

  • 20-я Всероссийская конференция с международным участием "Математические методы распознавания образов" (Москва, 2021)

Наименование источника: 

  • Сборник тезисов 20-й Всероссийской конференции с международным участием "Математические методы распознавания образов" (Москва, 2021)

Город: 

  • Москва

Издательство: 

  • Российская Академия наук

Год издания: 

2021

Страницы: 

466
Аннотация
Одним из подходов, используемых при рассмотрения NP-трудных задач теории расписаний, является метрический подход. Он основан на введении метрик, с помощью которых по исходному примеру, не являющемуся полиномиально разрешимым, проекцированием на известную полиномиално разрешимую область, получается оптимальное или приближённое решение. Рассматривается проблема минимизации задачи на быстродействие на двух параллельных приборах с использованием известных алгоритмов со сложностью O(n2) и O(e + nα(n)) для получения полиномиальных решений при рассмотрении работ, выполняемых за равные промежутки времени с заданной последовательностью выполнения: P 2|prec, pj = p|Cmax. Для получения оценки абсолютной погрешности и нахождении приближённого решения для задач теории расписаний проводится эксперимент.

Библиографическая ссылка: 

Кудинов И.Д., Букуева Е.С., Лемтюжникова Д.В. Метрический подход для задач на быстродействие / Сборник тезисов 20-й Всероссийской конференции с международным участием "Математические методы распознавания образов" (Москва, 2021). М.: Российская Академия наук, 2021. С. 466.