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

Введем следующие обозначения:? общая задача (1),? частная задача, в которой вышедший из начальной точки процессор сначала обслуживает совокупность объектов с индексами из произвольного подмножества, а затем, в заключение обслуживает объект .

Пусть — совокупность эффективных оценок в задаче. Если — пустое множество, то.

(2).

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

.

где.

.

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

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

.(3).

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

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

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

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

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

Таблица № 1. Исходные данные задачи.

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

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

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

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

Таблица № 2. Результаты итерации 1.

{Ш}.		(4, 20, 120).	(1).
{Ш}.		(8, 21, 63).	(2).
{Ш}.		(10, 14, 70).	(3).
{Ш}.		(13, 19, 19).	(4).

Для иллюстрации ниже приведем цепочку вычислений для нахождения совокупности :

.

.

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

Таблица № 3. Результаты итерации 2.

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

.

.

.

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

Таблица № 4. Результаты итерации 3.

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

Таблица № 5. Результаты итерации 4.

{1, 2, 3}.		(13, 49, 455) (17, 52, 429) (25, 45, 331) (21, 45, 434)	(1, 2, 3, 4) (1, 3, 2, 4) (3, 1, 2, 4) (2, 1, 3, 4)
{1, 2, 4}.		(28, 44, 509) (24, 46, 490) (16, 50, 511)	(4, 1, 2, 3) (2, 1, 4, 3) (1, 2, 4, 3)
{1, 3, 4}.		(30, 47, 366) (26, 44, 419) (18, 51, 452) (26, 42, 445)	(3, 1, 4, 2) (3, 4, 1, 2) (1, 3, 4, 2) (4, 3, 1, 2)
{2, 3, 4}.		(22, 40, 484) (26, 45, 453) (22, 42, 458)	(4, 3, 2, 1) (3, 2, 4, 1) (3, 4, 2, 1)

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

Таблица № 6.

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

(26, 41, 484).	(4, 3, 2, 1).
(26, 43, 458).	(3, 4, 2, 1).
(26, 54, 452).	(1, 3, 4, 2).
(30, 57, 429).	(1, 3, 2, 4).
(30, 46, 453).	(3, 2, 4, 1).
(34, 45, 445).	(4, 3, 1, 2).
(34, 47, 419).	(3, 4, 1, 2).
(38, 50, 331).	(3, 1, 2, 4).

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

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

.

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

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

В таблице 7 приведены оценки решающего задачу (1) алгоритма GA, реализующего типовую вычислительную схему эволюционно-генетической концепции [11]. В качестве оценок были взяты: — средняя продолжительность решения задачи (1);? минимальное, максимальное и среднее количество эффективных («субэффективных» для GA) оценок.

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

.

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

Таблица № 7. Результаты вычислительных экспериментов.

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

Пусть — множество эффективных оценок, полученных при решении задачи (1) алгоритмом DP, — множество оценок, полученных при решении задачи алгоритмом GA, в общем случае.

;, , ,.

— элементы соответствующих множеств. Значения критериев, , при фиксированном S можно рассматривать, как декартовы координаты точки в трехмерном пространстве, при этом точка соответствует началу координат. Через обозначаем расстояние между точками (оценками) и; отклонение вычисляем по формуле.

.

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

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