Электронная библиотека диссертаций и авторефератов России
dslib.net
Библиотека диссертаций
Навигация
Каталог диссертаций России
Англоязычные диссертации
Диссертации бесплатно
Предстоящие защиты
Рецензии на автореферат
Отчисления авторам
Мой кабинет
Заказы: забрать, оплатить
Мой личный счет
Мой профиль
Мой авторский профиль
Подписки на рассылки



расширенный поиск

Разработка программного обеспечения САПР средств управления проектом на основе теории графов Кожин Павел Борисович

Разработка программного обеспечения САПР средств управления проектом на основе теории графов
<
Разработка программного обеспечения САПР средств управления проектом на основе теории графов Разработка программного обеспечения САПР средств управления проектом на основе теории графов Разработка программного обеспечения САПР средств управления проектом на основе теории графов Разработка программного обеспечения САПР средств управления проектом на основе теории графов Разработка программного обеспечения САПР средств управления проектом на основе теории графов Разработка программного обеспечения САПР средств управления проектом на основе теории графов Разработка программного обеспечения САПР средств управления проектом на основе теории графов Разработка программного обеспечения САПР средств управления проектом на основе теории графов Разработка программного обеспечения САПР средств управления проектом на основе теории графов Разработка программного обеспечения САПР средств управления проектом на основе теории графов Разработка программного обеспечения САПР средств управления проектом на основе теории графов Разработка программного обеспечения САПР средств управления проектом на основе теории графов
>

Диссертация - 480 руб., доставка 10 минут, круглосуточно, без выходных и праздников

Автореферат - бесплатно, доставка 10 минут, круглосуточно, без выходных и праздников

Кожин Павел Борисович. Разработка программного обеспечения САПР средств управления проектом на основе теории графов : диссертация ... кандидата технических наук : 05.13.12, 05.13.11 / Кожин Павел Борисович; [Место защиты: Моск. гос. гор. ун-т].- Москва, 2009.- 146 с.: ил. РГБ ОД, 61 09-5/2041

Содержание к диссертации

Введение

Глава 1. Система комплексной автоматизации (СКА) промышленного предприятия

1.1. Проблемы комплексной автоматизации промышленных предприятий в России

1.2. Оптимизация СКА промышленного предприятия на производственном уровне стр. 31

Глава 2. Информационная модель проекта (ИМП)

2.1. Методы представления ИМП. Сети Петри

2.2. Процедура порождения функционально-сетевой модели (ФСМ) проекта на осове ИМП, представленной в виде расширенной сети Петри

2.3. Диаграмма Ганта стр. 41

Глава 3. Интеллектуализация средств управления проектом

3.1. Ресурсное обеспечение проекта

3.2. Ресурсный рейтинг стр 54

3.3. Динамический синтез диаграмм Ганта для проекта, использующего однородные ресурсы

3.3.1. Алгоритм синтеза оптимальной диаграммы Ганта при использовании однородных ресурсов

3.4. Кластеризация ФСМ проекта по типам используемых разнородных ресурсов. Динамический синтез диаграмм Ганта для проекта, использующего разнородные ресурсы

3.4.1. Алгоритм синтеза оптимальной диа граммы Ганта при использовании разно- стр. 70

родных ресурсов

Глава 4. Разработка программного обеспечения САПР средств управления проектом в рамках СКА промышленного предприятия стр. 74

4.1. Информационное обеспечение САПР интеллектуального инструментария плани- стр 81 рования работ и ресурсов

4.2. Программное обеспечение САПР интеллектуального инструментария плани- стр# 88 рования работ и ресурсов

4.3. Планирование операций автоматизированной транспортно-складской системы стр. 116 (АТСС) стр. 133

4.4. Оптимальное принятие проектных решений в условиях риска

Заключение стр. 136

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

Введение к работе

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

Оптимизация СКА промышленного предприятия на производственном уровне

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

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

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

Из вершины х в вершину у ведет дуга, если и только если х и у находятся в отношении инцидентности - xFy. Сеть Петри - динамическая сеть, в ней местам приписываются специальные разметки, моделирующие выполнение условия, и с сетью связывается понятие ее функционирования, изменяющего эти разметки (условия) в результате так называемых срабатываний переходов. В графическом представлении сети выполнение условий изображается проставлением п фишек (маркеров) в соответствующее место, где п 0 - емкость условия переходами, F с РхТиТхР - отношение инцидентности, (P,T,F) - конечная сеть, для которой выполнены следующие условия: РпТ=0, (F*0)A(VxGPuT,3yGPuT:xFyvyFx) (2) и Ур„ЛєР: (рГ=рв2х)л(рГ=рГ)=>(Р, =Рг) (3)

W: F->N\{0} и М0: Р-> N - две функции, называемые соответственно кратностью дуг и начальной разметкой. Первая сопоставляет каждой дуге число п>0 (кратность дуги). Если п> 1, то в графическом представлении сети число п выписывается рядом с короткой чертой, пересекающей дугу. Сеть Петри, кратность всех дуг которой равна 1, называется ординарной. Вторая функция сопоставляет каждому месту р є Р некоторое число M0(p)eN (разметка места). В графическом представлении сети разметка места р изображается помещением в вершину-кружок числа М0(р) или соответствующего числа точек (фишек).

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

Разметка сети ./V - это функция М: Р -»N. Если предположить, что все места сети N строго упорядочены каким-либо образом, т.е. Р = (/?,,...,/?„), то разметку М сети (в том числе и начальную разметку) можно задать как вектор чисел М = (т^...,тп), Vi:(\

Процедура порождения функционально-сетевой модели (ФСМ) проекта на осове ИМП, представленной в виде расширенной сети Петри

Когда функционально-сетевая модель (ФСМ) проекта построена, перед руководством предприятия встает вопрос: какова продолжительность реализации проекта. Очевидно, что это время не может быть меньше суммы длительностей всех времен, взятых вдоль самого неблагоприятного пути из S0+ (начало ФСМ) в S (конец ФСМ). Отсутствие "возвратных" работ ("отрицательного времени") позволяет рассматривать ФСМ как частично упорядоченную систему {,}, : (VS,)(S0+ S, Sn ).

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

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

Вычисление критического времени сводится к применению рекурсивной процедуры: для события Sj вычисляется максимум суммы тах(Г(ЯЛ) + t{Sik,Sj)\ 5йєГ 5у (9) с последующим суммированием его со временем выполнения t(Sj) события Sj; полученное число сопоставляется с событием Sj: Г(5у ) = /(,)+ max(T(Sik) + t(Sik ,Sj)) (і о)

Здесь и ниже Т - время выполнения нескольких операций (событий), t - время выполнения одной операции (события).

События (операции), включенные в критический путь, называются критическими, невключенные — некритическими.

Резерв события представляет собой допустимое запаздывание, которое может быть допущено в наступлении работы Sj} или транспортной операции Slj=(Si,SJ) без изменения фиксированных сроков наступления критических событий и, в частности, конечного события S, соответствующего выполнению проекта. Полный резерв представляет собой максимальную допустимую отсрочку начала выполнения события (операции).

Если событие Sj некритическое, то оно представлено дважды - ожидаемым событием и максимально задержанным. Разность между началами (концами) этих величин равна полному временному резерву события At(Sj).

Доказано, что полный временной резерв At(Sj) события S, равен: Д №)-тт1п(s;,s-„)-(rmin(s;,s;)+тт.т(s;,s;))+t(s,) (11 где: Tmin(SJ ,S ) - критическое время сети [З1,1",S"]; Sf - на чальное, S - конечное события; Tmin(Sf,S7) - критическое время антисиндрома [Sf,S ]; Tmin(Sj ,Sn) - критическое время синдрома [ ,+ 5 „]; t($i) - время выполнения события St.

Синдромом C(S;)} порожденным вершиной v(«S(.) является граф Vn , состоящий из вершин v(Sj), v(S;) й v(Sj) v(Sn ) и дуг, соединяющих эти вершины. Антисиндромом С(І5.)5 порожденным вершиной v .) является граф Vt, , состоящий из вершин v(Sj), v(Sf ) v(Sj) v(Sl) . Аналогично вычисляется полный временной резерв At(Si,SJ) транспортной операции (S Sj): At(si ,Sj)=тт,п (s; ,s;)- t(s, ,Sj)-( Tmin (s; A-) + Tmin (sj ts )) (12) где: t(SnSj) - длительность транспортной операции (5,.,Sj); Tmia(Sf,S ) - критическое время антисиндрома C(Sj) работы /j Tmin(Sj S ) - критическое время синдрома C(Sj) работы

По найденным временным значениям синтезируем диаграмму Ганта.

При фиксированном начале и конце всех работ ФСМ однозначно определяет диаграмму Ганта. Диаграммой Ганта называется двумерная таблица, каждой строке которой взаимно однозначно соответствует событие (работа), столбцу -временной квант (минимальный для проекта отрезок времени), и если /-ое событие выполняется в у-ом кванте, то клетка (/, у) отмечается, например, штриховкой. Диаграмма Ганта используется для оптимального планирования ресурсов при выполнении работ, наглядного представления таких данных как: ход выполнения проекта, график рабочего времени, графики отпусков, использование оборудования, занятость помещений и другие.

Количество эквивалентных диаграмм Ганта, определяемых сетевым графом (ФСМ) равно произведению полных временных резервов всех работ и транспортных операций, при этом в каждом из сомножителей добавлена "единица": {Я, Я, - диаграмма Ганта}\ = П (А , ) + Vi&iS, , ) + 1) (і 3 ) I.J Диаграмма Ганта однозначно определяет необходимые для осуществления проекта ресурсы

Динамический синтез диаграмм Ганта для проекта, использующего однородные ресурсы

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

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

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

Типовой задачей экспертного прогнозирования является задача оценивания (вычисления рейтингов) альтернатив.

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

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

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

Для вычисления рейтингов воспроизводимых ресурсов, используемых на производственном проекте, воспользуемся методом попарного сравнения. Алгоритм реализации данного метода представляет собой процедуру построения каждым экспертом двоичной матрицы смежности, R — ІЛ/]„хл, определяющей бинарное отношение и во множестве альтернатив: «альтернатива а, лучше (важнее) альтернативы а,» - г(а,) г(ау), ги= 1, если /"(а,) r(a ) О в противном случае (14) где: г(а,), г(ау) - рейтинги альтернатив (т.е. ресурсов) соответственно; п - число альтернатив (количество типов используемых разнородных воспроизводимых ресурсов).

Для упорядочивания альтернатив возводим матрицу смежности R в степени 2,3, ... до тех пор, пока матрица достижимости = 2-і не будет содержать ни одного недиаго нального нулевого элемента. Если известен диаметр d(G) графа G = V,U , определяемого матрицей R, то максимальная степень, в которую возводится матрица смежности, равен диаметру этого графа (15) d{G) 1=1 Будем называть синдромом C(at) і-й альтернативы частичный граф G= V, графа G= V,U , V = {at І і = 1,2,...,«} 5 бинарное отношение определяет путь достижимости из г-й в у -ю (i j) вершину графа G.

Для каждого у-го эксперта и каждой альтернативы (я,-) строим синдром С(я,у), при этом альтернатива я,у имеет ми нимальный рейтинг. Анализируя синдром С{а )} с достоверностью D(a.j) получаем упорядочивание альтернатив. Рейтинг г (а 7-го эксперта оцениваем высотой / (#,) элемента Qj в соответствующем упорядоченном множестве альтернатив согласно графу G= V,o.

Под достоверностью В(а0) экспертизы при выбранном минимальном элементе а, будем понимать отношение мощности сигнатуры упорядоченного множества V Uy к мощности сигнатуры исходного графа G — V,U , заданного j-м экспертом -і (16) D(av) = \Uy\-U Очевидно, что путь [ amin, атах] упорядоченного множества является гамильтоновым. Рейтинг r{ak,aj) альтернативы яА, при выбранном минимальном элементе я,-, определяется формулой: r{ak,ai)=h(ak,al)-D(aij) (17) Окончательный рейтинг Кй,у) альтернативы я,, определенный 7-м экспертом, равен: _ п — (18) В общем случае, синдром С(а ) может содержать несколько гамильтоновых путей, началом которых является вершина #,у. При этом, выбираем экспертизу с максимальной достоверностью. Используя эту процедуру, проводим остальные экспертизы, назначая, последовательно, минимальным элементом один из (п — Y) оставшихся. Окончательно, выбираем экспертизу с максимальной достоверностью для у-го эксперта. Повторяем эту процедуру для (N— Ї) оставшихся экспертов, N - число экспертов. На практике, эксперты имеют разную компетентность. Коэффициент компетентности K(3j) у -го эксперта оценим величиной, обратной среднему квадратичному отклонению рейтингов У-го эксперта от их среднего значения:

Программное обеспечение САПР интеллектуального инструментария плани- стр# 88 рования работ и ресурсов

База данных блока интеллектуализации (БД БИ) (рис. 5) состоит из пяти таблиц: таблица проектов (PROJECTS), таблица операций (работ) (TASKS), таблица ФСМ (FSM), таблица типов воспроизводимых разнородных ресурсов (RE-STYPES) и таблица диаграмм Ганта (DGANTT). БД БИ может быть реализована в любой современной СУБД, поддерживающей экспорт и импорт таблиц в какой-либо из перечисленных ниже форматов: dBase, Lotus, Oracle, TXT, HTML, XML. Подробное описание таблиц базы данных БИ приведено в таблице 1.

Структура базы данных любой ЕРМ-системы схожа со структурой БД БИ. Единственное отличие БД ЕРМ-системы от БД блока интеллектуализации заключается в том, что БД ЕРМ-системы содержит в себе еще виды и параметры ресурсов, параметры визуализации диаграмм Ганта и некоторые системные параметры.

При импорте сетевого графика проекта из БД ЕРМ-системы в БД БИ передаются следующие данные, необходимые и достаточные для построения ФСМ проекта (при этом задействованы 4 таблицы БД БИ: PROJECTS, TASKS, FSM и RESTYPES): дата и время начала и окончания проекта, список операций (работ), с сопоставленными каждой операции временем ее выполнения, списком предшествующих операций и типом необходимых для ее реализации ресурсов. Также передаются краткое и полное наименования проекта. Синтез оптимальной диаграммы Ганта и ее последующий экспорт в БД ЕРМ-системы происходит с использованием ФСМ проекта, построенной в БИ, и таблицы DGANTT.

На случай, если БИ используется в отрыве от ЕРМ-системы, в качестве независимого инструмента оптимального планирования проекта, в нем предусмотрена возможность создавать и редактировать проекты (рис. 7).

Далее приводится подробное описание программной реализации в БИ шагов алгоритма синтеза оптимальной диаграммы Ганта.

Как уже отмечалось выше, экспортированный из ЕРМ-системы в БИ проект записывается в базе данных БИ в таб При редактировании поля "Краткое название проекта (16 символов)" работает фильтр по событию "Потеря фокуса (Lost Focus)", следящий за уникальностью мнемокодов (кратких названий) проектов в БД БИ. При редактировании даты и времени начала проекта также работает фильтр по событию "Потеря фокуса (Lost Focus)", обеспечивающий неравенство "Дата и время окончания проекта " "Дата и время начала проекта".

Практически во всех существующих на сегодняшний день ЕРМ-системах минимальная продолжительность временного кванта равна 1 минуте. Поэтому, при редактировании поля "Продолжительность временного кванта (в часах)" работает фильтр по событию "Потеря фокуса (Lost Focus)", г следящий за тем, чтобы продолжительность временного кванта была больше или равна 1 минуте (0,16 часа), и, конечно, меньше времени реализации проекта. При редактировании продолжительности любой операции (работы) проекта работает фильтр по событию "Потеря фокуса (Lost Focus)", обеспечивающий соотношение: 0 "Продолжительность операции (работы) " " Время реализации проекта". При выходе из формы редактирования проекта (нажатие кнопки "Выход") проверяется соответствие критического времени ФСМ проекта и времени его реализации.

Для удобства построения ФСМ проекта и последующей работы с ней создается массив gantt_post [Количество операций (работ), 7]. Здесь: 1-й столбец - идентификатор операции (работы), 2-й столбец - список последующих операций (работ) (получается из таблицы ФСМ, где каждой операции (работе) сопоставлен список предшествующих операций (работ)), 3-й столбец — продолжительность операции (работы) во временных квантах, 4-й столбец — признак стартовой ("S") или финишной ("F") операции (работы), 5-й

столбец - номер временного кванта, раньше которого не может начаться выполнение операции (работы), 6-й столбец - полные временные резервы некритических операций (работ) и 7-й столбец - идентификатор типа необходимых для реализации операции (работы) ресурсов. Очевидно, что на этапе построения ФСМ столбцы 5 и 6 пусты.

Похожие диссертации на Разработка программного обеспечения САПР средств управления проектом на основе теории графов