Комбинированное решение однородных распределительных задач на основе модифицированного алгоритма Романовского и селективно-перестановочного алгоритма

Ставится задача улучшения точностных свойств быстрых приближённых алгоритмов без значительного ухудшения их ресурсных свойств. Предложен подход комбинированного применения модифицированного алгоритма Романовского (МАР) и селективно-перестановочного алгоритма (СПА) для решения однородных распределительных задач (ОРЗ). Подход основывается на улучшении приближённого решения, полученного модифицированным алгоритмом Романовского, путём выборочного обмена заданиями между исполнителями. Осуществлён сравнительный анализ с такими приближёнными алгоритмами, как метод критического пути (МКП) и эволюционно-генетический алгоритм (ЭГА). Проведены вычислительные эксперименты при разных значениях параметров задачи. Комбинированное применение МАР и СПА для решения ОРЗ невысоких размерностей позволяет достигать достаточно высоких ресурсно-точностных показателей по сравнению с другими приближёнными алгоритмами. Однако на более высоких размерностях задач СПА ни разу не улучшил решения, полученные МАР, что, скорее всего, обусловлено высокими точностными характеристиками МАР. Поэтому целесообразность комбинированного использования МАР и СПА для решения ОРЗ высоких размерностей требует дальнейшего исследования.