Найти

Результаты поиска

• ТЕОРЕТИЧЕСКИЕ ОСНОВЫ СОЗДАНИЯ САМООРГАНИЗУЮЩИХСЯ ДИСПЕТЧЕРОВ РАСПРЕДЕЛЕННЫХ СИСТЕМ НА БАЗЕ МУЛЬТИАГЕНТНОГО СОЦИОИНСПИРИРОВАННОГО ПОДХОДА

  А. И. Каляев

  2021-11-14

  Аннотация ▼

  Описаны новые принципы организации, методы и алгоритмы функционирования дис-
  петчера Распределенной системы (РС), позволяющие распределять и перераспределять
  ресурсы с динамически изменяющимися параметрами между поступающими заданиями с
  целью минимизации времени их выполнения. Основная проблема, не позволяющая сегодня
  эффективно оценивать время выполнения заданий в гетерогенной РС, напрямую вытекает
  из распределенности системы: каждый из её элементов обладает частичной независимо-
  стью и может существенно отличаться от других, более того, в процессе работы его
  возможности могут изменяться, и все это существенно влияет на эффективность рас-
  пределения задач между узлами РС и на время выполнения заданий. В статье предложен
  новый подход к организации диспетчера РС, базирующийся на применении теории муль-
  тиагентных систем и социоинспирированных (базирующихся на принятых в человеческом
  обществе) методов: пользователи РС размещают свои задания на специальных узлах –
  досках объявлений, на каждом узле РС размещается проактивный программный агент,
  осуществляющий постоянный мониторинг параметров своего узла и поиск на досках объ-
  явлений подходящих для решения задач. При этом агенты, участвующие в решении общего
  задания формируют сообщества, в которых осуществляют планирование процесса реше-
  ния задания и распределение частей заданий для минимизации времени задержки их реше-
  ния. В качестве критерия эффективности работы РС было решено принять значение
  среднего времени задержки выполнения функциональных заданий относительно требуемых
  моментов времени, соответственно агенты распределяют задания таким образом, чтобы
  минимизировать значение указанного критерия. Настоящая статья включает введение,
  формальную постановку задачи диспетчирования ресурсов РС, обзор существующих под-
  ходов к организации диспетчера РС, описание предлагаемого мультиагентного решения
  задачи диспетчирования ресурсов РС с использованием социоинспирированного подхода,
  алгоритм работы распределенной системы и ее элементов, описание применения социоин-
  спирированного подхода применительно к процессу диспетчирования задач и заключение.
  К основным преимуществам предложенного подхода можно отнести: возможность ис-
  пользования достоверной и актуальной информации о специализации и текущей произво-
  дительности ресурсов при диспетчировании; высокая отказоустойчивость, обусловленная
  отсутствием элементов РС, выход из строя которых приводит к полной потере работо-
  способности РС; возможность гибкого масштабирования РС (увеличения числа ресурсов),
  достигаемая за счет децентрализации процесса диспетчирования.

• МНОГОУРОВНЕВЫЙ ПОДХОД ДЛЯ РЕШЕНИЯ ЗАДАЧИ ТРЕХМЕРНОЙ УПАКОВКИ БОЛЬШОЙ РАЗМЕРНОСТИ

  В. В. Курейчик, А. Е. Глущенко

  2020-07-20

  Аннотация ▼

  Рассмотрена одна из важных комбинаторных задач оптимизации – задача трехмер-
  ной упаковки разногабаритных элементов в объеме. Она относится к классу NP- сложных
  и трудных оптимизационных задач. В работе приведена и описана постановка задачи трех-
  мерной упаковки в объеме, введена комбинированная целевая функция учитывающая все огра-
  ничения. В связи со сложностью данной задачи предлагается многоуровневый подход заклю-
  чающийся в разделение задачи трехмерной упаковки на 3-и подзадачи и решения каждой под-
  задачи в строгом порядке. При этом для каждой из подзадач определен уникальный набор
  объектов, не повторяющихся в остальных подзадачах. Для реализации многоуровневого под-
  хода авторами разработан комбинированный биоинспирированный алгоритм, основанный на
  эволюционном и генетическом поиске. Такой подход позволяет значительно сократить время
  получения результата, частично решить проблему предварительной сходимости алгоритмов
  и получить наборы квазиотимальных решений за полиномиальное время. Разработан про-
  граммный комплекс и реализованы на ЭВМ алгоритмы автоматизированной трехмерной
  упаковки на основе комбинированного биоинспирированного поиска. Проведен вычисли-
  тельный эксперимент на тестовых примерах (бенчмарках). Качество упаковки, получен-
  ное, на основе разработанного комбинированного биоинспирированного алгоритма, в сред-
  нем на 5 % превосходит результаты упаковки, полученные с использованием известных
  алгоритмов, а время решения меньше от 5 % до 20 %, что говорит об эффективности
  предложенного подхода. Проведенные серии тестов и экспериментов позволили уточнить
  теоретические оценки временной сложности алгоритмов упаковки. В лучшем случае вре-
  менная сложность алгоритмов O(n2), в худшем случае – O(n3).