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

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

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

-

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

- при ;

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

- если , то ;

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

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

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

51) сформированное промежуточное решение передается на третий уровень системы для формирования расписания ;

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

53) на основе решения , полученного на третьем уровне системы, на втором уровне выполняется вычисление значения критерия ;

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

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

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

55) если для решения выполняется условие (решение является более эффективным, чем исходное решение ), тогда индекс решения p=1 добавляется в множество P номеров решений, эффективность которых анализируется (градиент целевой функции сравнивается с глобальным значением градиента G2, рассматриваемом на втором этапе (на второй стадии) алгоритма; если для решения выполняется , то решение в дальнейшем не рассматривается;

56) сравнение типов требований и в партиях, которыми будет выполняться обмен между и множеством Q, сравнение количества требований в этих партиях: если при выполняется условие , то обмен партиями между и множеством Q не осуществляется, реализуется переход к шагу 62;

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

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

-

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

- , при ;

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

- если , то ;

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

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

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

58) полученное промежуточное решение передается на третий уровень иерархии системы для формирования расписания ; выполняется анализ построенного решения для группы партий , если длительность реализации расписания не удовлетворяет ограничению (19), реализуется переход к шагу 62;

59) для решения выполняется вычисление значения критерия (исполь-зуется решение с третьего уровня иерархии в виде матриц и при );

60) вычисление значений левого (правого ) дискретных градиентов целевой функции (для решения ) по формулам:

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

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

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

62) если , то переход к шагу 66;

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

64) для локально эффективного решения выполняется сравнение градиента с «глобальным» значением G2, если , то локально эффективное решение является более оптимальным, чем исходное (оптимизируемое) решение , тогда ; ; ; ; ;

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

66) модификация номера рассматриваемой партии в множестве Q (партии требований i-го типа в соответствующем элементе ): h=h+1; ; если , то переход к шагу 48;

67) если (для соответствующего k-го элемента множества Q), то модификация номера k набора параметров вида в множестве Q: k=k+1; ; если , то переход к шагу 46;

68) если , то получено локально оптимальное промежуточное решение , которое является результатом обмена партиями требований типов и в количестве и элементов между группой партий и множеством Q партий, не размещённых ни в одной из групп ;

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

70) сравнение вариантов локально эффективных решений , полученных на основе решения путём обмена партиями требований между: а) группой и группой партий (номер которой сохранён в параметре l1 (l1=z)); б) группой и множеством Q партий, которые не были размещены ни в одной из групп ; выбор эффективного варианта решения (глобально эффективного решения на текущем шаге алгоритма) выполняется следующим образом: а) если при и выполняется условие , то переход к шагу 71; б) если при , выполняется условие , то новое решение формируется следующим образом:

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

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

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

-

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

- при ;

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

- если , то ;

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

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