Sciact
  • EN
  • RU

Точный полиномиальный алгоритм для задачи Джонсона с маршрутизацией на ассиметрической сети. Доклады на конференциях

Язык Русский
Тип доклада Секционный
Конференция Математика в Академгородке
02-04 дек. 2024 , Новосибирск, НГУ, ИМ СО РАН
Авторы Кононов А.В. 1 , Севастьянов С.В. 1 , Черных И.Д. 1
Организации
1 Институт математики им. С.Л. Соболева СО РАН

Реферат: Рассмотрена двухстадийная задача теории расписаний потокового типа (задача Джонсона) с маршрутизацией машин на асимметрической транспортной сети. Установлены структурные свойства оптимальных расписаний. Построен точный алгоритм с полиномиальным временем работ, в предположении, что количество узлов сети ограничено произвольной константой. Алгоритм с полиномиальным временем работы (в предположении, что количество узлов сети ограничено любой константой) является первым положительным результатом по сложности задачи маршрутизации машин в задаче Джонсона с произвольной структурой транспортной сети, даже в случае симметричной сети. Этот результат контрастирует со сложностью задачи маршрутизации открытого цеха для двух машин, которая является NP-трудной даже в сети из двух узлов.
Библиографическая ссылка: Кононов А.В. , Севастьянов С.В. , Черных И.Д.
Точный полиномиальный алгоритм для задачи Джонсона с маршрутизацией на ассиметрической сети.
Математика в Академгородке 02-04 дек. 2024