Содержание к диссертации
Введение
ГЛАВА 1. Задачи распределения ресурсов в иерархических системах (планирование и оперативное управление) 17
1.1. Место задач распределения ресурсов в классе задач математического программирования 17
1.2. Математический аппарат, используемый при формализации процессов распределения ресурсов в иерархических системах 18
1.2.1. Методы решения задач совместности системы линейных неравенств 18
1.2.2. Методы решения задач квадратичного программирования 21
1.2.3. Методы решения задач календарного планирования и оперативного управления 31
ГЛАВА 2. Общая математическая модель многокритериального распределения ресурсов и постановки оптимизационных задач 51
2.1. Иерархия рассматриваемых задач 51
2.2. Содержательное описание проблемы распределения ресурсов при планировании и оперативном управлении производственными системами 52
2.2.1. Задача ситуационного анализа, планирования и оперативного управления процессом изготовления интегральных схем с микронными и субмикронными проектными нормами 52
2.2.2. Задача распределения производительности купола по газовым скважинам 56
2.2.3. Задача планирования и оперативного управления процессом изготовления изделий машиностроения 58
2.3. Общее описание проблемы распределения ресурсов при планировании и оперативном управлении производственными системами 60
2.3.1. Задача предварительного планирования распределения ресурсов 61
2.3.2. Задача календарного планирования и оперативного управления 62
2.4. Построение и исследование общей математической модели распределения ресурсов в иерархических системах 66
2.4.1. Математическая модель 66
2.4.2. Пример математического описания задачи распределения ресурсов в радиоэлектронном производстве 71
2.5. Постановка оптимизационных задач распределения ресурсов 76
2.5.1. Квадратичные многокритериальные задачи распределения ресурсов 76
2.5.2. Постановка задачи построения лексикографически оптимального решения 77
2.5.3. Построение неулучшаемого -приближенного решения многокритериальной задачи распределения ресурсов 77
2.5.4. Пример постановки задачи нахождения лексикографически оптимального и -приближенного решения 78
2.5.5. Задачи календарного планирования и оперативного управление 80
2.5.6. Пример постановки задачи календарного планирования и оперативного управления
82
2.6. Вычислительная сложность оптимизационных задач распределения ресурсов в иерархических системах 83
ГЛАВА 3. Алгоритм решения многокритериальных задач распределения ресурсов в иерархических системах 86
3.1. Релаксационный метод Агмона-Моцкина решения задачи проверки совместности системы линейных неравенств 86
3.2. Метод центрального пути решения задач линейного и квадратичного программирования 87
3.3. Решение задачи объемно-календарного планирования с единичной матрицей ограничений 91
3.4. Нахождение -приближенного решения задачи объемно-календарного планирования
95
3.4.1. Нахождение -приближенного решения 95
3.4.2. Пример нахождения -приближенного решения задачи объемно календарного планирования 96
3.5. Нахождение лексикографически оптимального решения задачи объемно- календарного планирования 97
3.5.1. Лексикографическая схема компромисса 97
3.5.2. Пример нахождения лексикографически оптимального решения задачи объемно-календарного планирования 100
3.6. Пошаговый алгоритм построения расписания выполнения операций задачи оперативного управления 102
3.7. Алгоритм решения задач календарного планирования и оперативного управления, основанный на вычислительных процедурах метода ветвей и границ 103
3.7.1. Основные вычислительные процедуры метода ветвей и границ 103
3.7.2. Процедура оценок 104
3.7.3. Процедура ветвления 104
3.8. Фронтальные алгоритмы решения задач оперативного управления 105
3.8.1. Стратегии назначения работ задач календарного планирования 105
3.8.2. Классический фронтальный алгоритм 105
3.8.3. Фронтальный алгоритм с рангами 107
3.8.4. Пример работы фронтального алгоритма с рангами 108
ГЛАВА 4. Диалоговые программные средства решения задач распределения ресурсов в иерархических системах 111
4.1. Описание диалоговых программных средств 111
4.1.1. Назначение и структура программного обеспечения 111
4.1.2. Основные модули 112
4.2. Типовой сценарий решения задачи распределения ресурсов в иерархических системах при помощи разработанного программного обеспечения 119
4.3. Примеры решения прикладных задач распределения ресурсов в иерархических системах с использованием диалоговых программных средств 123
4.3.1. Использованные аппаратные средства 123
4.3.2. Обозначения 124
4.3.3. Результаты решения задач распределения ресурсов 126
Заключение 128
Список литературы 129
- Математический аппарат, используемый при формализации процессов распределения ресурсов в иерархических системах
- Задача ситуационного анализа, планирования и оперативного управления процессом изготовления интегральных схем с микронными и субмикронными проектными нормами
- Метод центрального пути решения задач линейного и квадратичного программирования
- Типовой сценарий решения задачи распределения ресурсов в иерархических системах при помощи разработанного программного обеспечения
Математический аппарат, используемый при формализации процессов распределения ресурсов в иерархических системах
Тогда, если положение максимума X известно относительно двух гиперплоскостей задаваемых данными выражениями для некоторого значения І, то кусочно-квадратичную функцию р (Л) можно заменить на квадратичную или линейную функцию, зависящую от Л:
Алгоритм нахождения максимума р(Л) является итеративным. На каждой итерации определенная часть оставшихся функций (р.(Л) заменяется на квадратичные функции в подобласти допустимых значений в пространстве Л. Для определения подобласти, заданной выбранными гиперплоскостями, в которой достигается максимум X на каждой итерации применяется техника многомерного поиска описанная в [111].
Выпуклая задача квадратичного программирования Если Q неотрицательно определенная матрица тогда критерий задачи F(x) является выпуклой функцией. В этом случае задача квадратичного программирования имеет глобальный минимум, если существует допустимое решение х удовлетворяющий ограничениям задачи (система ограничений совместна) и функция F(x) ограниченна снизу. Если Q положительно определенная матрица и существует допустимое решение, тогда глобальный минимум единственный.
Для этой задачи в [75] приведен конечный метод нахождения решения, основанный на методе направленного перебора, при этом в качестве вспомогательной задачи на каждой итерации алгоритма рассматривается задача квадратичного программирования с ограничениями равенствами, которая сводится к задаче безусловной минимизации квадратичной выпуклой функции с последующим применением метода сопряженных градиентов [108].
Методы отсечений для решения задачи квадратичного программирования Один из основных классов методов решения выпуклых задач квадратичного программирования - методы отсечений. Среди методов данного класса можно выделить метод эллипсоидов предложенный Н.З. Шором [93]. Именно для этого метода была доказана полиномиальная разрешимость задачи выпуклого квадратичного программирования в работе Л.Г. Хачияна [28].
Определяется совместность системы линейных неравенств Ах Ъ на основе результатов изложенных в работе [86].
В случае совместности системы линейных неравенств устанавливается ограниченность снизу функционала F{x) на множестве допустимых значений, путем проверки совместности из п + т линейных неравенств и равенств относительно переменных хєЯ" и ЛєЯт:
Несмотря на то, что впервые полиномиальная разрешимость задачи выпуклого квадратичного программирования была показана именно при помощи метода отсечений, на практике чаще применяют другой метод, показывающий лучшую сходимость на реальных задачах - метод внутренних точек. Среди алгоритмов внутренних точек предназначенных для решения задач квадратичного программирования, можно выделить несколько различных подходов.
Аффинно-масштабируемые алгоритмы, разработанные И.И. Дикиным, В.И. Зоркальцевым [20], В.Г. Евтушенко, В.Т. Жаданом [21, 22]. Методы центрального пути, предложенные М. Коджимой, С. Мизуной, А. Йошиз [109], а также Р. Монтейро, И. Адлером [114].
Основной идеей методов внутренних точек является итеративное приближение решения точками, лежащими внутри или вне допустимой области, но никогда на границе. Каждый шаг алгоритма достаточно сложен, но зато значительно приближает к искомому решению [116].
Симплекс метод решения выпуклой задачи квадратичного программирования Для решения задачи квадратичного программирования П. Вольф (P. Wolfe) в своей работе [118] предложил алгоритм решения, основанный на модификации симплекс метода.
Используя прием предложенный E. M. L. Beale можно расширить применение описываемого алгоритма на случай когда матрица Q неотрицательно определенна. Для этого необходимо применить механизм виртуальных возмущений, позволяющий вместо рассмотрения qtj рассматривать q + yJ из малой 8 окрестности и оперировать с матрицей Q как с положительно определенной.
Задача ситуационного анализа, планирования и оперативного управления процессом изготовления интегральных схем с микронными и субмикронными проектными нормами
Объектом автоматизации является процесс производства изделий микроэлектроники и кристального производства с субмикронными нормами (задача 1.1) ([53, 54, 58]), который обеспечивает решение задач выпуска широкой номенклатуры продукции малыми сериями или единичными партиями, а так же изготовление пластин с заказанными элементами. Задачу планирования и оперативного управления процессом изготовления интегральных схем с микронными и субмикронными проектными нормами можно представить как две взаимосвязанных подзадачи: задача предварительного планирования на квартал объемов производства интегральных схем по подразделениям на различных уровнях административной иерархии (задача 1.1.1) и задача оперативного управления и календарного планирования выполнения работ по подразделениям в соответствии с квартальным планом по изготовлению партий пластин (задача 1.1.2).
Задача предварительного планирования на квартал объемов производства интегральных схем по подразделениям на различных уровнях административной иерархии (задача 1.1.1) заключается в выборе из возможных заказов тех, которые будут приняты к исполнению подразделениями предприятия. Результатом решения задачи будут не только принятые заказы, но и сроки начала и окончания их выполнения а так же некоторая обобщенная информация, связанная с ресурсными затратами на его выполнение (требуемый фонд времени работы оборудования, требуемые затраты материально-технологических ресурсов) и т.д. После решения этой задачи будут известны заказы, рекомендованные к включению в портфель заказов, подразделения исполнители и календарные сроки их выполнения, причем изделия заказов могут быть из группы уже выпускаемых, так и новые, информация по которым должна формироваться на основе наиболее «близких» к ним изделий, о которых у предприятия уже есть некоторая информация. Тем самым по некоторым изделиям заказа может быть «подробная» информация (описание технологического процесса), а по некоторым - «обобщенная» информация, полученная либо по аналогам, либо экспертным путем.
Таким образом, для формирования пакета заказов и объемно-календарного планирования требуется определить на заданный период планирования программу производства для подразделения предприятия в объемных показателях (нормо-часы, рубли, условные тонны), обеспечивающую эффективное функционирование подразделения, и удовлетворяющую ограничениям возможных объемов работы. При этом накладываются следующие ограничения: - объем работ, выполненный в подразделении в планируемом периоде по каждому заказу не должен превышать объемов незавершенного производства; -общий объем работ, который будет выполнен в подразделении в планируемом периоде, не должен превышать мощности подразделения. Критериями оптимальности задачи являются: - минимизация квадратичных функций штрафов, характеризующих отклонения выполняемых объемов работ от оптимальных величин загруженности подразделений; - минимизация квадратичных функций штрафов, характеризующих отклонения выполняемых объемов работ от плановых величин.
При решении задачи оперативного управления и календарного планирования выполнения работ по подразделениям в соответствии с квартальным планом по изготовлению партий пластин (задача 1.1.2) на вход поступает сформированный квартальный план на выпуск изделий по подразделениям, который необходимо выполнить. Для каждого заказа определены объемы и сроки начала и окончания его выполнения. Результатом решения этой задачи является расписание выполнения заказов, в котором определены сроки начала и окончания выполнения каждой операции каждого изделия каждого заказа. Критериями оптимальности являются: максимизация количества выполненных за планируемый период операций и минимизация времени на выпуск приоритетных партий изделий.
Для решения задачи оперативного управления и календарного планирования выполнения работ по подразделениям в соответствии с квартальным планом по изготовлению партий пластин используется позаказная система планирования. Каждый заказ включает в себя наборы партий пластин, для которых определены директивные сроки выполнения. С учетом процента выхода годной продукции, каждая партия пластин определяет количество кристаллов, которые поступят на операцию сборки. Перед операцией сборки допускается формирование из одной партии кристаллов нескольких подпартий на сборку, для каждой из которых может быть определен свой перечень технологических операций. Далее под изделием производства здесь понимается заказ (часть заказа), состоящий из партий пластин, которые в свою очередь могут состоять из подпартий, состоящих из подподпартий пластин. Причем число уровней иерархии может быть произвольным. Для каждой партии (подпартии) пластин задан перечень технологических операций, которые выполняются на оборудовании, причем для каждой технологической операции однозначно определен тип оборудования, на котором эта технологическая операция должна выполняться. Для каждой технологической операции определено количество различных материалов, необходимых для ее выполнения, а так же время ее выполнения на оборудовании. Оборудование может работать как по общему графику (рабочие дни, число смен, время обеденного перерыва…) так и по графику специфичному для данного оборудования. Часть технологических операций объединяются в группы (групповые операции), которые должны выполняться последовательно и без перерывов. Для некоторых технологических операций задано время пролеживания - минимально возможный интервал времени до начала следующей технологической операции (время, меньше которого не должно пройти до выполнения следующей по технологии операции). Для некоторых технологических операций задано межоперационное время - максимально возможный интервал времени до начала следующей технологической операции (время, больше которого не должно пройти до выполнения следующей по технологии операции). Определены завершающие работы для изделий - директивные работы, - для которых заданы сроки их выполнения (директивные сроки).
Метод центрального пути решения задач линейного и квадратичного программирования
Предположим, что на множестве частных критериев оптимальности (2.5.1.1) задачи можно задать полный порядок « », предполагая (не уменьшая общности), что Ft F+1,i = 1,s-1. Лексикографически оптимальным решением многокритериальной задачи назовем такое допустимое решение q =(q0,q20,...,q0„), что не существует допустимого решения q и натурального k, = 2Я таких, что F1(g ) F1(50 ), или FiQ ) = Fi(q),i = 1,k-1, FkQ) Fk(q). Задача нахождения лексикографически оптимального решения может быть поставлена в случае, если на множестве частных критериев оптимальности можно установить полный порядок.
Задачи, соответствующие случаю упорядоченности частных критериев обозначим как задача 1.1.1 .а, задача 1.2.1 .а и задача 1.3.1 .а соответственно. Построение неулучшаемого -приближенного решения многокритериальной задачи распределения ресурсов
Назовем -приближенным решением s -критериальной задачи такое допустимое решение задачи q , что Ft(q ) є,i = 1,s. Здесь є 0 - заданный управляемый параметр, определяющий «качество» полученного решения многокритериальной задачи. Назовем неулучшаемым -приближенным решением задачи такое -приближенное решение J , что не существует такого є\є} є и q eR", что
Задача нахождения неулучшаемого є-приближенного решения может быть поставлена, когда все критерии многокритериальной задачи имеют одинаковую значимость.
Таким образом, при нахождение неулучшаемого є-приближенного решения будет найдено такое решение, что наибольшее отклонение среди всех критериев от 0 будет минимальным на данном решении, что соответствует нахождению решению исходной задачи согласно принципу гарантированного
Пример постановки задачи нахождения лексикографически оптимального и є-приближенного решения Рассмотрим постановку задачи нахождения лексикографически оптимального (задача 1.1.1.а) и -приближенного решения (задача 1.1.1.б), на примере задачи описанной в пункте 2.4.2. Выбор показателей объемов производства на планируемый период осуществляется исходя из следующих условий: - необходимость обеспечения средней ежеквартальной наработки цеха. В соответствии со стандартами предприятия у цеха есть усредненные показатели производительности в квартал, невыполнение этих показателей (как в большую, так и в меньшую стороны) ведет к возникновению административных последствий. Кроме того отклонение от средних плановых показателей зачастую означает простой оборудования или же необходимость внеурочной работы; -необходимость обеспечения 25% запаса изготавливаемых партий изделий, для обеспечения запасных частей и нивелирования брака.
Третий заказ является более срочным и приоритетным, поэтому изготовление по нему дополнительных запасных элементов является приоритетной задачей. Среди первого и второго заказа более приоритетным является первый заказ, так как он поступил от заказчика с многолетней историей сотрудничества. Выполнение планов по изделиям является приоритетной первоочередной задачей, напротив обеспечение средней ежеквартальной наработки цеха является задачей скорее эффективного управления и расходования ресурсов. В связи с тем, что подведением итогов четвертого квартала совпадает по времени с подведением итогов года, производимого по фактически выполненным работам, обеспечение средней ежеквартальной наработки цеха в третьем квартале является более приоритетной задачей, чем в четвертом квартале. Таким образом, над множеством критериев 1-5 можно построить полный порядок Fl - F2 - F3 - F4 - F5, а значит, имеет смысл говорить о задачи нахождения лексикографически оптимального решения. В случае если обеспечения 25% запаса изготавливаемых партий изделий уже включено в ограничения задачи (критерии FltF2,F3 отсутствуют), имеет смысл рассматривать критерии, связанные с необходимость обеспечения средней ежеквартальной наработки цеха, как равнозначные. В этом случае ставиться задача нахождения неулучшаемого -приближенного решения.
Кроме того, на условия эффективного функционирования рассматриваемых производственных систем могут накладываться требования, которые не учитываются в ограничениях математической модели. Например, это могут быть условия предотвращения нарушений межоперационных времен. Определим для каждой операции с определенными межоперационными
Для работ могут быть заданы приоритеты, в соответствии с которыми должно происходить назначение операций на выполнение (операции, соответствующие партиям с большим приоритетом, должны выполняться раньше). Пусть Rp - множество работ, для которых заданы приоритеты, а Рг, Рг 0- приоритет, определенный для работы г, причем, если rRp, то Рг=0. Тогда технологические операции, необходимые для работ также обладают приоритетами, равными максимальным приоритетам среди всех приоритетов работ находящихся в соответствующих ветках иерархий:
Типовой сценарий решения задачи распределения ресурсов в иерархических системах при помощи разработанного программного обеспечения
Фронтальный алгоритм с рангами [34, 35] позволяет учитывать «мягкие» технологические условия благодаря дополнительному введению рангов выполняемых работ. Критерием оценки решения для каждой итерации алгоритма является суммарный штраф, налагаемый за нарушение «мягких» технологических условий.
В алгоритме, можно выделить две основные фазы: итерационное изменение рангов операций в соответствии с вызываемыми ими нарушениями дополнительных ограничений; дополнительная оценка возможностей сдвига предков операций вызывающих нарушения, которые не могут быть устранены изменением рангов операций.
В основе первой фазы лежит итерационный вызов фронтального алгоритма. При этом фронтальный алгоритм использует схему упорядочивания работ, описанную в предыдущем пункте, дополненную стратегией упорядочивания По рангам работ , имеющей наибольший приоритет в лексикографическом упорядочивании. Ранги операций вычисляются, в зависимости от величины нарушений «мягких» технологических условий, после построения очередного расписания фронтальным алгоритмом на основе рангов. Ранг операции rng на шаге і вычисляются путем суммирования ранга на шаге /-1 и величины штрафа вызванного этой операцией
Благодаря использованию фронтального алгоритма для построения расписаний всегда гарантируется допустимость построенного решения с точки зрения «жестких» технологических условий. Критерием окончания первой фазы служит выполнение любого из двух условий: - выполнение предопределенного числа итераций. - значительное уменьшение скорости улучшения критерия оценки. После окончания работы первой фазы алгоритма, среди построенных расписаний на основе приоритетов, выбирается лучшее расписание и для него запускается вторая фаза.
Во время второй фазы последовательно оцениваются только те операции, которые вызвали нарушение «мягких» технологических условий. Для каждой из этих операций предпринимается попытка построить расписание с лучшим значением критерия оценки, путем сдвига предыдущих операций на величину нарушения дополнительных условий. Изменение принимается, если достигнутое значение критерии оценки улучшает значение критерия оценки, достигнутое на предыдущем шаге.
Работа первой фазы фронтального алгоритма с рангами начинается с получения допустимого расписания при помощи фронтального алгоритма. После первого прохода фронтального алгоритма в цепочке технологических операций, предназначенных для изготовления изделий по третьему заказу, было обнаружено нарушение директивного срока операции «Проявление» (Рис. 2).
В соответствии с вышеописанным алгоритмом ранг всех операций предшествующих операции «Проявление» был увеличен. В результате чего операция «Химической очистки», предназначенная для изготовления изделий из состава третьего заказа стала более приоритетной, чем аналогичная операция, предназначенная для изготовления изделий из состава второго заказа. Это вызвало назначение операции «Химической очистки», предназначенной для изготовления изделий из состава третьего заказа, на более ранний срок, что в результате привело к снятию нарушения директивного срока (Рис. 3.)
После выполнения нескольких итераций первой фазы, фронтальный алгоритм с рангами переходит ко второй фазе, во время которой происходит попытка уменьшить количество нарушении путем дополнительного сдвига предков операции. Одним из таких нарушенных условий, исправить которое не удалось во время первой фазы алгоритма, является межоперационное время между операциями «Химическая очистка» и «Окисление и осаждение Si3N4» установленное равным 2 часа. После завершения первой фазы алгоритма операция «Химическая очистка» заканчивается в 09:00, а операция «Окисление и осаждение Si3N4» начинается только в 12:52, таким образом, перерыв между операциями составляет 03 часа 52 минуты вместо положенных 2 часов (Рис. 4).
Нарушение данного срока вызвано, как занятостью оборудования, так и выпадением выполнения цепочки операций на обеденное время. Результатом работы второй фазы фронтального алгоритма с рангами стал дополнительный сдвиг начала выполнения операции «Химическая очистка», так чтобы ее завершение было перенесено на время 10:52 (Рис. 5).
Для решения этих задач в ПО реализованы алгоритмы, описанные в главе 3. Исходными данными для ПО являются данные, полученные из системы управления производством. Эти данные могут быть представлены, как в виде таблиц в БД (Oracle или MS SQL), так, и в виде специально структурированного XML файла. Полученные результаты могут быть загружены в систему управления производством также посредством БД или XML файла. Кроме того, ПО имеет собственный интерфейс пользователя, который обеспечивает: - отображение списка доступного оборудования; - отображение списка планируемых работ по партиям; - составление графика Ганта выполнения работ; - составление графика расходования ресурсов; - выявление «узких» мест по ресурсам; - выявление «свободных» ресурсов;
