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

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

11 2 А.М. Пушкин1, Д.И. Коган1, Ю.С. Федосенко2

1 Московский государственный университет информационных технологий, радиотехники

и электроники

2Волжский государственный университет водного транспорта, Нижний Новгород

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

Ключевые слова: многокритериальная оптимизация, стратегии обслуживания, динамическое программирование, эволюционные вычисления, КР-трудность, мобильный процессор, стационарные объекты.

Рассматриваемая в статье модель предназначена для описания функционирования локальных логистических систем [1,2], в которых мобильный процессор осуществляет обслуживание рассредоточенной в рабочей зоне группировки стационарных объектов.

В ранее опубликованных работах [3,4,5] по обслуживанию группировки объектов априорно учитываются обусловленные спецификой конкретных приложений те или иные ограничения на перемещения процессора в одномерной рабочей зоне. Так, в [3,4] рассматривается модель обслуживания при реализации процессором двух рейсов - от начальной до

Введение

конечной точки зоны и обратно. Модель, изучаемая в [5], требует обслуживания всех объектов группировки при реализации процессором только прямого рейса - от начальной точки зоны к её конечной точке; при этом разрешены ограниченные по глубине возвратные движения процессора для обслуживания «пропущенных» объектов. Для синтеза эффективных стратегий обслуживания в указанных работах сформулированы бикритериальные [6] задачи оптимизации и в рамках парадигмы Парето [7] сконструированы решающие алгоритмы динамического

программирования [8].

Ниже исследуемая трехкритериальная [9] задача оптимизации стратегий управления обслуживанием формулируется в разделе 1 в рамках обобщенной математической модели, свободной от каких-либо ограничений на перемещения процессора в его рабочей зоне. Такая модель существенно расширяет сферу покрываемых логистических приложений и создает теоретическую базу для разработки достаточно универсальной информационной системы поддержки управления обслуживанием группировки стационарных объектов, рассредоточенных в одномерной рабочей зоне процессора.

Конструируемый в разделе 2 решающий алгоритм БР основан на концепциях эффективных оценок [7], многокритериального динамического программирования [10]. Здесь же приведен численный пример реализации алгоритма и результаты сравнительных вычислительных исследований алгоритмов динамического программирования и сконструированного по типовой схеме алгоритма ОЛ, основанного на эволюционно-генетической концепции [11].

В заключительном разделе статьи обсуждаются полученные результаты и возможные направления развития исследований

рассматриваемого класса прикладных задач в интересах создания компьютерных систем поддержки логистических процессов.

Математическая модель и постановка задачи

Полагается заданной совокупность Оп ={о1,о2,...,оп} подлежащих

однофазному обслуживанию стационарных объектов, расположенных соответственно в точках 1,2,..., п одномерной рабочей зоны Ь обслуживающего процессора Р. Зона Ь конечна, её начальная точка А является базовой для процессора, присвоим ей номер 0. Подлежащие обслуживанию объекты считаем пронумерованными в порядке возрастания их расстояний от точки А. Конечная точка В зоны Ь является местом расположения объекта оп. Для параметров модели обслуживания объектов

оу, у = 1, п, примем следующие обозначения:

ту - продолжительность обслуживания процессором Р объекта оу; г у - ранний срок начала обслуживания (момент готовности к обслуживанию) объекта о ;

sj-1 у - расстояние между точками у -1 и у ;

7]-1 у и у] ]-1 - продолжительности перемещения процессора Р соответственно от точки у -1 к точке у и от точки у к точке у -1;

^ (?) - монотонно возрастающая в нестрогом смысле функция индивидуального штрафа по объекту оу от момента ? завершения его обслуживания;

Трд - продолжительность перемещения процессора от точки р к

д-1 р-1

точке д: Урд = е г7,у+1, если р < д и Урд = е^+1,у, если р > д;

у=р у=д

:

q-l

spq - расстояние между точками p ид: spq = ^ sJ 3+1, если p < д и

з=Р

р-1

sp,д = Е SJ,з+l, если Р > д .

3=д

Считаем параметры тз, sJ-13, уз-1 , уз -1 принимающими натуральные значения, а параметр г3 принимающим только целые неотрицательные

значения. Процессор Р начинает движение из базовой точки А в момент времени ? = 0; по завершению обслуживания всех объектов группировки Оп он возвращается в точку А. Обслуживание каждого объекта осуществляется процессором Р однократно, без прерываний; одновременное обслуживание процессором двух и более объектов запрещено.

Стратегией обслуживания будем называть произвольную упорядоченную по возрастанию последовательность индексов £ =

из совокупности N = {1,2,...., п}, определяющую порядок обслуживания объектов. Реализующими стратегию £ расписаниями обслуживания р именуем кортежи вида р = ( а., Ък),..., (¡к, а1к, Ъч),..., (1п, ап, Ьп), в которых а1к

и Ъ{ - соответственно моменты начала и завершения обслуживания объекта

о, , к = 1, п .

гк

Не связанные с обслуживанием объекта о3 и ожиданием момента

наступления раннего срока гз, 3 = 1, п начала его обслуживания

промежуточные простои процессора запрещены, т.е. ниже будут рассматриваться только стратегии £, которым соответствуют компактные [12] г -расписания. Совокупность таких стратегий будем обозначать символом ^.

В зависимости от складывающейся оперативной обстановки ээффективность той или иной стратегии обслуживания в рассматриваемом

классе локальных логистических систем может оцениваться ЛПР с учетом различных обстоятельств, среди которых основными являются следующие: K1( S) - суммарное пройденное процессором расстояние до момента возврата процессора в точку A; K2(S) - суммарное время работы процессора; K3(S) -суммарный по всем объектам штраф за простои в ожидании обслуживания. Соответствующая трехкритериальная задача имеет вид

min{Ki

При решении задачи (1) принимается концепция Парето, предусматривающая отыскание полной совокупности эффективных в ней оценок [7]. Соответствующие алгоритмы конструируются на основе концепции эффективных оценок [7].

Синтез стратегий обслуживания

Введем следующие обозначения: Z - общая задача (1), Z (V, i) -

частная задача, в которой вышедший из начальной точки A процессор сначала обслуживает совокупность объектов с индексами из произвольного подмножества V с N, а затем, в заключение обслуживает объект ot, i £ V.

Пусть E(V, i)- совокупность эффективных оценок в задаче Z(V, i).

Если V - пустое множество, то

E

Введем функцию Т л (M), которая преобразует каждый из трехмерных

векторов множества M по правилу (a, b, c) ^ (a + sjt, J, c + ф (J)), где

J = max (b + Yji, Г ) + т. Считается, что данное правило работает в

следующем предположении: конструируемая в процессе работы алгоритма стратегия обслуживания на конкретной итерации завершается в точке J

рабочей зоны и имеет оценку (а, Ь, с), после чего из этой точки совершается

переход в точку I зоны с пересчетом оценки согласно указанному правилу. Предположим, что множества оценок Е(V, I) для всех I е N и всех

возможных к -элементных множеств V уже вычислены (к - фиксированная

константа, к < п). Тогда значение Е(V , I), где V - любое (к +1)-элементное

подмножество совокупности N \ {}, вычисляется по формулам

Е

Пусть все объекты прошли обслуживание. Тогда процессору необходимо совершить переход от последнего обслуженного объекта а, а е N в базовую точку А. В этом случае полная совокупность эффективных оценок Е^ в задаче 2 находится из соотношения

Ем = е//{и [Е

lаеN )

в котором операция © определяется следующим образом:

{(^ ^ с1),..., (а, Ь, с )}©( й, е / ) = = {( + й, Ь1 + е, С1 + /),..., (а + й, Ь + е, с1 + /)}.

В процессе решения на каждой итерации отмечается индекс вершины перехода процессора и сохраняется полный путь, который он прошел для достижения данного набора эффективных оценок.

Формулы (2)-(4) - рекуррентные соотношения многокритериального динамического программирования [8,10] для решения задачи (1). Реализующие эти соотношения алгоритм БР имеет экспоненциальную оценку вычислительной сложности.

Пример выполнения алгоритма БР. Требуется найти полную совокупность эффективных оценок для задачи (1) с исходными данными, представленными в таблице 1.

Таблица № 1

Исходные данные задачи

1 51 -1,1 71 -1,1 71,1 -1 Т Г г)

1 4 4 1 3 17 бг

2 4 2 2 10 11 3*

3 2 2 1 4 10 5*

4 3 1 1 10 7 г

Процедуру решения представляем как процесс заполнения таблицы 2 и последующих, каждая следующая таблица соответствует очередной выполненной итерации (под итерацией понимается набор вычислений множеств Е (V, г) при условии, что \У\ = к).

В процессе вычислений по рекуррентным соотношениям (2) и (3) значение к последовательно принимает значения 0,1,..., п -1. Последняя,

выполняемая по формуле (4), итерация синтезирует полную совокупность эффективных оценок в задаче (1).

В таблицах рядом с каждой эффективной оценкой в той же строке указывается порождающая ее стратегия £ *. Стратегия £ * отличается от других допустимых стратегий обслуживания тем, что после обслуживания перечисленных в ней объектов процессор не совершает переход в базовый пункт А .

Согласно формуле (2) в таблице 2 запишем результаты первой итерации.

Таблица № 2

Результаты итерации 1

V г Е (V, г) 5 *

{0} 1

{0} 2

{0} 3

{0} 4

Для иллюстрации ниже приведем цепочку вычислений для нахождения совокупности Е ({0} ,2): t2 = тах (^02, г2 ) + т2 = тах(6,11) +10 = 21,

Е ({0} ,2) = ( (t2 )) = (8,21,63).

Применяя формулу (4), в таблице 3 запишем результаты второй итерации.

Таблица № 3

Результаты итерации 2

V г Е (V, г) 5 *

{1} 2

{1} 3

{1} 4

{2} 1

{2} 3

{2} 4

{3} 1

{3} 2

{3} 4

{4} 1

{4} 2

{4} 3

Иллюстрирующая цепочка вычислений для нахождения совокупности Е({2},4) выглядит следующим образом:

eff {Т 2,4 ((8,21,63))} = eff {(8,21,63) (8 + s2,4, t24,63 + ф (t2A))}, t24 = max (21 + y24, r4 ) + т4 = max (21 + 3,7) +10 = 34,

eff {Т 23 ((12,72))} = eff {(8 + 5,34,63 + 34 • 1)} = (13,34,97).

Аналогично второй итерации в таблице 4 представлены результаты третьей итерации.

Таблица № 4

Результаты итерации 3

V i E (V, i) S *

{1, 2} 3

{1, 2} 4

{1, 3} 2

{1, 3} 4

{1, 4} 2

{1, 4} 3

{2, 3} 1

{2, 3} 4

{2, 4} 1

{2, 4} 3

{3, 4} 1

{3, 4} 2

Результаты четвертой итерации приведены в таблице 5.

Таблица № 5

Результаты итерации 4

V г Е (V, г) 5 *

{1, 2, 3} 4

{1, 2, 4} 3

{1, 3, 4} 2

{2,3, 4} 1

Последняя итерация, реализуемая по формуле (5), отображает факт перехода процессора в базовую точку после завершения обслуживания всех объектов. Финальные оценки работы процессора и соответствующие им стратегии обслуживания представлены в таблице 6.

Таблица № 6

Результаты итерации 5

Е 5

В итоге построена полная совокупность эффективных оценок, и для каждой такой оценки определено соответствующее расписание обслуживания. Из построенной совокупности эффективных оценок ЛПР осуществляет свой выбор, принимая во внимание обстоятельства, не предусмотренные построенной в разделе 1 математической моделью.

Отметим, что задача (1) относится к числу труднорешаемых [13] в силу того, что указанным свойством обладают некоторые её частные конкретизации. В качестве одной из таковых отметим бикритериальную задачу

тш {К (5), К3 ( 5 )},

которая ИР -трудна [13] даже в условии принятия для неё схемы лексикографического упорядочения критериев с ведущим критерием К1

и линейными функциями индивидуального штрафа. Указанный результат установлен в [4].

При создании компьютерных средств поддержки оперативного управления обслуживанием потоков объектов в локальных логистических системах существенным обстоятельством, которое приходится учитывать при разработке математического обеспечения таких средств, являются жесткие ограничения [3,4,12] на допускаемую штатным регламентом длительность формирования стратегий обслуживания; обычно этот промежуток времени не должен превышать 15 минут. В силу этого задача (1) для ряда практических значимых размерностей потока Оп оказывается

нерешаемой, и, следовательно, актуальной является проблема построения алгоритмов, позволяющих генерировать субоптимальные стратегии обслуживания за приемлемое для приложений время.

В таблице 7 приведены оценки решающего задачу (1) алгоритма ОЛ, реализующего типовую вычислительную схему эволюционно-генетической

концепции [11]. В качестве оценок были взяты: Ттеап - средняя продолжительность решения задачи (1); Кей. - минимальное, максимальное и среднее количество эффективных («субэффективных» для ОЛ) оценок.

Выбираемые для вычислений значения параметров модели соответствовали равномерному закону распределения на следующих обусловленных физическим смыслом диапазонах замкнутых интервалов: з-ч е [1,5], Г-ч е [5,20], Ги-1 е [5,20], г, е [1,10], г е [10,10• п], а, е[1,10], где п - размерность задачи, аг - коэффициент линейной функции штрафа щ (г ) = а • г.

Для сравнения в этой же таблице приведены значения показателей Ттеап и Кей-, полученные при реализации алгоритма БР.

Таблица № 7

Результаты вычислительных экспериментов

п т теап ? К е£Т А,%

ОЛ БР ОЛ БР

5 0 0 1 - 5 (2) 1 - 5 (2) 0

10 16 2 1 - 8 (3) 1 - 9 (3) 3

15 180 90 1 - 6 (3) 2 - 9 (4) 10

17 360 660 1 - 8 (4) 1 - 12 (5) 20

19 660 5400 1 - 5 (2) 2 - 10 (4) 26

20 900 15300 1 - 7 (3) 3 - 11 (5) 36

Приведенный в таблице 7 показатель А используется для интегральной оценки отклонения множества «субэффективных» оценок от точного множества оценок. При определении значений этого показателя исходим из следующих соображений.

Пусть Ж - множество эффективных оценок, полученных при решении задачи (1) алгоритмом БР, Q - множество оценок, полученных при решении

задачи алгоритмом ОЛ, в общем случае |Ж| ф \Q\; wl, / = 1, |Ж|, , } = 1, Q| -

элементы соответствующих множеств. Значения критериев К1 (5), К2 (5), К3 (5) при фиксированном 5 можно рассматривать, как декартовы координаты точки в трехмерном пространстве, при этом точка О (0,0,0) соответствует началу координат. Через |С1С2| обозначаем расстояние между точками (оценками) С1 и С2; отклонение А вычисляем по формуле

А = max min %.

f

Программная реализация алгоритмов DP и GA была выполнена на высокоуровневом языке программирования общего назначения Python 2.7, вычислительные эксперименты проводились на ПК с процессором Intel Core™ i7 4.20 GHz и оперативной памятью объемом 16 Gb.

Как следует из таблицы 7, для задачи (1) с размерностью потока n не более 17, следует использовать алгоритм DP; в случае больших значений n целесообразно использовать алгоритм GA.

Авторами сформулирована и изучена трехкритериальная задача обслуживания мобильным процессором линейно рассредоточенной группировки стационарных объектов с учетом предписанных ранних сроков их готовности к обслуживанию. При решении принята концепция Парето; совокупность эффективных в задаче оценок строится с использованием рекуррентных соотношений многокритериального динамического программирования. Полученный теоретический результат о вычислительной сложности соответствует оценке трудоёмкости решающего задачу алгоритма.

Выполненные вычислительные эксперименты и сравнение характеристик разработанного алгоритма динамического программирования с аналогичными характеристиками эволюционно-генетического алгоритма

Результаты

приближенного синтеза стратегий обслуживания позволили установить области их целесообразного применения.

В направлении развития рассматриваемого класса прикладных задач представляется целесообразной разработка и экспериментальное исследование алгоритмов синтеза стратегий обслуживания в локальных логистических системах с существенно более высокими характеристиками отработки, в том числе основанных на иных метаэвристических парадигмах.

Статья подготовлена по результатам исследований, выполненных при финансовой поддержке Российского фонда фундаментальных исследований в рамках проекта № 15-07-03141.

Литература

1. Кочерга В.Г., Зырянов В.В., Хачатурян А.В. Планирование и организация грузовых автомобильных перевозок на улично-дорожной сети мегаполисов // Инженерный вестник Дона, 2012, №2, URL: ivdon.ru/ru/magazine/archive/n2y2012/869.

2. Шегельман И.Р., Кузнецов А.В., Скрыпник В.И., Баклагин В.Н. Методика оптимизаций транспортно-технологического освоения лесосырьевой базы с минимизацией затрат на заготовку и вывозку древесины // Инженерный вестник Дона, 2012, №4 (ч.2) URL: ivdon.ru/ru/magazine/archive/n4p2y2012/1284.

3. Коган Д.И., Федосенко Ю.С., Дуничкина Н.А. Бикритериальные задачи обслуживания стационарных объектов в одномерной рабочей зоне процессора // Автоматика и телемеханика, 2012, №10, с. 93-110.

4. Дуничкина Н.А., Коган Д И., Пушкин А.М., Федосенко Ю.С. Об одной модели обслуживания стационарных объектов перемещающимся в одномерной рабочей зоне процессором // Труды XII Всероссийского совещания по проблемам управления. М.: ИПУ РАН, 2014, с. 5044-5052.

5. Пушкин А.М. Модель обслуживания стационарных объектов перемещающимся процессором с возможностью возвратов // Научно-технический вестник Поволжья, 2014, №5, с. 288-292.

6. Steuer, R. Multiple Criteria Optimization: Theory, Computation and Application, Russian Edition, Radio e Svyaz, Moscow, 1992, 504 p.

7. Подиновский В.В., Ногин В.Д. Парето-оптимальные решения многокритериальных задач. М.: Наука, 1982. 256 с.

8. Беллман Р., Дрейфус С. Прикладные задачи динамического программирования. М.: Наука, 1965. 460 с.

9. T'kindt V., Billaut J. Multicriteria scheduling: models and algorithms. Springer, 2006. 359 p.

10. Коган Д.И. Динамическое программирование и дискретная многокритериальная оптимизация. Нижний Новгород: Изд-во ННГУ, 2005. 260 с.

11. Батищев Д.И., Костюков В.Е., Неймарк Е.А., Старостин Н.В. Решение дискретных задач с помощью эволюционно-генетических алгоритмов. Нижний Новгород: Изд-во ННГУ им. Н.И. Лобачевского, 2011. 199 с.

12. Коган Д.И., Федосенко Ю.С. Задача диспетчеризации: анализ вычислительной сложности и полиномиально разрешимые подклассы // Дискретная математика, 1996, т. 8, вып. 3, с. 135-147.

13. Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. М.: Мир, 1982. 416 с.

References

1. Kocherga V.G., Zyrjanov V.V., Hachaturjan A.V. Inzenernyj vestnik Dona (Rus), 2012, №2, URL: ivdon.ru/ru/magazine/archive/n2y2012/869.

2. Shegel'man I.R., Kuznecov A.V., Skrypnik V.I., Baklagin V.N. Inzenernyj vestnik Dona (Rus), 2012, №4 (p.2) URL: ivdon.ru/ru/magazine/archive/n4p2y2012/1284.

3. Kogan D.I., Fedosenko Yu.S., Dunichkina N.A. Avtomatika i telemekhanika, 2012, №10, pp. 93-110.

4. Dunichkina N.A., Kogan D.I., Pushkin A.M., Fedosenko Yu.S. Trudy XII Vserossiyskogo soveshchaniya po problemam upravleniya. M.: IPU RAN, 2014, pp. 5044-5052.

5. Pushkin A.M. Nauchno-tekhnicheskiy vestnik Povolzh'ya, 2014, №5, pp. 288-292.

6. Steuer, R. Multiple Criteria Optimization: Theory, Computation and Application, Russian Edition, Radio e Svyaz, Moscow, 1992, 504 p.

7. Podinovskiy V.V., Nogin V.D. Pareto-optimal'nye resheniya mnogokriterial'nykh zadach [Pareto-optimal solutions of multiobjective problems]. M.: Nauka, 1982. 256 p.

8. Bellman R., Dreyfus S. Prikladnye zadachi dinamicheskogo programmirovaniya [Applications of dynamic programming]. M.: Nauka, 1965. 460 p.

9. T'kindt V., Billaut J. Multicriteria scheduling: models and algorithms. Springer, 2006. 359 p.

10. Kogan D.I. Dinamicheskoe programmirovanie i diskretnaya mnogokriterial'naya optimizatsiya [Dynamic programming and discrete multi-objective optimization]. Nizhniy Novgorod: Izd-vo NNGU, 2005. 260 p.

11. Batishchev D.I., Kostyukov V.E., Neymark E.A., Starostin N.V. Reshenie diskretnykh zadach s pomoshch'yu evolyutsionno-geneticheskikh algoritmov [Solution of discrete tasks using genetic algorithms]. Nizhniy Novgorod: Izd-vo NNGU im. N.I. Lobachevskogo, 2011. 199 p.

12. Kogan D.I., Fedosenko Yu.S. Diskretnaya matematika, 1996, t. 8, vyp. 3, pp. 135-147.

13. Geri M., Dzhonson D. Vychislitel'nye mashiny i trudnoreshaemye zadachi [Computers and intractable problems]. M.: Mir, 1982. 416 p.