2016 УДК:519.854.3 ЗАДАЧИ И АЛГОРИТМЫ ОПТИМИЗАЦИИ РАСПИСАНИЙ ПАРАЛЛЕЛЬНО-ПОСЛЕДОВАТЕЛЬНЫХ СИСТЕМ С НЕОПРЕДЕЛЕННЫМИ МАРШРУТАМИ ОБСЛУЖИВАНИЯ Ю.А. <...> Мезенцев, И.В. Эстрайх Новосибирский государственный технический университет Представлен новый подход к решению проблем составления оптимальных по быстродействию расписаний параллельно-последовательных систем с использованием двухэтапной схемы: кластеризации и последующего определения маршрутов. <...> Частными случаями применения разработанного инструментария являются решения различных модификаций задач маршрутизации с минимаксным критерием. <...> Приведены формальные постановки рассматриваемых подзадач кластеризации и составления маршрутов в виде NP-трудных задач дискретного программирования. <...> Предложен приближенный алгоритм решения поставленной задачи, основанный на ее декомпозиции на подзадачу оптимального по равномерной нагрузке на приборы разбиения множества заявок на подмножества и ряд подзадач определения последовательностей их обслуживания приборами. <...> Приведены иллюстративные примеры применения развиваемого подхода, вычислены эмпирические оценки точности и быстродействия его программной реализации. <...> На сгенерированных тестовых примерах в широком диапазоне размерностей исследованы быстродействие и точность реализованных алгоритмов. <...> Обозначены возможные практические применения при построении календарных графиков реализации крупных промышленных проектов и определены направления развития предложенного подхода. <...> Ключевые слова: параллельно-последовательная система, неопределенные маршруты обслуживания, оптимальность по быстродействию, маршрутизация, кластеризация, задача коммивояжера. <...> Например, задача коммивояжера (ЗК) является частным случаем open shop problem (OSP) для одного прибора. <...> Задачи же на составление маршрутов и оптимальных по быстродействию расписаний движения по этим маршрутам, являющиеся расширениями ЗК, в состав <...>