ПРИБЛИЖЕННЫЙ МЕТОД ПОСТРОЕНИЯ КОМПЛЕКСНЫХ РАСПИСАНИЙ ГРУППОВОЙ ОБРАБОТКИ ПАРТИЙ ПРИ НАЛИЧИИ ОШРАНИЧЕНИЙ 3 страница

25) так как решение является локально эффективным по количеству и составу партий для требований -го типа (ему соответствует значение ) и оно построено на основе текущего «глобального» эффективного решения , сформированного ранее, то переход от глобально эффективного решения (с значением критерия ) к решению возможен при обеспечении улучшения значения критерия ( ), в случае выполнения условия реализуется присваивание вида: (т.е. полученное локально эффективное решение по количеству и составу партий требований -го типа фиксируется как глобально эффективное); при этом ;

26) если является истинным условие Ø, то выполняется переход к формированию количества и состава партий требований другого типа; изменение идентификатора -го типа требований, состав партий для которого будет формироваться, выполняется следующим образом: , тогда (начальное значение для данного типа требований задано равным 2 ( =2));

27) полученное глобально эффективное решение рассматривается как оптимизируемое для требований типа , выполняется присвоение , реализуется переход к шагу 5;

28) в случае выполнения условия полученное решение является эффективным по количеству и составу партий требований соответствующих типов (n типов).

Пример реализации градиентного алгоритма метода определения эффективных количества и составов партий представлен на Рисунке 1 (для случая ). При переход от состава партий к составу партий невозможен, т.к. элемент и процесс изменения состава партий для должен быть завершен, для переход от состава партий (6,4,2) к составу партий (5,5,2) не обеспечивает , изменяется состав партии, номер которой h’=3, увеличение числа требований в партии с h’=3 обеспечивает условие до тех пор, пока не выполнится условие прекращения формирования состава партий при ( ), тогда выполняется поиск эффективного состава партий при изменении (увеличении) . Понятно, что эффективные решения внутри каждой группы сравниваются со значением , в результате выбирается такое количество и состав партий требований типа i, которые гарантируют глобальный min .

Рисунок 1 – Пример реализации градиентного алгоритма метода определения эффективного количества и состава партий

Для формирования решений по составу групп партий на втором уровне иерархии к введенным обозначениям решений на этом уровне (множество наборов вида: ), введено обозначение множества Q – множества партий, не размещенных ни в одной из групп , заданное в виде: (в Q определяются: количество партий требований i-го типа, вектор состава этих партий (размер вектора )). Обобщенное решение, формируемое на втором уровне иерархии системы на s-ом шаге алгоритма определения состава групп партий, имеет вид: (где ) и , где – количество наборов заданного вида в множестве Q. Реализация метода построения эффективных составов групп партий на втором уровне системы предполагает выполнение двух стадий: 1) формирование начального решения (начального состава групп партий); 2) переход к приближенному эффективному решению (формирование эффективных составов групп партий). Формирование начального решения (начальных составов групп партий) предполагает распределение партий, полученных в решении [(M),(A)] с первого уровня системы, по множествам наборов параметров вида и множеству Q с учетом ограничений на время обработки партий в группах. Формирование алгоритма построения начального решения (начального состава групп партий, который должен быть оптимизирован) предваряется введением в рассмотрение следующих обозначений: 1) – номер типа требований, партия которых размещается в рассматриваемой группе (номер элемента в векторе (M), номер строки в матрице (A)); 2) – i-ый элемент вектора (M), соответствующий количеству партий требований i-го типа, размещаемых в группах ( ) и в множестве Q; 3) – количество партий требований типа, размещенных в группах и в множестве Q; 4) z – индекс текущей рассматриваемой (формируемой) группы партий; 5) h – номер партии требований i-го типа, размещаемой в группе , число требований в которой соответствует значению элемента матрицы (А). Начальная инициализация исходных данных для реализации алгоритма формирования начального состава групп партий выполнена следующим образом: 1) (т.е. формирование групп выполняется, начиная с требований (i=1)-го типа); 2) ( ), т.е. первоначально множества совокупностей параметров вида не содержат ни одного элемента; 3) инициализация значением 0 ( ); 4) начальная инициализация множеств вида ( ) и множества в виде: ; (инициализация значением предполагает, что наборы вида будут добавляться в состав соответствующих множеств). Для формирования алгоритма определения начального состава групп партий в рассмотрение также введены множества: – множество номеров (идентификаторов) групп партий, в которых партии могут быть размещены (первоначально ); – текущее (изменяемое) множество номеров групп партий, с которым оперирует алгоритм. Алгоритм формирования начального состава групп партий содержит следующие шаги:

1) определение состава множества номеров групп партий, в которых на данной итерации алгоритма будут размещаться партии: ;

2) определение номера текущей рассматриваемой группы партий , в которой будут размещаться партии требований -го типа: , (номер заполняемой группы партий удаляется из множества );

3) инициализация параметра (число размещенных в группах и в множестве Q партий требований -го типа) значением 0 ( );

4) задание номера h текущей рассматриваемой партии требований -го типа, добавляемой в группу партий равным 1 ( , т. е. рассматривается первая партия из , добавляемая в группу партий ).

5) для -го типа требований и группы выполняется формирование набора параметров , сформированный набор параметров включается в состав группы партий : ; ; ; ;

6) определение значений параметров в наборе (для -го типа требований): ;

7) сформированная группа партий (множество наборов ) передается на третий уровень системы для формирования эффективного расписаний обработки партий , ей соответствующего;

8) проверка для расписания выполнения ограничения на длительность его реализации вида (4); если данное ограничение выполняется, то , ;

9) проверка для сформированного состава группы партий (в которую добавлена рассматриваемая партия с количеством требований в ней равным ) выполнения условия вида:

, (5)

где – количество типов требований, партии которых размещены в группе ;

10) если ограничение на длительность реализации расписания вида (4) выполнено, условие вида (5) не выполняется, то при переход к шагу 6, при переход к шаг 23;

11) если условие, введенное выражением (5), выполнено, то (т.е. партии в группе в последующем размещены быть не могут);

12) если условия вида (5) и ограничение (4) выполняются то:

- при и – определение номера следующей рассматриваемой группы партий на основе выражения вида: , , переход в шагу 5;

- если , то переход к шагу 23;

13) если для расписания , соответствующего группе партий , ограничение вида (4) на время его реализации не выполняется, то ; (рассматриваемая партия требований -го типа с количеством элементов в ней исключается из группы , так как она не может быть в ней размещена);

14) если получено в результате , то , (из группы исключается набор , рассматриваемые партии требований -го типа в группу партий не включены);

15) если , то выполняется определение номера формируемой группы партий следующим образом: , ; переход к шагу 5.

16) если , то рассматриваемая партия требований (количество требований ) ни в одной из групп ( ) размещена быть не может, тогда выполняется проверка условия для соответствующего -го типа требований;

17) при выполнении условия для соответствующего -го типа требований (набор параметров вида сформирован на предыдущих шагах алгоритма, параметры проинициализированы соответствующими значениями), то выполняется модификация значений этих параметров следующим образом: , ;

18) если , то формируется набор параметров вида , который включается в множество Q: ; ; выполняется инициализация значений параметров, входящих в набор: , ;

19) модификация значений параметров h и : , ;

20) определения значения номера формируемой партии требований -го типа следующим образом: , ;

21) если , то при выполнении условия для рассматриваемого -го типа требований вида (где z – номер текущей группы , определенный на шаге 19, в которой размещается партия) реализуется переход к шагу 6;

22) если и для рассматриваемого -го типа требований выполняется (набор параметров требуемого вида не включен в состав группы на предыдущих шагах алгоритма), то реализуется переход к шагу 5;

23) при выполняется переход к размещению партий требований другого типа: изменение номера типа требований если , то выполняется определение номера z группы партий, в которой может быть размещена первая партия требований этого типа (соответствующий элемент матрицы (А) с верхнего уровня), следующим образом: , , ; переход к шагу 3;

24) при получен начальный состав групп партий, который должен быть оптимизирован.

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