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

Аннотация

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