Abstract: Рассмотрена двухстадийная задача теории расписаний потокового типа (задача Джонсона) с маршрутизацией машин на асимметрической транспортной сети. Установлены структурные свойства оптимальных расписаний. Построен точный алгоритм с полиномиальным временем работ, в предположении, что количество узлов сети ограничено произвольной константой. Алгоритм с полиномиальным временем работы (в предположении, что количество узлов сети ограничено любой константой) является первым положительным результатом по сложности задачи маршрутизации машин в задаче Джонсона с произвольной структурой транспортной сети, даже в случае симметричной сети. Этот результат контрастирует со сложностью задачи маршрутизации открытого цеха для двух машин, которая является NP-трудной даже в сети из двух узлов.

Cite: Кононов А.В. , Севастьянов С.В. , Черных И.Д.
Точный полиномиальный алгоритм для задачи Джонсона с маршрутизацией на ассиметрической сети.
Математика в Академгородке 02-04 дек. 2024