автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.01, диссертация на тему:Распределение ресурсов в многоуровневых иерархических системах с активными элементами

На правах рукописи

Дикарев Константин Игоревич

Распределение ресурсов в многоуровневых иерархических системах с активными элементами

Специальность 05.13.01. — «Системный анализ, управление и обработка информации (в науке и промышленности)» по техническим наукам

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

9 ОКТ 2014

Нижний Новгород — 2014 г.

005553240

005553240

Работа выполнена на кафедре информатики и автоматизации научных исследований Федерального автономного бюджетного образовательного учреждения высшего профессионального образования «Нижегородский государственный университет им. Н.И.Лобачевского»

Научный руководитель:

Официальные оппоненты:

Ведущая организация:

доктор технических наук, профессор

Прилуцкий Михаил Хаимович

доктор технических наук, профессор Максимов Юрий Михайлович, профессор кафедры «Экономическая теория и эконометрика» Института Экономики и Управления НГТУ им. P.E. Алексеева, г. Нижний Новгород кандидат физико-математических наук, Дуничкина Надежда Александровна, старший научный сотрудник кафедры Информатики, систем управления и телекоммуникаций Волжской

государственной академии водного транспорта, г. Нижний Новгород Открытое акционерное общество «Опытное Конструкторское Бюро Машиностроения имени И.И. Африкантова», г. Нижний Новгород

Защита диссертации состоится «20» ноября 2014 года в 13 часов в ауд. 1258 на заседании диссертационного совета Д 212.165.05 при Нижегородском государственном техническом университете им. P.E. Алексеева по адресу: 603950, г. Нижний Новгород, ул. Минина, 24.

С диссертацией можно ознакомиться в библиотеке Нижегородского государственного технического университета им. P.E. Алексеева и на сайте http://wvvw.nntu.ru/content/asniranlura-i-doktoran tura/disserlacii.

Автореферат разослан «19» сентября 2014 года.

Ученый секретарь диссертационного совета

Суркова Анна Сергеевна

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность работы. Одной из актуальных и важных задач, возникающих в области управления большими техническими и производственными системами, является проблема эффективного управления и планирования. В большинстве случаев такие задачи связаны с оптимальным распределением ресурсов, в том числе и в рамках сложных систем.

Развитием этой научной области являются труды таких ученых, как Бурков В.Н., Зуховицкий С.И., Кантарович JI.B., Корбут A.A., Кукса А.И., Михалевич B.C., Сигал И.Х., Танаев B.C., Финкельштейн Ю.Ю., Шкурба В.В., Юдин Б.Д. и многие другие. Из зарубежных ученых в данной области работали Данциг Дж. Б., Джонсон Б., Беллман Р., Конвей Р., Месарович М. и др. Следует также отметить школу Нижегородского университета и ученых Батищева Д.И., Когана Д.И., Костюкова В.Е., Прилуцкого М.Х., Федосенко Ю.С. и др., которые рассматривали подобные проблемы.

В настоящее время задачи нахождения оптимальных режимов функционирования технических объектов, и согласования входных и выходных параметров промышленных систем по критериям минимизации ресурсных затрат в основном решаются с применением прямого детерминистического подхода, в основу которого положено применение «одноуровневых» математических моделей рассматриваемых структур. При таком подходе зачастую необходим учет в моделях элементов систем сложных функциональных зависимостей, описывающих их режимы работы. Для современных промышленных комплексов, и учитывая высокие требования к точности результатов решаемых задач, такие подходы подразумевают учет в моделях огромного числа параметров. Вышесказанное приводит к тому, что задачи математического программирования, которые ставятся на основе разработанных моделей, обладают существенной математической сложностью, и их решение затруднительно даже с применением современных высокопроизводительных многопроцессорных ЭВМ, так как требует

существенных вычислительных ресурсов.

3

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

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

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

Задачи работы. В соответствии с этой целью в диссертационной работе поставлены и решены следующие задачи:

- проведена классификация задач распределения ресурсов как задач математического программирования;

1- выделен класс задач распределения ресурсов в иерархических системах с активными элементами;

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

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

- поставлены оптимизационные задачи распределения ресурсов в сетевых иерархических системах с активными элементами, из которых выделены полиномиально разрешимые и КР-трудные задачи;

- разработаны методы решения задач рассматриваемого класса;

- разработаны программные средства решения задач распределения ресурсов в иерархических системах с активными элементами, которые применяются учебном процессе, а также в повседневной практике проектирования газотранспортных систем и планирования микроэлектронного производства.

Методы исследования. Для решения поставленных задач в диссертационной работе использовались методы системного анализа, теории графов, сетевого планирования, линейного и дискретного программирования.

Научная новизна работы состоит в следующих основных результатах.

1. Выделен новый класс задач распределения ресурсов в сетевых иерархических системах с активными элементами.

2. Построены общая математическая модель и частные подмодели распределения ресурсов в иерархических системах с активными элементами.

3. В рамках построенных математических моделей поставлена общая задача и частные подзадачи оптимального распределения ресурсов в иерархических системах с активными элементами по критериям минимизации затрат на функционирование систем. Из рассматриваемых задач выделены полиномиально разрешимые и КР-трудные.

4. Для решения ЫР-трудных задач предложены приближенные алгоритмы решения, основанные на комбинациях фронтальных алгоритмов и дихотомического деления допустимых «ресурсных» интервалов. Для полиномиально разрешимых задач предложены алгоритмы, основанные на методах сетевого планирования.

Практическая значимость и внедрение. Теоретические исследования и научные результаты работы доведены до инженерных решений в виде

5

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

Практическая значимость диссертационной работы состоит в разработке интерактивного программного обеспечения, предназначенного для решения задач согласования входов и выходов участков газотранспортных систем, и для поиска оптимальных режимов производств с многорежимным оборудованием. Программное обеспечение апробировано на задачах расчетного определения оптимальных режимов функционирования для участков газотранспортных систем по критерию минимизации суммарных капитальных и эксплуатационных затрат на стадии проектирования в ФГУП «РФЯЦ-ВНИИЭФ». Разработанные программные средства также были апробированы на задачах планирования производства электронных микросхем в ФГУП «ФНПЦ НИИИС им. Ю.Е.Седакова».

Результаты диссертационной работы используются в учебном процессе Нижегородского государственного университета им. Н.И. Лобачевского на факультете вычислительной математики и кибернетики при преподавании курса «Теория систем и системный анализ».

Личный вклад автора. Все выносимые на защиту результаты и положения, составляющие основное содержание диссертационной работы, разработаны и получены лично автором или при его непосредственном участии. Им же лично подготовлены публикации [4], [13], [17-18], [20].

Основные положения, выносимые на защиту.

1. Общая математическая модель распределения ресурсов в иерархических системах с активными элементами, в рамках которой ставятся задачи системного анализа, оптимизации и управления активными элементами.

2. Частные подмодели, описывающие реальные производственные

системы: модель транспорта природного газа в многониточных

газотранспортных системах с газоперекачивающими мощностями в

качестве активных элементов; модель функционирования

6

производственных систем с многорежимным оборудованием в качестве активных элементов; модель распределения теплоносителя в рамках фрагментов систем теплоснабжения с сетевыми насосами в качестве активных элементов.

3. Точные и приближенные методы и алгоритмы решения оптимизационных задач распределения ресурсов в иерархических системах с активными элементами, и результаты их исследования.

Апробация результатов работы. Результаты работы докладывались и обсуждались на Международных научно-технических конференциях «Информационные системы и технологии» ИСТ-2011, ИСТ-2013 и ИСТ-2014 (Н.Новгород, 2011г., 2013г. и 2014г.), Всероссийской научно-технической конференции «Новые информационные технологии» НИТ-2011 (Москва, 2011 г.), XII Всероссийской конференции «Высокопроизводительные параллельные вычисления на кластерных системах» (Н. Новгород, 2012г.), XIV Международной конференции «Супервычисления и математическое моделирование» (Саров, 2012г.), на Всероссийских научно-практических конференциях по графическим информационным технологиям и системам "КОГРАФ-2012" и "КОГРАФ-2013 (Н. Новгород, 2012г., 2013г.), Международной научной конференции "Numerical Computations: Theory And Algorithms" NUMTA-2013 (Фалерна, Италия, 2013г.), а также на научных семинарах кафедры информатики и автоматизации научных исследований факультета ВМК ННГУ.

Публикации. Научные результаты диссертационной работы изложены в 20 работах: - 6 статей, из которых 5 в изданиях, рекомендованных ВАК РФ для публикации результатов диссертаций на соискание ученых степеней доктора и кандидата наук, 4 свидетельства о государственной регистрации программ для ЭВМ, 10 тезисов докладов на международных и всероссийских конференциях.

Структура и объем работы. Работа состоит из введения, четырех глав, заключения, списка литературы и приложения. Основное содержание изложено

на 143 страницах машинописного текста и иллюстрировано 6 рисунками. Список литературы содержит 122 наименования.

КРАТКОЕ СОДЕРЖАНИЕ РАБОТЫ Во введении отражена актуальность задач распределения ресурсов в сложных иерархических системах. Отражены цели, задачи и методы исследования, научная новизна выполняемой работы. Указана практическая значимость, личный вклад автора, выносимые на защиту положения, а также сведения об апробации результатов.

В главе 1 рассматриваются классические задачи распределения ресурсов, а также место задач распределения ресурсов в сложных иерархических системах в классе задач математического программирования.

В разделе 1.1 рассматриваются аспекты подхода, связанного с формализацией различных технических систем в виде многоуровневых иерархических структур.

В разделе 1.2 задачи оптимального распределения ресурсов в сложных иерархических системах рассматриваются как задачи математического программирования и исследования операций. Приведены примеры задач распределения ресурсов в сложных иерархических системах. Выполнен обзор литературных источников, в которых рассматриваются подобные задачи.

В разделе 1.3 приводится содержательное описание актуальных технических и промышленных задач распределения ресурсов в иерархических системах с активными элементами. Конкретизуется понятие активности и пассивности элементов иерархической системы.

Содержательное описание приводится для нескольких типов задач:

— задачи согласования параметров для участков газотранспортных систем (раздел 13.1);

— задачи поиска оптимальных режимов функционирования производственных систем с многорежимным оборудованием (раздел 13.2);

— задачи поиска оптимальных режимов функционирования для фрагментов систем отопления (раздел 1.3.3);

— общей проблемы оптимального распределения ресурсов в иерархических системах с активными элементами (раздел 13.4).

Глава 2 посвящена рассмотрению математической модели распределения ресурсов в сложных иерархических системах с активными элементами.

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

Пусть й = (У,А), А с У2 — ориентированный граф без петель и контуров, множество вершин V которого соответствует элементам системы, множество дуг А - связям между ними; К(у) - множество элементов, непосредственно предшествующих элементу V, <2(у) — множество элементов непосредственно следующих за элементом V, уеС; Vхи увых - множества входных и выходных элементов, К®* ={у|К(у) = 0,уеК|, Увых ={у|д(у) = 0,уеК); I- множество характеристик системы; иу - множество допустимых управлений для элемента v, уеК; И>у- вектор, определяющий значения характеристик на входе у-го элемента системы, уеУ, е ; (V/ и ()*- минимальные и максимальные возможные значения характеристики /' на входе у-го элемента системы, а Н"и

— минимальные и максимальные возможные значения характеристики г на выходе у-го элемента системы, О<W¡V<QV¡, 0< Я/ < Я",, /е/,уеК; ¿¡у-заданные значения характеристик для входного элемента v,ve Vх\ заданные значения характеристик для выходного элемента у,уеКвь",

Введение множества допустимых управлений и" подразумевает, что иерархическая система формализуется в виде совокупности активных Уа и пассивных Ур элементов, V" сУ, УрсУ, Уа1)Ур=У, УаГ)Ур = 0. Применение того или иного управления для активного элемента при заданных входных параметрах по-разному реализует выходные параметры, с различными затратами. Пассивные элементы автоматически преобразуют входные параметры в выходные, и для них управления недопустимы.

Варьируемыми параметрами математической модели являются вектор й", определяющий значения характеристик на входе у-го элемента системы, уе V, е а также йу- вектор допустимых управлений, применяемых к элементу иу ,уеУ.

На основании введенных варьируемых параметров определим: фу(н>у.й*",<?)- вектор-функцию, преобразующую входные характеристики элемента V в его выходные характеристики под воздействием допустимых управлений и", ф1",йу,8)еЯМ, где параметр д принимает значение 1, если уеУа,и значение 0 - если уеУр, и" еиу,у еУ;

,й* ,5),зъК(у))- вектор-функцию, в соответствии с которой вычисляются входные характеристики элемента V по выходным характеристикам всех элементов, непосредственно предшествующих элементу у.уеК;

функцию, определяющую затраты, которые получит система, при применении к V вектора допустимых управлений му, й"е£/у, уе К.

Ограничения математической модели

Интервальные ограничения для характеристик системы на входах элементов:

Заданные значения характеристик на входных элементах:

к." = 5^6 И".

Интервальные ограничения для характеристик на выходах элементов:

Н] < ,6) < 8?,5 = 0,1,1 е /, V € V;

Заданные значения характеристик на выходных элементах:

фу (, б) = 6 = о, 1, V 6 (Увых П Ур); Соотношение баланса между входными характеристиками промежуточного элемента системы и выходными характеристиками непосредственно предшествующих ему элементов:

й." = /у(фу (, й5,5), 6 = 0,1, 5 € ЛГОО), у е (V \ Vе*). Проводится исследование построенной математической модели. Показано, что проверка существования допустимого решения для построенной математической модели относится к классу № - трудных задач.

В разделе 2.2 на основе разработанной общей математической модели построены частные подмодели распределения ресурсов в иерархических системах с активными элементами.

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

Здесь Р^*^** - входное и выходное давление газа для активного элемента газотранспортной системы, соответственно; У®"* - выходной расход газа для активного элемента газотранспортной системы; и* — допустимое управление (число оборотов вала цехового газоперекачивающего агрегата), <еГ(у); Г(у)-

множество агрегатов у-го компрессорного цеха, и" б V еУ.

Используя введенные варьируемые параметры, в рамках общей модели построена частная подмодель, описывающая функционирование участков газотранспортных систем.

Общая математическая модель конкретизируется для важного практического случая отдельного активного элемента газотранспортной системы (компрессорного цеха). Исходными параметрами указанной частной подмодели являются < = 1 ,т — номера групп газоперекачивающих агрегатов компрессорного цеха; у = 1,л - номера подинтервалов дискретизации возможных объемов перекачиваемого газа для всех групп агрегатов; т]~ и /несоответственно минимально возможное и максимально допустимое число агрегатов »-ой группы, которое может быть использовано, / = 1 ,т\ Зц и -

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

дискретизации объемов, 0<3^<1{Тр 1=17т,У = Гй; о,у и 6,у - коэффициенты линейной функции, определяющей зависимость потребляемой при функционировании агрегатов мощности от объема компримируемого газа; плановый коммерческий объем газа, который цех должен «перекачать».

Варьируемыми параметрами частной подмодели являются: количество а1регатов ¿-ой группы, которые работают в планируемом периоде в компрессорном цехе, / = 1,т; уг объем газа, который перекачивается агрегатом /-ой группы, ¡ = ],т; 7,у- булева переменная, 7,у = 1, если агрегат /-ой группы

работает в у-ом интервале допустимых объемов производительности, и г,у = 0, в

противном случае, / = 1,т, _/ = 1 ,п.

На основе введенных параметров строится математическая модель функционирования отдельного компрессорного цеха. Ограничения математической модели

Плановый объем газа для компрессорной станции должен быть выполнен:

;=1

Ограничения по возможному количеству используемых агрегатов:

т~ < х! < т*, / = 1 ,т. Ограничения на возможные объемы перекачиваемого газа для каждого агрегата:

" " + —

£ 5 >7 2 I ,' = 1т. М 7=1

Для каждого агрегата выбирается только один «рабочий» интервал производительности:

п _

£ г,у =1, / = 1,т.

Естественные условия на переменные:

x¡-целые, / = 1,1я; е {ОД} , « = 1,т, У = 1,л. В разделе 2.2.2 приводится частная подмодель функционирования производственной системы с многорежимным оборудованием. В данной модели роль активного элемента играет многорежимное оборудование. Пассивные элементы системы - это транспортировочные линии для продукции. Варьируемыми параметрами являются управления иу, уеУа, представляющие интенсивность потребления ресурса элементом, а также вектор входных характеристик элемента и-1' производственной системы со следующими компонентами:

Здесь tv - время выполнения производственной операции элементом у; gv-

ресурсоемкость операции для элемента v; v <е V".

В разделе 2.2.3 построена частная подмодель функционирования участка системы теплоснабжения, которая конкретизируется для случая теплофикационной установки ТЭЦ.

В разделе 2.3 рассматриваются различные постановки оптимизационных задач распределения ресурсов в иерархических системах с активными элементами на основе разработанных математических моделей.

В разделе 2.3.1 приведена общая постановка задачи оптимального распределения ресурсов в иерархических системах с активными элементами на основе общей математической модели, построенной в разделе 2.1. Задача заключается в нахождении стратегии управления активными элементами системы, обеспечивающей согласование параметров элементов системы с минимальным значением функции затрат на управления. Критерий в задаче оптимального согласования запишется таким образом:

vgV"

Здесь фу(wv,öv) - функция затрат системы, в случае применения для активного элемента системы v заданных допустимых управлений üv, v е V".

В разделе 2.3.2 приведена постановка задачи оптимизации режимов транспорта природного газа в газотранспортных системах. Для случая отдельного активного элемента газотранспортной системы задача выражается в нахождении таких значений варьируемых переменных, чтобы суммарная потребляемая мощность для всех газоперекачиваемых агрегатов в цехе была минимальной:

гп л . .

F(x,y,Z) = YSL\аиУ, + bij Fijxi min. ы м

В разделе 23.3 приведена постановка задачи поиска оптимальных режимов функционирования для производственной системы. Задача представляет собой проблему поиска стратегии управления производственной

14

системой с- активными элементами. Под такой стратегией понимается функция т](у), v eV", со значениями из множества управлений Uv, определяющая для каждого активного элемента «интенсивность», с которой будет выполняться соответствующая операция, связанная с данным элементом.

Пусть S - множество всех возможных стратегий. Задача ставится как бикритериальная проблема минимизации компонент вектора-функции $(rj(y),D) = (ip[(Ti(v),D),fc(ti(.v),D)) по всевозможным стратегиям tj(v), veVa, из множества S:

<h(t](v),D) -> min, fc(rj(v),D) -> min. Здесь D - директивный срок окончания изготовления изделия; <j\(rt(y),D)— функция, определяющая штрафные санкции, связанные с возможными нарушениями директивного срока Z>; <fa(r](v),D) — функция, определяющая суммарные затраты на функционирование активных элементов системы.

В разделе 2-3.4 на основе соответствующей частной математической подмодели приведена постановка задачи поиска оптимальных режимов функционирования теплофикационной установки ТЭЦ.

В главе 3 приводится описание алгоритмов решения оптимизационных задач распределения ресурсов в иерархических системах с активными и пассивными элементами.

Раздел 3.1 посвящен рассмотрению общего алгоритма решения задачи оптимального распределения ресурсов в иерархических системах с активными элементами. Предлагаемый приближенный алгоритм представляет собой стратегию фронтального протягивания характеристик от входных элементов иерархической системы до ее выходных элементов.

Раздел 3.2 посвящен конкретизации общего алгоритма решения для случая оптимизации режимов транспорта газа в газотранспортных системах.

Для отдельного активного элемента предложен точный алгоритм, основанный на направленном переборе допустимых вариантов. Для решения поставленной задачи необходимо проверить на совместность

= 2m • nm ■ П (m* - m, +1) наборов, и из совместных наборов выбрать тот, на

котором достигается минимальное значение функции суммарной потребляемой

мощности. Пусть кьк2.....кт — произвольный допустимый набор, где кг

количество агрегатов / -ой группы, которые будут использованы в планируемом периоде, / = 1 ,т. Тогда для этого набора решаем следующую задачу:

ЪкгУ1=Гых- izy.Jy<yi< tzg-Jj, i = üi ; 1^=1, i = /=1 7=1 j=\ j=\

_ ___ m n . .

Zy-6{0,1}, i = \,m, j = l,n; F{y,Z)=Y. E ("¡j ■ >', + by ]z,y -> min.

i-lj-i

Эту задачу предлагается решать перебором всевозможных наборов значений Zjj € {0,1}, i = \,m, у = 1,п. Количество таких различных наборов будет пт.

Т.е. надо решить пт задач линейного программирования с номерами = 1,2... пт, следующего вида:

т __(т \

Для решения каждой указанной задачи достаточно рассмотреть 2т точек, "подозрительных" на допустимость, для каждой точки проверить ее на допустимость, подставив значения координат точки в уравнение баланса

т

X к, ■ = Jeblx, и среди допустимых точек найти точку с минимальным /=1

значением критерия.

Раздел 3.3 посвящен конкретизации общего алгоритма решения задачи распределения ресурсов на случай задачи поиска оптимальных режимов участка теплоснабжающей системы с насосами сетевой воды в качестве активных элементов.

В Разделе 3.4 приводится алгоритм решения задачи поиска оптимального режима функционирования производственной системы с многорежимным оборудованием.

Для рассматриваемых производственных систем первичными будем считать условия, связанные с выполнением директивного срока изготовления й. Предложена лексикографическая схема свертки поставленной бикритериальной задачи, которая заключается в последовательном решении двух оптимизационных задач.

Задача 1. Найти стратегию 7?0(у) , для которой выполняются ограничения

увЬ1Х _увых увых

задачи и минимизируется функционал ф1{т](у),0) = а(—-——--——хЮО),

..вых „вых ..вых „

где <р( (й ,и ) - время окончания выполнения завершающей операции, а а - коэффициент, определяющий штрафные санкции в случае нарушения директивного срока изготовления изделия на 1 процент.

Задача 2. Найти стратегию, для которой выполняется условие ф1(т;(у\О)=ф1(г]0(у),О), и минимизируется функционал

Алгоритм решения задачи 1. Стратегию представим такими

управлениями активными элементами, при которых минимально время выполнения соответствующих операций. Пусть при такой стратегии имеет место:

— ситуация 1: <р( ,и )>£>, несмотря на минимальные длительности выполнения операций, директивный срок будет нарушен, тогда

1,выдг _увых увых ^

для задачи 1 определен оптимум = -——-хЮО);

вых вых вых

— ситуация 2: <р{ (й<у У )<£>, тогда определим максимально возможные длительности выполнения активных операций, и если суммарное

вых вых вых

время при данных длительностях д>'\ О ,и )>А, то задача 1 решена, стратегия щ(у) находится при условиях, что значение критерия ф[(щ(у),В) = 0;

, вых „вых „вых „вых вых вых

— ситуация 3: ^ (Л У )<Д, а <р'\ У )<О, то задача 1 решена, стратегия щ(у) находится при условиях, что все операции

выполняются с минимальными затратами ресурса (интенсивностями), и значения критерия <^(щ(у),0) = 0 .

В алгоритме решения задачи 2 рассчитываются временные характеристики сетевого графика, определенного стратегией, найденной при решении задачи 1. Для операций критического пути сохраняются интенсивности, определяемые найденной оптимальной стратегией задачи 1. Для операций с ненулевым резервом времени интенсивности выбираются так, чтобы затраты на их использование были минимальны из возможных интенсивностей, при которых длительность выполнения операций не превышает критического пути. Указанная стратегия определит оптимальное решение поставленной двухкритериальной задачи.

В главе 4 рассматриваются программные средства решения задач распределения ресурсов в иерархических системах с активными элементами. Приведены примеры решения задач поиска оптимальных режимов работы для участка газотранспортной системы и для производства интегральных микросхем.

Пусть ставится задача оптимального согласования характеристик участка газотранспортной системы. На рис. 1 приведена структура участка. На входах и выходах участка заданы ограничения на значения распределяемых характеристик системы - коммерческого расхода и давления транспортируемого газа.

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

Рис. 1. Структура участка газотранспортной системы

Наименование обобщ. элемента Вход Выход Стоимость (млн.руб.)

Давление (ата) Расход (млн.м3 /сут.) Давление (ата) Расход (млн.м3 /сут.) Эксплуатации Модернизации

3.1 55.42 540.09 63 517.77 872.69 0

5.1 63 221.58 63.06 211.70 835.26 1122.23

6.2 63 350.97 62.50 350.97 16.99 0

8.1 35 74.98 35.04 60.54 384.64 0

9.2 63.13 50.76 63.06 50.76 1.79 0

10.1 63.06 252.46 63.13 253.43 984.46 1600.14

14.1 45 270.84 72.32 267.72 4388.94 1197.47

Таблица 1

Пусть ставится следующая задача: для участка микроэлектронного

производства больших интегральных схем (БИС) определить режимы функционирования, применение которых приведет к минимизации времени изготовления изделий БИС, для заданного временного интервала планирования производства.

Исходные данные для задачи следующие. Процесс производства изделия состоит из семи партий. Общее число операций составляет 1513, а число типов оборудования равно 30. Исходное сырье представляет из себя наборы партий пластин, из которых изготавливаются интегральные схемы. Для каждой

19

технологической операции однозначно определено оборудование, на котором эта технологическая операция должна выполняться, а также время ее выполнения на оборудовании. Для некоторых технологических операций задано время пролеживания, и межоперационное время.

Результаты решения описанной задачи по построению эффективного расписания всего комплекса операций производства БИС приводятся ниже. На рис. 2 представлен график сводного отчета по партиям БИС. В отчете на каждый такт планирования представлена информация о времени запуска партии изделий, об объеме выполненных работ, о директивном сроке завершения работ, о планируемом сроке завершения в соответствии с составленным расписанием для оборудования.

•j

".) $«>U . Qkms . *«м«?рм

ОтмЛлчии. Срк*. '

'} Ш idl □ Щ У- ; i«s

Сводный отчет по партиям

не дату ' 6 2012

Рис. 2. Сводный отчет по партиям БИС

В заключении изложены основные научные и практические результаты диссертационной работы.

В приложении содержатся документы, подтверждающие апробацию и внедрение результатов работы.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

1. В работе рассмотрены задачи распределения ресурсов в иерархических системах с активными элементами. Определено место задач распределения ресурсов в сложных иерархических системах в классе задач математического программирования. Выделен новый класс задач распределения ресурсов в сетевых иерархических системах с активными элементами.

2. Построена общая математическая модель распределения ресурсов в сложных иерархических системах с активными элементами. Математическая

модель конкретизирована на случаи частных подмоделей, связанных с актуальными промышленными задачами. Проведено исследование построенных математических моделей. В рамках моделей поставлены оптимизационные задачи, из которых выделены полиномиально разрешимые и NP-тpyдныe.

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

4. Теоретические результаты диссертационной работы легли в основу диалоговых программных средств, апробированных в расчетах оптимальных режимов для участков газотранспортных систем, по критерию минимизации суммарных капитальных и эксплуатационных затрат на стадии проектирования в ФГУП «РФЯЦ-ВНИЙЭФ», а также применяемых в практике определения оптимальных режимов работы оборудования для производства электронных микросхем в ФГУП «ФНПЦ НИИИС им. Ю.Е.Седакова».

ОСНОВНЫЕ ПУБЛИКАЦИИ

Публикации в изданиях, рекомендованных ВАК РФ

1. Прилуцкий, М.Х. Оптимизационные задачи согласования параметров для участков газотранспортной системы [Текст] / М.Х. Прилуцкий, К.И. Дикарев // Системы Управления и Информационные Технологии. - Воронеж: Научная книга, 2011 - № 3.1 (45) - С. 185-189.

2. Прилуцкий, М.Х. Распределение ресурсов в иерархических системах с активными элементами [Текст] / М.Х.Прилуцкий, К.И. Дикарев // Вестник Нижегородского университета им. Н.И. Лобачевского. - Н. Новгород: Изд-во Нижегородского госуниверситета, 2012. - № 5(2). - С. 181-189.

3. Прилуцкий, М.Х. Бикритериальная задача распределения ресурсов в сетевых структурах с активными элементами [Текст] / М.Х.Прилуцкий, К.И. Дикарев // Вестник Нижегородского университета им. Н.И. Лобачевского. - Н. Новгород: Изд-во Нижегородского госуниверситета, 2012. - № 6. — С. 153-158.

4. Дикарев, К.И. Математические модели распределения материальных ресурсов в графовых системах заданной структуры [Текст] / К.И. Дикарев // Промышленные АСУ и контроллеры. - М.: Изд-во «НАУЧТЕХЛИТИЗДАТ», 2012 -№ 9- С.14-18.

5. Дикарев, К.И. Оптимизация режимов функционирования систем водяного отопления. [Текст] / К.И. Дикарев, C.B. Фотин, Н.В. Фотина // Альтернативная энергетика и экология. - Саров: НТЦ «TATA», 2013. - № 6(1). -С. 30-36.

Свидетельства о государственной регистрации программ

6. Свидетельство о государственной регистрации программы для ЭВМ № 2010614637. Программное обеспечение «Нагнетатель» (ПО «Нагнетатель») [Текст] / М.Х. Прилуцкий, Н.В. Старостин, Л.Г. Афраймович, A.B. Филимонов, C.B. Фотин, К.И. Дикарев. - зарегистрировано 14.07.10. - Федеральная служба по интеллектуальной собственности, патентам и товарным знакам РФ. Реестр программ для ЭВМ.

7. Свидетельство о государственной регистрации программы для ЭВМ № 2010614640. Программное обеспечение «Заказ-О» (ПО «Заказ-О») [Текст] / М.Х. Прилуцкий, Н.В. Старостин, Л.Г. Афраймович, A.B. Филимонов, C.B. Фотин, К.И. Дикарев. - зарегистрировано 14.07.10. - Федеральная служба по интеллектуальной собственности, патентам и товарным знакам РФ. Реестр программ для ЭВМ.

8. Свидетельство о государственной регистрации программы для ЭВМ № 2011614445. Программное обеспечение «Проектировщик-1» (ПО «Проектировщик-1») [Текст] / М.Х. Прилуцкий, Н.В. Старостин, Л.Г. Афраймович, A.B. Филимонов, C.B. Фотин, К.И. Дикарев. - зарегистрировано 06.06.11. - Федеральная служба по интеллектуальной собственности, патентам и товарным знакам РФ. Реестр программ для ЭВМ.

9. Свидетельство о государственной регистрации программы для ЭВМ № 2012614244. Программное обеспечение «Проектировщик-2» (ПО

«Проектировщик-2») [Текст] / М.Х. Прилуцкий, Н.В. Старостин, Л.Г. Афраймович, A.B. Филимонов, К.И. Дикарев. - зарегистрировано 12.05.12. -Федеральная служба по интеллектуальной собственности, патентам и товарным знакам РФ. Реестр программ для ЭВМ.

Публикации в прочих изданиях

10. Дикарев, К.И. Опыт моделирования работы аппаратов воздушного охлаждения на компрессорных станциях в рамках разработки программного обеспечения «Нагнетатель» для оптимизации стационарных режимов транспорта природного газа [Текст] / К.И. Дикарев, C.B. Фотин, С.Ф. Перетрухин // X сессия отраслевой молодежной школы-семинара «Промышленная безопасность и экология». Сборник тезисов докладов, ФГУП «РФЯЦ-ВНИИЭФ». - Саров: ФГУП «РФЯЦ-ВНИИЭФ», 2010. - С.6.

11. Прилуцкий, М.Х. Математическая модель для оптимизации режимов участков газотранспортных сетей. [Текст] / М.Х.Прилуцкий, К.И. Дикарев // Сборник трудов XIV Всероссийской научно-технической конференции «Новые информационные технологии». — М.: Издательство МГУПИ, 2011. - С. 101-104.

12. Прилуцкий, М.Х. Оптимизационная модель согласования параметров для сетевых иерархических систем [Текст] / М.Х.Прилуцкий, К.И. Дикарев // Информационные системы и технологии ИСТ-2011. Материалы XVII Международной научно-технической конференции. - Н.Новгород: Изд-во НГТУ им. Р.И. Алексеева, 2011. - С.345-346.

13. Дикарев, К.И. Распределение ресурсов в иерархических системах с пассивными элементами [Текст] / К.И. Дикарев // КОГРАФ-2012. Материалы XXII Всероссийской научно-практической конференции по графическим информационным технологиям и системам. — Н.Новгород: Изд-во НГТУ им. Р.И. Алексеева, 2012. - С. 14-18.

14. Расчет оптимизационных режимов для участков газотранспортной системы с использованием параллельной вычислительной среды [Текст] / Л.Г. Афраймович, К.И. Дикарев, A.A. Макаров, Г.И. Наместников, Д.В. Парфенов, С.Ф. М.Х. Перетрухин, Прилуцкий, Н.В. Старостин, A.B. Филимонов // Супервычисления и математическое моделирование. Труды XIV Международной конференции»/ под ред. P.M. Шагалиева. - Саров: ФГУП «РФЯЦ-ВНИИЭФ», 2013. - С. 44-49.

15. Программные средства для определения оптимальных режимов газотранспортной системы на стадии ее проектирования или модернизации с применением технологий многопоточного программирования [Текст] / Л.Г. Афраймович, К.И. Дикарев, A.A. Макаров, Г.И. Наместников, Д.В. Парфенов, С.Ф. Перетрухин, М.Х. Прилуцкий, Н.В. Старостин, A.B. Филимонов // Сборник «Высокопроизводительные параллельные вычисления на кластерных системах. Материалы XII Всероссийской конференции» / под ред. проф. В.П. Гергеля. - Н. Новгород: Изд-во Нижегородского госуниверситета, 2012. - С. 8-11.

16. Прилуцкий, М.Х. Распределение ресурсов в многоуровневых иерархических системах с активными элементами [Электронный ресурс] / М.Х. Прилуцкий, К.И. Дикарев // Электронный журнал «Исследовано в России». -2012. - № 028. - С.377-402.

Режим доступа: http://zhumal.ape.relam.rn/articles/2012/028.pdf

17. Дикарев, К.И. Верификация математической модели распределения материального ресурса в иерархической газотранспортной системе с пассивными элементами [Текст] / К.И. Дикарев // КОГРАФ-2013. Материалы XXIII Всероссийской научно-практической конференции по графическим информационным технологиям и системам. - Н.Новгород: Изд-во НГТУ им. Р.И. Алексеева, 2013. - С.141-145.

18. Дикарев, К.И. Оптимизация режимов функционирования систем водяного отопления [Текст] / К.И. Дикарев // Информационные системы и технологии ИСТ-2013. Материалы XIX Международной научно-технической конференции. - Н.Новгород: Изд-во НГТУ им. Р.И. Алексеева, 2013. - С.323-324.

19. Prilutskii, M. Resource allocation within the controlled hierarchical systems [Текст] / M. Prilutskii, К. Dikarev // Proceedings of the International Conference «Numerical Computations: Theory and Algorithms» (Falema (CZ), Italy) 17 - 23 June 2013. - Cosenza: Luigi Pellegrini Editore, 2013. - C.l 15.

20. Дикарев, К.И. Задача поиска оптимальных режимов работы насосной станции [Текст] / К.И. Дикарев // Информационные системы и технологии ИСТ-2014. Материалы XX Международной научно-технической конференции. -Н.Новгород: Изд-во НГТУ им. Р.И. Алексеева, 2014. - С.303-304.

Подписано в печать 15.09.2014. Формат 60х84'/1б. Бумага офсетная. Печать офсетная. Уч.-изд. л. 1,0. Тираж 100 экз. Заказ 589.

Нижегородский государственный технический университет им. P.E. Алексеева. Типография НГТУ. 603950, Нижний Новгород, ул. Минина, 24.