1. Объединенный институт проблем информатики Минск, Сурганова, 6

УДК: УДК 681.32

Реферат:

Задача построения оптимального расписания обслуживания m приборами n требований с раз-личными маршрутами является NP-трудной при любом m > 2 для всех регулярных критериев, рас-сматриваемых в теории расписаний. Для ее решения разработаны эвристические алгоритмы для трех регулярных критериев: минимизации общего времени обслуживания заданных требований; ми-нимизации суммарного времени обслуживания n требований и минимизации суммарного запаздыва-ния обслуживания n требований. Экспериментальное сравнение разработанных программ с одним из наиболее эффективных эвристических алгоритмов показало их превосходство по времени реализации и достаточно близкие результаты по качеству получаемых расписаний в случае, когда число m боль-ше числа n. Неравенство m > n выполняется, в частности, для задач, возникающих при составлении оптимальных расписаний движения поездов по одноколейным железным дорогам.