Информатика и автоматизация
RUS  ENG    ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ПАКЕТ AMSBIB  
Общая информация
Последний выпуск
Архив

Поиск публикаций
Поиск ссылок

RSS
Последний выпуск
Текущие выпуски
Архивные выпуски
Что такое RSS



Информатика и автоматизация:
Год:
Том:
Выпуск:
Страница:
Найти






Персональный вход:
Логин:
Пароль:
Запомнить пароль
Войти
Забыли пароль?
Регистрация


Информатика и автоматизация, 2022, выпуск 21, том 1, страницы 5–40
DOI: https://doi.org/10.15622/ia.2022.21.1
(Mi trspy1182)
 

Цифровые информационно-телекоммуникационные технологии

Математическая модель и алгоритм метода ветвей и границ для оптимизации решений по составам пакетов в многостадийных системах

К. В. Кротов

ФГАОУ ВО Севастопольский Государственный университет (СевГУ)
Аннотация: Современные методы решения задач планирования выполнения пакетов заданий в многостадийных системах характеризуются наличием ограничений на их размерность, невозможностью гарантированного получения лучших результатов в сравнении с фиксированными пакетами при различных значениях входных параметров задачи. В статье автором решена задача оптимизации составов пакетов заданий, выполняющихся в многостадийных системах, с использованием метода ветвей и границ. Проведены исследования различных способов формирования порядков выполнения пакетов заданий в многостадийных системах (эвристических правил упорядочивания пакетов заданий в последовательностях их выполнения на приборах МС). Определен способ упорядочивания пакетов в последовательностях их выполнения (эвристическое правило), обеспечивающий минимизацию общего времени реализации действий с ними на приборах. На основе полученного правила сформулирован способ упорядочивания типов заданий, в соответствии с которым их пакеты рассматриваются в процедуре метода ветвей и границ. Построена математическая модель процесса реализации действий с пакетами на приборах системы, которая обеспечивает вычисление его параметров. Выполнено построение метода формирования всех возможных решений по составам пакетов заданий для заданного их количества. Решения по составам пакетов заданий разных типов интерпретируются в процедуре метода ветвей и границ с целью построения оптимальной их комбинации. Для реализации метода ветвей и границ сформулирована процедура ветвления (разбиения), предполагающая формирование подмножеств решений, включающих пакеты разных составов заданий одного типа. Построены выражения для вычисления нижних и верхних оценок значений критерия оптимизации составов пакетов для сформированных в процедуре ветвления подмножеств. Процедура отсева предполагает исключение подмножеств, нижняя оценка которых не меньше рекорда. Для поиска оптимальных решений применена стратегия поиска в ширину, предусматривающая исследование всех подмножеств решений, включающих различные пакеты заданий одного типа, полученных в результате процедуры разбиения подмножеств заданий, не исключенных из рассмотрения после реализации процедуры отсева. Разработанные алгоритмы реализованы программно, что позволило получить результаты планирования выполнения пакетов заданий в многостадийной системе, являющиеся в среднем на 30 % лучшими, чем для фиксированных пакетов.
Ключевые слова: многостадийная система, пакеты заданий, метод ветвей и границ, эвристическое правило, расписания.
Поступила в редакцию: 05.07.2021
Реферативные базы данных:
Тип публикации: Статья
УДК: 004.453
Образец цитирования: К. В. Кротов, “Математическая модель и алгоритм метода ветвей и границ для оптимизации решений по составам пакетов в многостадийных системах”, Информатика и автоматизация, 21:1 (2022), 5–40
Цитирование в формате AMSBIB
\RBibitem{Kro22}
\by К.~В.~Кротов
\paper Математическая модель и алгоритм метода ветвей и границ для оптимизации решений по составам пакетов в многостадийных системах
\jour Информатика и автоматизация
\yr 2022
\vol 21
\issue 1
\pages 5--40
\mathnet{http://mi.mathnet.ru/trspy1182}
\crossref{https://doi.org/10.15622/ia.2022.21.1}
\mathscinet{http://mathscinet.ams.org/mathscinet-getitem?mr=4378693}
Образцы ссылок на эту страницу:
  • https://www.mathnet.ru/rus/trspy1182
  • https://www.mathnet.ru/rus/trspy/v21/i1/p5
  • Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    Информатика и автоматизация
    Статистика просмотров:
    Страница аннотации:102
    PDF полного текста:132
     
      Обратная связь:
     Пользовательское соглашение  Регистрация посетителей портала  Логотипы © Математический институт им. В. А. Стеклова РАН, 2024