Содержание к диссертации
Введение
ГЛАВА 1. Современное состояние теории расписаний 17
1.1. Актуальность задач теории расписаний 17
1.2. Проблемы вычислительной сложности задач теории расписаний 19
1.3. Регулярные методы решения задач теории расписаний 25
1.3.1. Метод динамического программирования 26
1.3.2. Метод ветвей и границ 27
1.3.3. Эвристические алгоритмы 30
1.4. Технология решения многокритериальных задач оптимизации 32
1.5. Типовые задачи обслуживания стационарных объектов
перемещающимся процессором 35
Выводы по главе 1 37
ГЛАВА 2. Однокритериальные задачи обслуживания стационарных объектов перемещающимся процессором 38
2.1. Двурейсовые задачи обслуживания 38
2.1.1. Математическая модель 1DZ1 38
2.1.2. Постановки однокритериальных оптимизационных задач 40
2.1.3. Вычислительная сложность задач 1DZ1(sP) и 1DZ1(mP) 40
2.2. Однорейсовые задачи обслуживания 44
2.2.1. Математическая модель 1DZ2 44
2.2.2. Постановки однокритериальных оптимизационных задач 45
2.2.3. Алгоритмы решения задач 1DZ2(sP) и 1DZ2(mP) 45
2.2.4. Иллюстрирующий пример и результаты вычислительных экспериментов 49
2.3. Обобщенные задачи обслуживания 53
2.3.1. Математическая модель 1DZ3 53
2.3.2. Постановки однокритериальных оптимизационных задач 53
2.3.3. Алгоритмы решения задач 1DZ3(sP) и 1DZ3(mP) 54
2.3.4. Иллюстрирующий пример и результаты вычислительных экспериментов 55
2.4. Задачи обслуживания в двумерной рабочей зоне 58
2.4.1. Математическая модель 2DZ3 58
2.4.2. Постановки однокритериальных оптимизационных задач 59
2.4.3. Алгоритмы решения задач 2DZ3(sP) и 2DZ3(mP) 60
2.4.4. Иллюстрирующий пример 61
Выводы по главе 2 63
ГЛАВА 3. Многокритериальные задачи обслуживания стационарных объектов перемещающимся процессором 64
3.1. Двурейсовые задачи обслуживания 64
3.1.1. Постановки многокритериальных задач для модели 1DZ1 64
3.1.2. Алгоритмы решения задач 1DZ1(T,sP), 1DZ1(T,mP), 1DZ1(sP) и 1DZ1(mP) 65
3.1.3. Алгоритм решения задачи 1DZ1(Tc,T) 69
3.1.4. Иллюстрирующие примеры и результаты вычислительных экспериментов 73
3.2. Однорейсовые задачи обслуживания 80
3.2.1. Постановки многокритериальных задач для модели 1DZ2 80
3.2.2. Алгоритмы решения задач 1DZ2(L,T,sP), 1DZ2(L,T,mP), 1DZ2(T,sP) и 1DZ2(T,mP) 81
3.2.3. Иллюстрирующий пример и результаты вычислительных экспериментов 85
3.3. Обобщенные задачи обслуживания 92
3.3.1. Постановки многокритериальных задач для модели 1DZ3 92
3.3.2. Алгоритмы решения задач 1DZ3(L,T,sP), 1DZ3(L,T,mP), 1DZ3(T,sP) и 1DZ3(T,mP) 93
3.3.3. Вычислительная сложность задач 1DZ3(T,sP), 1DZ3(T,mP), 1DZ3(L,T,sP) и 1DZ3(L,T,mP) 96
3.3.4. Иллюстрирующий пример и результаты вычислительных экспериментов 97
3.4. Задачи обслуживания в двумерной рабочей зоне 104
3.4.1. Постановки многокритериальных задач для модели 2DZ3 104
3.4.2. Алгоритмы решения задач 2DZ3(L,T,sP), 2DZ3(L,T,mP), 2DZ3(T,sP) и 2DZ3(T,mP) 105
3.4.3. Иллюстрирующий пример 108
Выводы по главе 3 110
ГЛАВА 4. Алгоритмы синтеза субоптимальных стратегий обслуживания 111
4.1. Проблемы сравнения двух множеств оценок 111
4.2. Идеология эволюционно-генетических вычислений 114
4.2.1. Обобщенная структура генетического алгоритма 114
4.2.2. Оператор скрещивания в задачах синтеза стратегий обслуживания 117
4.3. Эволюционно-генетический алгоритм синтеза совокупности субэффективных оценок для решения задач, сформулированных в рамках моделей 1DZ3 и 2DZ3 120
4.3.1. Алгоритм решения однокритериальных задач 121
4.3.2. Алгоритм для решения многокритериальных задач 123
4.4. Результаты вычислительных экспериментов 126
Выводы по главе 4 131
ГЛАВА 5. Программный комплекс поддержки диспетчерского управления обслуживанием рассредоточенных объектов перемещающимся процессором 132
5.1. Обоснование выбора языка программирования Python 132
5.2. Программный комплекс поддержки оперативного управления обслуживанием рассредоточенных объектов 134
5.2.1. Назначение и функциональные возможности 134
5.2.2. Архитектура программного комплекса 135
5.2.3. Схема работы с программным комплексом 137
Выводы по главе 5 138
Заключение 139
Литература
- Регулярные методы решения задач теории расписаний
- Вычислительная сложность задач 1DZ1(sP) и 1DZ1(mP)
- Алгоритмы решения задач 1DZ1(T,sP), 1DZ1(T,mP), 1DZ1(sP) и 1DZ1(mP)
- Оператор скрещивания в задачах синтеза стратегий обслуживания
Регулярные методы решения задач теории расписаний
Теория расписаний – раздел исследования операций, в котором строятся и анализируются математические модели календарного планирования (т.е. распределения и упорядочения во времени) целенаправленных действий с учетом целевой функции и различных ограничений [56]. Здесь изучаются вопросы оптимального распределения и упорядочения конечных ресурсов или объектов – работ, требований или заявок – в системах с определенным числом обслуживающих процессоров – машин, приборов, станков – при различных ограничениях на перемещения и обслуживание.
Определение расписания (стратегии обслуживания) заключается в нахождении очередности обработки объектов процессором. Оптимальность стратегии подразумевает минимизацию или максимизацию какого-либо критерия, например, общего времени работы процессора, суммарного по объектам рабочей зоны штрафа, максимального по объектам штрафа и т.п. Различают три основных способа представления расписаний: 1) графическое представление – диаграмма Гантта [102] и др.; 2) табличное представление – в таблицах указываются промежутки времени, в которые выполняются задания, а также их исполнители (номер станка, процессор и т.п.); 3) векторное представление, где указывается лишь порядок обслуживания объектов. Именно такое представление будет использоваться в данной диссертационной работе. Первой в теории расписаний была известная работа Gantt H.L. (1903 г.) [102]. Термин «теория расписаний» в 50-х годах ввел Bellman R. [88]. К числу первых в этой теории следует отнести работы Smith W.E. [121], Johnson S.M. [106], Jackson J.R. [105]. Отдельным направлением в области исследования операций данная проблематика стала благодаря работам Bellman R. [13], Brucker P. [93, 94], Coffman E.G. [95, 96], Conway R.W. [98], Garey M. [26], Graham R.L. [104], Johnson D. [26], Karp R.M. [35], Lawler E.L. [109], Lenstra J.K. [110], Maxwell W.L. [98], Miller L.W. [98], Pinedo M.L. [119], Танаева В.С. [23, 79, 80, 81, 82], Шкурбы В.В. [79].
Различные проблемы управления обслуживанием в моделях транс-портно-технологических систем и соответствующие им задачи синтеза расписаний обслуживания исследовались в работах Blazewicz J. [89, 90, 91, 92], Gen-dreau M. [103], Nossack J. [103, 116, 117], Pesch E. [89, 90, 91, 92, 118], Sterna M. [89, 90, 91], Werner F. [89, 90, 91], Батищева Д.И. [3], Беленького А.С. [11, 12], Буркова В.Н. [16], Гимади Э.Х. [19, 80], Гордона В.С. [23, 24], Зака Ю.А. [33, 34], Ковалева М.Я. [82], Корбута А.А. [47, 48], Лазарева А.А. [54, 55], Лев-нера Е.В. [11, 12], Новикова Д.И. [22, 44], Подчасовой Т.П. [64], Прилуц-кого М.Х. [65], Серваха В.В. [75, 76], Сигала И.Х. [77, 78], Сотскова Ю.Н. [81], Струсевича В.А. [81], Ульянова М.В. [83, 84], Фазылова В.Р. [1, 15], Финкель-штейна Ю.Ю. [85], Шафранского Я.М. [80, 82] и др.
В работах указанных авторов, как правило, полагается, что обслуживающие процессоры стационарны, а требующие обслуживания объекты поступают к ним в заданные моменты времени; оптимизируется только один критерий. В работах Дуничкиной Н.А. [27], Когана Д.И. [38, 39], Федосенко Ю.С. [38, 39], Шлюгаева А.Ю. [86] объекты считаются стационарными, расположенными в рабочей зоне перемещающегося процессора. Настоящее исследование развивает работы, относящиеся к последнему направлению. При этом принципиальными являются следующие особенности: – учет ранних сроков готовности объектов к обслуживанию; – системные ограничения на возможные траектории перемещения обслуживающего процессора; – возможность одновременного учета нескольких критериев оценки качества стратегий обслуживания. Первая особенность объясняется тем, что в ряде приложений обслуживание объекта до раннего срока либо запрещено, либо не имеет смысла.
Вторая особенность объясняется тем фактом, что на содержательном уровне модель может описывать различные технологические производства или транспортные системы. Рассмотрение двух различных видов рабочих зон поможет более гибко подобрать модель к реальной ситуации.
Третья особенность объясняется тем, что для практических задач наличие одного критерия оценки стратегии обслуживания недостаточно и ЛПР необходимо учитывать набор независимых критериев, которые зачастую могут противоречить друг другу. В таком случае в распоряжение ЛПР предоставляется совокупность эффективных векторных оценок (по каждой такой оценке легко строится порождающая ее Парето-оптимальная стратегия обслуживания).
Большой вклад в многокритериальную оптимизацию внесли работы T Kindt V. и Billaut J.-Ch. [122], Villareal B. и Karwan M. [124], Когана Д.И. [36], Ногина В.Д. [60, 63], Подиновского В.В. [63], и др.
Спецификой задач теории расписаний является тот факт, что на синтез стратегий обслуживания накладывается жесткий регламент времени (до 30 минут). Как следствие, актуальна разработка быстрых методов решения задач, способных предоставить стратегию обслуживания за малый промежуток времени. Поэтому существенное внимание в теории расписаний уделяется вопросам вычислительной сложности рассматриваемых задач, а также сложности решающих их алгоритмов. Задачи теории расписаний - подкласс задач дискретной оптимизации. Дискретные задачи имеют разную сложность решения. Существует два принципиально различающихся подхода к оценке сложности решающего алгоритма. Первый подход подразумевает оценку сложности создания алгоритма решения, где учитываются такие параметры, как количество операторов, количество циклов, количество итераций и т.п. Второй подход подразумевает оценку, характеризующую трудоемкость реализации алгоритма при компьютерных вычислениях; здесь фигурируют такие параметры, как количество элементарных операций, объем памяти, скорость центрального процессора (ЦП) и т.д., т.е. оценка описывает время вычислений на рабочей станции. Именно второй подход является целесообразным при классификации задач по их вычислительной сложности [36].
Каждый алгоритм создается для решения массовой задачи Z, т.е. множества однотипных задач, отличающихся друг от друга лишь начальными данными. Отсюда имеем, что оценки вычислительной сложности являются функциями от объема начальных данных.
Вычислительная сложность задач 1DZ1(sP) и 1DZ1(mP)
Перемещающийся в одномерной рабочей зоне L процессор Р должен обслужить совокупность стационарных объектов Оп = {о1,о2,...,оп}, расположенных соответственно в точках 1,2,...,п . Указанная зона конечна; её начальная точка А является базовой для процессора, обозначим ее цифрой 0. Объекты пронумерованы в порядке возрастания их расстояний от точки А. Конечная точка В зоны L является местом расположения объекта оп. Из точки А, начиная с момента времени t = 0, процессор поступательно перемещается в точку В (прямой рейс, примем для него обозначение Л+) и затем, достигнув ее, возвращается в точку А (обратный рейс, примем для него обозначение Л_).
При реализации маршрута Л+Л_ процессор Р должен выполнить однократное без прерываний обслуживание каждого объекта группы 0„. Часть объектов обслуживается в рейсе Л+, остальные объекты - в рейсе Л_.
Для каждого объекта о. указаны следующие величины: требуемая продолжительность обслуживания объекта о] процессором Р; г] - ранний срок начала обслуживания объекта о., ср} (f) - монотонно возрастающая (в нестрогом смысле) функция индивидуального штрафа, выражающая зависящую от момента завершения обслуживания объекта величину экономических по терь по объекту оj. Также заданы величины у 1 и у }_1, определяющие затраты времени на перемещения процессора между точками (у-1) иу в рейсах Л+ и Л_ соответственно; при этом у01 и у1 0 - затраты времени на перемещение процессора между точкой ,4 и объектом о1 в прямом и обратном рейсах соответственно. Все величины y j, Yjj-1, tj - натуральные числа; г. - целые неотрицательные числа. Стратегией обслуживания именуем произвольное подмножество элементов p = {l1,l2,...,lk) из совокупности индексов N = {1,2,...,«}. Объекты о где у є /7, в реализации стратегии /7 обслуживаются процессором в рейсе Л+, все остальные объекты группы Оп - в рейсе А.. Далее для определенности полагаем, что объект оп обслуживается при завершении процессором рейса Л+. Множество допустимых для модели 1DZ1 стратегий обозначим через И11.
При реализации определяемого стратегией р рейса обслуживание любого объекта о j., j є N, начинается либо от момента его готовности г., либо от момента прибытия процессора в точку j (если на момент прибытия объект уже готов к обслуживанию). В случае прибытия процессора в точку j в момент времени t , t Tj, процессор простаивает в ожидании готовности объекта о j. Величина (г, ) - время ожидания готовности объекта о] к обслуживанию. Завершив обслуживание, процессор продолжает выполняемый рейс. Не связанные с обслуживанием объектов и ожиданием наступления ранних сроков промежуточные простои процессора запрещены. Одновременное обслуживание двух и более объектов недопустимо.
Описанную модель далее будем именовать 1DZ1. 2.1.2. Постановки однокритериальных оптимизационных задач Здесь и далее для минимизируемых критериев будут использоваться следующие обозначения: 1) KsP(p)- суммарный по объектам штраф; 2) КтР(р)- максимальный из индивидуальных штрафов. С позиций повышения эффективности диспетчерского управления обслуживанием совокупности объектов Оп целесообразно рассмотрение следующих задач. Задача 1DZ1(sP). Минимизировать суммарный штраф по всем объектам множества Оп: min1fc(p)). (2.1) Задача 1DZ1(mP). Минимизировать максимальный из индивидуальных штрафов по всем объектам множества Оп: Решение поставленных задач выполняется путем их расширения до бикритериальных постановок, где в качестве второго критерия вводится общее время работы процессора на рабочей зоне. Общий алгоритм решения представлен в п. 3.1.2 данной диссертации.
Доказательства приводимых далее теорем заключаются в выполнении полиномиальных сведений М -полной задачи «Разбиение» к сформулированным в них проблемам. Напомним содержание задачи «Разбиение». Имеется конечное множество натуральных чисел W = {w1,w2,...,wnY Спрашивается, можно ли это множество разбить на два непересекающихся подмножества так, чтобы сумма чисел, входящих в первое подмножество, оказалась равной сумме чисел, входящих во второе подмножество. Очевидным необходимым условием положительного ответа является непревышение каждым из чисел множества W половины их суммы. Отметим также, что задача сохраняет NP-полноту в случае, когда все элементы множества W являются четными чис п лами. Далее считаем, что У . = 2U, все w. - четные числа и w. U,i = 1,п. 2=1 Теорема 1. Задача (2.1), в которой все функции индивидуального штрафа линейны и имеется объект с отличным от нуля ранним сроком начала обслуживания, М -трудна. Доказательство. По исходным данным задачи «Разбиение» строим задачу, в которой процессор Р при последовательном выполнении рейсов Л+ и Л_ должен обслужить расположенные в одномерной рабочей зоне L стационарные объекты о1,о2,...,ои+2; объект о. считаем находящимся в точке /. Каждая из введенных в основном тексте статьи величин yt_1., yi м, где i = 1,n + 2, считается равной единице. В множестве Оп+2 = {о1,о2,...,ои+1,ои+2} в качестве особых выделяем объекты о1 и оп+2; все остальные объекты именуем ординарными. Продолжительность обслуживания процессором ординарного объекта о.+1 полагаем равной wt, i = 1,n; таким образом, суммарные затраты времени на обслуживание всех ординарных объектов равны 2U. Продолжительности обслуживания особых объектов следующие: т1 = U +1, тп+2 = 1. Функции индивидуального штрафа для особых объектов определяются так: (p1(t} = t, (pn+2(t) = Dt, где D - достаточно большая константа, ее значение будет определено ниже. Функции индивидуального штрафа для ординарных объектов считаем тождественно равными нулю. Каждый из объектов о j = 1,п +1, считается готовым к обслуживанию, начиная от момента t = 0; полагаем, что
Обслуживание особого объекта оп+2 может быть начато в момент времени гп+2 в том и только том случае, когда на обслуживание всех остальных объектов в прямом рейсе процессор затрачивает время, не превосходящее U (на все перемещения процессора в прямом рейсе затрачивается п + 2 единицы времени).
Предположим, что обслуживание объекта оп+2 начинается в момент гп+2. Тогда величина индивидуального штрафа по нему оказывается равной D((n + 3) + Uy; при этом объект о1 в прямом рейсе не обслуживается и на непосредственное обслуживание ординарных объектов в прямом рейсе затрачивается время U - Е,, где Е, - число из множества {0,1,...,/}. Легко подсчи тывается, что обслуживание объекта о1 в таком случае завершается в момент времени Т = 2n + 3U + 5 + Е, . Суммарный штраф по всем объектам оказывается равным Dun + 3) + її) + Т.
Отметим, что Т 2п + 4U + 5 и положим D = 2n + 4U + 6 . При этом получаем, что в случае, когда объект о1 обслуживается в прямом рейсе или на непосредственное обслуживание ординарных объектов в прямом рейсе затрачивается время, превышающее U, суммарный штраф по всем объектам превышает D((n + 3) + U + 1); если же объект о1 обслуживается в обратном рейсе и на непосредственное обслуживание ординарных объектов в прямом рейсе затрачивается время, не превышающее U, этот штраф меньше, чем ((« +3) + С/+ 1).
Алгоритмы решения задач 1DZ1(T,sP), 1DZ1(T,mP), 1DZ1(sP) и 1DZ1(mP)
Далее через F обозначим совокупность двумерных векторов с индексами F(/),/ = 1,и , имеющих записи вида (а,Ь)., где а - значение по первому критерию, Ь - значение по второму критерию J - последний объект обслуживания в стратегии р, оцениваемой критериями а и Ь. Элемент F(j)mF - оценка работы процессора при условии, что последним обслуживается объект о}. Через Е обозначим эффективные в F оценки. Очевидно, что Совокупность эффективных оценок в задаче (3.14) находим по формуле: E = Qtt\F(j)j = \ji}. (3.25) Выбор в совокупности Е осуществляет ЛПР. В соответствии с выбранной оценкой определяется соответствующая стратегия обслуживания. Пусть ЛПР выбрал оценку (к0,К02) . Порождающая эту оценку стратегия р0 стро ится следующим образом (здесь через ркном обозначим подпоследовательность последовательности рном, включающую только те элементы из рном, которые превосходят к). Если j0=n, то р0 = {1,2,..., и}. Если j0=n-1, то р0 = {1,2,...,и - 2,п}. Если j0 = р, то р0 состоит из двух частей: первую часть составляет подпоследовательность чисел 1,2,...,/?-1, а вторую подпоследовательность рЩ (здесь р = п-3,п-4,...,2). Если р = 1, то р0 = р\ом .
Формулы (3.15)-(3.25) - рекуррентные соотношения динамического программирования для решения задачи (3.3).
Для иллюстрации технологий расчета по рекуррентным соотношениям (3.4)-(3.11) и (3.15)-(3.25) рассмотрим примеры решения задач 1DZ1(T,sP) и 1DZ1(Tc,T).
Процесс решения задачи начнем с определения для каждого значения к, к = 1,п, множества 0 . возможных значений моментов t прибытия процессора в точку к при реализации рейса Л+. Очевидно, что единственным возможным значением t при к = 1 является у01 = 1, то есть &1 = {1}. Согласно (3.11) получаем: 02 = {16,6}, 03= {18,8,17,7} Начинаем вычисление значений E(k,t) по соотношениям (3.4)-(3.9).
Так, запись {а,Ъ). означает, что оценка (а,Ь) с номером / получена из оценки с номером j, при этом объект ок обслуживается в рейсе Л+. Запись (а,Ь). . _ означает, что оценка (а,/?) с номером / получена из оценки с номером j, при этом объект ок обслуживается в рейсе Л_. Данная информация потребуется в дальнейшем при построении стратегии обслуживания, обеспечивающей определенные значения критериев.
Используя (3.4) заполняем третью строку таблицы (к = 3). При этом считаем, что все оценки при к = 3 получены из фиктивной оценки с номером О, и имеем в виду, что последний объект всегда обслуживается в рейсе Л+.
Применение соотношений (3.5)-(3.9) продемонстрируем на вычислении значения Е(2,6). Согласно (3.9) Е(2,б) = eff (Р(2,6)и 2(2,б)).
Определение множества Р(2,6). Начинаем с вычисления величины // . // =//2 + Г23=тах(ґ,г2) + г2 + г23=тах(б,4) + 1 + 1 = 8. Таким образом, при подсчете будут использоваться оценки из множества ІІ(3,8) = {(0,16)} . Согласно (3.5) и (3.6) имеем Р(2,б) = {(\6 + узл, р2(так(б,г2) + т2) 0)} = {(17, 2 (17))} = {(17,0)}. Оценке (17,0) присваиваем следующий номер по порядку - 5, она получена из оценки с номером 2; вычисление по формуле (3.6) соответствует обслуживанию объекта о2 в рейсе Л+. Определение множества 2(2,б). Начинаем с вычисления величины v\. v 2=t + 723=6 + \ = 7. Таким образом, при подсчете будут использоваться оценки из множества (3,7) = {(0,16)}. Согласно (3.7) и (3.8) имеем т2 = max(l6 + уъ 2,г2) + г2, g(2,6) = {(cr2, 2(cr2))J = (l8, 2(l8)) = {(18,2)}. Оценке (18,2) присваиваем следующий номер по порядку - 6, она получена из оценки с номером 1; вычисление по формуле (3.8) соответствует обслуживанию объекта о2 в рейсе Л_. Определение множества Я(2,6). (2,6) = eff ({(17,0),(18,2)}) Аналогичным образом проводим вычисления остальных значений E(k,t} и вносим их в таблицу. Пустые ячейки в таблице 3.2 соответствуют нереализуемым парам {k,t}. Таблица 3.2. Значения E(k,t) примера 3.1. t к\ 1 6 7 8 16 17 18 1 (25,10)9,7,+ (32,3)10,5,- 2 (17,0)5,2,+ (20,10)7,4,+ 3 (16,0)i,o,+ (16,0)2,о,+ (18,5)з,о,+ (19,10)4,о,+ Согласно (3.10) получаем Е = {(26,10),(33,3)}. Пусть из множества Е ЛПР выбрало для реализации оценку (33,3). Для восстановления стратегии обслуживания, порождающей указанную оценку, воспользуемся значениями нижних индексов, которые мы вносили в таблицу во время счёта. Оценке (33,3) соответствует оценка (32,3) с номером 10. Она соответствует обслуживанию объекта ох в рейсе Х_ и получена из оценки с номером 5 - (17,0). Оценка (17,0) соответствует обслуживанию объекта o2 в рейсе Л+ и получена из оценки с номером 2 - (16,0). Оценка (16,0) соответствует обслуживанию объекта о3 в рейсе Л+ и получена из оценки с номером 0, то есть фиктивной оценки. Процесс восстановления стратегии на этом заканчивается, в прямом рейсе обслуживаются объекты о2 и о3, т.е.
Вычисления начинаются с нахождения значений W(k) по формуле (3.16): W(l) = 3ll, W(2) = 26l, W(3) = 159, W(A) = 9S, W(5) = 10.
Согласно формулам (3.15) и (3.17) находим значения D(k): D(l) = 115, D(2) = 138, D(3) = 186, D(4) = 219, D(5) = 188. Согласно изложенному алгоритму при вычислении значений D(k) в последовательность рном вносим требуемые индексы: рном = (3,5).
Далее по формулам (3.18) и (3.19) находим пары значений Sk(p ) и Ck(p )\ Sx(p ) = \22, Q(р ) = 132, S2(p ) = 16&, С2(р ) = 174, S3(p ) = 222, С3(р ) = 227, S4(p ) = 3U, С4(//) = 317, 55(/? ) = 358, С5(/? ) = 368.
Теперь по формулам (3.20), (3.22) и (3.24) находим множество оценок F = {(432,452)1,(416,459)2,(381,472)3,(353,472)4,(368,528)5}.
Согласно формуле (3.25) из полученного набора F выбираем эффективные оценки и для каждой из них строим соответствующие стратегии обслуживания. Полученные результаты представлены в таблице 3.4. Таблица 3.4. Эффективные оценки и соответствующие им стратегии обслуживания для примера 3.2.
Оператор скрещивания в задачах синтеза стратегий обслуживания
Синтез совокупности оптимальных по Парето стратегий обслуживания при использовании алгоритмов, предложенных в главах 2 и 3, не всегда укладывается в допустимый временной регламент, установленный на производстве. В связи с этим обстоятельством несомненный интерес представляют алгоритмы построения совокупностей субэффективных оценок с погрешностями, приемлемыми для приложений.
При реализации приближенных алгоритмов синтеза субоптимальных решений возникает необходимость сравнения множества оценок E, полученного точным методом решения (паретовское множество), с приближенной совокупностью оценок E , полученной каким-либо приближенным методом (квазипаретовское), для оценивания отклонения E от E.
Указанное отклонение вычисляется следующим образом. Предположим, что pi, / = 1,iil, qj, j = 1, E - элементы множеств E и E соответственно, в общем случае \Е\Ф Е . Набор критериев оценки работы процессора можно рассматривать как декартовы координаты точки в пространстве (при этом размерность пространства определяется количеством критериев). Точка О с нулевыми координатами соответствует началу координат. Через \АВ\ будем обозначать расстояние между точками (оценками) А и В, вычисляемое следующим образом (при наличии в оценке т критериев):
Таким образом, для каждой оценки pt из множества Е ищется ближайшая по расстоянию оценка q} из множества Е . Затем полученное значение нормируется на длину отрезка от рг до начала координат. Из полученных величин выбирается большая из них, как более точная.
Такой способ оценивания отклонения дает представление об общем приближении квазипаретовского множества Е к паретовскому множеству Е. Существует недостаток, который продемонстрируем на паре примеров. Предположим, что Е и Е - равномощные множества. Пусть Я = {(40Д02Д30),(30Д04Д20)}, Я = {(39Д01Д28),(32Д08Д25)}. Тогда по формуле (4.2) отклонение будет следующим: A(,-) = maxfm n(2-45-1U8), mln 12-41-6J1)].100 = 4.15%. v \ 170.01 161.60 ) Теперь рассмотрим пример с неравномощными множествами Е и Е . Пусть Я = {(40Д02Д30),(30Д04Д20),(50Д08Д10)},Я = {(39,101,128)}. Тогда по формуле (4.2) отклонение будет равно: ./ г ч fmin(2.45) min(l2.4l) тіп(22.23Л 1ПП л,-,0/ А\Е,Е ) = тах , , -100 = 13.76%. v \ 170.01 161.60 162.06 ) Из примеров становится ясно, что неравномощные множества Е и Е могут порождать достаточно большие значения отклонения. В работе [27] представлен другой подход к оцениванию отклонения. Предлагается следующая формула (для бикритериального случая): avg ( mm t(p((W,Q);(W ,Q )))\ A(E,E ) = {W {W,Q)&E( (l —Ґ гтч 100,%, (4.3) avg (p[{W,Q);(0,0)j) 112 где W - значение первого критерия, Q - значение второго критерия, p((W,Q);(W ,Q )) = тах(Ж - W \,\Q - Q \) - расстояние между двумя оценками, avg - операция вычисления среднего значения, p[(W,Q),(0,0)j - расстояние между оценкой (W,Q) и оценкой (0,0).
Здесь для каждой оценки из паретовского множества Е находят ближайшую к ней оценку из квазипаретовского множества Е , затем проводится усреднение по всем оценкам из Е и полученную величину нормируют на среднее значение расстояния от эффективной оценки до нуля.
Очевидно, что неравномощные множества Е и Е также могут порождать большие вычисляемые по формуле (4.4) значения отклонения, однако эти значения меньше, чем вычисляемые по формуле (4.2).
Первый способ оценивания определяет максимальное отклонение по всем оценкам паретовского множества Е, тогда как второй - усредненное. Предложенные формулы (4.2) и (4.4) вычисления отклонений будут использованы ниже для оценивания возможностей разрабатываемых алгоритмов синтеза квазипаретовских совокупностей оценок обслуживания стационарных объектов перемещающимся процессором.
Эволюционно-генетический алгоритм [8, 10, 20] - это эвристический алгоритм поисковой оптимизации, который начинает свою работу с начальной популяции П0, состоящей из К хромосом, и итеративно исполняющий специальный набор операций. Популяцией считается множество хромосом к0\к0п,к02,...,к0Л, где і: = 1,К, п - количество генов в хромосоме, зависит от характеристик решаемой задачи. Исполняемые в цикле операции (для произвольного поколения g) следующие. 1. Оценивание - вычисление значений функции приспособленности для каждой хромосомы к , здесь і= ЦС, g - итератор поколений (номер текущего поколения). Функция приспособленности соответствует вычислению критериев оптимальности в рассматриваемой задаче оптимизации. 2. Селекция - выбор из популяции Ug репродукционной совокупности Ng - подмножества хромосом из Пй . 3. Репродукция (создание нового поколения) - синтез новых хромосом из множества Ng при помощи следующих операций (или комбинации этих операций).