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

Куликов Михаил Сергеевич

Модели и методы распределительного типа при планировании и оперативном управлении производственными системами

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

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

5 <1£3 2015

005558556

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

005558556

Работа выполнена на кафедре информатики и автоматизации научных исследований ФГАОУ ВО «Нижегородский государственный университет им. Н.И.Лобачевского».

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

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

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

доктор технических наук, профессор Прилуцкий Михаил Хаимович

Коган Дмитрий Израилевич, доктор технических наук, профессор. Московский государственный

университет приборостроения и информатики. Профессор кафедры прикладной математики института высоких технологий.

Цветков Александр Игоревич,

кандидат технических наук, научный

сотрудник.

Федеральное государственное

бюджетное учреждение науки Институт прикладной физики Российской академии наук. Научный сотрудник.

«Российский федеральный ядерный центр - Всероссийский научно-исследовательский институт

экспериментальной физики», г. Саров.

Зашита диссертации состоится «05» марта 2015 года в 11:00 часов в ауд. 1258 на заседании диссертационного совета Д 212.165.05 при Нижегородском государственном техническом университете им. P.E. Алексеева по адресу: 603950, г. Нижний Новгород, ул. Минина, 24.

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

Автореферат разослан «26 » О/ 2015 года.

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

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

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

Актуальность темы. В настоящее время на производстве все больше внимания уделяется вопросам эффективного управления и планирования. Задачи планирования и оперативного управления возникают во многих областях человеческой деятельности, где необходима эффективная организация производственных процессов. Эти задачи могут быть сформулированы следующим образом: с помощью некоторого множества ресурсов необходимо построить расписание выполнения заданного комплекса взаимозависимых работ (сложное изделие), чтобы оптимизировать выбранную меру эффективности. При использовании одноуровневых математических моделей, для их реализации, принимая во внимание высокие требования к результатам решаемых задач, необходимо учитывать большой объем исходных данных. Это приводит к тому, что задачи математического программирования, реализующие задачи управления, обладают большой математической сложностью, что делает их решение затруднительным даже с использованием высокопроизводительных вычислительных средств. Существующие подходы системного анализа дают возможность представления моделей производственных объектов в виде иерархических многоуровневых систем, что позволяет упрощать их структурный состав и разделять вычислительные операции между различными вычислительными средствами.

Можно отметить следующих ученых, внесших большой вклад в развитие научной области, связанной с вопросами эффективного управления и планирования: Бурдюк В.Я., Бурков В.Н., Гордон B.C., Ковалев М.Я., Лазарев A.A., Мироносецкий Н.Б., Михалевич B.C., Подчасова Т.П., Севастьянов C.B., Сервах В.В., Сотсков Ю.Н., Танаев B.C., Шкурба В.В., Шор Н.З., Baptiste P., Blazewicz J., Brucker P., Giffler В., Graham К., Johnson S., Conway R., LawlerE.L., Maxwell W., Thompson G., Werne F. и многие другие. Следует отметить школу нижегородского университета и ученых Батшцева Д.И., Когана Д.И., Костюкова В.Е., Прилуцкого М.Х., Федосенко Ю.С., которые рассматривали подобные проблемы.

Большинство задач планирования и оперативного управления являются NP-трудными, что определяет необходимость использования для решения этих

задач различных эвристических алгоритмов и специального программного обеспечения. В настоящее время существует много эвристических алгоритмов и реализующих их программного обеспечения. К такому программному обеспечению можно отнести такие известные продукты как: Microsoft Project, Project Libre, PRIMAVERA, продукты 1С и др.

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

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

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

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

— проведены исследования построенной модели;

— разработаны методы решения задач, описываемых рассматриваемой моделью;

— создана диалоговая система, которая используется в практике планирования и оперативного управления на ряде предприятий.

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

— методы системного анализа;

— методы решения задач сетевого планирования и управления;

— методы решения задач линейного и квадратичного программирования.

Научная новизна.

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

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

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

4. Предложен фронтальный алгоритм с рангами для решения задач оперативного управления.

Практическая значимость и внедрение. Практическая ценность диссертациошгой работы состоит в разработке и реализации диалоговой программной системы решения задач распределения ресурсов в иерархических системах, которая используется для ситуационного анализа, планирования и оперативного управления процессом изготовления интегральных схем с микронными и субмикронными проектными нормами в ФГУП «ФНПЦ НИИИС им. Ю.Е.Седакова». С помощью диалоговой системы решены задачи планирования и оперативного управления процессом изготовления изделий машиностроения для опытного производства в ФГУП «ФНПЦ ОКБМ им. И.И. Африкантова».

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

Публикация результатов. По теме диссертации опубликованы 13 печатных работ, в том числе 4 статьи в журналах, рекомендованных ВАК РФ

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

Апробация полученных результатов. Основные результаты диссертационной работы докладывались на:

— XV международной научно-технической конференции «Информационные системы и технологии ИСТ-2009» в НГТУ им. P.E. Алексеева в 2009 году;

— конференции «Технологии Microsoft в теории и практике программирования» в ННГУ им Н.И. Лобачевского в 2009 году;

— всероссийской научно-технической конференции «новые информационные технологии» в МГУПИ в 2010 году;

— IV научно-технической конференции молодых специалистов Росатома. Высокие технологии атомной отрасли. Молодежь в инновационном процессе. В 2009 году;

— конференции «Технологии Microsoft в теории и практике программирования» в ННГУ им Н.И. Лобачевского в 2010 году;

— XVI международной научно-технической конференции «Информационные системы и технологии ИСТ-2010» в НГТУ им. P.E. Алексеева в 2010 году;

— семинаре «Суперкомпьютерные технологии решения болыперазмерных труднорешаемых задач» в СарФТИ в 2014 году;

— XII Всероссийском совещании по проблемам управления Россия, Москва, ИПУ РАН, в 2014 г.;

— научных семинарах кафедры информатики и автоматизации научных исследований факультета ВМК ННГУ (2009 - 2014 г.).

Личный вклад автора. Личный вклад автора заключается в следующем:

— участие в постановке целей и задач исследования;

— построение математической модели и постановка оптимизационных задач;

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

— реализация алгоритмов решения в виде программных модулей, используемых во внедренном программном обеспечении;

— участие во внедрешш созданного программного обеспечения.

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

— общая математическая модель распределения ресурсов в иерархических системах, в рамках которой ставятся многокритериальные задачи объемно-календарного планирования и задачи календарного планирования и оперативного управления;

— точные и приближенные методы решения оптимизационных многокритериальных задач объемно-календарного планирования и задач календарного планирования и оперативного управления производственными системами;

— программные средства решения задач распределения ресурсов производственных систем.

Структура п объем работы. Диссертационная работа состоит из введения, четырех глав, заключения и списка использованной литературы из 121 наименования, а также приложения. Объем основного текста диссертации составляет 127 страниц машинописного текста, общий объем работы составляет 144 страницы.

КРАТКОЕ СОДЕРЖАНИЕ РАБОТЫ

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

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

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

В разделе 1.2 дается обзор известных методов нахождения решения задач совместности систем линейных уравнений (метод исключений Фурье-Моцкина, теорема Черникова и теорема Александрова-Фань-Цзи), методов решения задач квадратичного программирования (с ограничениями типа равенств, задач сепарабельного квадратичного программирования, метод направленного перебора для выпуклой задачи квадратичного программирования, симплекс метод, методы отсечений, алгоритмы внутренних точек и др.), методов решения задач календарного планирования (метод критического пути, оценки и пересмотра программ, анализа и графической оценки и др.). Приведены методы «Муравьиные колонии», «Генетический алгоритм», «Алгоритм имитации отжига» для задачи построения расписания для проекта.

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

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

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

1.1.1. Задача предварительного планирования на квартал объемов производства интегральных схем по подразделениям на различных уровнях административной иерархии;

1.1.2. Задача оперативного управления и календарного планирования выполнения работ по подразделениям в соответствии с квартальным планом по изготовлению партий пластин;

1.2. Задача распределения производительности купола по газовым скважинам:

1.2.1. Задача формирования диспетчерских заданий;

1.2.2. Задача оперативного управления и календарного планирования выполнения работ по поддержанию режимов работы и наладке оборудования;

1.3. Задача планирования и оперативного управления процессом изготовления изделий машиностроения:

1.3.1. Задача предварительного планирования объемов производства изделий машиностроения, их компонент и запасных частей;

1.3.2. Задача оперативного управления и календарного планирования выполнения работ по изготовлению комплектов компонент изделий.

В разделе 2.2 приведены примеры задач распределительного типа.

Приведено описание задач ситуационного анализа, планирования и

оперативного управления процессом изготовления интегральных схем с

микронными и субмикронными проектными нормами (задача 1.1), задачи

распределения производительности купола по газовым скважинам (задача 1.2), а

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

изготовления изделий машиностроения (задача 1.3).

В разделе 2.3 дается содержательное описание многокритериальных задач

распределения ресурсов в иерархических системах. Задача распределения

ресурсов в иерархических системах сводится к последовательному решению

задачи объемно-календарного планирования (предварительного планирования)

и задачи календарного планирования и оперативного управления.

Задача предварительного планирования заключается в планировании

объемов производства на определенный период. Имеется набор возможных

работ верхнего уровня, которые могут быть выполнены. При этом на

выполнение работ требуется затратить определенное количество ресурсов.

Ограничения на ресурсы являются линейными ограничениями транспортного

типа. Требуется определить на заданный период планирования набор

выполняемых работ, обеспечивающий эффективное функционирование

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

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

Решение задачи предварительного планирования оггределяет сетевую структуру,

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

календарного планирования.

Задача календарного планирования заключается в составлении

календарного плана выполнения определешгого набора работ, взаимосвязь

9

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

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

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

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

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

К организационным ограничениям относятся:

— директивные сроки работ и операций — сроки, до которых необходимо выполнить данную работу;

— межоперационное время (максимальное время пролеживания) — максимальное время которое может пройти между операциями.

Все оборудование производственной системы разбивается на группы:

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

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

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

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

- кластерное оборудование: оборудование, представляющего собой совокупность из нескольких «камер». Каждая «камера» представляет собой отдельную единицу оборудования и может работать независимо от остальных «камер». Если кластерное оборудование находится в нерабочем состоянии, то все камеры кластерного оборудования находятся в нерабочем состоянии;

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

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

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

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

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

«Мягкими» технологическими условиями можно считать: сохранение директивных сроков, межоперационное время не должно нарушаться и т.д.

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

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

b<Aq<c,qeR", (1)

где А — матрица размерности /их п с коэффициентами из множества {0,1,-1}, h и с произвольные m -мерные векторы с рациональными компонентами,

<? - и-мерный вектор, компоненты которого являются показателями объемов производства на планируемый период по каждой из п возможных работ.

Объемы производства на планируемый период, заданный множеством тактов планирования Г = {0,1,2,...,Г0}, по каждому виду возможных работ

Ц определяют состав работ верхнего уровня Ог(д) = /<",, где Ип = {Л,, /<',,...,/<',, },

для задачи календарного планирования. Для выполнения работ верхнего уровня может понадобиться выполнение определенного набора работ первого уровня = \,Ии, которые в свою очередь также могут состоять из работ и т.д. Обозначим через = {\,2,...ЫМ,}~ набор всех технологических операций (работы нижнего уровня), а через / к) Я № - множество

технологических операций, обеспечивающих выполнение работы Ri j к. Для

операций определены порядки их выполнения. Множество всех операций, непосредственно предшествующих операции с номером обозначим через К( нО, м' е Ш. Таким образом, определяется иерархия и взаимосвязь работ, задаваемая сетевой структурой.

Пусть IV0 множество технологических операций для которых определены директивные сроки выполнения Ц,; IV'"'" - множество операций, для которых определено минимальное время пролеживания; - минимальное время пролеживания тс-й операции, № е 1Утпт; IVП1ах - множество операций, для которых определено межоперационное время; /™ах - межоперационное время (максимальное время пролеживания) 1г-й операции, и1 е 1Утах; I ={0,1,...,М} — множество, которое включает в себя все оборудование, на котором выполняются технологические операции.

Обозначим через (рЫ) = {/'[,/,...} — множество видов оборудования, на котором может выполняться операция и', и' е IV, ц, ¡2... е /.

Для каждого оборудования определенно множество лО) ~ {['/.гП,[г2'г2] -■■}'' е 1промежутков времени, в которые оборудова1ше может осуществлять выполнение операций:

Пусть Н- множество единиц оборудования, для которых необходимо производить операцию «разогрева», г,, - максимально возможное время простоя, после которого необходим «разогрев» оборудования, ик - время разогрева оборудования А, Л е Н ,Н с. 1.

Обозначим через /1И. — время выполнения IV -й операции на / -м оборудовании, ; е I, м' е IV.

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

В качестве варьируемых параметров математической модели выступают: и-мерный вектор q, компоненты которого являются показателями объемов производства на планируемый период по каждому виду возможных работ, мерные целочисленные векторы х и у, компоненты которых определяют такты начала и окончания выполнения операций, а так же матрица ^ = ||г51| ^ , ^, элемент которой = 1, если операция ] выполняется на оборудовании и гу = 0 в противном случае ; е I, ] е IV.

Ограничения математической модели, обозначенные как (2), включают:

Естественные ограничения на переменные:

хн. е Т,ук е Т, е {0,1}, н> е IV,; е / .

Каждая операция должна выполняться на возможном для нее оборудовании: = 1, = 0, 1Г 6 Ж, / е I.

/с/

Взаимозависимость операций, определяющая каноничность сетевой модели: А"(н')> 1г е IV

Условия вьнголнения операций на оборудовании без перерывов:

У и, - хи' = .1,1 е IV, г е (¡?0), гы. Ф 0

Условия выполнения операций на оборудовании, требующем разогрев:

хк ^ + у*> есш хь-У) 2,,к =гЪ] =1,

Условия, определяющие невозможность одновременного выполнения на одном и том же оборудовании разных операций: > хк + 11к или хк > х№ + для всех тех к\к,1, для которых ф 0, 21к * 0, г е 1,м',ке IV

Условия, определяющие необходимость выполнения операции в допустимое время для оборудования: хК,ум, е 77 (/'),/' е <р(н'), и' е IV

Ограничения для операций с минимальными сроками пролеживания: > уъ + 6 (К(Л о £ ТГ

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

В разделе 2.5 ставятся оптимизационные задачи.

Выбор показателей объемов производства на планируемый период по каждому виду возможных работ определяется исходя из следующей

5-критериальной задачи: = |> где ' = й\

6(0£{1,2,...,и},/' = удовлетворяет ограничениям (1). Поставленная задача соответствует задачам 1.1.1, 1.2.1 и 1.3.1.

В случае если на множестве частных критериев 5-критериальной задачи можно установить полный порядок - ставится задача нахождения

лексикографически оптимального решения. Предполагая (не уменьшая общности), что урм,1 = 1,5-1, лексикографически оптимальным решением многокритериальной задачи назовем такое допустимое решение

Ч = О?, , что не существует допустимого решения г/ и натурального к,

к = 2,5, таких, что Ц(д') < ^(д"), или = = 1,£-1,

Задачи, соответствующие случаю упорядоченности частных критериев

обозначим как задача 1.1.1.а, задача 1.2.1.а и задача 1.3.1 .а соответственно.

15

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

приближенным решением такое допустимое решение задачи q*, что

Г1 (д*) < е, / = 1, х. Здесь е > 0 - заданный управляемый параметр.

Назовем неулучшаемым е-приближенным решением такое е-приближенное решение q*, что не существует такого с',с'< с и с/'е К", что система

Ъ < Ас]'< с,д'е Д" г— ^ /—г — будет совместна. Неулучшаемое

/ееп)

ограничении ■

е-приближенное решение будет соответствовать решению исходной задачи согласно принципу гарантированного результата: minmax] -й, f. В

«* "и [Ь^о ) \

случае равноправности частных критериев обозначим полученные задачи как задача 1.1.1.6, задача 1.2.1.6 и задача 1.3.1.6 соответственно.

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

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

управления (задачи 1.1.2, 1.2.2, 1.3.2) с критерием, полученным аддитивной сверткой частных критериев оптимальности и ограничениями (2).

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

сведения к поставленной задаче известной задачи о ранце показана № - трудность задачи планирования и управления.

В главе 3 рассматриваются различные алгоритмы решения оптимизационных задач, поставленных в главе 2. Вводится алгоритм поиска лексикографически оптимального решения задачи объемно-календарного планирования путем рассмотрения вершин Б-мерного /?+/-ичного куба. Строится фронтальный алгоритм с рангами для решения задачи календарного планирования и оперативного управления.

В разделе 3.1 рассматривается релаксационный метод Агмона-Моцкина решения задачи проверки совместности системы линейных неравенств.

В разделе 3.2 рассматривается метод центрального пути решения задач линейного и квадратичного программирования.

В разделе 3.3 строится точный алгоритм нахождения решения задачи объемно-календарного планирования, в случае, если А является единичной матрицей размерности их и, ^ = и + 1 и £(/) = {'},' = Кп, <2(п + 1) = {1,2...и} и доказывается оптимальность найденного решения. Алгоритм имеет вычислительную сложность О(п').

В разделе 3.4 строится алгоритм нахождения неулучшаемого Е-приближенного решения задачи объемно-календарного

планирования (задачи 1.1.1.6, 1.2.1.6, 1.3.1.6), основанный на сведении исходной задачи к решению задачи линейного программирования.

В разделе 3.5 строится алгоритм нахождения лексикографически оптимального решения задачи объемно-календарного

планирования (задачи 1.1.1.а, 1.2.1.а, 1.3.1.а) путем бинарного поиска по вершинам Б-мерного/?+7-ичного куба.

Для каждого критерия = 1,5, вводятся совокупности из р +1

вложенных друг в друга сегментов Б", г = 0, р, таких, что а< е 8], / = , т = 07р: Я* £ 1, / = 1, л, V = 0, р -1. В качестве критериев оптимальности

рассматриваются кусочно-постоянные функции х,

принимающие значение /, если е 5/, но ^Я, & ^Т', ' е р},/ = 1,5

)

Рассматривается 5-мерный р+7-ичный куб, на котором определен порядок. Каждой вершине куба V ставится в соответствие система с(к), содержащая не зависящие от вершины куба ограничения задачи, и ограничения, зависящие от координат вершины следующим образом: если К = /, то (.'(г7) будет содержать

ограничения задачи и ограничение ^ qj е Я,'. На множестве вершин куба

^есо

задается двузначная монотонная функция пршшмающая значите 1, если

соответствующая вершине V система с(к) совместна, и 0 в противном случае. Оптимальная вершина куба находится путем применения бинарного поиска. Оптимальной вершине куба V соответствует система линейных алгебраических двусторонних неравенств транспортного типа С(К'). Любое решение этой системы с точки зрения введенного компромисса будет равноправно. Учитывая это, находится такое допустимое решение системы

С(Уа), для которого принимают экстремальные значения частные критерии оптимальности исходной задачи, что можно осуществить, решив 2х задач линейного программирования с ограничениями транспортного типа.

В разделе 3.6 рассматривается пошаговый алгоритм построения расписания выполнения операций задачи календарного планирования и оперативного управления (задачи 1.1.2, 1.2.2, 1.3.2).

В разделе 3.7 рассматривается алгоритм, основанный на вычислительных процедурах метода ветвей и границ задачи календарного планирования и оперативного управления (задачи 1.1.2, 1.2.2, 1.3.2).

В разделе 3.8 рассматриваются фронтальные алгоритмы решения задачи календарного планирования и оперативного

управлешы (задачи 1.1.2, 1.2.2, 1.3.2). Строится фронтальный алгоритм с рангами, позволяющий лучше учесть специфические особенности.

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

является суммарный штраф, налагаемый за нарушение «мягких» технологических условий. В алгоритме, можно выделить две основные фазы:

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

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

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

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

Благодаря использованию фронтального алгоритма для построения расписания на каждой фазе фронтального алгоритма с рангами всегда гарантируется допустимость построенного решения с точки зрения «жестких» технологических условий.

В главе 4 рассматриваются созданные диалоговые программные средства и приводятся результаты их работы.

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

В разделе 4.2 рассматривается типовой сценарий решения задачи распределения ресурсов в иерархических системах.

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

В Таблицах 1, 2, 3, 4 приведены результаты решения задач построения расписаний выполнения операций при оперативном управлении производством интегральных схем с субмикронными топологическими нормами (ФГУП «ФНПЦ НИИИС им. Ю.Е. Седакова» (г. Н. Новгород)).

Таблица 1. Исходные даппые

ЧЙ;.!-' :: операций, е;;.. : Чи.ЛО : .:; Чи-чо : операций: .; проверки по'.1 ТОЧВОИИ^ед;;;; ^ Чиг:к> сдими-Е : СД : : Чис™ Шодараций: ё:;; Д^МИ.'-Н'.'МИ :: :: СроИа:^{Й|,: ¿Д '; \ie.i «|!1-{|апи.'ВК'гм : рреченеч. £.1

Задача 1 1376 1178 198 68 1376 222

Задача 2 4022 3824 198 68 4022 1224

Задача 3 13724 13526 198 68 13724 4898

Задача 4 30482 30284 198 68 30482 11244

Задача 5 51648 51452 196 68 51648 19260

Таблица 2. Результаты решения задач каноническим фронтальным алгоритмом

'^ решений::::; : Чие ы инсрл;кй. ;п«кйторьгх:; : ДНрсК ШИНЫС М : ?': ■ Чнся6:йдер4цкй о нарушаннами;:: врсмей,: СД::: ! Ш^ммарное зизче!ч 1 ¡:

Задача 1 00:00:00 03 2 14 2167870

Задача 2 00:00:00.05 8 233 39480390

Задача 3 00:00 0027 18 1198 1027186720

Задача 4 00:00:00.77 7388 5542 3429178522

Задача 5 00:00:01.67 28463 6737 17857778620

Таблица 3. Результаты решении задач фроптальпым алгоритмом с рапгамп

■ВрСМ! решен!« ЧаЛа1!». Ч : Число операций, ДЛЯ которых:: ндр>ан.¡и дкр^гкыше > ерокн, с-1 : ЧИСЛО ОйфйЦИЙ V Г.<|>) Ш'.НИИМ И ЩыетаверацйЬвйшг :. Суммарное значенийV : Ш:; оЙйбнкнвого критерии

Задача 1 00:00:00.59 1 12 1962420

Задача 2 00:00:07.96 4 62 9968070

Задач а 3 00:00:27.62 89 436 121047866

Задача 4 00:30:56.80 7186 1277 3187927590

Задача 5 03:24:52.64 28467 3611 17668170899

Таблица 4. Ацализ полученных решений

-Задача :: : Прйиект улучнь-ггня значена у ::: : .ЛНЧГК'Ш.ЧО КрИКрИЯ. % Процент у ^гш^ння даачЩЩ:;: : критерия лоднректйвньм срокам; Процент )[умшс7шя Ь^марн^га;воказа ге'ад::: .11 Ш'ГрафоВ1:1 нарушения М;.*«1>иср.1!;ИИ»!;ЫЧ ■; ; ¡феМСТ^

Задача 1 95 0 9.5

Задача 2 74.6 70.8 74.8

Задача 3 88.2 -511 88.7

Задача 4 7 -4.9 85.7

Задача 5 I -1 64,2

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

В заключении сформулированы основные результаты работы и приводятся примеры реального использования созданных алгоритмов и ПО.

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

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

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

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

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

- задача распределения производительности купола по газовым скважинам.

2. Проведена формализация критериев оптимальности для указанных задач (случай лексикографической упорядоченности критериев, случай равнозначности критериев).

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

21

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

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

ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ

Статьи в рецензируемых изданиях, рекомендованных ВАК РФ:

1. Прилуцкий, М.Х. Об одном классе многокритериальных задач квадратичного программирования транспортного типа [Текст] / М.Х. Прилуцкий, Л.Г. Афраймович, М.С. Куликов // Вестник Нижегородского университета им. Н.И. Лобачевского - Н.Новгород: Изд-во ННГУ Им. Н.И. Лобачевского, 2009. - №6. - С. 178-183.

2. Прилуцкий, М.Х. Многокритериальные задачи квадратичного программирования с ограничениями транспортного типа [Текст] / М.Х. Прилуцкий, М.С. Куликов // Системы Управления и Информационные Технологии. Научно-технический журнал. - Воронеж: Научная книга, 2010. -№3(41).-С. 17-21.

3. Куликов, М.С. Ранговый итерационный алгоритм решения задачи распределения ресурсов в сетевых системах [Текст] / М.С. Куликов // Системы Управления и Информационные Технологии. Научно-технический журнал. -Воронеж: Научная книга, 2011. - №4(46). - С.37-43.

4. Задачи планирования и оперативного управления процессом изготовления интегральных схем с микротшыми и субмикронными топологическими нормами [Текст] / Л.Г. Афраймович, B.C. Власов, М.С. Куликов, М.Х. Прилуцкий, Д.В. Седаков, Н.В. Старостин, A.B. Филимонов // Автоматизация в промышленности. Ежемесячный научно-технический и производственный журнал. - Москва: ООО Издательский дом «ИнфоАвтоматизация», 2014. -№8. — С. 17-21.

Публикации в других научных изданиях:

5. Прилуцкий, М.Х. Решение одной многокритериальной задачи с квадратичными критериями [Текст] / М.Х. Прилуцкий, Л.Г. Афраймович, М.С. Куликов // Информационные системы и технологии ИСТ-2009. Материалы XV международной научно-технической конференции. -Н.Новгород: Изд-во НГТУ Им. P.E. Алексеева, 2009. - С.297-298.

6. Прилуцкий, М.Х. Распределение производительности купола по газовым скважинам [Текст] / М.Х. Прилуцкий, Л.Г. Афраймович, М.С. Куликов // Технологии Microsoft в теории и практике программирования. Материалы конференции под ред. проф. В.П. Гергеля. - Н.Новгород: Изд-во Нижегородского госуниверситета, 2009. - С.350-352.

7. Куликов, М.С. Специальная задача квадратичного программирования при распределении производительности купола по газовым скважинам [Текст] / М.С. Куликов, М.Х. Прилуцкий // Труды Нижегородского государственного технического университета им. P.E. Алексеева. Системы обработки информации и управления - Н.Новгород: Изд-во НГТУ Им. P.E. Алексеева, 2009. - Том 76. -С.23-26.

8. Прилуцкий, М.Х. Об одной специальной задаче квадратичного программирования [Текст] / М.Х. Прилуцкий, М.С. Куликов // Труды Нижегородского государственного технического университета им. P.E. Алексеева - Н.Новгород: Изд-во НГТУ Им. P.E. Алексеева, 2010. -№1(80).-С.70-75.

9. Куликов, М.С. Лексикографическая схема решения многокритериальной задачи распределения производительности купола по газовым скважинам [Текст] / М.С. Куликов, М.Х. Прилуцкий // Сборник трудов 13 всероссийской научно-технической конференции. Новые информационные технологии. - Москва: МГУПИ, 2010. - С.92-95.

10. Куликов, М.С. Схема лексикографичес кого компромисса для многокритериальной задачи распределения производительности купола по газовым скважинам [Текст] / М.С. Куликов // Технологии Microsoft в теории и практике программирования. Материалы конференции под ред. проф.

B.П. Гергеля. - Н.Новгород: Изд-во Нижегородского госуниверситета, 2010. -

C.244-246.

11. Куликов, М.С. Лексикографическая схема решения многокритериальных задач квадратичного программирования с ограничениями транспортного типа [Текст] / М.С. Куликов // Информационные системы и технологии ИСТ-2010. Материалы XVI международной научно-технической конференции. - Н.Новгород: Изд-во НГТУ Им. P.E. Алексеева, 2010. -С.334-335.

12. Куликов, М.С. Применение лексикографических схем решения многокритериальных задач в задаче распределения производительности купола по газовым скважинам [Текст] / М.С. Куликов // Материалы IV научно-технической конференции молодых специалистов Росатома. Высокие технологии атомной отрасли. Молодежь в инновационном процессе, (принята в печать).

13. Планирование и оперативное управление процессом изготовления сложных изделий [Текст] / Л.Г. Афраймович, B.C. Власов, М.С. Куликов, М.Х. Прилуцкий, Н.В. Старостин, A.B. Филимонов // Труды XII всероссийского совещания по проблемам управления ВСПУ-2014. 2014г.: ТРУДЫ. - Москва: Институт проблем управления им. В. А. Трапезникова РАН, 2014. -С.5138-5149.