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

Анализ условия равновесия по Нэшу [3] позволяет сделать вывод: если при переходе от одного состава групп партий двумя игроками к другому составу этих групп для этих же игроков значения критериев этих игроков улучшаются, то равновесие не достигнуто и полученные решения могут рассматриваться как промежуточные при переходе к эффективным решениям, обеспечивающим ситуацию равновесия. Реализуемый метод выполняет формирование на промежуточном шаге алгоритма составов групп партий, которые обеспечивают одновременное улучшение значений критериев игроков (на некотором промежуточном шаге улучшение значений критериев двух игроков).

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

Рисунок 2 – Заданный вид последовательностей обработки партий в группе для идентификации позиции удаляемой партии (текущее решение по составу группы партий )

Анализ видов последовательностей (Рисунок 2) позволил определить причины неэффективного использования временного ресурса приборов системы при обработке партий:

1) несогласованность длительностей обработки требований партии в j-ой позиции в последовательностях (на различных l-ых приборах), которая обуславливает простои приборов в ожидании готовности к обработке требований этой партии; в частности, несогласованность длительностей обработки требований r-го типа (партия в позиции j=2 в последовательностях ) обуславливает простой второго и третьего (l=2,3) приборов в ходе обработки этой партии; в то же время простои приборов в ожидании готовности к обработке требований партии (в j-ой позиции в ) являются причиной «сдвига» последовательности партий в конец интервала , что обуславливает неэффективное использование оборудования системы на стадии освобождения конвейера (на заключительной стадии обработки партий группы ); тогда исключение из группы партии, находящейся в соответствующей j-ой позиции в , и замена её партией требований другого типа позволяет уменьшить несогласованность в длительностях обработки требований этого типа на различных приборах и уменьшить время простоя приборов при обработке партий группы;

2) длительная переналадка приборов системы на обработку требований (для партии, расположенной в j-ой позиции в ) обуславливает простои приборов в ожидании начала обработки партии (неэффективное использование приборов системы на стадии обработки партий из группы ), является причиной «сдвига» последовательности партий в конец интервала , при этом несогласованность моментов времени окончания переналадки l-го прибора на обработку партии i-го типа (в j-ой позиции) и окончания обработки первого требования этой же партии на (l-1)-ом приборе (при незначительной длительности интервала переналадки) обуславливает простой l-го прибора в ожидании начала обработки партии (на Рисунке 2– это интервалы простоя второго и третьего приборов после окончания его переналадки на обработку партии требований r-го типа, а также простой 3-го прибора после окончания переналадки на обработку требований k-го типа); наличие интервала ожидания прибором начала обработки партии вместе с соответствующим интервалом переналадки обуславливает неэффективное использование приборов системы (суммарный интервал простоя прибора перед началом обработки партии, который обуславливает «сдвиг» партий в конец интервала );

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

Определение значений интервалов времени, характеризующих общую неэффективность использования оборудования при обработке партий, реализуется при зафиксированном (в соответствии с ) порядке партий. Поэтому идентифицируется (для исключения из группы ) не партия требований i-го типа, а партия требований, занимающая j-ю позицию в последовательностях . Для идентификации партии, исключаемой из и занимающей j-ю позицию в , необходимо определять суммарное время (общий интервал времени) неэффективного использования всех приборов системы при обработке этой партии, а не интервал времени простоя отдельного прибора при ее обработке

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

. (6)

В этот интервал входят: время переналадки прибора на обработку требований партии в -ой позиции в , возможное время простоя l-го прибора в ожидании начала обработки этой партии. Так как -я позиция рассматриваемой партии является неизменной во всех последовательностях , тогда выражение (6) может быть использовано для расчёта интервалов времени простоя каждого l-го прибора в ожидании начала обработки этой партии. Тогда суммарное время простоя приборов системы в ожидании обработки партии, занимающей -ю позицию в последовательностях , будет вычислено в соответствии с выражением вида:

при . (7)

Обозначим номер позиции партии в (индекс партии), исключаемой из группы партий , через . Тогда индекс партии требований, исключаемой из группы партий , соответствует номеру позиции этой партии в , для которого выполняется условие:

, где . (8)

Время простоя l-го прибора в в ожидании начала обработки первого требования первой партии в в определяется значением . В данный интервал входят: интервал времени первоначальной наладки приборов rна выполнение операций с первой партией в , интервал возможного простоя приборов после наладки в ожидании начала обработки. Суммарное время простоя всех L приборов в ожидании начала обработки первой партии в вычисляется в соответствии с выражением вида: . На основе введённого выражения вида и выражения (8) индекс (соответствующий исключаемой из партии) – это номер её j-й позиции в (при ), который определяется с использованием следующих выражений:

(9)

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

Время простоя отдельного ( -го) прибора в ходе обработки партии, занимающей j-ю позицию в последовательности (простой прибора в ожидании готовности к обработке требований, входящих в эту партию), определяется с использованием выражения вида:

,

где r_j – число требований в этой партии. Введём в рассмотрение параметр , значение которого соответствует суммарному простою приборов системы в ожидании готовности требований к обработке в партии, занимающей j-ю позицию в последовательностях (всех L приборов при обработке одной партии группы ). Значение , для каждой j-й партии в (j– номер позиции партии в ) определяется выражением вида:

.

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

, при . (10)

Таким образом, выражения (9) и (10) позволяют идентифицировать в группе партии, которые могут быть из неё удалены (для замены партиями из других групп) для обеспечения более эффективного использования временного ресурса оборудования ( и -ая партии в (элементы ( ) и ( )матриц (P) и (R) для соответствующих i-ых типов требований)). Для формирования метода построения эффективного состава групп партий в рассмотрение введены следующие обозначения: 1) – индекс текущей группы партий, состав которой оптимизируется; 2) – индекс рассматриваемой группы партий , в результате обмена партиями с которой состав группы может быть улучшен; 3) – вектор идентификаторов типов требований, партии которых размещены в группе ; – вектор идентификаторов типов требований, партии которых размещены в группе ; 4) – индекс партии (номер позиции партии в расписания ), вызывающей максимальный простой оборудования при её обработке в соответствии с условиями (9) и (10) ( ); 5) – номер партии (номер позиции партии в расписания ), вызывающей максимальный простой оборудования при её обработке в соответствии с условиями (9), (10) ( ); 6) – решения, сформированные на основе состава группы партий (решения) путём извлечения из неё поочерёдно партий с индексами (с номерами их позиций в ) и добавления в группу партий с номерами (с номерами их позиций в расписания ), извлекаемых из группы ; 7) – решения, сформированные на основе решения , путём извлечения из него партий с номерами их позиций в расписания и добавления в него партий, извлекаемых из группы партий (с номерами их позиций в последовательностях расписания ); 8) , – левые дискретные градиенты целевых функций и соответственно, которые могут быть получены при переходе от исходных решений и к решениям и соответственно ; 9) , – правые дискретные градиенты целевых функций и , которые могут быть получены при переходе от исходных решений и к решениям и соответственно ; 10) P – множество номеров вариантов решений и , формирование которых позволило получить отрицательные значения левых дискретных градиентов и целевых функций и ; 11) G1 – «глобальное» отрицательное значение левого дискретного градиента функции , которое характеризует наилучший (наиболее эффективный) вариант решения в первой части алгоритма оптимизации (обмен партиями между группами и ); 12) l1 – сохранённое значение номера группы , обмен партиями с которой (для группы ) обеспечивает «глобальное» отрицательное значение градиента функции , соответствующее G1; 13) G2 – «глобальное» отрицательное значение левого дискретного градиента функции , получаемое во второй части алгоритма в результате обмена партиями требований между множеством Q и группой партий ; 14) – номера типов требований, партии которых занимают соответствующие -ые позиции в последовательностях расписания , соответствующего группе партий (индексы элементов вектора типов требований в партиях в группе ); 15) – типы требований, определяемые по соответствующим номерам типов с использованием вектора , партии которых занимают -ые позиции в расписания ; 16) – номера (индексы) типов требований в векторе , партии которых занимают -ые позиции в расписания , соответствующего группе партий ; 17) – типы требований, определяемые в соответствии с их номерами (индексами) в векторе ; 18) – количество требований в партиях, которые занимают -е позиции в расписания для группы ; 19) – количество требований в партиях, которые занимают -е позиции в расписания для группы ; 20) – количество наборов вида в промежуточных решениях ; 21) – количество наборов вида в промежуточных решениях ; 22) – значения критерия , вычисляемые для промежуточных решений ; 23) – значения критерия , вычисляемые для промежуточных решений ; 24) – промежуточное локально эффективное решение, полученное на текущем шаге алгоритма, по составу группы партий ; 25) – промежуточное локально эффективное решение, полученное на текущем шаге алгоритма, по составу группы партий ; 26) , – типы требований, партиями которых выполняется обмен между группами и для получения решений и ; 27) , – количество требований в партиях, которыми выполняется обмен между группами и для получения решений и ; 28) – тип требований, партия которых удаляется из группы партий , – количество требований -го типа в партии, удаляемой из группы , – тип требований, партия которых добавляется в группу партий , – количестве требований –го типа , партия которых добавляется в группу (при этом гарантируется переход к локально эффективному решению ) . Для реализации алгоритма метода формирования эффективного состава групп партий выполнена инициализация используемых в алгоритме параметров значениями: G1=0; G2=0, множества . Последовательность шагов алгоритма метода оптимизации состава групп партий имеет следующий вид: