Модели и методы распределительного типа при планировании и оперативном управлении производственными системами тема диссертации и автореферата по ВАК РФ 05.13.01, кандидат наук Куликов, Михаил Сергеевич

• Куликов, Михаил Сергеевич
• кандидат наук
• 2014

Оглавление диссертации кандидат наук Куликов, Михаил Сергеевич

Содержание

Содержание

Аннотация

Введение

ГЛАВА 1. Задачи распределения ресурсов в иерархических системах (планирование и оперативное управление)

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

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

1.2.1. Методы решения задач совместности системы линейных неравенств

1.2.2. Методы решения задач квадратичного программирования

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

ГЛАВА 2. Общая математическая модель многокритериального распределения ресурсов и постановки оптимизационных задач

2.1. Иерархия рассматриваемых задач

2.2. Содержательное описание проблемы распределения ресурсов при планировании и оперативном управлении производственными системами

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

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

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

2.3. Общее описание проблемы распределения ресурсов при планировании и оперативном управлении производственными системами

2.3.1. Задача предварительного планирования распределения ресурсов

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

2.4. Построение и исследование общей математической модели распределения ресурсов в иерархических системах

2.4.1. Математическая модель

2.4.2. Пример математического описания задачи распределения ресурсов в радиоэлектронном производстве

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

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

2.5.2. Постановка задачи построения лексикографически оптимального решения

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

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

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

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

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

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

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

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

3.3. Решение задачи объемно-календарного планирования с единичной матрицей ограничений

3.4. Нахождение е-приближенного решения задачи объемно-календарного планирования

3.4.1. Нахождение е-приближенного решения

3.4.2. Пример нахождения е-приближенного решения задачи объемно календарного планирования

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

3.5.1. Лексикографическая схема компромисса

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

3.6. Пошаговый алгоритм построения расписания выполнения операций задачи оперативного управления

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

3.7.1. Основные вычислительные процедуры метода ветвей и границ

3.7.2. Процедура оценок

3.7.3. Процедура ветвления

3.8. Фронтальные алгоритмы решения задач оперативного управления

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

3.8.2. Классический фронтальный алгоритм

3.8.3. Фронтальный алгоритм с рангами

3.8.4. Пример работы фронтального алгоритма с рангами

ГЛАВА 4. Диалоговые программные средства решения задач распределения ресурсов в иерархических системах

4.1. Описание диалоговых программных средств

4.1.1. Назначение и структура программного обеспечения

4.1.2. Основные модули

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

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

4.3.1. Использованные аппаратные средства

4.3.2. Обозначения

4.3.3. Результаты решения задач распределения ресурсов

Заключение

Список литературы

ПРИЛОЖЕНИЕ. Документы, подтверждающие внедрение результатов диссертационной работы

Аннотация

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

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

Введение диссертации (часть автореферата) на тему «Модели и методы распределительного типа при планировании и оперативном управлении производственными системами»

Введение

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

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

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

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

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

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

Большинство задач планирования и оперативного управления являются NP-трудными, что определяет необходимость использования для решения этих задач различных эвристических алгоритмов и специального программного обеспечения. В настоящее время существует много эвристических алгоритмов и реализующих их программного обеспечения. К такому программному обеспечению можно отнести такие известные продукты как: Microsoft Project, Project Libre, PRIMA VERA, продукты 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 дается общая постановка многокритериальных задач распределения ресурсов в иерархических системах. Задача распределения ресурсов в иерархических системах сводится к последовательному решению задачи объемно-календарного планирования (предварительного планирования) и задачи календарного планирования и оперативного управления.

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

В разделе 2.5 ставятся оптимизационные задачи. Выбор показателей объемов производства на планируемый период по каждому виду возможных работ определяется исходя из 5 -критериальной задачи. Поставленная задача соответствует задачам 1.1.1, 1.2.1 и 1.3.1. В случае если на множестве частных критериев 5 -критериальной задачи оптимальности можно установить полный порядок - ставится задача нахождения лексикографически оптимального решения. В случае если все критерии многокритериальной задачи имеют одинаковую значимость, рассматриваются е-приближенные решения.

Решение 5 -критериальной задачи определяет необходимый набор работ, которые требуется выполнить в планируемый период. Нарушение «жестких» технологических условий не допускается, что отражено в ограничениях математической модели. При нарушении «мягких» технологических условий на систему накладываются штрафные санкции, соответственно возникает множество частных критериев оптимальности связанных с минимизацией штрафов. В качестве критерия задачи оптимального планирования выступает обобщенный функционал, - аддитивная свертка частных критериев оптимальности, связанных с минимизацией штрафов накладываемых на систему. Таким образом, ставится задача календарного планирования и оперативного управления (задачи 1.1.2,1.2.2,1.2.3).

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

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

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

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

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

В разделе 3.3 строится точный алгоритм нахождения решения задач объемно-календарного планирования, с единичной матрицей ограничений и критериями специального вида Алгоритм имеет вычислительную сложность 0(п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.а) путем бинарного поиска по вершинам Б-мерного /?+/-ичного куба.

В разделе 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. Задачи распределения ресурсов в иерархических системах (планирование и оперативное управление)

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

математического программирования

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

Задачи календарного планирования изучаются в рамках теории расписаний и представляют собой задачи распределения ограниченного числа ресурсов во времени на выполнение определенного набора работ с максимизацией прибыли. Этим задачам в литературе уделялось и уделяется много внимания, можно отметить следующих ученых внесших большой вклад в развитие этой области: Бурдюк В.Я. [10], Бурков В.Н. [7, 11], Гимади Э.Х. [14, 15], Гордон B.C. [78], Ковалев М.Я. [23, 81], Лазарев A.A. [37, 38, 39, 40, 105], Мироносецкий Н.Б. [31, 42], Михалевич B.C. [43, 44], Подчасова Т.П. [50, 92], Севастьянов С.В.[15, 68, 69], СервахВ.В. [70, 71, 72, 73], Сотсков Ю.Н. [74, 82], Танаев B.C. [78, 79, 80, 81, 82], ШкурбаВ.В. [10, 50, 79, 92], Шор Н.З. [43], Baptiste Р. [97], BlazewiczJ. [99], Brucker Р. [100, 101], Graham К. [107], LawlerE.L. [107, 110], Muth J.F. [48], Werner F [105] и многие другие.

Следует отметить школу нижегородского университета и ученых Батищева Д.И. [8, 52], Когана Д.И. [24, 25, 26], Костюкова В.Е. [33, 57, 59], Прилуцкого М.Х. [3, 4, 5, 33, 35, 53, 54, 55, 56, 58, 59, 60, 61, 62, 63],

Федосенко Ю.С [24, 25, 26, 83, 84, 85], а также многих других [41, 88], работы которых также посвящены подобным проблемам.

Задача формирования портфеля заказов заключается в определении, какие заказы предприятие будет выполнять в планируемом периоде ([3,56,60]). Задача объемно-календарного планирования заключается в распределении производственной программы предприятия, найденной на этапе формирования портфеля заказов, по календарным подпериодам (месяцам) ([55]). Такие задачи рассматривают не в общей постановке с учетом всех зависимостей и связей, а с определенной степенью идеализации при этом вместо конкретных работ с их длительностями рассматриваются объемные показатели, связанные с совокупностями работ. Задачи формирования портфеля заказов и объемно-календарного планирования являются предметом исследований многих работ (см. например [53, 54, 55]).

Все эти задачи можно рассматривать не отдельно, а как последовательные стадии решения одной задачи распределения ресурсов. На первом этапе выбирается, какие обязательства по составу и объему работ могут быть приняты на себя предприятием (задачи формирования портфеля заказов и объемно-календарного планирования), а на втором этапе происходит конкретное распределение работ по датам и ресурсам. Так же на эти задачи можно взглянуть как на составные части задачи планирования на разных уровнях административной иерархии производства.

1.2. Математический аппарат, используемый при формализации

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

1.2.1. Методы решения задач совместности системы линейных неравенств

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

Ax<b, Ae Rmx",b e R*

(1.2.1.1)

В случае если коэффициенты системы (1.2.1.1) являются целочисленными и требуется проверить, существует ли целочисленное решение этой системы, задача проверки совместности системы (1.2.1.1) принадлежит классу NP [77]. Если не требовать целочисленности решений (1.2.1.1), то проверить совместность системы линейных неравенств можно за полиномиальное время.

Задачи проверки совместности системы линейных неравенств тесно связаны с задачами линейного программирования (ЛП) и методами их решения. Наиболее известным и широко применяемым на практике для решения общей задачи ЛП является симплекс-метод [87] аналогичный, описанному в п. 1.2.2.6 Несмотря на то, что симплекс-метод широко используется для решения прикладных задач, показано, что его сложность экспоненциальна.

Первым полиномиальным алгоритмом для решения задачи ЛП является метод эллипсоидов предложенный Л.Г. Хачияном [76]. Метод эллипсоидов для нахождения решения задачи ЛП аналогичен методу эллипсоидов для нахождения решения задачи квадратичного программирования, описанного в п. 1.2.2.4. Несмотря на то, что алгоритм, предложенный Л.Г. Хачияном, является полиномиальным, на практике он показывает результаты хуже, чем симплекс метод. Гораздо более эффективными на практике алгоритмами являются алгоритмы внутренних точек, первым из которых был алгоритм Н. Кармаркара [76]. Алгоритмы этого типа используют непрерывную трактовку задачи ЛП, когда вместо перебора вершин многогранника решений задачи ЛП осуществляется поиск вдоль траекторий в пространстве переменных задачи, не проходящих через вершины многогранника.

Также для проверки совместности системы линейных неравенств хорошо себя зарекомендовали метод исключений Фурье-Моцкина [18], релаксационный метод Агмона-Моцкина [115], теорема Черникова и теорема

Александрова - Фань-Цзн [90], вообще говоря, не являющиеся полиномиальными.

1.2.1.1. Метод исключений Фурье-Моцкина Пусть дана система (1.2.1.1), поскольку неравенства можно умножать на положительные скаляры, не уменьшая общности можно считать, что элементы первого столбца А равны либо 0, либо 1. Таким образом, исходную систему можно свести к виду:

4Х +ахх'< Д, 1=1 ,..,т\ +а1х'< Д, / = т'+1,..,/72", (1.2.1.2)

ахх'< Д, / = т"+\,..,т, (1.2.1.3)

где х = ,х'= ,ах,...,ат- столбцы матрицы А с

выброшенной первой строкой. Так как система (1.2.1.2) равносильна:

шах {а х*-р ) < £ < гшп(Д - а,х<),

т+1£у£т" ' * 1 й!йт

(1.2.1.4)

то переменную можно исключить, получив аналогичную систему линейных неравенств:

а]х'-/3} < Д = 1 = т'+1,...,т"

а,дс'< Д,/ = т"+1,...,т.

(1.2.1.5)

Эта система имеет т\т"-т') + т-т" ограничений с п-1 неизвестными. Повторяя эту процедуру, можно исключить первые п — 1 компонент и свести задачу к равносильной тривиальной системе с одной неизвестной, из любого решения которой можно восстановить решение исходной системы.

1.2.1.2. Теорема Черникова Необходимыми и достаточными условиями совместности системы

над пространством Я" ранга г > 0 является существование в матрице её коэффициентов отличного от нуля минора порядка г:

аии ' - аи,

А = ■■ аи1 >0, (1.2.1.7)

аи\ " аи.

такого, что выполняются соотношения:

аа • ■ аиРи

аи • ■ аир1

аи ' аарг

> 0, для любого / = 1, т,

(1.2.1.8)

1.2.1.3. Теорема Александрова - Фань-Цзи Для совместности системы (1.2.1.1) ранга г > 0 необходимо и достаточно, чтобы для любых N неотрицательных чисел Л1 >0,/ = 1,А^, из

N N N

равенства = 0 следовало неравенство ^ АД > 0.

/=1 м ы

1.2.2. Методы решения задач квадратичного программирования

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

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

Ах <b, А е Rnxm,b е Rm. (1.2.2.2)

Ограничения типа равенств:

Dx = d, где DeR"*',deR'. (1.2.2.3)

Где R"x" пространство матриц размерности п на и, а пространство векторов размерности п.

Замечание 1

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

Список литературы диссертационного исследования кандидат наук Куликов, Михаил Сергеевич, 2014 год

Список литературы

1. Акулич И.Л. Глава 3. Задачи нелинейного программирования // Математическое программирование в примерах и задачах. М.: Высшая школа, 1986. — 319 с.

2. Ананий В. Левитин Глава 5. Метод уменьшения размера задачи: Топологическая сортировка // Алгоритмы: введение в разработку и анализ = Introduction to The Design and Analysis of Algorithms. M.: «Вильяме», 2006. — С. 220-224.

3. Афраймович Л.Г., Прилуцкий М.Х. Многоиндексные задачи оптимального планирования производства // Автоматика и телемеханика. - 2010. - №10. - С. 148-155.

4. Афраймович Л.Г., Прилуцкий М.Х. Многоиндексные задачи распределения ресурсов в иерархических системах // Автоматика и телемеханика. - 2006. - №6 - С. 194-205.

5. Афраймович Л.Г., Власов B.C., Куликов М.С., Прилуцкий М.Х., Старостин Н.В., Филимонов A.B. ПЛАНИРОВАНИЕ И ОПЕРАТИВНОЕ УПРАВЛЕНИЕ ПРОЦЕССОМ ИЗГОТОВЛЕНИЯ СЛОЖНЫХ ИЗДЕЛИЙ//XII ВСЕРОССИЙСКОЕ СОВЕЩАНТЕ ПО ПРОБЛЕМАМ УПРАВЛЕНИЯ ВСПУ-2014. МОСКВА, 16-19 ИЮНЯ 2014г.: ТРУДЫ. - Москва: Институт проблем управления им. В. А. Трапезникова РАН. - 2014. - С. 5138-5149.

6. Ахьюджа Х.Н. Сетевые методы в проектировании и производстве. -М.: Мир, 1979. - 638 с.

7. Баркалов С.А., Бурков В.Н., Воропаев В.И. (Ред.) Математические основы управления проектами. М.: Высшая школа, 2005. - 432 с.

8. Батищев Д.И., Неймарк Е.А., Старостин Н.В. Применение генетических алгоритмов к решению задач дискретной оптимизации. Нижний

Новгород: Нижегородский государственный университет им. H.H. Лобачевского, 2007 - 85 с.

9. Булгак A.C. Многокритериальная задача теории расписаний с ресурсами складируемого типа//АиТ. - 1987. - №12. - С. 143-146.

10. Бурдюк В. Я., Шкурба В. В. Теория расписаний. Задачи и методы решений//Кибернетика - 1971 - №1. - С. 89-102.

11. Бурков В.Н., Ланда Б.Д., Ловецкий С.Е., Тейман А.И., Чернышев В.Н. Сетевые модели и задачи управления. М. : Советское радио, 1967. - 163 с.

12. Вахания H.H. Построение сокращенного дерева вариантов для общей задачи теории расписаний // Дискр. Матем - 1990. -Т.2. - Вып.З. - С. 1020.

13. Витковский Я.Я. Основы сетевого планирования и управления. Рига: 1966.-236 с.

14. Гимади Э. X. О некоторых математических моделях и методах планирования крупномасштабных проектов // Модели и методы оптимизации. Новосибирск: Наука, (Тр. / АН СССР. Сиб. Отд-ние. Ин-т математики;) - 1988. - Том 10. - С. 89-115.

15. Гимади Э.Х., Залюбовский В.В., Севастьянов C.B. Полиномиальная разрешимость задач календарного планирования со складируемыми ресурсами и директивными сроками // Дискретный анализ и исследование операций, Сер.2. -2000. - Т. 7, N. 1. - С. 9-34.

16. Голенко Д. И. Статистическое моделирование в технико-экономических системах - Л.: Изд-во Лен. ун-та: 1977. - 264с.

17. Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. - М.: Мир, 1982. - 416 с.

18. Данциг Д. Линейное программирование, его применения и обобщения. Москва: Прогресс 1966. - 600 с.

19. Джонс М.Т. Программирование искусственного интеллекта в приложениях. М.: ДМК Пресс, 2004. - 312 с.

20. Дикин И.И., Зоркальцев В.И. Итеративное решение задачи математического программирования: алгоритмы метода внутренних точек. Новосибирск: Наука. Сиб. Отд-ние, 1980 - 144 с.

21. Евтушенко Ю.Г. Жадан В.Г. Двойственные барьерно-проективные и барьерно-ньютоновские методы для задач линейного программирования. //Журнал вычислительной математики и математической физики. - 1996. - Т.36, №7. - С. 30-45.

22. Евтушенко Ю.Г. Методы решения экстремальных задач и их применение в системах оптимизации. М.: Наука, 1982. - 432 с.

23. Ковалев М.Я. Интервальные е-приближенные алгоритмы решения дискретных экстремальных задач // Дис. канд. физ.-мат. наук. -Минск: 1986. - 110 с.

24. Коган Д.И., Федосенко Ю.С. ЗАДАЧА ДИСПЕТЧЕРИЗАЦИИ: АНАЛИЗ ВЫЧИСЛИТЕЛЬНОЙ СЛОЖНОСТИ И ПОЛИНОМИАЛЬНО РАЗРЕШИМЫЕ ПОДКЛАССЫ // Дискретная математика. - 1996.- Т. 8. №3. - С. 135.

25. Коган Д.И., Федосенко Ю.С. ЗАДАЧИ СИНТЕЗА ОПТИМАЛЬНЫХ СТРАТЕГИЙ ОБСЛУЖИВАНИЯ СТАЦИОНАРНЫХ ОБЪЕКТОВ В ОДНОМЕРНОЙ РАБОЧЕЙ ЗОНЕ ПРОЦЕССОРА // Автоматика и телемеханика. - 2010. - № 10. - С. 50-62.

26. Коган Д.И., Федосенко Ю.С., Дуничкина H.A. БИКРИТЕРИАЛЬНЫЕ ЗАДАЧИ ОБСЛУЖИВАНИЯ СТАЦИОНАРНЫХ ОБЪЕКТОВ В ОДНОМЕРНОЙ РАБОЧЕЙ ЗОНЕ ПРОЦЕССОРА // Автоматика и телемеханика. - 2012. - № 10. - С. 93-110.

27. Козлов М.К., Шафранский В.В. Календарное планирование выполнения комплексов работ при заданной динамике поступления складируемых

ресурсов II Изв. АН СССР. Техническая кибернетика. - 1977. - №.4. -С. 75-81.

28. Козлов М.К., Тарасов СП., Хачиян Л.Г.. Полиномиальная разрешимость выпуклого квадратичного программирования. // Доклады Академии Наук СССР 248. - 1979. - С. 1049-1051.

29. Конвей Р.В., Максвелл В.Л., Миллер Л.В. Теория расписаний. -М.:Наука, 1975.-359 с.

30. Кормен, Т., Лейзерсон, Ч., Ривест, Р., Штайн, К. Глава 22.4. Топологическая сортировка // Алгоритмы: построение и анализ = Introduction to Algorithms / Под ред. И. В. Красикова. — 2-е изд. — М.: Вильяме, 2005. — С. 632-635.

31. Коробкин А.Д., Мироносецкий Н.Б. Оптимизация производственного планирования на предприятии. Новосибирск.: Наука, 1978. - 335с.

32. Коротаев Ю.П., Ширковский А.И. Добыча, транспорт и подземное хранение газа. М.: Недра, 1984, 488 с.

33. Костюков В.Е., Прилуцкий М.Х. Распределение ресурсов в иерархических системах. Оптимизационные задачи добычи, транспорта газа и переработки газового конденсата. Учебное пособие. Нижний Новгород: Изд-во Нижегородского госуниверситета, 2010. - 78с.

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

35. Куликов М.С., Афраймович Л.Г., Власов B.C., Прилуцкий М.Х., Седаков Д.В., Старостин Н.В., Филимонов A.B. Задачи планирования и оперативного управления процессом изготовления интегральных схем с микронными и субмикронными топологическими нормами. //

АВТОМАТИЗАЦИЯ В ПРОМЫШЛЕННОСТИ Ежемесячный научно-технический и производственный журнал. - 2014 - № 8 - С. 17-21.

36. Кумагина Е.А. Об одном подходе к решению задач упорядочения. // Труды Всероссийской конференции «Интеллектуальные информационные системы», Воронеж. - 1999. - С. 61-63.

37. Лазарев A.A., Гафаров Е.Р. Теория расписаний. Исследование задач с отношениями предшествования и ресурсными ограничениями. ВЦ им. Дороницына, РАН, 2007. - 80 с.

38. Лазарев A.A., Гафаров Е.Р. Теория расписаний. Задачи и алгоритмы -М.: Московский государственный университет им. М.В. Ломоносова (МГУ), 2011.-222 с.

39. Лазарев A.A., Мусатова Е.Г., Кварацхелия А.Г., Гафаров Е.Р. Теория расписаний. Задачи управления транспортными системами. Москва: Физический факультет МГУ имени М.В. Ломоносова, 2011. - 160 с.

40. Лазарев A.A. Теория расписаний. Оценки абсолютной погрешности и схема приближенного решения задач теории расписаний. М.:МФТИ, 2008. - 222 с.

41. Милов В.Р., Суслов Б.А., Крюков О.В. ИНТЕЛЛЕКТУАЛИЗАЦИЯ ПОДДЕРЖКИ УПРАВЛЕНЧЕСКИХ РЕШЕНИЙ В ГАЗОВОЙ ОТРАСЛИ // Автоматизация в промышленности. - 2009. - № 12. - С. 1620.

42. Мироносецкий Н.Б. Экономико-математические методы календарного планирования. Новосибирск: Наука, 1973. -140 с.

43. Михалевич В. С., Трубин В. А., Шор Н. 3. Оптимизационные задачи производственно-транспортного планирования. М.: Наука, 1986.-260 с.

44. Михалевич B.C., Кукса А.И. Методы последовательной оптимизации в дискретных сетевых задачах оптимального распределения ресурсов. М.: Наука, 1983. - 208 с.

45. Мищенко A.B. Устойчивость решений задачи оптимального распределения ресурсов при динамичеком изменении структуры сети. М.: ВЦАНСССР 1980. - 12с.

46. Моисеев H.H., Иванилов Ю.П., Столярова Е.М. Методы оптимизации. Москва: Наука, 1978.-351 с.

47. Моудер. Дж., Элмаграби С. Исследование операций. М.: Мир, 1981. -326 с.

48. Мут Дж. Ф., Томпсон Дж. Л. Календарное планирование. Москва: Прогресс, 1966. - 467 с.

49. Панченко Т.В. Генетические алгоритмы: Учебно-методическое пособие / под ред. Ю.Ю. Тарасевича. Астрахань: АГУ, 2007. - 87 с.

50. Подчасова Т.П., Португал В.М., Татаров В.А., Шкурба В.В. Эвристические методы календарного планирования. Киев: Техника, 1980.-140 с.

51. Поспелов Г.С., Тейман А.И. Автоматизация процессов управления разработками больших систем или сложных комплексов. // М.: Известия АН СССР. Техническая кибернетика. - 1963. - №4 - С. 60-79.

52. Прилуцкий М. X., Батищев Д. И., Гудман Э. Д., Норенков И. П. Метод комбинирования эвристик для решения комбинаторных задач упорядочения и распределения ресурсов. // Информационные технологии. Москва. - 1997. - №2. - С. 29-32.

53. Прилуцкий М.Х. Многоиндексные задачи объемно-календарного планирования транспортного типа. // SICPR006 . Труды 5 Международной конференции «Идентификация систем и задачи управления» SICPRO 2006. Москва 30 января - 2 февраля 2006, Институт проблем управления им. В.А.Трапезникова РАН. М.: Институт проблем управления им. В.А.Трапезникова РАН. - 2006. - С. 503-519.

54. Прилуцкий М.Х. Многокритериальное распределение однородного ресурса в иерархических системах // Автоматика и телемеханика. - 1996. - №2. - С. 24-29.

55. Прилуцкий М.Х. Многокритериальные многоиндексные задачи объёмно-календарного планирования. // Известия академии наук. Теория и системы управления. - 2007. - №1. - С. 78-82.

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

57. Прилуцкий М.Х., Васильев Е.В., Костюков В.Е. Многокритериальная задача распределения производительности купола по газовым скважинам//Системы управления и информационные технологии.-2007 - №3.2(29) - С. 291-296.

58. Прилуцкий М.Х., Власов С.Е. Многостадийные задачи теории расписаний с альтернативными вариантами выполнения работ. // Системы управления и информационные технологии». - 2005. - №2, -С. 44-48.

59. Прилуцкий М.Х., Костюков В.Е. Потоковые модели для предприятий с непрерывным циклом изготовления продукции. // Информационные технологии. - 2007. - №10. - С.47-52.

60. Прилуцкий М.Х., Куликов М.С. Многокритериальные задачи квадратичного программирования с ограничениями транспортного типа // Системы управления и информационные технологии. - 2010. -№3(41). - С. 17-21

61. Прилуцкий М.Х., Кумагина Е.А Управляемый фронтальный алгоритм решения задачи распределения ресурсов в сетевых канонических

структурах // Вестник Нижегородского университета им. Н.И.Лобачевского. №6, Н. Новгород: Изд-во ННГУ. - 2008. - №6 -С. 126-129

62. Прилуцкий М.Х., Кумагина Е.А. Задача упорядочения работ как задача о назначениях // Вестник Нижегородского государственного университета. Математическое моделирование и оптимальное управление. Изд-во ННГУ. - 1999. - Вып.2(21). - С. 270-275.

63. Прилуцкий М.Х., Нефедов Д.С., Попов Д.В. Распределение ресурсов в дискретно управляемых системах // Электронный журнал «Исследовано в России», 032/020228. - 2002. - С. 322-337

64. Прилуцкий М.Х., Попов Д.В. Многостадийные задачи распределения и упорядочения с нечеткими характеристиками // Электронный журнал «Исследовано в России», 2001, 043/010331.-2001. - С. 476-484

65. Прилуцкий М.Х., Попов Д.В. Многостадийные задачи теории расписаний с нечеткими характеристиками // Сборник научных статей «Математика и кибернетика», ННГУ, Н.Новгород. - 2003. - С. 243-252

66. Протасов В.Н., Жердзинский И.Ю. Оптимизация функционирования конвейерной производственной системы. // Системное моделирование. -1991.-№18.-С. 135-159.

67. Рейнгольд Э., Нивергельт Ю. Комбинаторные алгоритмы. Теория и практика. М.: Мир, 1980. - 476 с.

68. Севастьянов C.B. Геометрические методы и эффективные алгоритмы в теории расписаний // Дис. док. физ.-мат. наук. Новосибирск, 2000. - 280 с.

69. Севастьянов C.B. Эффективное построение расписаний в системах открытого типа. // Сибирский журнал исследования операций. - 1994. -Т.1. № 1. - С. 20-42

70. Сервах B.B. Эффективные алгоритмы для некоторых задач календарного планирования // В кн. Методы решения и анализа задач дискретной оптимизации. Сб.научных трудов под ред. A.A. Колоколова, Омск, ОмГУ. - 1992. - С. 94-106.

71. Сервах В.В. Алгоритм решения задачи календарного планирования с единичными длительностями работ // В кн. Дискретная оптимизация и анализ сложных систем, ВЦ СО АН СССР, Новосибирск. -1989 - С. 99107.

72. Сервах В.В. Задачи календарного планирования со штрафами за превышение директивных сроков // Инф. бюллетень №4 Ассоциации математического программирования. Тезисы докл. конференции "Математическое программирования и приложения", Екатеринбург. -1993.- С. 76

73. Сервах В.В. Календарное планирование с работами единичной длительности // Материалы межреспубликанского семинара по дискретной оптимизации. Киев. - 1990. - С. 66

74. Сотсков Ю.Н. Оптимальное обслуживание двух требований при регулярном критерии // Автоматизация процессов проектирования, Минск: ИТК АН БССР. - 1985. - С. 52-62.

75. Сухарев А.Г., Тимохов A.B., Федоров В.В. Курс методов оптимизации: Учебное пособие - 2е изд. М.: ФИЗМАТЛИТ. - 2005. - С. 265-274.

76. Схрейвер А. Теория линейного и целочисленного программирования в 2т. М.: Мир, 1991 том 1. - 360 с.

77. Схрейвер А. Теория линейного и целочисленного программирования в 2т. М.: Мир, 1991 том 2. - 342 с.

78. Танаев B.C., Гордон B.C., Шафранский Я.М. Теория расписаний. Одностадийные системы. М.: Наука, 1984. - 348 с.

79. Танаев B.C., Шкурба B.B. Введение в теорию расписаний. М.: Наука, 1975. - 256 с.

80. Танаев B.C. Теория расписаний. - М.: Знание, 1988. - 32 с.

81. Танаев B.C., Ковалев М.Я., Шафранский Я.М. Теория расписаний. Групповые технологии. Минск: ИТК HAH Беларуси, 1998. - 290 с.

82. Танаев B.C., Сотсков Ю.Н., Струсевич В.А. Теория расписаний. Многостадийные системы. М.: Наука, 1989. - 328 с.

83. Федосенко Ю.С., Дуничкина H.A. БИКРИТЕРИАЛЬНАЯ МОДЕЛЬ И АЛГОРИТМЫ СИНТЕЗА УПРАВЛЕНИЙ ОБСЛУЖИВАНИЕМ ГРУППИРОВКИ СТАЦИОНАРНЫХ ОБЪЕКТОВ // Информационно-измерительные и управляющие системы. - 2010. - Т. 8. № 2. - С. 20-24.

84. Федосенко Ю.С., Цветков А.И. ЗАДАЧА СИНТЕЗА ОПТИМАЛЬНО-КОМПРОМИССНЫХ СТРАТЕГИЙ ОБЛУЖИВАНИЯ БИНАРНОГО ПОТОКА ОБЪЕКТОВ В ЛИНЕЙНОЙ РАБОЧЕЙ ЗОНЕ ДВУХ MOBILE-ПРОЦЕССОРОВ // Вестник Нижегородского университета им. Н.И. Лобачевского. - 2011. - №4-1. - С. 160-165.

85. Федосенко Ю.С., Цветков А.И. СИНТЕЗ СТРАТЕГИЙ УПРАВЛЕНИЯ В БИКРИТЕРИАЛЬНОЙ МОДЕЛИ ОДНОПРОЦЕССОРНОГО ОБСЛУЖИВАНИЯ БИНАРНОГО ПОТОКА ОБЪЕКТОВ // Информационно-измерительные и управляющие системы. - 2011. - Т. 9. № 3. - С. 28-32.

86. Хачиян Л. Г. Полиномиальные алгоритмы линейного программирования. // Вычисл. матем. и матем. физ. - 1980. - т. 20, №1. -С. 51-68.

87. Хемди A. Taxa Глава 3. Симплекс-метод // Введение в исследование операций = Operations Research: An Introduction.— 7-е изд., M.: «Вильяме». - 2007. — С. 95-141

88. Хранилов В.П., Прохоров Д.В. НЕЧЕТКАЯ ДИНАМИЧЕСКАЯ МОДЕЛЬ ИНТЕРАКТИВНОГО РАСПРЕДЕЛЕНИЯ ВЫЧИСЛИТЕЛЬНЫХ РЕСУРСОВ // Системы управления и информационные технологии. - 2006. - №4.1 (26). - С. 189-193.

89. Черенков А.П. Задачи распределения разнотипных ресурсов с насыщением // Вычисл. мат. и мат. физ. - 1988. - Т. 28, №7. - С. 11021107.

90. Черников С.Н. Линейные неравенства. М.: Наука, 1968. - 488 с.

91. Шахлевич Н.В. Оптимальное обслуживание двух требований в неоднородных системах с прерываниями // 6 Конф. Мат. Беларуси Тез докл. Ч.4/Гродн. Гос. Ун-т. Гродно. - 1992. - С. 105.

92. Шкурба В.В., Подчасова Т.П., Пшичук А.Н., Тур Л.П. Задачи календарного планирования и методы их решения. Киев: Науковадумка, 1966. - 154 с.

93. Шор Н.З., Гершович В.И. Об одном семействе алгоритмов для решения задач выпуклого программирования //Кибернетика. - 1979 - №4 - С. 6267

94. Aho A., Garey М. R.; and Ullman J. D. The Transitive Reduction of a Directed Graph.//SIAM J. Comput. 1 - 1972. - P. 131-137.

95. Antill J.M., Woodhead R.W. Critical Path Methods in Construction Practice, New York: Wiley, 1970.

96. Artentano Vinicius A., Ronconi Debora P. Tabu-search for total tardiness minimization in flowshop problems // Сотр. and Oper. Res. - 1999. -26, №3 - P. 219-235.

97. Baptiste Ph., Le Pape C., Nuijten W. Constraint-based scheduling:applying constraint programming to scheduling problems. Kluwer Academic Publishers, 2001.-198 p.

98. Bellman R. Mathematical Aspects of Scheduling Theory // J. Soc. Indust. and Appl. Math. - 1956. - V.4 №3. - P. 168-205.

99. Blazewicz J., Ecker K., Pesch E., Schmidt G., Weglarz J. Scheduling Computer and Manufactoring Processes. Springer Berlin. 1996.

100. Brucker P. Scheduling Algorithms. Springer-Verlag, 2001. - 365 p.

101. Brucker P., Knust S. Complex scheduling Springer-Verlag Berlin, Heidelberg, Germany, 2006.

102. Burer S., Vandenbussche D.: A finite branch-and-bound algorithm for nonconvex quadratic programming via semidefinite relaxations. Manuscript, Department of Management Sciences, University of Iowa, Iowa City, IA, USA, June 2005. Revised April 2006 and June 2006. Math. Program.

103. Coffman E. G., Jr.; Graham R. L. Optimal scheduling for two-processor systems // Acta Informatica 1 - 1972 - P. 200-213.

104. Daniel Richard L., Hua Stella Y., Webster Scott Heuristics for parallel-machine flexible-resource scheduling problems with unspecified job assignment//CoTp. and Oper. Res. - 1999. - 26, №2. - P. 143-155.

105. Gafarov E.R. , Lazarev A.A. and Werner. F. Algorithms for Some Maximization Scheduling Problems on a Single Machine // Automation and Remote Control. - 2010. - Vol. 10. - P. 2070-2084.

106. Gould N. I. M., Hribar M. E., J. Nocedal On the Solution of Equality Constrained Quadratic Programming Problems Arising in Optimization // SLAM Journal of Scientific Computing - 2001 - 23(4) - P. 1375 - 1394

107. Graham R.L., Lawler E.L., Lenstra J.K., Rinnooy Kan A.H.G Optimization and approximation in determenistic sequencing and scheduling: a servey // Ann. Descrete Optimization. - 1979. - V. 2. - P. 287-325.

108. Hestenes R. Magnus; Stiefel E. Methods of Conjugate Gradients for Solving Linear Systems // Journal of Research of the National Bureau of Standards. -

1952.- 49 (6).-P. 409-436

109. Kojima M., Mizuno S., and Yoshise A. A Polynomial-Time Algorithm for a Class of Linear Complimentarity Problems // Mathematical Programming. -1989. - №44. - P. 1-26.

110. Lawler E.L. On scheduling problems with deferral costs // Management Science. - 1964. - V. 11. - P. 280-288.

111. Megiddo N. Linear programming in linear time when the dimension is fixed//J.ACM. - 1984. - 31-P. 114-127.

112. Megiddo N., Tamir A. Linear time algorithms for some separable quadratic programming problems. // Operations Research Letters. - 1993. - 13. -P. 203-211.

113. Mehrotra S. (1992). On the implementation of a primal-dual interior point method. // SIAM Journal on Optimization. - 1992. - 2 (4). - P. 575-601.

114. Monteiro R.D.C. and Adler I. Interior Path Following Primal-Dual Algorithms. Part II: Convex Quadratic Programming// Mathematical Programming. - 1989. - №44 - P.43-66.

115. Motzkin T.S., Schoenberg I.J. The relaxation method for linear inequalities // Caned. J. Moth. - 1954. - V. 6. №3. - P. 393-404.

116. Nocedal J. and Wright S. Numerical Optimization Second Edition. New York: Springer, 2000. - 634 p.

117. Panos M. Pardalos and Stephen A. Vavasis Quadratic programming with one negative eigenvalue is NP-hard // Journal of Global Optimization. - 1991 -Volume 1, Number 1. - P. 15-22.

118. Philip Wolfe, THE SIMPLEX METHOD FOR QUADRATIC PROGRAMMING // Econometrica - 1959 - Vol. 27, No. 3 - P. 382-398

119. Poole D. Linear Algebra: A Modern Introduction (2nd ed.), Canada: Thomson Brooks/Cole, 2006. - 736 p.

120. Reslow Kriith T. Interior-Point Algorithms for Quadratic Programming. Kongens Lyngby: Technical University of Denmark, 2008 - 117 p.

121. Sahni S. Computationally related problems // SIAM Journal on Computing. -1974-3-P. 262-279.

ПРИЛОЖЕНИЕ. Документы, подтверждающие внедрение результатов диссертационной работы

результатов диссертационной работы Куликова М.С.

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

в учебный процесс факультета ВМК ИНГУ,

Материалы диссертационной работы Куликова М.С. «Модели и методы распределительного типа прп плакировании и оперативном управлении производственными системами» (научный руководитель д.т.н, профессор Прнлуцкий М.Х.) внедрены в учебный процесс факультета вычислительной математики и кибернетики ННГУ, и используются с 2012-2013 учебного года при проведении курса «Теория систем и системный анализ» для студентов, обучающихся по направлению подготовки 230700 «Прикладная информатика».

Результаты, полученные в диссертационной работе Куликова М.С., отражены в учебно-методической разработке «Многокритериальные задачи распределения ресурсов в иерархических системах. Задачи планирования и оперативного управления» (авторы М.Х. Прнлуцкий, М.С. Куликов) размещенной в Фонде электронных образовательных ресурсов ННГУ.

Утверждаю

Проректор ННГУ по научной работе профессор

Декан факультета ВМК профессор Зав. Кафедрой ИАНИ профессор

Гергель В.П. Прнлуцкий М.Х.

УТВЕРЖДАЮ

СПРАВКА

об использовании результатов диссертационной работы М.С. Куликова

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

при планировании процесса изготовления изделий опытного производства.

В 2012 г. версия программной системы «ПРОГРАММНЫЙ МОДУЛЬ РАСЧЕТА РАСПИСАНИЯ», включающая прикладную часть диссертационной работы М.С. Куликова «Модели и методы распределительного типа при планировании и оперативном управлении производственными системами», передана для эксплуатации в ОАО «Опытное Конструкторское Бюро Машиностроения им, И.И. Африкантовз». Программное обеспечение было использовано для тестирования расчета оптимального плана производства в рамках задачи календарного планирования производственных мощностей для функционирующей на предприятии системы управления производством АСВП. Проведенные тесты и полученные результаты в области составления графиков выполнения заказов показали эффективность применяемой математической модели и предлагаемых подходов при решении задач планирования производства.

Начальник отдела

Начальник бюро

М.И. Быстрое

С.Л. Васьков

(ш)

УТВЕРЖДАЮ

Зам, директора по качеству и информационным технологиям «НИИИС мм.

Д.В» Седаков

СПРАВЙА^-

об использовании результатов диссертационной работы М.С. Куликова

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

при планировании процесса изготовления сложных изделий.

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

Начальник НИО 97» к.т.и. . В,Ф. Морозов Старший научный сотрудник, к.т.и.' ^сч__В.С. Власов