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

- если при и ), то ; ; ; ; ; ;

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

е) для элементов вектора элемента реализуется преобразование значений в соответствии с выражением вида:

-

- индекс , где h такой, что ;

- при ;

- ; если , то сформировано промежуточное решение , в которое будет добавлена партия требований -го типа из группы ;

- если , то ;

ж) добавление в решение партии требований -го типа в количестве элементов:

- если при , ), то , ;

- если при , ), то ; ; ; ; ; ;

з) полученные решения и рассматриваются как текущие оптимизируемые; инициализация «глобальных» значений и левого дискретного градиента целевой функции значением 0 ( и ); ; переход к шагу 1;

71) формируется новое эффективное решение путем обмена партиями требований - и -ых типов между группой партий (исходное решение) и множеством Q партий, не размещённых ни в одной из групп , в соответствии с указанными ниже действиями:

а) выполняется инициализация промежуточного решения : ;

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

б) для элементов вектора набора параметров выполняется преобразование значений в соответствии с выражениями вида:

-

- индекс , где h такой, что ;

- при ;

- ; если , то сформировано промежуточное решение , в которое будет добавлена партия требований из множества Q;

- если , то ;

в) добавление в промежуточное решение партии требований -го типа в количестве элементов из множества Q:

- если при , ), то ; ;

- если при , ), то ; ; ; ; ; ;

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

д) для элементов вектора набора параметров выполняется преобразование значений в соответствии с выражениями вида:

-

- индекс , где h такой, что ;

- при ;

- ; если , то сформировано промежуточное решение , в которое будет добавлена партия требований из группы ;

- если , то ;

е) добавление в промежуточное решение партии требований -го типа в количестве элементов из группы :

- если при , ), то ; ;

- если при , ), то ; ; ; ; ; ;

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

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

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

Формирование расписания обработки партий каждой группы ( ) предполагает определение эффективного порядка обработки партий этой группы на третьем уровне системы (т.е. последовательностей обработки партий группы ). Так как порядок партий в последовательностях одинаков, количество типов требований в множестве N ограничено, тогда является ограниченным и число возможных решений. Шаги алгоритма метода формирования расписания обработки партий отдельной группы предполагают [4]: 1) размещение рассматриваемой партии требований в последовательностях путем добавления ее (партии) в конец каждой последовательности; 2) изменением положения партии в на одну позицию ближе к началу последовательностей в случае, если гарантируется выполнение условия (где – левый дискретный градиент целевой функции , соответствующий некоторому расписанию для группы партий ). На третьем уровне системы для формирования порядка обработки партий группы использован метод окрестности, связанный с поиском некоторого более эффективного решения в окрестностях текущего. Для формирования метода определения порядка обработки партий в рассмотрение введены дополнительные обозначения: – количество партий требований, размещенных в последовательностях на предыдущих s шагах реализации алгоритма, – номер типа требований, соответствующий некоторому -ому типу требований, партия которых размещается в последовательностях (для группы партий сформирован вектор типов требований, партии которых принадлежат группе , тогда – это номер элемента в векторе , который соответствует -ому типу требований в рассматриваемой партии, количество элементов в векторе равно ), v – индекс текущего рассматриваемого столбца матриц , (на s-ом шаге алгоритма). Вычисление метрики окрестности исходного решения выполняется в соответствии с введенным в рассмотрение выражением вида: , где – количество типов требований в партиях в группе партий ( , – количество партий требований разных типов, добавленных до s-го (и включая его) шага алгоритма в последовательности расписания , соответствующего группе партий , g– номер промежуточного решения по построению расписания для группы . Вид расписания – матрицы порядка обработки партий , количества требований в партиях в соответствующих позициях в – (дополнительно формируются матрицы и ). Исходное оптимизируемое решение формируется путём добавления партии требований -го типа в количестве в конец последовательностей . Решение ,сформированное на основе исходного решения , находится в его окрестности , характеризуемой метрикой . Метрика определяет число элементов в матрице (число позиций в последовательности), в которых изменены значения по отношения к исходному решению. Формирование решения предполагает изменение положения рассматриваемой партии в последовательностях относительно положения этой партии в , соответствующего решению . Решение по составу группы партий , поступающее на третий уровень системы планирования, для которого формируется расписание , имеет вид . Начальная инициализация параметров перед началом реализации алгоритма предполагает задание значения индекса k набора вида равным 1 ( ), значения индекса столбца матриц и , в котором задаются значения , , соответствующие добавляемой в последовательности партии, равным 1 ( =1, – значение индекса столбца соответствующих матриц, с которым оперирует алгоритм на s–ом шаге алгоритма). Размер формируемых матриц и равен , где – количество типов требований в размещаемых в последовательностях партиях (равен количеству наборов вида в множестве таких наборов (группе партий), – количество партий, которые должны быть размещены в последовательностях , значение определяется следующим образом: , где – параметр в соответствующем -ом наборе вида в множестве (группе партий). Алгоритм определения эффективного порядка обработки партий группы (формирования расписания обработки партий) на третьем уровне системы планирования содержит следующие шаги:

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

2) добавляемая в последовательности партия требований i-го типа в количестве элементов ( ) размещается в конце последовательностей ; для этого в -ой строке столбца матриц , задаются значения, соответствующие этой партии (элементы и инициализируются значениями 1 и ); действия с матрицами , ( , на s–ом шаге алгоритма), связанные с инициализацией элементов -ых столбцов их -ых строк , выполняется следующим образом: , , при k≠i’, ; , , при k≠i’, ;