RT - article
SR - Electronic
T1 - ЭВРИСТИЧЕСКИЕ АЛГОРИТМЫ ДЛЯ ПОСТРОЕНИЯ РАСПИСАНИЙ ОБСЛУЖИВАНИЯ ТРЕБОВАНИЙ С РАЗЛИЧНЫМИ МАРШРУТАМИ
JF - Информатика
SP - 2018-02-23
A1 - Голами О. , 
A1 - Сотсков Ю. Н., 
YR - 2012
UL - https://www.academjournals.by/publication/18650
AB - Задача построения оптимального расписания обслуживания m приборами n требований с различными маршрутами является NP-трудной при любом m > 2 для всех регулярных критериев, рассматриваемых в теории расписаний. Для ее решения разработаны эвристические алгоритмы для трех регулярных критериев: минимизации общего времени обслуживания заданных требований; минимизации суммарного времени обслуживания n требований и минимизации суммарного запаздывания обслуживания n требований. Экспериментальное сравнение разработанных программ с одним из наиболее эффективных эвристических алгоритмов показало их превосходство по времени реализации и достаточно близкие результаты по качеству получаемых расписаний в случае, когда число m больше числа n. Неравенство m > n выполняется, в частности, для задач, возникающих при составленииоптимальных расписаний движения поездов по одноколейным железным дорогам.