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

В производственных и вычислительных системах конвейерного типа (в многостадийных системах (МС)) возникают задачи планирования выполнения пакетов заданий (ПЗ). Для их решения используется иерархический подход [1]. Под заданием подразумевается работа, выполняемая на приборах с материалами либо данными, после которой будут сформированы результаты. При планировании заданными являются наборы однотипных заданий (однотипными являются зaдaния, длительности выполнения которых нa приборах МС одинaковы, длительности перенaладок приборов нa выполнение этих заданий также одинaковы). При значительных неоднородностях длительностей выполнения заданий и неоднородностях длительностей переналадок приборов действия с ними в МС реализуются в составе пакетов. Пакетом является набор однотипных заданий, выполняемых на приборах МС без их переналадки на выполнение заданий других типов. Количество заданий в пакетах определяется с учетом временных характеристик процесса их выполнения в МС. Если составы пакетов не оптимизируются и в пакеты входят все задания из их наборов, то такие пакеты называются фиксированными. Оптимизация составов пакетов, осуществляемая с учетом временных параметров выполнения заданий, позволяет повысить эффективность планирования реализации действий с ними на приборах МС.

Решение задачи планирования выполнения ПЗ в МС предполагает определение их составов и расписаний реализации действий с ними на приборах МС [1]. Развитием задачи [1] является задача планирования выполнения ПЗ в МС при формировании комплектов результатов (КР) [2]. Под комплектом подразумевается набор заданного состава результатов выполнения в МС заданий разных типов. Также развитием иерархического подхода к планированию является задача построения комплексных расписаний выполнения ПЗ в МС при ограничении на длительности интервалов времени функционирования системы [3]. Планирование выполнения ПЗ в МС при ограничении на длительности интервалов времени ее функционирования предполагает определение решений по [3]: составам пакетов, составам групп пакетов, выполняемых в течение интервалов времени заданной длительности, расписаний реализации действий с пакетами, входящими в группы, на приборах МС. Развитием иерархического подхода к планированию выполнения ПЗ [1–3] является задача построения комплексных расписаний реализации действий с пакетами в МС при ограничении на интервалы времени функционирования системы и формировании КР. Не смотря на то, что являются разработанными методы определения составов ПЗ [1], распределения результатов выполнения ПЗ по комплектам [2], определения составов групп ПЗ [3], они могут быть применены при решении указанной задачи. В силу того, что задача комплексного планирования выполнения ПЗ в МС является NP -трудной ([3]), ее решение может быть найдено с использованием приближенных методов оптимизации.

Цель работы состоит в совершенствовании методов планирования выполнения ПЗ в МС при ограничениях и формировании КР. Для достижение цели решаются задачи: обоснования применения иерархического подхода при планировании выполнения ПЗ в МС с учетом введенных условий; построения модели иерархической игры планирования выполнения ПЗ в МС; построения алгоритма распределения результатов выполнения ПЗ, входящих в группы, по комплектам; построения метода оптимизации составов групп ПЗ.

• 1.    Анализ существующих методов построения комплексных расписаний выполнения пакетов заданий в многостадийных системах

• 2.    Математическая модель иерархической игрыдля комплексного планирования выполнения ПЗ в МСпри ограничении на ресурсы и условии формирования КР

В работах отечественных авторов [4–8] исследуются методы построения расписаний выполнения единичных заданий. При этом рассматриваются различные виды систем обработки (с одинаковыми, различными и нефиксированными маршрутами выполнения заданий), учитываются упрощающие условия (ограниченное количество приборов, одинаковые порядки выполнения заданий в системах, упорядочивание значений длительностей выполнения заданий). Задачи оптимизации составов ПЗ в [4–8] не решаются.

Методы планирования выполнения ПЗ в обрабатывающих системах различного вида (где каждое задание, входящее в пакет, представляет собой отдельную работу, выполняемую с материалами или данными) рассмотрены в [9–19]. Использование целочисленного линейного программирования (ЦЧЛП) для планирования обработ- ки ПЗ на параллельных приборах рассмотрено в [9]. Путем решения задачи ЦЧЛП (определения значений целочисленных и бинарных переменных) формируется комплексное решение, включающее составы ПЗ и расписания их выполнения на приборах МС. Так как для решения задач применено ЦЧЛП, то их размерность является ограниченной. В [10] рассматривается метод планирования выполнения ПЗ на параллельных приборах на основе локального поиска совместно с методом муравьиной колонии (МК) при использовании эвристических правил. Для включения задания в пакет вычисляется значение параметра, в котором учтены длительности выполнения задания и соответствующего пакета. Задания сортируются по не убыванию значений этого параметра, и определенное их количество включается в пакеты. Использование алгоритма МК для планирования выполнения ПЗ на параллельных приборах рассматривается в [11]. Алгоритм объединяет в пакеты задания, имеющие близкие длительности выполнения. В силу стохастического характера алгоритма он не гарантируют получения решений, приближающихся к оптимальным, при разных значениях входных параметров задачи. В [12,13] решается задача планирования выполнения ПЗ на параллельных приборах при указании директивных сроков окончания заданий. В состав пакетов включаются задания, у которых близкими являются директивные сроки их выполнения. В работе [14] рассматривается решение задачи определения составов ПЗ и очередности их выполнения на параллельных приборах с использованием эвристических правил. При формировании пакетов для каждого задания вычисляется значение параметра, учитывающего его вес, длительность выполнения, среднюю длительность выполнения заданий, не распределенных по пакетам и т.д. В соответствии со значениями параметра формируется порядок заданий, количество заданий, соответствующее размеру пакета, закрепляется за прибором.

Применению эвристических правил при определении составов ПЗ, выполняемых на параллельных приборах, посвящена работа [15]. В соответствии с правилами в пакет включаются задания с близкими значениями длительностей их выполнения. Использование различных эвристических правил при формировании чередующихся окрестностей текущего локально оптимального решения по составам ПЗ рассмотрено в [16]. В формируемых окрестностях реализуется определение нового локально оптимального решения по составам ПЗ и расписаниям их выполнения. Рассмотренный способ реализует не направленный поиск локально оптимальных решений, а стохастический поиск, что не гарантирует получения результатов при разных значениях входных параметров. Работы [17,18] также посвящены рассмотрению эвристических правил формирования ПЗ. В [17] правило предусматривает включение в пакет заданий, длительности выполнения которых связаны с длительностью выполнения первого задания в этом пакете определенным образом. В [18] правила предусматривают формирование различных множеств отклоняемых заданий и для каждого множества не отклоненных заданий формирование пакетов.

Анализ существующих способов комплексного планирования выполнения ПЗ в МС показал, что отсутствуют методы, позволяющие определять составы ПЗ без ограничения на размерность решаемой задачи для обрабатывающих систем любого вида. Ни один из рассмотренных методов не решает задачу определения составов ПЗ в МС при учете ограничения на интервалы времени ее функционирования и формировании КР.

Для решения задачи планирования выполнения ПЗ в МС при ограничении на интервалы времени ее функционирования и условии формирования КР реализована декомпозиция обобщенной функции системы построения расписаний на совокупность подфункций. Каждая из них реализуется с использованием соответствующей подсистемы. Функционирование этих подсистем предполагает оптимизацию решений по: составам ПЗ, выполняемых в МС (первый уровень); составам групп ПЗ, выполняемых в течение временных интервалов заданной длительности (второй уровень); порядкам выполнения ПЗ из групп на приборах МС (третий уровень). При этом в системе реализуется заданный порядок ходов. В связи с этим для оптимизации решений на уровнях в иерархической системе построения расписаний применена теория иерархических игр. В этом случае игрок первого уровня реализует формирование решений по составам ПЗ, игрок второго уровня – по составам групп ПЗ, игрок третьего уровня – по расписаниям выполнения ПЗ из групп в МС. Порядок взаимодействия игроков в иерархической игре следующий: 1) первый ход делает первый игрок, определяя составы ПЗ, и передает решение на второй уровень; 2) второй ход делает второй игрок, определяя для полученных составов ПЗ решение по составам их групп, и передает это решение на третий уровень; 3) третий ход делает третий игрок, формируя оптимальное расписание выполнения ПЗ, входящих в группы, в МС, и передает его на второй уровень для оценки на его основе степени оптимальности решения по составам групп; 4) для решения по составам ПЗ второй игрок определяет локально оптимальное решение по распределению этих пакетов по группам, после чего это решение передается первому игроку для анализа степени оптимальности его решения; 5) игрок первого уровня формирует новое решение, передает его игроку второго уровня; оптимизация решений по составам ПЗ на первом уровне реализуется с учетом решений по составам групп. Игрок с нижестоящего уровня принимает решения, которые являются благоприятствующими для игрока вышестоящего уровня, т.е. реализуется не антагонистическая иерархическая игра.

В модели процесса выполнения ПЗ в МС при ограничении на длительности интервалов времени ее функционирования использованы обозначения [1]: m i – количество ПЗ i -го типа (i = 1,n), формируемых на первом уровне, элементы m i образуют вектор M ; А - матрица, элемент a ih которой - это количество заданий i -го типа в h-ом ПЗ (h = 1,m i ). Решение по составам ПЗ имеет вид: [М, А]. Задача предполагает задание длительностей интервалов времени функционирования МС t z (z = 1, Z). Решение по составам групп ПЗ, представляется множеством {N ^z |z = 1,Z } кортежей вида [3] : N ^z = { [i,m z , (A) z ] _k , | k = 1,k _z } ^z , где m z - количество ПЗ i-го типа, включенных в группу N ^z , (A) Z — вектор, h-ый элемент которого соответствует составу ПЗ i-го типа. Для ПЗ, не включенных в группы, введено множество Q кортежей вида: Q = { [i,m q , (A) q ] _k , | k = 1, k q } , где m q - количество ПЗ i -го типа, (A) q - вектор составов пакетов i-го типа. Решение по составам групп ПЗ имеет вид: { N ^z | (z = 1, Z) } (где N ^z = { [i, m Z , (A) Z ] k , | k = 1Л } ^z ) и Q = { [i, m q , (A) q ] k , | k = 1Л } .

Расписание выполнения ПЗ групп Nz в МС формируется в предположении, что порядок реализации действий с ними является одинаковым на всех приборах МС. С целью определения расписания выполнения ПЗ введены [3]: Pz – матрица порядка выполнения заданий, пакеты которых включены в группуN z , на приборах системы, Rz – матрица количества заданий i-ых типов в ПЗ, занимающих в последовательностях j-е позиции; (T01 )z - матрицы моментов времени (t^)z начала выполнения q-ых заданий в пакетах, занимающих j -е позиции в последовательностях реализации действий с ними на приборах МС (z = 1,Z, l = 1,L). Также в рассмотрение введены параметры, характеризующие процесс выполнения ПЗ в МС [3]: (tii)z - длительности выполнения заданий i-ых типов на l-ых приборах МС, пакеты которых включены в группы Nz (i = 1,n, l = 1,L, z = 1,Z)); (tii)z — длительности переналадок l-ых приборов с выполнения заданий i-ых типов на выполнение заданий i-ых типов, пакеты которых включены в группы Nz (l = 1,L,z = 1,Z), np - количество

пакетов в группе N z . Расписание выполнения ПЗ из групп N z (z = 1, Z) имеет вид:

{ [P ^z ,R ^z , { (T ^{0 1} ) ^z | (l = 1,L) } ] | z = 1,Z) } .

начала вы-

Согласно обозначениями [3] (t°L n Z)zсоответствует моменту времени p, np полнения последнего nnzp -го задания в nzp-м пакете из группы Nzна L-ом приборе. С использованием выражения [3] (t^L,n^z )z+^k= 1 (tLi)z-p^z (где ^k= 1 (tLi)z -Pz^nzопределяет длительность выполнения последнего задания в nzp-м пакете на L-м приборе) реализуется вычисление момента времени окончания выполнения ПЗ, включенных в группу Nz.

С целью построения модели иерархической игры оптимизации решений по составам ПЗ, групп ПЗ и расписаниям выполнения ПЗ (при формировании КР) введены обозначения: g – идентификатор типа комплекта, который формируется из результатов выполнения ПЗ в МС (g = 1,g ^KOM ),w _ig - количество результатов выполнения заданий i-го типа, которые включаются в один комплект g-го типа, n _g ^ком – количество комплектов g-го типа (g = 1,g ^ком ), которые требуется сформировать из результатов выполнения ПЗ, n g (g = 1,g ^ком ) - количество комплектов g-го типа, которые будут сформированы из результатов выполнения ПЗ, включенных в группы N ^z , N _g – вектор количества сформированных комплектов g-х типов. Параметры g ^ком , w _ig , n _g ^ком являются входными данными для задачи планирования, вектор N g – результат решения задачи. Он включен в состав решения на втором уровне: [ { N ^z | (z = 1, Z ) } , Q, N g ].

Результаты выполнения заданий всех n типов входят в определенном количестве в комплекты каждого типа. В рассмотрение введены множества и параметры, позволяющие реализовать распределение результатов выполнения ПЗ в МС по комплектам:K _y ^ком , K _y ^{ком ′} – множества идентификаторов типов комплектов, упорядоченные в соответствии с рассматриваемым в [2] способом (по сложности составов комплектов); p – позиция типа g комплекта, на которой он размещается в множествах K _y ^ком и K _y ^{ком ′} ; g _p – идентификатор типа комплекта, занимающий в множестве К к ^ом p -ю позицию (p = 1,g ^ком ).

Комплекты формируются из результатов выполнения ПЗ, включенных в группы. Количество выполненных в течение интервалов t ^z заданий зависит от составов ПЗ; составы групп ПЗ и количество сформированных КР является зависящими от составов пакетов. Построение решений по составам ПЗ, распределение ПЗ по группам, построение расписаний выполнения ПЗ из групп должно обеспечить формирование максимального количества КР. Количество сформированных КР определяется выражением^ д₌₁ n g , которое является критерием оптимальности решений [M,A].

Выполнение ПЗ в течение интервалов tz должно обеспечивать наиболее полное использование ресурса времени МС. Решения по составам групп Nz (z = 1, Z) должны обеспечивать минимальное количество выполненных заданий, результаты которых не будут включены в комплекты. Тогда на втором уровне наряду с определением решений по составам групп ПЗ требуется выполнить формирование КР (вектора Ng).

Через [(ah)Z]k обозначен h-ый элемент вектора (A)Z, входящего в к-ый кортеж [i,mZ, (A)Z]k € Nz, соответствующего составам ПЗ i-го типа, включенным в группу Nz . Количество заданий i-го типа в пакетах, включенных в группу Nz , определяется выражением^m 1 [(ah)Z]k, количество заданий разных типов в этой группе - выражением Ek=1 Em= 1 [(ah)z ]k. Количество заданий, которые выполнены в составе пакетов, включенных в группы Nz, определяется выражениемEZ=1 Ek=1 Em= 1 [(ah)z]k• Выражение Eg=i En=1 ng • wig определяет общее количество выполненных в группах Nz заданий, результаты которых включаются в комплекты. Количество заданий, которые включены в пакеты в группах Nz (z = 1, Z), но их результаты не используются при формировании комплектов, определено выражением EZ=1 EkE Em 1 [(ah)Z ]k — ^g=1 En=1 ng • wig. Оптимизация расписаний выполнения ПЗ, входящих в группы, в МС, осуществляется с использованием критерия, аналогичного полученному в [3]. Модель иерархической игры для оптимизации решений по составам ПЗ, групп ПЗ и расписаний выполнения ПЗ имеет вид:

• 1)    первый уровень:

ком где f1 = Eg=i ng;

• 2)    второй уровень:

Z kz mi              gком n где f = E E E [HZ]k - E E ng • Wig;

z =1 k =1 h =1            g =1 i =1

max fi([M, A], Ng), min f2([M,A], [{Nz|(z = О)},Q,Ng]),

• 3)    третий уровень [3]:

min f (N ^z , { [P ^z ,R ^z , { (T ^{0 l} ) ^z | (l = 1,L) } ])(при z =1,Z),              (3)

L          L np                            kz                     L np nj где fz = E[t01 ]z + EE W- №0-i,„j-i]z + E[tih]z• ph-1] + E E E М]z-l=2         l=1 j=2                           h=1                   l=2 j=1 q=2

k z

- [^[t ° q - 1 ^{] Z} + E ^[t lh ^] z • p hj ] ;

h =1

4) ограничение на длительность выполнения ПЗ в МС [3]:

при z = 1, Z.

(t n p n np ) z + ib (t L ) •     / S t z                             (4)

Решение по составам групп N ^z (z = 1, Z ), полученное на втором уровне, требуется проинтерпретировать с точки зрения формирования комплектов g -ых типов

(g = 1,gком). Для этого используются значения количества результатов выполнения заданий i-ых типов в пакетах, распределенных по группам Nz (z = 1, Z), обозначенные как az (i = 1,n), определяемые следующим образом: az = EZ=1 Em= 1 (ah)Z. Также при распределении результатов по комплектам используются: множества Kyком и Kyком′ типов комплектов и параметр stg– количество сформированных компонент в комплекте g-го типа. Перед реализацией алгоритма выполняется инициализация значений его входных параметров: Кком = Кком, ng = 0 (g = 1,дком), aZ = ^Z=1 ^m= 1 (ah)Z (i = 1,n). Входным данными является решение по составам групп NZ (z = 1, Z), а выходными - вектор Ng.

Алгоритм распределения результатов выполнения заданий в пакетах, включенных в группы N ^Z (z = 1,Z ), по комплектам g -х типов имеет следующий порядок шагов:

• 1.    Если К к ^ом = 0 , то извлечь идентификатор типа комплекта (в p -ой позиции в множестве К к ^ом ‘ ): g ‘ = min p { g p | g _p Е к ^ом ‘ } , К к ^ом ‘ = К к ^ом ' \{ g ’ } , положить st _g ‘ = 0. Если K к ^ом = 0 , то перейти на пункт 6.

• 2.    Если I 2 = 0 , то извлечь идентификатор типа результатов, распределяемых в комплект g’-го типа: i ‘ = min { i | i Е I Z } , I Z = I Z \{ i ’ } . Если I Z = 0 , то перейти на пункт 5.

• 3.    Если a Z ‘ >  w i/ _g ‘ , то st _g ‘ = st _g ‘ + 1. Если 1 2 = 0 , то перейти на пункт 2. Если I 2 > = 0 , то переход на пункт 4. Если a Z ’ <  w i ’ g ’ , то K к ^ом = К к ^ом \{ g ’ } . Переход на пункт 5.

• 4.    Модифицировать значение счетчика количества комплектов g’-го типа: n _g ‘ = n _g ‘ + 1. Если n _g ‘ = п ко^м , то K к ^ом = К к ^ом \{ g ' } . Модифицировать значения параметров a Z (i = 1,n) для n типов результатов: a Z = a Z — w ig ’ (i = 1,n). Положить I Z = I Z . Перейти на пункт 1.

• 5.    Положить I Z = I Z , перейти на пункт 1.

• 6.    Если К к ^ом = 0 , то K к ^ом ‘ = К к ^ом , I Z = I Z . Перейти на пункт 1. Если K к ^ом = 0 , то перейти на пункт 7.

• 7.    Останов алгоритма.

• 3.    Метод локальной оптимизации составов групп ПЗпри формировании КР

При реализации алгоритма определяются компоненты вектора N _g , а также значения a Z >  0 (i = 1, n), соответствующие количеству результатов каждого типа, не включенных в составы комплектов.

Решения по составам ПЗ формируются с использованием метода, рассмотренного в [1], расписания выполнения ПЗ в группах N ^Z (z = 1,Z) формируются с использованием метода, рассмотренного в [3]. Необходимо построение метода оптимизации составов групп ПЗ, выполняемых в течение интервалов t ^z , учитывающего условие формирования КР.

В [3] рассмотрен метод формирования начального решения по составам групп ПЗ, выполняемых в течение временных интервалов t ^Z (z = 1,Z). По причине введения условия формирования КР, получаемых при выполнении ПЗ в течение интервалов t ^z (z = 1, Z ), этот метод модифицирован для решения рассматриваемой задачи. Модификация предусматривает последовательное добавление в группы N ^Z (z = 1,Z ) по одному ПЗ каждого типа до тех пор, пока выполняется ограничение (4). Если ПЗ не могут быть размещены в группах N ^Z (z = 1, Z), то они размещаются в множестве Q.

Оптимизация составов групп ПЗ предполагает определение для каждого ПЗ i -го типа, включенного в группу N ^Z , значения отклонения количества заданий (a h ) _i ^Z (h = 1,m Z ) в нем от значения a Z , полученного после распределения результатов по комплектам ((a ^ ) Z >  a Z , a Z > 0). Среди всех ПЗ i-го типа в группе N ^Z выбирается пакет, отклонение количества (a h ) _i ^Z заданий в котором от значения a _i ^Z минимально. Для этого отклонения введено обозначение mh Z : mh Z = min 1 < _h < _m z ((a _h ) Z — a Z ) (((a h ) Z — a Z ) >  0, a Z > 0).

Для обоснования алгоритма оптимизации групп ПЗ выполнены следующие рассуждения:

– после распределения результатов выполнения заданий по КР получены значения n g (g = 1,д ком ) и значения a Z >  0 (i = 1, n);

– для каждого i-го типа заданий, пакеты которых включены в группу N ^z , реализуется проверка условия a Z > 0; в случае его выполнения в группе N ^Z выбирается h Z -ый ПЗ этого типа, для которого отклонение количества заданий в нем от значения a Z > 0 минимально (равно mh Z при ((a _h ) Z — a Z ) >  0 и a Z > 0));

– h _i ^z -ый ПЗ i -го типа исключается из группы N ^z , вместо него в нее добавляются пакеты разных типов, не включенные в группы N ^Z (z = 1, Z ) (из Q); среди добавляемых пакетов выбирается тот, включение которого в N ^z обеспечивает получение решения, характеризуемого уменьшением значения критерия / ₂ ( ^- ) в максимальной степени;

• – действия, связанные с исключением пакетов из группы N ^z и добавлением в нее пакетов из множества Q, повторяются для всех i-х типов заданий (при a^z > 0); для группы N ^z фиксируются параметры исключаемого и добавляемого в нее ПЗ, действия с которыми формируют решение, характеризуемое максимальным уменьшением критерия f ₂ ( - );

• - действия, связанные с исключением ПЗ i -х типов (при a Z > 0) и добавлением ПЗ из множества Q, повторяются для каждой группы N ^Z (z = 1,Z); среди решений по составам групп N ^Z (z = 1,Z) в качестве локально оптимального фиксируется решение, которое характеризуется уменьшением значения критерия / ₂ ( ^- ) в максимальной степени.

Для алгоритма оптимизации составов групп ПЗ в рассмотрение дополнительно введены обозначения: 1) i’ – рассматриваемый тип заданий; 2) z’ – идентификатор рассматриваемой группы ПЗ; 3) I ₁ ^q , I ₂ ^q – множества типов заданий, пакеты которых входят в множестве Q ; 4) N ₁ ^z _T ^′ – промежуточное решение по составу группы N ^{z ′} , формируемое путем исключения из нее h _i ^z ′^′ - го пакета i’-го типа, характеризуемого значением mh _i ^z ′^′ ; 5) N ₂ ^z _T ^′ – решение по составу группы N ^{z ′} , формируемое путем добавления в решение N ₁ ^z _T ^′ ПЗ различных типов из множества Q; 6) h i q – номер ПЗ i-го типа, который включен в состав множества Q; 7) H i q , H _i ^T q – множества номеров h i q пакетов i -х типов, которые включены в множество Q ; 8) ( V - f 2 ) ^Z (z = 1, Z) - значение левого дискретного градиента критерия f₂0, характеризующее лучшее решение по составу группы N ^Z ; 9) ( V ^- f ₂ ) g - значение левого дискретного градиента критерия f ₂ ( - ), характеризующее лучшее решение среди всех групп N ^Z (z = 1,Z ); 10) i ^Z , a ^Z ( z = 1 , Z ) - переменные для хранения типа заданий и количества заданий в пакете, исключение которого из группы N ^z позволяет получить решение, являющееся лучшим среди всех решений по ее составу; 11) i ^qz , a ^qz – переменные для хранения типа заданий и количества заданий в пакете, добавление которого в группу N ^z из множества Q позволяет получить лучшее решение; 12) i ^z _G , a ^z _G , i ^q _G , a ^q _G – переменные для хранения типов заданий и количества заданий в пакете, исключаемом из группы N ^z , и пакете, добавляемом в N ^z из Q, обмен которыми гарантирует лучшее решение среди всех решений по составам групп N ^Z (z = 1, Z); 13) p ^Z - флаг, единичное значение которого указывает на наличие в окрестности локально оптимального решения лучшего решения, 14) z1 – переменная, предназначенная для хранения номера группы N ^z , обмен ПЗ между которой и множеством Q гарантирует лучшее решение; 15) ε – точность.

Значение левого дискретного градиента ( V - f ₂ ) критерия ^(^определяется выражением ( V - f ₂ ) = (f ₂ ( ^ ,s + g ) — f ₂ ( ^ ,s)) < 0, где s - индекс шага алгоритма, на котором получено текущее локально оптимальное решение, (s+g) - индекс шага алгоритма, выполненного для поиска лучшего решения в окрестности. Значение правого дискретного градиента ( V ⁺ f ₂ ) определяется следующим образом: ( V ⁺ f ₂ ) = (.Ы^ ^s + ^{g) — f} 2 ( ' , ^s)) >  °-

В качестве входных данных для алгоритма оптимизации используется начальное решение по составам групп N ^z (z = 1,Z) и множества Q. Инициализация входных параметров алгоритма выполняется следующим образом: 1) I z = { i 1 ,i 2 , ..,ik_ } при i z = i, где i такой, что [i,m ^z , (A) ^z ] k G N ^z (k = 1, k z ); I z = I z ; 2) I q = { i 1 ,i 2 , ..,il q } при i q = i, где i такой, что [i,m q , (A) q ] _k G Q (k = 1, k q ); 3) для кортежей [i,m q , (A) q ] _k G Q (k = 1, k q ) задать значения элементов h i q множеств H i q : H i q = { 1, 2,.., m q } ; H iT = H i q ; 4) ( V - f ₂ ) ^z = 0 (z = 1,Z ); ( V ^- f ₂ ) G = 0; 5) задать значение s Последовательность шагов алгоритма оптимизации составов групп N ^z (z = 1, Z) следующая:

• 1.    Задать номер z’ группы N ^z : z = 1. Инициализировать N zT : N zT = N ^z .

• 2.    Если I z = 0 , то извлечь из I z тип задания i’: i ‘ = min { i | i G I q } ; I z = I z \{ i ‘ } . Положить p ^z = 0. Перейти на пункт 3. Если I z = 0 , то перейти на пункт 11.

• 4.    Сформировать промежуточное решение N ₁ ^z _T ^′ путем исключения h _i ^z ′^′ -го элемента (a _hz‘ ) ^z/ из вектора (A) ^z/ в кортеже [i^m z, (A) ^z/ ] G N zT :  (a h ) ^z/ = (a h +i ) z ‘ при h =

• 5.    Извлечь из множества I ₂ ^q элемент, соответствующий типу ПЗ в множестве Q : i q = min { i | i g Iq } , Iq = Iq \{ i q } .

• 6.    Извлечь из множества H _i ^T q идентификатор ПЗ, который добавляется в группу N ^z ' : h - q = min { h - q | h - q G H iT } , H iT = H iT \{ h - q } .

• 7.    Инициализировать N zT = N zT . Сформировать промежуточное решение N zT :

З.Для i’-го типа заданий в множестве Nz определить кортеж [i‘, mz , (A)z ]k такой, что [i‘, mz', (A)Z'']k G Nz‘. Если az > 0, то в векторе (A)z' кортежа [i^mz, (A)z']k G Nz' определить идентификатор h элемента (ah)z‘, для которого mhz = min1 0). Задать hz = h. Перейти на пункт 4. Если элементы (ah)z‘ вектора (A)Z' такие, что ((ah)z‘ — az) < 0, то перейти на пункт 2. Если az = 0, то перейти на пункт 2.

i′

′            ′                         ′                  ′                                          ′                                   ′                    ′             ′            ′                 ′ hv, my — 1; m-’ = m^ — 1; если m-’ = 0, то NiT = NT\{[i , m-’, (A)-']} , kz‘ = kz' — 1.

• -    если при i = i q выполняется [i,m z , (A) z ] _k G N T (k = 1, k _z ‘ ), то m z = m z + 1; ^(a m z' ^{) z} ' = ^(a h 'q ) q q ;

ii

• -    если не существует такого i , что при i = i ^q выполняется [ i, m _- ^z , ( A ) _- ^z ] _k G N ^z _T (k = 1,k z ‘ ), то присвоить i = i q ; m i ^z ' = 1; (a m z ‘ ) ^z = (a h ’ ) q q ; k z ‘ = k z ‘ + 1; k = k z ‘ ;

• 8.    Передать решение N ^z _T в алгоритм формирования расписаний выполнения ПЗ в МС (на третий уровень иерархии) [3]. Получить решение [P ^z , R^z, { (T ^{0 l} ) ^z | (l = 1,L) } ] * . Если для [P ^z ,R ^z , { (T ^{0 1} ) ^z | (l = 1,L) } ] * выполняется ограничение (4), то реализовать процедуру формирования КР выполнения ПЗ в группах N ^z (z = 1,Z ). Определить значение критерия f ₂ ( • ), значение левого ( V ^- f ₂ ) < 0 либо правого ( V ⁺ f ₂ ) >  0 дискретных градиентов. Если ( V ^- f ₂ ) >  ( V ^- f ₂ ) ^z , то перейти на пункт 9; если ( V f 2 ) < ( V f ₂ ) ^z , то сохранить значения параметров, характеризующих добавляемый в группу пакет: i ^qz = i q , a ^qz = (a h ’ ,_q ) q , ( V ^- f ₂ ) ^z ' = ( V ^- f ₂ ), p ^z ' = 1.

• 9.    Если H iT = 0 , то перейти на пункт 6. Если H iT = 0 , то проверить условие I q = 0 . Если I q = 0 , то перейти на пункт 10. Если I q = 0 , то перейти на пункт 5.

• 10.    Если p z = 0, то сохранить значения параметров исключаемого из группы N ^Z пакета: i ^Z = i ' ; a z = (a z^ ‘ ) Z ‘ . Если I Z = 0 , то I q = I l , для всех i q E I l положить i^′

• 11.    Выполнить сравнение значения ( V - f ₂ ) ^Z для группы N ^Z и значения ( V - f ₂ ) g . Если ( V - f ₂ ) ^Z < ( V - f ₂ ) G , то сохранить значения параметров исключаемого из N ^Z пакета и добавляемого в нее пакета: i G = i ^z , a G = a ^Z , i G = i ^qz , a G = a ^qz , z1=z’. Модифицировать номер z’ группы ПЗ: z’=z+1. Если z ' <  Z , то положить ( V - f ₂ ) ^Z = 0. Перейти на пункт 2. Если z >  Z , то перейти на пункт 12. Если ( V - f ₂ ) ^z >  ( V - f ₂ ) g , то ( V - f ₂ ) ^z = 0, модифицировать номер z’ группы ПЗ: z’=z+1. Если z ' <  Z , перейти на пункт 2. Если z ^′ > Z, то перейти на пункт 12.

• 12.    Если | ( V - f ₂ ) G | < е, то перейти на пункт 13 (где | • | - модуль ( V ^- f ₂ )). Если l (V-f 2 ) g | >  е, то сформировать новые составы: множества N ^Z (где z=z1 ) кортежей вида [i,m Z , (A) Z ] E N ^z , множества Q кортежей вида [i,m q , (A) q ] _k E Q (сформировать локально оптимальное решение по составам групп ПЗ (состав группы N ^z , для которой z=z1 )):

• -    для i = i G определить кортеж [i,m Z , (A) Z ] E N ^z ; в векторе (A) Z определить индекс h’ элемента, для которого (a h ‘ ) Z = a G ; исключить h’-ый элемент из вектора (A) Z : (a h ) Z = (a h +1 ) Z при h = h',m Z — 1; m Z = m Z — 1; если m Z = 0, то N ^Z = N ^Z \{ [i,m^z, (<] } ; k Z = k Z — 1; I Z = I Z l{ i G } .

• -    если при i = i G выполняется [i,m q , (A) q ] _k E Q, то m q = m q + 1; (a m q ) q = a G ;

• -    если не существует такого i, что при i = i G выполняется [i,m q , (A) q ] k E Q ^{( k} = ^1,k q ), ^то i = i G ; m q = 1; ⁽a m q G = ^a G ; k q = k q + 1; k = k q ; ^Q = ^Q u^{{ [i},m q , (A) q ^] k ^} ; I q = Aq и { i G } ;

• -    если при i = i G выполняется [i,m ^z , (A) ^z ] _k E N ^Z , то m ^z = m ^z + 1; (a m z ) ^z = a G ;

• -    если не существует такого i, что при i = i G выполняется [i,m Z , (A) Z ] k E N ^Z , то присвоить i = i G ; m Z = 1; (a m z ) Z = a G ; k Z = k Z + 1; k = k Z ; N ^Z = N ^Z U { [i,m Z , (A) Z ] k } ; I Z = I Z и { i G } ;

• -    для i = i G определить кортеж [i,m q , (A) q ] E Q; в векторе (A) q определить индекс h’ элемента, для которого (a h ‘ ) q = a G ; исключить h’ -ый элемент из вектора (A) q : ⁽a h ^{) q} = ⁽a h +1 ^{) q} при ^h = ^h'^,m q ^— 1; ^m q = ^m q ^— 1;^{если m} q = ⁰, ^{то Q} = ^Q \^{{ [i},m q , ⁽A^{) q ] }} ; k q = k q — 1; I q = I q |{ i G }.                                   ____

• -    для каждого k -го кортежа [i,m q , (A) q ] k E Q (k = 1, k _q ) задать значения элементов h i q множеств H i q и H iT :H i q = { 1, 2, ..,m q } , H iT = H i q . Выполнить инициализацию I 2 > = I Z ; I q = I q . Задать значения ( V ^- f ₂ ) ^Z = 0 (z = 1,Z); ( V ^- f ₂ ) G = 0. Перейти на пункт 1.

• 13. Останов алгоритма.

• 4. Исследование метода комплексного планированиявыполнения ПЗ в МС при ограничении и формировании КР

m i              ^iq

N T = N T U{ [i,m z - , (A) z ' ] k } .

H iT = H i q , p z = 0, перейти на пункт 2. Если I Z = 0 , то перейти на пункт 11. Если p z = 0 и I Z = 0 , то положить I q = I^ , для всех i ^q E I 1 q положить H iT = H i q , перейти на пункт 2. Если p ^z = 0 и I ₂ ^z = 0 , то перейти на пункт 11.

Рассмотренный алгоритм формирует локально оптимальное решение по составам групп (решение [ { N ^Z | (z = 1,Z) } ,Q,N g ] * ), которое соответствует решению [M,A] по составам ПЗ.

Целью исследования метода комплексного планирования выполнения ПЗ в МС при введенных условиях является определение степени увеличения количества формируемых комплектов при использовании метода оптимизации решений по составам групп в сравнении с фиксированными группами ПЗ. Результатом являются зависимости отношения f _эмосгn = (f M ^ocrn — ^ ф ^икс )/^ ф ^икс от входных параметров задачи (f _эмосгn – степень увеличения количества комплектов при оптимизации составов групп ПЗ по сравнению с фиксированными группами ПЗ, f ^фикс - значение критерия f ₁ ( • )для решений, не предусматривающих оптимизацию групп (фиксированных групп), f ₁ ^мосгп – значение критерия f ₁ ( • )при условии, что составы групп оптимизируются рассмотренным методом). Исследования эффективности планирования проводились для параметров задачи: max(t li )/ min(t li ) - отношение максимальной и минимальной длительностей выполнения заданий на l-ых приборах МС; max(t l j )/min(t l k ) - отношение максимальной и минимальной длительностей переналадок приборов; max(w ig )/ min(w ig ‘ ) – отношение максимального и минимального количества результатов i-х типов в комплектах. Значения max(t ij )/min(t l _k ) задавались равными 1, 2, 4, 8; max(t i )/min(t i ) -равными 1, 2, 4; max(w ig )/min(w _ig ‘ ) - равными 1, 2, 4. Значения параметра п ком заданы равными 4 и 8, д ^ком = 4. При п ком = 4 длительности интервалов времени t z (z = 1, 3) задавались равными 100, при п ком = 8 длительности интервалов t z (z = 1, 3) – равными 200. Улучшение решений с использованием метода оптимизации групп ПЗ сравнивается с применением генетических алгоритмов (ГА) ([19]). Зависимости значений f _эмосгn от параметров задачи (n=5, L=5, t z = 100 при п ком =4, t z = 200 при п ком = 8, Z=3 ) в сравнении с ГА представлены на рис. (МО СГП - метод оптимизации составов групп пакетов).

(а) п ком =4, t z = 100, Z = 3, max( w _ig ) / min( w _ig ‘ ) = 1

(b) п ком =4, t z = 100, Z = 3, max( w _ig ) / min ( w ig ’ ) = 2

(c) п к ^ом = 8, t z = 200, Z = 3, max( w _ig ) / min( w _ig ‘ ) = 1

(d) п ком = 8, t z = 200, Z = 3, max( w _ig ) / min ( w ig ’ ) = 2

Увеличение количества комплектов при оптимизации составов групп ПЗ

Конечность алгоритмов обеспечивается конечностью множества решений по со- ставам пакетов заданий каждого i-го типа [2] (максимально возможное количество n2i

пакетов каждого i-го типа определяется как где ni - количество заданий i-го

типа (i = 1,n) , [-J - операции округления в меньшую сторону). Вычислительная сложность алгоритма оптимизации составов групп - O(n • ni • Z).

Анализ результатов исследований комплексного планирования выполнения ПЗ в МС при условии формирования КР и ограничениях на интервалы времени ее функционирования, показал, что в среднем эффективность планирования составляет 60% (т.е. на 60% увеличивается количество формируемых комплектов по сравнению с фиксированными группами ПЗ).

Заключение

Рассматриваемый в работе подход предполагает комплексную оптимизацию решений по составам ПЗ, составам групп ПЗ и расписаниям выполнения ПЗ из групп в МС с применением теории иерархических игр. Это позволяет выполнить решение большого количества задач теории расписаний, получение результатов в которых существующими способами является затруднительным. Использование иерархического подхода и методов локальной оптимизации решений на каждом из уровней иерархии системы позволяет формировать решения задач без ограничений на их размерность, без введения дополнительных упрощений. Разработан метод построения начальных решений по составам групп ПЗ, метод распределения результатов выполнения пакетов из групп по комплектам, а также метод локальной оптимизации решений по составам групп ПЗ. Рассмотренный метод локальной оптимизации решений по составам групп ПЗ обеспечивает повышение эффективности планирования выполнения заданий в МС (увеличение количества сформированных комплектов по сравнению с фиксированными составам групп ПЗ составляет в среднем 60%). В развитии работ [1–3] получены: новая модель иерархической игры, новый метод формирования начальных решений по составам групп ПЗ, новый метод оптимизации составов групп ПЗ, учитывающий формирование КР, новый метод распределения результатов выполнения заданий, входящих в пакеты, включенные в группы, по комплектам. Использование рассмотренного подхода обеспечивает улучшение решений по планированию выполнения ПЗ при ограничении на длительности интервалов времени функционирования МС и формировании КР.