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

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

Ермолаева Любовь Викторовна

ОПТИМИЗАЦИОННЫЕ МОДЕЛИ вЕКТ - СЕТЕВОГО ПЛАНИРОВАНИЯ И УПРАВЛЕНИЯ ПРОИЗВОДСТВЕННЫМИ

ПРОЦЕССАМИ

05.13.01 - Системный анализ, управление и обработка информации

Автореферат

диссертации на соискание ученой степени кандидата технических наук

ООЗ174250

Красноярск - 2007

003174250

Работа выполнена в ГОУ ВПО «Красноярский государственный торгово-экономический институт»

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

Сенатов Сергей Иванович

Официальные оппоненты доктор технических наук, профессор

Семенкин Евгений Станиславович, Сибирский государственный аэрокосмический университет им академика М.Ф Решетнева, г. Красноярск

кандидат технических наук, доцент Царев Роман Юрьевич, Сибирский федеральный университет, г. Красноярск

Ведущая организация. Томский государственный университет

Защита состоится " 1<&л£(и1. 2007 года в 14 часов на заседании

диссертационного совета Д 212.249 02 при Сибирском государственном аэрокосмическом университете имени академика МФ. Решетнева по адресу: 660014, г Красноярск, пр. им. газеты «Красноярский рабочий», 31.

С диссертацией можно ознакомиться в библиотеке Сибирского государственного аэрокосмического университета имени академика М.Ф. Решетнева

Автореферат разослан "££" Р-^.Л^Л 2007 г.

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

И.В. Ковалев

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

Актуальность Современная экономическая ситуация диктует жесткие требования участникам рыночных отношений Выживают только высокоорганизованные предприятия, в основу управления которыми положен принцип быстрой реакции на непрерывно изменяющиеся требования рынка. Мировая практика показала, что динамичные и гибкие производства строятся на базе современных информационных систем управления класса MES (Manufacturing Execution System - производственные исполнительные системы) Развернутым смысловым определением MES систем, соответствующим отечественной практике и терминологии (АСУ ПП -автоматизированные системы управления производственными процессами), можно считать следующее: системы оперативного планирования, оптимизации и управления производственными процессами

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

Диссертационная работа посвящена построению математического аппарата расчета производственных расписаний и распределения ресурсов различного характера Данный инструментарий может быть применен в системах класса MES. Его основой является циклическая стохастическая сетевая модель (GERT-сеть), являющаяся обобщением таких методов сетевого планирования как метод критического пути, PERT -сетей, обобщенных сетевых моделей.

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

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

Указанная цель определила необходимость решения следующих задач.

1 Анализ подходов к оптимизации планирования и управления производственными процессами

2 Разработка модельных средств детерминированного формирования распределенных производственных процессов.

3 Стохастическое представление моделей формирования производственных процессов

з

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

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

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

Научная новизна работы.

1 Разработана многокомпонентная сетевая модель с унифицированной СЕЯТ-подобной узловой логикой для формального представления и автоматизированного формирования операций распределенных производственных процессов.

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

3. Доказано существование допустимой реализации распределенного процесса, если сетевая модель его формирования ациклична и ее параметры удовлетворяют условиям СЕЯТ-подобной узловой логики.

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

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

Практическая ценность. Реализация предложенного формального аппарата СЕЯТ-сетевого моделирования производственных процессов в автоматизированных системах поддержки принятия решений при планировании и управлении производственными процессами позволит повысить эффективность и обоснованность принимаемых управленческих решений.

Апробация работы. Результаты диссертационного исследования обсуждались на IV всероссийской научно-практической конференции «Актуальные проблемы науки в России», Кузнецк, 2007; на заочных электронных конференциях РАЕ «Управление стратегией развития производства», 2006, 2007; на международной научной конференции ИННОВАТИКА-2007, Ульяновск, 2007, на IV международной конференции «Методы и средства управления технологическими процессами МСУПТ-2007», Саранск, 2007; на VII региональной конференции «Теория и практика коммерческой деятельности», Красноярск, 2005, на научных семинарах КГТЭИ, НИИ СУВПТ и СибГАУ.

Структура и объем работы. Диссертация состоит из введения, трех глав и заключения. Изложена на 128 страницах машинописного текста. Список источников содержит 82 наименования

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

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

Рассмотрены задачи объемно-календарного планирования производства, задачи распределения производственной программы предприятия по плановым периодам, задачи формирования производственной программы при мелкосерийном производстве, задачи планирования финансирования выполнения производственных программ

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

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

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

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

заданий с использованием ориентированного графа или графа предшествования является наиболее популярным в литературе по планированию Модифицированные вЕКТ-узлы в этом графе могут представлять независимые операции или части цикла операций, которые связаны между собой во времени

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

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

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

1) определение минимума времени, необходимого для обработки графа операций процесса при фиксированном числе ресурсов,

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

Первым шагом в решении этой задачи является разметка узлов произвольного графа Узлу N. присваивается метка а, = X, + 1, где X, — длина наидлиннейшего пути от Л', до конечной вершины в графе. Разметка начинается с конечной вершины, которой присваивается метка а/ = 1, Узлы, на единицу отдаленные от конечного, получают метку 2 и т. д. Смысл этой схемы меток в том, что минимальное время Тщ,,,, необходимое для обработки графа, связано с а(шах) узлами с наивысшими индексами через соотношение Тт11 > д(шах).

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

1. Включаем в план первые т начальных узлов с наивысшими индексами меток Термин «начальный узел» применяется к узлу без предшественников. Если количество таких узлов больше т, то выбрать т. узлов с наибольшими значениями а, В случае нескольких одинаковых величин выбор производится случайным образом.

2. Удаляем т обслуженных узлов из грзфа.

3. Повторяем шаги I и 2 для оставшегося 1рафа.

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

/¿Л

Т1? т 1 т '» 1 1 и т и Т. тг

т.* Т,, т 113 т 1 1П Т.

Г. Т„ Т *<>

(3 2 1 5 7 К

(Ь)

Рисунок 1 - Оптимизационный алгоритм генерации 2-В: а - корневое дерево, размеченное в соответствии с процедурой Хью; Ь - оптимальный план для трех ресурсов

Как было показано выше, минимальное время обработки графа, размеченного в соответствии с процедурой Хыо, равно й(тах). Предположим, требуется обработать граф за предписанное время г, где г = д(тах)+ С и С -положительное целое число.

Минимальное число т ресурсов, необходимых для обработки графа за время (, вычисляется как

т-\<{М(у +1 ~])<т,

■ I

где р(г) обозначает количество узлов в графе с меткой а,, а у* - величина константы у, которая максимизирует данное выражение. Для пояснения алгоритма генерации 2-В, рассмотрим рисунок 1. Для С = 0 величина у* имеет место, когда у = I или у =; 2. То есть, для обработки графа за минимальное

время необходимо четыре ресурса Для С = 1,; = 8 и>*, имеющем место ищу = 2 или у=5, требуется три ресурса Меняя С, далее мы определим, что необходимы три ресурса, когда задачи должны быть выполнены за 9 единиц, и только два ресурса необходимы для максимального времени вычисления в 10 единиц

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

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

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

Итак, в работе дополнительно предполагается наличие множества видов ресурсов К-1Я,,...,Я3} Если для выполнения операции необходим ресурс /?„ то это требование принимается во внимание в течение всего периода выполнения операции. Потребность операции ], в ресурсе И, обозначается через рч (0<ру <1) Пусть г,{г) обозначает общее количество ресурсов Я„ которое

используется в момент времени /. Тогда ф) = Бит(рц) для всех 7,, выполняемых в момент времени I и г, (г) < 1. Для данной постановки в работе

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

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

• при Я={Я,} (в системе существует только один вид ресурса) - и>/и>' < п,

• при Я={И1/ и независимости всех задач - <3 — 1 /п,

• при Я=(Я/, Я2, , независимости задач и п>г - ы/ы' < Б + \

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

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

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

Пусть Е, — максимальное время выполнения одной итерации операции J„ а - частота выполнения Таким образом, каждой операции ], соответствуют два параметра Е,), 1 <1<п, где п - количество включаемых в план

операций. Период повторения равен Т„ величине, обратной/. Рассматривается класс операций, для которого верно следующее если п операций с У/ по Jn распределены так, что /, > /+/, то предполагается, что /, = , либо допускаются операции с любой частотой.

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

Таблица 1 - Характеристики для множества задач с бинарным частотным распределением

Задача Частота Период Время выполнения

7/ ^ 4 1

Зг 1/8 8 2

75 1/16 16 1'/2

14 1/32 32 5

75 1/64 64 3

На рисунке 2, а, показаны операции 7, и 72. спланированные на разных ресурсах, а на рис 2, Ь показан план, уменьшающий количество ресурсов с двух до одного Проблемой является определение минимального количества ресурсов без перебора всех возможных альтернатив. Заметим, что слияние двух операций, приведенное на рис 2, Ь, создает новую периодичную операцию с периодом г/ (равным 2Т0 и временем выполнения е} (равным Т] + Е\). Кроме того, имеются два промежутка с простоями: /( периодичный простой с длительностью Гу - в/, и Д'2 принудительное время простоя длинной 11 - Е2 (обозначение Д^указывает, что принудительное время простоя получается, когда 7; объединяется с 7,) В процессе объединения остальных операций плана нет необходимости в рассмотрении размещения операций в интервале принудительного простоя Вместо этого для такой среды план с минимальным числом ресурсов формируется в соответствии со следующим алгоритмом.

1) Пусть У/*, 72*, - подмножества операций, назначаемых ресурсам Я/, Я2,.. . Сначала . =0, а /;=/г= -= <я. Всякий раз, когда операция 7, назначается в некоторое пустое подмножество 7/*, /, = 7) - .

2) Чтобы назначить очередную операцию 7„ необходимо найти наименьшее I такое, чтобы выполнялось условие £,</,, и назначить У, в подмножество Оптимальный план для набора операций из таблицы 1 показан на рисунке 3. Этот результат обобщен для случая, когда/ = к(/1+1), к - положительное целое число больше 1.

□ □ □

-!-1-1-"--1---1-1

2 4 6 8 10 12 14 (а)

и—-1-и

--е,-^ п

■Ч 1 >*

и

(Ь)

Рисунок 2 - Планирование периодичных операций с бинарным частотным

распределением: а — временная диаграмма для первых двух операций из таблицы !; Ь - ослабление ограничений на число ресурсов путем слияния операций

Ш НИ] ОШ И1 3 14 2 I аЗЕШШ ЕПП ЕШ ОШ Ш \шш

4 I __I 4 |

—-1-~—I--]-,-^-1----——I-1——--1-]—.-I-1

0 4 К 12 16 20 24 28 32 36 40 44 48 52 56

Рисунок 3 - Оптимальный план для операций из таблицы 1

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

1. Б порядке уменьшения частоты.

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

2. В порядке уменьшения критерия загрузки.

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

следующим образом: Ц = Е/Г,.

3. Сохранение минимальной длины критического интервала.

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

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

И-

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

При тестировании данных методов, задачи разделялись на два класса В 1-м классе частоты операций кратны более чем двум базовым частотам, а во 2-м - не более чем двум базовым частотам Ни один из алгоритмов не показал значительного превосходства над другими Однако подход 2 исключительно хорошо показал себя на задачах первого класса Подход 3 лучше решает некоторые задачи второго класса, а оба подхода 1 и 2 неплохо решают задачи, которые оказались трудными для подхода 3 В этом нет ничего необычного, так как число ресурсов, необходимых для задач второго класса, было значительно меньше, чем для задач первого класса

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

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

Далее в качестве формальной базы алгоритмической СЕ11Т-процедуры используется аппарат стохастических сетей и графического метода оценки и пересмотра планов Рассмотрены модели временной реализации распределенных процессов, которые описываются детерминированными структурами вЕЯТ-сетей СЕЯТ-сеть можно отнести к классу управляющих графов, представляющих собой графо-аналитические модели с достаточно большим числом входных спецификаций

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

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

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

Пусть N — ациклическая сетевая модель распределенного процесса с источниками и стоками (действия, соответствующие операциям, представляются дугами), где множество узлов обозначается V, а множество дуг — Е. Сеть имеет только один исток, который обозначается через г и соответствует началу рассматриваемого процесса. Предполагается, что один из стоков N представляет собой успешное завершение процесса и обозначается б Оставшиеся стоки, если они есть, могут представлять собой различные виды неудачного завершения или прерывания реализации процесса.

Ациклическую сетевую модель только с одним истоком и со стоками назовем формирующей сетью распределенного процесса, если каждый узел / из N определен через входную характеристику Х~ е { 0,1,. , } и выходную

характеристику X*е {ОД, ,|5(г]( } Эти характеристики, формирующие узловую логику, имеют следующие значения (а) узел активируется сразу же, как только входные действия Х~ завершаются, (б) как только узел г активирован, то не более X* выходных действий начинает выполняться. Если узел I не активируется, то ни одно выходное действие не выполняется Для источника г полагаем X~ = 0, те. он всегда активирован Кроме того, Х,+ =0 для г е 5, где 5 — множество стоков Заметим, что если Х~ =1, то узел / имеет ОЯ-вход, а если Х~ = |р(г)|, то тогда г имеет ЛМ?-вход. И если "не более" заменяется на "точно" в условии (б), то Х,+ = 1 соответствует вероятностному выходу, а Х1+=|5(г)( соответствует детерминированному выходу. Если же заданная сеть N для формирования процесса имеет множество источников Я (|Д |>1) и множество Я с К, К ^ О активизируется в начале выполнения реализации процесса, то можно формально перевести сеть N в соответствующую одно-истоковую.

Обозначим дуговые переменные через , положив и>у =1, если (¡, ^ выполняется (( 1, .О е Е), и м>у = 0 — в противном случае. Узловые переменные и,, =1 (1 е V), если I активируется Иначе — му = 0, причем иг= 1, т.е источник всегда активируется. Тогда условия базовой СЕЛТ-подобной узловой логики ((а) и (б)) представляются в следующем виде:

^wLl>X;u,, <.eV4r}), (1)

£ wkl < x; + M,u, , где M, > -x; AieV /{r}), (2)

(ieWS) (3)

Каждая реализация сетевой модели может быть соотнесена с множеством выполняемых операций процесса (выполняемых действий сети) или с функцией w Е —> {0,1},(0,у) G Е), значения которой задаются как w((i, j)) = wv=l, если (i, j) выполняется, и - 0, иначе

Очевидно, что если некоторая w-я реализация процесса задана, то как узловые, так и дуговые переменные для этого случая специфицированы и можно говорить о допустимой реализации процесса, если w удовлетворяет условиям GERT-подобной узловой логики Тогда е = {w . Е —» {0, 1}| wv удовлетворяет (1)-(3); (г, j) е Е }, и е — множество всех допустимых реализаций процесса.

Если в GERT-сети для формирования процессов, обозначить вес дуги (i, j) g Е как длительность dy соответствующей операции, то dw — длительность w-й реализации процесса, т е время, требуемое для исполнения всех операций (г, ]) при wtJ = 1. Каждая операция процесса начинается в наиболее ранний t', возможный при данной w-й реализации рассматриваемого алгоритма, срок. В этом случае необходимо минимизировать dw при условиях w активирует s; (w е е). Через е* .={ w е 8 | w активирует s} обозначим множество успешных реализаций процесса.

Для е* * 0 d* = mm dw (4)

wee

соответствует минимальному значению целевой функции задачи

Рассматривая моменты t, как компоненты вектора временной развертки процесса, которые удовлетворяют (tr tr dv) wtJ > 0, (i,f)eE,t,> 0, / eV\{r}, tf= 0, можно утверждать, что для некоторой w-й реализации (w ее*), t,w отвечают этим ограничениям, а самые ранние t' удовлетворяют им для соответствующей минимальной we £*. Соответствующая оптимизационная задача при выполнении ограничений вектора временной развертки имеет вид: Минимизировать max {(*,*+ dv) wtJ}

('j)eE

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

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

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

Росту функциональных возможностей системы GERT способствует применение моделей в несколько сотен или более дуг (или узлов) Однако при использовании топологического уравнения Мейсона канонического вида с увеличением размерности сети экспоненциально возрастает число петель г-х порядков, г=1, ,п Для определения плотности распределения вероятностей GERT-сети используется модификация численного метода нахождения закона распределения выходной величины GERT-сети, для которой трудоемкость решения задачи характеризуется полиномом второй степени относительно числа дуг GERT-сети

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

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

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

На основе анализа полученных моделей и известных методов псевдобулевой оптимизации, в качестве методов решения оптимизационных задач определены метод изменяющихся вероятностей (МИВЕР) и метод ветвей и границ.

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

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

1. Данные методы предложены изначально для задач с ограничениями

и

вида X х, = const , где п — размерность задачи.

i=i

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

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

Чтобы избавиться от перечисленных недостатков, в схему МИВЕР внесены изменения

1. Построен новый алгоритм изменения вероятностей аддитивное изменение вероятностей заменено мультипликативным в соответствии с формулой P,L+' = hpkt , где к — номер шага, р, — i-я компонента вектора вероятностей, h — коэффициент изменения вероятностей, что позволяет алгоритму быстрее выходить к точкам, близким к оптимуму.

2. При таком подходе при увеличении числа шагов (>100) компоненты вектора вероятностей принимают значения близкие к 0 или 1 (<0,01 или >0,99), в следствие чего, алгоритм генерирует одну и ту же точку — движение к оптимуму прекращается. Для устранения этого недостатка периодически (на каждом шаге или через несколько шагов) некоторому количеству компонент

вектора вероятностей присваивается значение, равное средней вероятности

п

Рч>=Т1Р,/П

1=1

Однако, при случайном выборе нескольких переменных для замены соответствующих компонент вектора вероятностей изменяется средняя вероятность при средней вероятности <0,5 после модификации она увеличивается (М{рс/+/}> рсрк ) и наоборот Таким образом, затрудняется адаптация по средней вероятности Во избежание этой ситуации мы должны либо нормировать вектор после модификации, приводя среднюю вероятность к прежнему значению, либо выбирать точки, где р,к<рсрк и те, где рк>р<у с различными вероятностями, такими, что математическое ожидание средней вероятности после модификации равно ее исходному значению (М{рс./+/}=рсрк) Этот подход и был применен при построении алгоритма

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

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

3. Для учета специфики условной оптимизации было реализовано три стратегии.

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

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

л

Zaux*

__У I

1 don ¿_j ,

J-1

Здесь atJ — коэффициент при i-й переменной в j-м ограничении, bj — правая часть j-го ограничения Суммирование производится по всем ограничениям, не выполненным в точке X. В дальнейшем (на этапе изменения вероятностей) рассматриваются не исходные сгенерированные точки, а

соответствующие найденные §геес!у-алгоритмом точки из области допустимых решений,

- применение метода штрафов целевая функция принимает вид Р(Х)-Рдоп(Х)

В работе были получены результаты как для метода штрафов, так и для поиска граничных точек greedy-aлгopитмoм

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

Модификация алгоритма требуется в силу следующих причин

- целевая функция в нашем случае максимизируется, а ограничения имеют как знак ">", так и "<",

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

- алгоритм работает не с вектором переменных, а с их матрицей пхт,

т

можно выделить особо ограничения Х!*» ~ * > 1= 1» >и> используя в

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

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

п т

Запишем ограничения в виде ~Укгде к — номер

,=1

ограничения, у*. — новая вспомогательная переменная

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

I Пусть д:у — свободная переменная, равная 1 Рассмотрим ограничения, коэффициенты при переменных в которых положительны. Если остальные ограничения выполняются (у>0), но не выполняется одно из этих ограничений, то присвоение данной переменной нулевого значения не даст допустимого решения Отсюда следует, что переменные, находящиеся в одном столбце с данной переменной, не должны принимать значение 1. Следовательно,

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

2 Обозначим через s<T> множество свободных столбцов переменных, для которых тест не выполняется. В данных столбцах рассмотрим только переменные, равные 1 Рассмотрим те ограничения, которые на данном шаге не выполняются (у<т>< 0), и коэффициенты при переменных в которых отрицательны Пусть хотя бы для одного из этих ограничений I Hfl,, I < I у(Т> I, ie sm, где ац — значение коэффициента при (ij)-fi переменной в данном ограничении Тогда значения всех переменных множества s(T> должны

<Т)

оставаться равными исходным, и частичное решение и считается прозондированным

3 Пусть sm — непустое множество (если оно пустое, то допустимых решений больше нет). Для каждой равной единице переменной этого множества вычислим v,<T> = X min { 0, у(Т> - ац] Здесь суммирование ведется по всем ограничениям, а1} — значение коэффициента в ограничении при (ij)-й переменной

Для ветвления на следующем шаге выбираем к-ю переменную, для которой vkm= max {v,<T>}

Если vk<T> =0, то объединение условия х^=0 с частичным решением и<т> дает допустимое решение со значением целевой функции большим, чем текущее значение нижней границы. При этом такое решение считается прозондированным

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

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

Тестирование алгоритмов на практических задачах выявило, что:

- время работы аддитивного алгоритма при размерности задачи 146 более чем в 90-200 раз больше, чем алгоритма схемы МИВЕР (по схеме МИВЕР выполнялось 150 шагов алгоритма с генерацией 30 точек на каждом шаге);

- аддитивный алгоритм дал точные решения, которые превосходили решения, полученные МИВЕР, на 0,3-2,4% (размерность задачи 146);

- вычислительная сложность метода ветвей и границ существенно зависит от ограничений, при изменении ограничений время выполнения варьировалось от 180 до 390 минут.

- с ростом размерности задачи до 548 аддитивный алгоритм не позволил найти допустимое решение в течение 20 часов, в то время, как МИВЕР давал решения за 10 минут для каждой задачи этой размерности; при увеличении времени счета до 8 часов полученные МИВЕРом решения улучшались не более чем на 1,5%.

Таким образом, предложенный алгоритм схемы МИВЕР можно считать эффективным для решения рассмотренных оптимизационных задач

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

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

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

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

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

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

Аддитивный алгоритм метода ветвей и границ адаптирован для решения рассматриваемого класса задач, проведена оценка его эффективности

Основные положения диссертации опубликованы в следующих работах.

По списку ВАК.

1. Ермолаева Л В Ресурсно-временной анализ при составлении производственных расписаний / Л В.Ермолаева // Системы управления и информационные технологии - 2007 - № 3.2(29) - С. 214-223.

2 Ермолаева Л В. СЕЯТ-сетевой анализ производственных процессов / Л В Ермолаева, С.И.Сенашов // Вестник СибГАУ / Красноярск. СибГАУ, 2007-Вып 3(16)-С 101-110

Остальные публикации.

3. Ермолаева Л.В Одноресурсные модели детерминированного формирования распределенных процессов/ Л В.Ермолаева И Актуальные проблемы науки в России Выпуск IV. мат-лы всероссийской научно-практической конференции / Новокузнецк. КИИУТ, 2007 - С. 115-117.

4. Ермолаева Л.В. СеП-сетевая модель формирования производственных процессов/ Л В Ермолаева // Управление стратегией развития производства: Заочная электронная конференция РАЕ, 2006

5. Ермолаева Л В. Модель планирования производственной программы конверсионного предприятия по выпуску гражданской продукции/ Л.В Ермолаева // Управление стратегией развития производства Заочная электронная конференция РАЕ, 2007.

6 Ермолаева Л.В. Формирование производственной программы при мелкосерийном производстве/ Л В Ермолаева // Управление стратегией развития производства: Заочная электронная конференция РАЕ, 2006.

7. Ермолаева Л.В Использование циклических альтернативных сетевых моделей при проведении ресурсно-временного анализа производственных расписаний/ Л В Ермолаева // ИННОВАТИКА-2007: мат-лы международной научной конференции / Ульяновск- УГУ, 2007 - С. 78-79.

8. Ермолаева Л В. Ресурсно-временной анализ производственных процессов на основе циклических альтернативных сетевых моделей/ Л.В.Ермолаева // Методы и средства управления технологическими процессами МСУПТ-2007. мат-лы IV международной конференции / Саранск МГУ, 2007.-С 87-90

9 Ермолаева Л В Применение информационных систем в производстве/ Л В Ермолаева // Теория и практика коммерческой деятельности- мат-лы VII региональной конференции / Красноярск: КГТЭИ, 2005 - С. 40-45.

10 Ермолаева Л В. Моделирование планирования производственных процессов предприятий ВПК в условиях конверсии / Л.В.Ермолаева // Вестник НИИ СУВПТ,- 2005 - Вып. 3(17) - С 94-101.

11 Ермолаева Л В Методы решения задачи оптимизации загрузки технологического оборудования предприятия / Л.В.Ермолаева // Вестник НИИ СУВПТ/Красноярск НИИ СУВПТ, 2006-Вып. 7(21) - С 176-184

Ермолаева Любовь Викторовна Оптимизационные модели GERT - сетевого планирования и управления производственными процессами

Автореферат

Подписано к печати 27 09 2007 Формат 60x84/16 Бумага писчая Печ Л 1.0 Тираж 100 экз Заказ №

Отпечатано Технический центр ГОУ ВПО КГТЭИ 660075, г Красноярск, ул. Л.Прушинской, 2

Введение.

1. ДЕТЕРМИНИРОВАННЫЕ МОДЕЛИ ФОРМИРОВАНИЯ ПРОИЗВОДСТВЕННЫХ ПРОГРАММ

1.1. Формальная модель задачи объемно-календарного планирования производства.

1.2. Формальная модель задачи распределения производственной программы предприятия по плановым периодам.

1.3. Задачи формирования производственной программы при мелкосерийном производстве.

1.4. Модели планирования финансирования выполнения производственных программ.

2. МОДЕЛЬНЫЕ КОМПОНЕНТЫ СТОХАСТИЧЕСКОЙ СТРУКТУРЫ ПРОИЗВОДСТВЕННЫХ ПРОЦЕССОВ

2.1. Модельные средства детерминированного формирования распределенных процессов.

2.1.1. Классификация моделей.

2.1.2. Одноресурсные модели.

2.1.3. Мультиресурсные модели.

2.1.4. Периодичные задачи при формировании планов.

2.1.4.1. Ограничения на классы ресурсов.

2.1.4.2. Периодичные задачи с бинарным частотным распределением.

2.1.4.3. Периодичные задачи с независимым распределением частоты.

2.1.4.4. Учет пределов.

2.2. Стохастическое представление моделей формирования.

2.2.1. вЕЯТ-сетевая модель стохастической структуры.

2.2.2Минимизация затрат ресурсов.

2.2.3. Случайные акции при реализации процессов.

2.2.4. Многократное исполнение операций.

2.2.5. Минимизация по времени.

2.3. Стохастическая модель определения нормативных времен выполнения операций в условиях неопределенности.

2.3.1. СЕИТ-сетевое представление моделей.

2.3.2. Определение вероятностных нормативных времен для процессов, реализуемых в условиях неопределенности.

3. АЛГОРИТМЫ РЕШЕНИЯ ЗАДАЧ ОПТИМИЗАЦИИ ЗАТРАТ

РЕСУРСОВ И ВРЕМЕНИ РЕАЛИЗАЦИИ

3.1. Анализ задач оптимизации.

3.2. Метод изменяющихся вероятностей.

3.3. Применение метода ветвей и границ.

Актуальность. Современная экономическая ситуация диктует жесткие требования участникам рыночных отношений. Выживают только высокоорганизованные предприятия, в основу управления которыми положен принцип быстрой реакции на непрерывно изменяющиеся требования рынка. Мировая практика показала, что динамичные и гибкие производства строятся на базе современных информационных систем управления класса MES (Manufacturing Execution System - производственные исполнительные системы) [10, 30-32, 51, 54-63]. Развернутым смысловым определением MES систем, соответствующим отечественной практике и терминологии (АСУ ПП - автоматизированные системы управления производственными процессами), можно считать следующее: системы оперативного планирования, оптимизации и управления производственными процессами.

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

Диссертационная работа посвящена построению математического аппарата расчета производственных расписаний и распределения ресурсов различного характера. Данный инструментарий может быть применен в системах класса MES. Его основой является циклическая стохастическая сетевая модель (GERT-сеть) [33-35, 64-66], являющаяся обобщением таких методов сетевого планирования как метод критического пути, PERT -сетей, обобщенных сетевых моделей [50-53, 67-76].

Выбор вЕИТ-сетей как основы для разработки алгоритмов ресурсно-временного анализа производственных процессов обоснован тем, что по сравнению со своими предшественниками СЕЯТ-сеть позволяет использовать многократное имитационное моделирование производственных процессов, временные параметры и внутренние логические связи которых могут иметь стохастическую природу.

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

Указанная цель определила необходимость решения следующих задач.

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

2. Разработка модельных средств детерминированного формирования распределенных производственных процессов.

3. Стохастическое представление моделей формирования производственных процессов.

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

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

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

Научная новизна работы.

1. Разработана многокомпонентная сетевая модель с унифицированной СЕЯТ-подобной узловой логикой для формального представления и автоматизированного формирования операций распределенных производственных процессов.

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

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

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

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

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

Апробация работы. Результаты диссертационного исследования обсуждались на международной научно-практической конференции «Математическое моделирование в образовании, науке и производстве»; Тирасполь, 2001, на Всероссийской научно-технической конференции «Перспективные материалы, технологии, конструкции, экономика», Красноярск, 2003, на II конференции «Фундаментальные и прикладные исследования», Рим, 2004, на III Международной конференции «Инновационные процессы в управлении предприятиями и организациями», Пенза, 2004, на заочной электронной конференции Российской академии естествознания 20-25 февраля 2005, на IV Всероссийской конференции по финансово-актуарной математике и смежным вопросам, Красноярск, 2005, на научно-технических советах и научных семинарах НИИ СУВПТ и ЦКБ «Геофизика».

Основные результаты диссертации опубликованы в работах [72-82].

1. Дегтерев Д.А. Модельное и алгоритмическое обеспечение объемно-календарного планирования на предприятиях ВПК в условиях конверсии / Д.А.Дегтерев // Дис. на соиск. уч. ст. канд. техн. наук / Красноярск: НИИ СУВПТ, 2003,- 118 с.

2. Ильина Т.Р. Модели и алгоритмы оптимизации загрузки ресурсов в условиях мелкосерийного производства / Т.Р.Ильина // Дис. на соиск. уч. степени канд. техн. наук. / Красноярск: НИИ СУВПТ, 2001.- 149 с.

3. Семенкина О.Э., Формализация задачи планирования загрузки ресурсов мелкосерийного производства / О.Э.Семенкина, Т.Р.Ильина, С.П.Коробейников // Интеллектуальные технологии и адаптация / Красноярск: НИИ СУВПТ, 1999- С. 31-40.

4. Семенкина О.Э. Метод обобщенного локального поиска для задач принятия решений в управлении сложными системами / О.Э.Семенкина // Дис. на соиск. уч. степени доктора техн. наук / Красноярск: НИИ СУВПТ, 2002.- 330 с.

5. Сумароков А.Д. Совершенствование управления и принятия решений по инновационной деятельности предприятий ВПК / А.Д.Сумароков // Дис. на соиск. уч. степени канд. техн. наук / Красноярск: СибГАУ, 2005. 129 с.

6. Внедрение и управление проектами. Электронный ресурс. Режим доступа: www.pmforum.org,www.choice.da.ru.

7. Абдулаев Д.А. Моделирование локальных вычислительных сетей с учетом вероятностно-временных характеристик / Д.А.Абдулаев, У.Б.Амирсаидов // Автоматика и вычислительная техника. 2004. № 3. - С. 151-160.

8. Емельянов C.B. Технология системного моделирования. / С.В.Емельянов, Е.Ф.Аврамчук.- М.: Машиностроение; Берлин: Техник, 1988. 520 с.

9. Алимханов А.М. Обзор современных методологий автоматизированного управления производством / А.М.Алимханов, Н.Н.Джиоева // Вестник НИИ СУВПТ.-./ Красноярск: НИИ СУВПТ. 2003.-Вып. 12.-С. 111-120.

10. Антамошкин А.Н. Оптимизация функционалов с булевыми переменными / А.Н. Антамошкин. Томск: Изд-во Том. ун-та, 1987. - 104 с.

11. Воеводин В.В. Математические модели и методы в параллельных процессах / Воеводин B.B. М.: Наука, 1986. - 328 с.

12. Методы анализа и синтеза структур управляющих систем / под ред. Б.Г.Волика.- М.: Энергоатомиздат, 1988. 296 с.

13. Введение в системный анализ / под ред. JI. А. Петросяна.- JL: ЛГУ, 1988. 232 с.

14. Зыков A.C. Роль информационных технологий на предприятии / А.С.Зыков // Современные проблемы информатизации в технике и технологиях: Сб. трудов. Вып. 9. Под ред. д.т.н., проф. О.Я. Кравца.-Воронеж: Изд-во «Научная книга», 2006, с. 228-229.

15. Калянов Г.Н. CASE-технологии: консалтинг в автоматизации бизнес-процессов / Г.Н.Калянов. М.: Горячая линия-Телеком, 2002. - 418 с.

16. Калянов Г.Н. Современные CASE-технологии / Г.Н.Калянов. М.: ИПУ, 2003. - 397 с.

17. Ковалев И.В. Моделирование и оптимизация параллельных процессов в информационно-управляющих системах / И.В.Ковалев, Р.Ю.Царев. Красноярск: ИПЦ КГТУ, 2005. - 111 с.122

18. Колесников С. Из истории автоматизации методологий управления предприятием / С.Колесников // Открытые системы.- 2006. № 4. - С. 44-56. http://www.osp.ru/os/1999/04/09.htm

19. Коржов В. Адекватные системы / В.Коржов // Открытые системы. -2006.-№ 12-С. 118-124.

20. Корячко В.П. Численный метод нахождения закона распределения выходной величины GERT-сети / В.П.Корячко // Информационные технологии. 2006.- № 7.- С. 16-21.

21. Ковальчук Е.Р. Основы автоматизации машиностроительного производства/ под ред. Ю.М. Соломенцева.- М.: Высш. шк., 1999. 349 с.

22. Руководство по методологии ABC. М.: Метатехнология, 1997. 230с.

23. Системный анализ: Проектирование, оптимизация и приложения. В 2 т./ под общ. ред. Антамошкина А.Н. Красноярск, CAA, 1996. 206 с.

24. Слепцов А.И. Автоматизация проектирования управляющих систем / Слепцов А.И. Киев: Техника, 1996. - 393 с.

25. Тихонов А.Н. Методы и системы поддержки принятия решений / А.Н.Тихонов, В.Я. Цветков М.: МАКС Пресс, 2001.-314 с.

26. Феллер В. Введение в теорию вероятностей и ее приложения. В 2-х томах. Т. 2.: пер. с англ. / Феллер В. М.: Мир. 1984. 738 с.

27. Филлипс Д. Методы анализа сетей / Д.Филлипс, Д.Гарсиа-Диас -М.: Мир, 1984.-496 с.

28. Шибанов А.П. Нахождение закона распределения выходной величины GERT-сети большой размерности / А.П.Шибанов // Информационные технологии.- 2007. № 1. - С. 42-45.

29. Яппаров Т.Г. Комплексные автоматизированные системы управления предприятием / Т.Г.Яппаров // Средства и системы компьютерной автоматизации сервер АСУТП. Электронный ресурс. -Режим доступа: http://www/asutp.ru/?p=600330.

30. CSRP. Электронный ресурс. Режим доступа: www.symix.com. Русский перевод по адресу: csrp@socap.msk.ru.

31. MRP-ERP. Электронный ресурс. Режим доступа: plant.da.ru (http://www.geocities.com/WallStreet/2907/), erp.da.ru.

32. Neumann К. Stochastic Project Network / K.Neumann // Lecture Notes in Economics and Mathematical Systems, No. 34, Springer Verlag, 1995. 327 p.

33. Neumann, K. An Optimality Equation for Stochastic Decision Networks. Wiss / K.Neumann // Zeitschrift Techn. Hochschule Leipzig, No. 8, 1984. Pp. 7987.

34. GERT: Graphical Evaluation and Review Technique Part.l, Fundamentals / A.A.Pritsker // The Journal of Industrial Engineering (May 1966). -Pp. 67-101.

35. Supply Chain. Электронный ресурс. Режим доступа: www-rcf.usc.edu/~xin/supplychainbookmarks.htm.

36. Семенкин Е.С. Оптимизация технических систем / Е.С.Семенкин, О.Э.Семенкина, С.П.Коробейников Красноярск: Сибирский институт бизнеса, управления и психологии, 1996. - 285 с.

37. Кузнецов А.В. Высшая математика: Математическое программирование / А.В. Кузнецов.: — Мн.: Выш. шк., 2001. — 351с.

38. Хедли Д. Нелинейное и динамическое программирование / Д.Хедли — М.:Мир, 1967. —213с.

39. System Analysis, Design and Optimization. An Introduction/General Editing by A.Zhilinskas. Krasnoyarsk: Krasnoyarsk Spase Technology University, 1993. - 203 p.

40. Берсенев В.А., Гимади Э.Х., Дементьев B.T. Экстремальные задачи стандартизации / В.А.Берсенев, Э.Х.Гимади, В.Т.Дементьев. Новосибирск: Наука, 1978. - 333с.

41. Деордица Ю.С. Исследование операций в планировании и управлении / Ю.С.Деордица, Ю.М.Нефедов. Киев: Выща Школа, 1991. -79с.

42. Системы оперативного управления производством Электронный ресурс. Режим доступа: http://www.mesa.ru/.

43. Маклаков С. Имитационное моделирование с Arena Электронный ресурс. Режим доступа: http://www.interface.ru/fset.asp?Url=/sysmod/arl.htm.

44. Воропаев В.И., Гельруд Я.Д. Циклические альтернативные сетевые модели и их использование при управлении проектами Электронный ресурс. Режим доступа: http://www.sovnet.ru/pages/casml.doc.

45. Дубова. Н. Системы управления производственной информацией / Н.Дубова // Открытые системы. 2006. - №3. С. 18-26.

46. Абакумов. В. Система сопровождения проектных данных IMAN / В.Абакумов. // Открытые системы. 2006. - № 5. -С. 76-83.

47. Краюшкин В. Система Optegra управление производственными данными / В.Краюшкин // Открытые системы. - 2007. - №1 - С. 54-60.

48. Клишин В. Интегрированные технологии CV / В.Клишин,B.Климов, М.Пирогова // Открытые системы. 2005. - №2. - С.42-50.

49. Куцевич И.В. Введение в LIMS / И.В.Куцевич // Мир компьютерной автоматизации. 2002. - № 4. - С. 83-89.

50. Colin Thurston, Integrating LIMS Into a Large-Scale Manufacturing Environment American Laboratory.- March 2004.- Pp. 33-50.

51. Нуцков Ю.В. Интеграция LabWare LIMS и SAP R/3 QM / Ю.В.Нуцков, Б.Хиллхауз // Мир компьютерной автоматизации.- 2003.- № 4.C.101-111.

52. Синенко О.В. Подход к анализу производственных процессов и созданию комплексных систем управления ресурсами / О.В.Синенко, Н.А.Куцевич // Мир компьютерной автоматизации, 2006. № 4. - С. 56-71.

53. Гребнев С.А. Современные подходы к интеграции АСУ / С.А.Гребнев, В.И.Кузякин, Синенко // Мир компьютерной автоматизации, 2005. № 5. - С.101-111.

54. Шибанов А.П. Нахождение плотности распределения времени исполнения GERT-сети на основе эквивалентных упрощающих преобразований / А.П.Шибанов // Автоматика и телемеханика, 2006. № 2. -С. 117-126.

55. Корячко В.П. Численный метод нахождения закона распределения выходной величины GERT-сети / В.П.Корячко, А.П.Шибанов, В.А.Шибанов Информационные технологии, 2004. № 7. - С. 16 - 21.

56. Прицкер А. Введение в имитационное моделирование и язык СЛАМII / А.Прицкер: М.: Мир, 1987. - 646 с.

57. Мазур И.И. Управление проектами / И.И.Мазур, В.Д.Шапиро // Справочник для профессионалов. Москва: Высшая школа, 2001. 875 с.

58. Шапиро В.Д. Project management. Управление проектами / В.Д.Шапиро // Толковый англо-русский словарь-справочник. Москва: Высшая школа, 1999. 379 с.

59. Решке X., Шелле X. Мир Управления Проектами / Х.Решке, Х.Шелле. Москва: Алане, 1994. - 303 с.

60. Voropaev V.I. Project Management in Russia / V.I.Voropaev. N.Y.: PMI, 1997. - 240 p.

61. Бурков B.H. Как управлять проектами: научно-практическое издание / В.Н.Бурков, Д.А.Новиков. М.: СИНТЕГ, 1997. - 188 с.

62. Воропаев В.И., Гельруд Я.Д. Циклические альтернативные сетевые модели и их использование при управлении проектами. Электронный ресурс. Режим доступа: http://sovnet.ru/pages/public/casm.htm.

63. Воропаев В.И., Гельруд Я. Д. Применение циклических альтернативных сетевых моделей при управлении проектами. Электронный ресурс. Режим доступа: http://sovnet.ru/pages/public/casm.htm.126

64. Воропаев В.И., Гельруд Я.Д. Использование ЦАСМ при управлении проектами. Электронный ресурс. Режим доступа: http://sovnet.ru/pages/public/casm.htm.

65. Авербах Л.И., Воропаев В.И., Гельруд Я.Д. Планирование работ проекта с учетом приведенной стоимости. Электронный ресурс. Режим доступа: http://sovnet.ru/pages/public/casm.htm.

66. Сопов Е.А. Эволюционные алгоритмы моделирования и оптимизации сложных систем / Е.А.Сопов // Дис. на соиск. уч. ст. канд. техн. наук / Красноярск: СибГАУ, 2004. 118 с.

67. Масич И.С. Поисковые алгоритмы решения задач условной псевдобулевой оптимизации / И.С.Масич // Дис. на соиск. уч. ст. канд. физ.-мат. наук / Красноярск: СибГАУ, 2004,126 с.

68. Попов A.A. Оптимизационные методы формирования мультиверсионного программного обеспечения критичных по надежности систем управления / А.А.Попов // Дис. на соиск. уч. ст. канд. техн. наук / Красноярск: НИИ СУВПТ, 2002,196 с.

69. Ермолаева Л.В. GERT-сетевая модель формирования производственных процессов / Л.В.Ермолаева // Управление стратегией развития производства: Заочная электронная конференция РАЕ, 2006.

70. Ермолаева Л.В. Модель планирования производственной программы конверсионного предприятия по выпуску гражданской продукции / Л.В. Ермолаева // Управление стратегией развития производства: Заочная электронная конференция РАЕ, 2007.

71. Формирование производственной программы при мелкосерийном • производстве / Л.В.Ермолаева // Управление стратегией развитияпроизводства: Заочная электронная конференция РАЕ, 2006.

72. Ермолаева Л.В. Применение информационных систем в производстве / Л.В.Ермолаева // Теория и практика коммерческой деятельности: мат-лы VII региональной конференции./ Красноярск: КГТЭИ, 2005. С. 40-45.

73. Ермолаева Л.В. Моделирование планирования производственных процессов предприятий ВПК в условиях конверсии / Л.В.Ермолаева // Вестник НИИ СУВПТ. Красноярск: НИИ СУВПТ.- 2005.- Вып. 3(17). С. 94101.

74. Ермолаева Л.В. Методы решения задачи оптимизации загрузки технологического оборудования предприятия / Л.В.Ермолаева // Вестник НИИ СУВПТ / Красноярск: НИИ СУВПТ, 2006.- Вып. 7(21). С. 176-184.

75. Ермолаева Л.В. Ресурсно-временной анализ при составлении производственных расписаний / Л.В.Ермолаева // Системы управления и информационные технологии 2007,- № 3.2(29).- С. 214-223.

76. Ермолаева Л.В., Сенашов С.И. GERT-сетевой анализ производственных процессов / Л.В.Ермолаева, С.И.Сенашов // Вестник СибГАУ / Красноярск: СибГАУ, 2007.- Вып. 3(16). С. 101-110.