Алгоритмы синтеза стратегий в трехкритериальной задаче однопроцессорного обслуживания группировки стационарных объектов
Аннотация
Дата поступления статьи: 01.07.2015Рассматривается модель обслуживания группы стационарных объектов, расположенных вдоль одномерной рабочей зоны перемещающегося процессора. Процессор выполняет одностадийный цикл обслуживания без прерываний, который начинается и заканчивается в базовой точке. Для каждого объекта считаются заданными его местоположение, требуемая продолжительность обслуживания, ранний срок начала обслуживания и функция индивидуального штрафа. Изучается многокритериальная задача, где в качестве минимизируемых критериев выступают: общее пройденное процессором расстояние, момент возвращения процессора в базовую точку после обслуживания всех объектов и величина суммарного по всем объектам штрафа. Решение выполняется с использованием соотношений, основанных на принципе динамического программирования, а также на основе идеологии эволюционно-генетических вычислений. При использовании динамического программирования изучаются вопросы построения полных совокупностей эффективных оценок. Исследуются вопросы сравнения двух множеств оценок, приводятся оценки вычислительной сложности, пример реализации и результаты экспериментов.
Ключевые слова: многокритериальная оптимизация, стратегии обслуживания, динамическое программирование, эволюционные вычисления, NP-трудность, мобильный процессор, стационарные объекты
05.13.01 - Системный анализ, управление и обработка информации (по отраслям)