Современные методы планирования процессов в конвейерных системах с буферами определенного размера между обрабатывающими приборами позволяют оптимизировать расписания выполнения единичных заданий либо фиксированных пакетов заданий при их ограниченном количестве и ограниченном количестве приборов. Применение математических моделей процессов выполнения единичных заданий (пакетов заданий), используемых этими методами, при оптимизации составов пакетов и расписаний их выполнения в системах с произвольным количеством пакетов и приборов является невозможным. В то же время математические модели процессов выполнения пакетов заданий в конвейерных системах при наличии буферов ограниченных размеров между приборами являются основой для разработки методов оптимизации их (пакетов) составов и расписаний реализации действий с ними на приборах конвейерных систем. В связи с этим в статье разработаны математические модели многостадийных процессов выполнения произвольного количества пакетов заданий в конвейерных системах при наличии промежуточных буферов ограниченных размеров для двух и трех приборов, а также для произвольного количества приборов. Использование этих моделей позволяет определять моменты времени начала выполнения пакетов заданий на приборах конвейерных систем с учетом ограниченных размеров промежуточных буферов, а также длительности интервалов времени использования этих ресурсов и эффективность их использования в течение времени. Также разработан алгоритм математического моделирования процессов выполнения пакетов заданий в конвейерных системах при наличии промежуточных буферов ограниченных размеров, осуществляющий на основе заданного порядка реализации действий с пакетами заданий на приборах конвейерных систем вычисление временных характеристик этих процессов. Осуществлена разработка приложения, реализующего синтезированные математические модели процессов выполнения пакетов заданий в конвейерных системах с промежуточными буферами ограниченных размеров и соответствующий метод моделирования этих процессов. Разностороннее тестирование разработанного приложения показало, что полученные математические модели и метод моделирования адекватно описывают ход многостадийных процессов выполнения пакетов заданий в конвейерных системах, задаваемый с использованием различных значений их (процессов) параметров.
Современные методы решения задач планирования выполнения пакетов заданий в многостадийных системах характеризуются наличием ограничений на их размерность, невозможностью гарантированного получения лучших результатов в сравнении с фиксированными пакетами при различных значениях входных параметров задачи. В статье автором решена задача оптимизации составов пакетов заданий, выполняющихся в многостадийных системах, с использованием метода ветвей и границ. Проведены исследования различных способов формирования порядков выполнения пакетов заданий в многостадийных системах (эвристических правил упорядочивания пакетов заданий в последовательностях их выполнения на приборах МС). Определен способ упорядочивания пакетов в последовательностях их выполнения (эвристическое правило), обеспечивающий минимизацию общего времени реализации действий с ними на приборах. На основе полученного правила сформулирован способ упорядочивания типов заданий, в соответствии с которым их пакеты рассматриваются в процедуре метода ветвей и границ. Построена математическая модель процесса реализации действий с пакетами на приборах системы, которая обеспечивает вычисление его параметров. Выполнено построение метода формирования всех возможных решений по составам пакетов заданий для заданного их количества. Решения по составам пакетов заданий разных типов интерпретируются в процедуре метода ветвей и границ с целью построения оптимальной их комбинации. Для реализации метода ветвей и границ сформулирована процедура ветвления (разбиения), предполагающая формирование подмножеств решений, включающих пакеты разных составов заданий одного типа. Построены выражения для вычисления нижних и верхних оценок значений критерия оптимизации составов пакетов для сформированных в процедуре ветвления подмножеств. Процедура отсева предполагает исключение подмножеств, нижняя оценка которых не меньше рекорда. Для поиска оптимальных решений применена стратегия поиска в ширину, предусматривающая исследование всех подмножеств решений, включающих различные пакеты заданий одного типа, полученных в результате процедуры разбиения подмножеств заданий, не исключенных из рассмотрения после реализации процедуры отсева. Разработанные алгоритмы реализованы программно, что позволило получить результаты планирования выполнения пакетов заданий в многостадийной системе, являющиеся в среднем на 30 % лучшими, чем для фиксированных пакетов.
Применение скоординированных групп автономных подводных роботов представляется наиболее перспективной и многообещающей технологией, обеспечивающей решение самого широкого спектра океанографических задач. Групповое выполнение комплексных широкомасштабных миссий, как правило, связано с длительным пребыванием роботов в заданной акватории, что в условиях ограниченной энергоемкости аккумуляторных батарей возможно только при наличии специализированных док-станций для ее пополнения. С целью обеспечения высокого уровня работоспособности действующей группировки возникают две параллельные задачи: эффективно распределить задания миссии между членами группы и определить порядок подзарядки роботов на длительном промежутке времени. При этом необходимо учитывать, что реальные робототехнические системы функционируют в динамической подводной среде, а значит, могут подвергаться влиянию непредвиденных событий и различного рода неполадок.
В данной статье предлагается двухуровневый подход к динамическому планированию групповой стратегии, основанный на декомпозиции миссии на последовательность рабочих периодов с обязательным сбором действующей группировки по окончанию каждого из них. Задача планировщика на верхнем уровне заключается в составлении такого расписания циклов зарядки для всех аппаратов в группе, которое обеспечивало бы своевременное пополнение батарей при недопущении одновременной зарядки большого количества роботов. На основе выбранного расписания осуществляется декомпозиция миссии таким образом, чтобы каждый сбор группы сопровождался либо выходом робота из группы для осуществления подзарядки, либо возвращением в группу уже заряженного аппарата. Такая схема позволяет отслеживать статус группы и осуществлять оперативное перепланирование при изменении ее состава. Маршрутизация группы на каждом рабочем периоде осуществляется низкоуровневым планировщиком, работающим на графе целей и учитывающим технические возможности всех аппаратов в группе, а также все действующие ограничения и требования к выполнению конкретных задач. В статье предлагается эволюционный подход к децентрализованной реализации обоих планировщиков с применением специализированных эвристик, процедур улучшения решений и оригинальных схем кодирования и оценки решений; приводятся результаты вычислительных экспериментов.
1 - 3 из 3 результатов