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