60108

Автор(ы): 

Автор(ов): 

4

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

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

Доклад

Название: 

Генерация примеров задачи теории расписаний для одного прибора, оценка их сложности и мера неразрешимости

ISBN/ISSN: 

978-5-91995-074-5

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

  • 13-я Мультиконференция по проблемам управления (МКПУ-2020): конференция "Математическая теория управления и ее приложения'' (МТУиП-2020). Санкт-Петербург, 6–8 октября 2020 г.

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

  • Труды 13-й Мультиконференции по проблемам управления (МКПУ-2020). Санкт-Петербург, 6-8 октября 2020 г.

Город: 

  • Санкт-Петербург

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

  • АО «Концерн «ЦНИИ «Электроприбор»

Год издания: 

2020

Страницы: 

221-223
Аннотация
Используется метод ветвей и границ для получения точного решения задачи теории расписаний для одного прибора с целевой функцией максимального временного смещения. Оценки осуществляются при помощи решения двойственной задачи. В качестве сложности примеров используется такая машиннонезависимая величина, как количество точек ветвления в дереве поиска. Представлены известные и новые разработанные способы поиска примеров (с большим количеством точек ветвления), а также описаны преимущества и недостатки каждого из них.

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

Лазарев А.А., Правдивец Н.А., Гришин Е.М., Галахов С.А. Генерация примеров задачи теории расписаний для одного прибора, оценка их сложности и мера неразрешимости / Труды 13-й Мультиконференции по проблемам управления (МКПУ-2020). Санкт-Петербург, 6-8 октября 2020 г. СПб.: АО «Концерн «ЦНИИ «Электроприбор», 2020. С. 221-223.