Использование генетических алгоритмов для построения эффективных комплексных расписаний обработки пакетов данных в конвейерной системе при задании ограничений на длительность интервалов времени ее функционирования

Аннотация

В статье решается задача формирования эффективных комплексных расписаний обработки пакетов данных при задании ограничений на интервалы времени функционирования конвейерной системы. Задача формирования комплексных расписаний разделена на три подзадачи, каждая из которых решается на определенном уровне иерархии. На первом уровне определяются составы пакетов данных, на втором уровне определяются составы групп пакетов данных, которые обрабатывается в течение заданных интервалов времени функционирования системы, на третьем уровне определяется расписание обработки пакетов данных, входящих в каждую группу. Для решения задачи построения комплексных расписаний в составе такой иерархической системы применен аппарат теории иерархических игр. Рассматривается модель иерархической игры, позволяющая определять локально оптимальные решения на каждом уровне иерархии. Выполнено обоснование применения генетических алгоритмов для определения составов групп пакетов данных, которые являются эффективными с точки зрения минимизации простоев сегментов конвейера в течение заданных временных интервалов. Сформулирован способ кодирования решений по составам групп пакетов данных. Определены способы реализации генетических операторов, которые позволяют осуществить поиск локально оптимальных решений по составам групп пакетов на основе начального решения. Выполнена программная реализация процедур оптимизации составов пакетов данных, составов групп пакетов данных и расписаний обработки пакетов, входящих в группы. Исследования предложенного метода оптимизации, использующего генетические алгоритмы, показало, что его применение для формирования составов групп пакетов данных позволяет до 45 % повысить эффективность использования ресурса времени сегментов конвейера по сравнению с начальным решением.