Содержание к диссертации
Введение
ГЛАВА 1. Анализ существующих методов сетевого планирования 8
1.1. Характеристика проекта и модели планирования и управления 8
1.2. Временные характеристики сетевого графика и алгоритм расчета 28
1.3. Учет неопределенности при расчете сетевых графиков 31
1.4. Постановка задачи исследования 32
ГЛАВА 2. Нечеткие числа, их свойства и характеристики 34
2.1. Арифметические операции и дефаззификация обобщенных гауссовых нечетких чисел 48
2.2. Сравнение нечетких обобщенных гауссовых нечетких чисел 54
ГЛАВА 3. Алгоритмы расчета и оптимизации сетевого графика с продолжительностями работ в форме обобщенных гауссовых нечетких чисел 61
3.1. Алгоритм расчета критических путей 61
3.2. Алгоритм расчета подкритического пути 66
3.3. Оптимизация сетевого графика 69
3.4. Алгоритм расчета GERT-сети 78
ГЛАВА 4. Программное обеспечение для расчета параметров сетевой модели 88
4.1. Программная реализация 88
4.2. Функциональные блоки программного комплекса 89
4.3. Интерфейсная часть программного комплекса 91
4.4. Результаты и анализ вычислительного эксперимента 95
Заключение 112
Список литературы 113
- Временные характеристики сетевого графика и алгоритм расчета
- Постановка задачи исследования
- Сравнение нечетких обобщенных гауссовых нечетких чисел
- Алгоритм расчета подкритического пути
Введение к работе
Актуальность темы. Важная особенность процессов принятия решений при реализации крупных проектов заключается в необходимости учета факторов неопределенности, порождаемых как влиянием внешней среды, так и использованием приближенной информации, в частности, полученной от экспертов. Продолжительное время классическим способом учета неопределенности являлась теория вероятностей. Отличительной особенностью планирования проектов и процессов с вероятностным временем выполнения операций является статистический подход к определению временных параметров модели. Основное предположение заключается в том, что время выполнения операции является случайной величиной, имеющей (5 -распределение, что позволяет вычислить вероятность выполнения проекта в заданный срок. Существенным недостатком данного подхода является невозможность получения аналитических выражений для характеристик проекта и невозможность приспособить известные алгоритмы поиска критического пути к вероятностным исходным данным. Другой наиболее известный способ учета неопределенности - применение аппарата нечетких множеств - также нашел свое применение в моделях сетевого планирования (Czamecki М.Т., Dinsmore Р.С, Fleming Q.W., Pennypacker J.S., Lientz В.P., Kerzner H., Новиков Д.А., Бурков B.H., Баркалов С.А., Рыбальский В.П., Позняков В.В., Голуб Л.Г. и др.). Основное преимущество данного подхода заключается в возможности построения аналитических выражений для временных характеристик проекта, при этом продолжительность операций задается в виде нечеткого числа, параметры которого оцениваются экспертом или определяются экспериментально. Проблема данного подхода заключается в выборе формы представления нечеткого числа, за счет чего может быть повышена степень адекватности и гибкость моделей, что важно для принятия управленческих решений.
Актуальность темы исследования определяется необходимостью разработки математических моделей, алгоритмов и программ для определения временных параметров проекта в условиях нечеткой неопределенности.
Работа выполнена в рамках одного из основных научных направлений ФГБОУ ВПО «Воронежский государственный технический университет» «Вычислительные комплексы и проблемно-ориентированные системы управления».
Цели и задачи исследования. Целью работы является разработка и исследование сетевых моделей и методов расчета их временных характеристик, основанных на представлении времени выполнения операций проекта в форме параметрических нечетких чисел.
Для достижения этой цели решались следующие задачи.
-
Анализ существующих подходов к расчетам сетевых моделей в условиях неопределенности.
-
Обоснование выбора обобщенных гауссовых чисел, определение для них арифметических операций и операции сравнения.
-
Разработка численных методов и алгоритмов расчета временных характеристик сетевой модели с продолжительностями операций, заданными в виде обобщенного нечеткого гауссова числа.
-
Разработка программного комплекса для моделирования сетевых графиков и проведение вычислительного эксперимента.
Методы исследования. При выполнении работы использовались основные положения и методы теории нечетких множеств, теории графов, численных методов, интервального анализа, объектно-ориентированного программирования.
Тематика работы. Содержание диссертации соответствует п. 3 «Разработка, обоснование и тестирование эффективных вычислительных методов с применением современных компьютерных технологий», п. 4 «Реализация эффективных численных методов и алгоритмов в виде комплексов проблемно-ориентированных программ для проведения вычислительного эксперимента», п. 8 «Разработка систем компьютерного и имитационного моделирования» Паспорта специальности 05.13.18 -«Математическое моделирование, численные методы и комплексы программ».
Научная новизна. В диссертации получены следующие результаты, характеризующиеся научной новизной:
-
арифметические операции и операции сравнения для обобщенных нечетких гауссовых чисел, отличающиеся параметрическим представлением и позволяющие определить аналитические выражения для временных характеристик сетевой модели;
-
алгоритмы расчета критического и подкритического путей сетевой модели с временами выполнения операций в виде обобщенного гауссова числа, позволяющие выявить такие операции проекта, которые должны быть в полной мере обеспечены ресурсами, и отличающиеся использованием операций интервальной арифметики на каждом а -срезе нечеткого числа;
-
метод расчета перераспределяемых ресурсов в алгоритме оптимизации нечеткой сетевой модели по времени, базирующийся на операциях над обобщенными гауссовыми числами и позволяющий за счет перераспределения ресурсов уменьшить критическое время проекта;
-
алгоритм расчета GERT-сетевой модели, позволяющий учитывать различные типы входов и выходов для каждого разрешающего узла, отличительной особенностью которого является задание времени выполнения операций в виде обобщенных гауссовых чисел;
-
структура программного комплекса, позволяющая за счет специальной подсистемы сформировать информационную среду для конкретной модели проекта для расчета параметров и оптимизации сетевых моделей с продолжительностями операций в виде обобщенных гауссовых чисел, включающая модули для реализации предложенных алгоритмов.
Практическая значимость работы заключается в расширении сферы применения методов сетевого планирования для оценки временных параметров проектов с продолжительностью операций в виде обобщенных гауссовых чисел, параметры которых позволяют обеспечить достоверность экспертной информации и, в конечном итоге, повысить эффективность планирования всего комплекса работ и обоснованность принимаемых решений по управлению реализацией проекта.
Реализация и внедрение результатов работы. Разработанный программный комплекс «Fuzzy Networks Graph» использовался в практической деятельности ОАО «Воронежпроект», а также в организации работы 1Т-подразделений ООО «Рексофт» (ГК «Техносерв»). Результаты диссертации в форме моделей и алгоритмов используются в учебном процессе ФГБОУ ВПО «Воронежский государственный технический университет» при чтении спецкурсов и выполнении выпускных квалификационных работ.
Апробация работы. Основные положения и результаты диссертации докладывались на следующих научных конференциях и семинарах: Современные проблемы прикладной математики и информатики (Воронеж, 2009), Конференция молодых ученых УМНИК (Воронеж, 2012), XXIV Международная научно-практическая конференция «Инновации в науке» (Новосибирск, 2013), XIX Международная научная конференция «Research Journal of International Studies» (Екатеринбург, 2013), Всероссийская конференция «Новые технологии в научных исследованиях, проектировании, управлении, производстве» (Воронеж, 2013).
Публикации. По результатам исследования опубликовано 7 научных работы, в том числе 3 - в изданиях, рекомендованных ВАК РФ. В работах, опубликованных в соавторстве лично соискателю принадлежит: [1,5] - метод дефаззификации нечеткого числа, [2] - алгоритм нечеткой классификации; [4] - разработка программного комплекса.
Структура и объём работы. Диссертационная работа состоит из введения, четырех глав, заключения, списка литературы из 125 наименований. Основная часть изложена на 120 страницах, содержит 33 рисунка, 21 таблицу.
Временные характеристики сетевого графика и алгоритм расчета
Планирование и управление комплексом проектных работ является достаточно сложной задачей с противоречивыми требованиями. При оценке стоимостных и временных параметров выполнения проектов используются различные методы. Среди уже существующих наибольшее значение имеют методы сетевого планирования [53,61,76,82], которые могут успешно и широко применяться при оптимизации планирования и управления сложными разветвленными комплексами работ, которые требуют участия большого количества исполнителей, а также затрат ограниченных ресурсов [5,6,46,53].
С помощью сетевого графика руководитель проекта имеет возможность системно представлять ход всех работ, оперативных мероприятий, может управлять процессом их реализации, а также маневрировать ресурсами.
Введем основные понятия сетевого планирования. Сетевое планирование и управление (СПУ) – метод планирования и управления различными видами работ, в основе которого лежит использование математического аппарата теории графов и системного подхода, с помощью которых производится отображение и алгоритмизация комплексов взаимосвязанных работ для достижения четко поставленной цели.
СПУ позволяет определить, какие работы или операции, составляющие проект, являются "критическими" и влияют на всю продолжительность проекта, а также, как построить оптимальный план выполнения комплекса работ по проекту, чтобы были выдержаны заданные сроки при минимальных затратах.
СПУ основывается на разработанных одновременно и независимо методе оценки и пересмотра планов PERT [61,62,90, 101] (PERT — Program Evaluation and Review Technique) и методе критического пути МКП (СРМ – Critical Path Method) [53, 62,69, 90,101].
Задача СПУ состоит в графическом, системном и наглядном отображении и оптимизации последовательности и взаимозависимости работ или мероприятий, которые обеспечивают планомерное и своевременное достижение поставленных целей. Для отображения и алгоритмизации комплекса работ по проекту чаще всего используются экономико-математические модели, также называемые сетевыми моделями, простейшие из которых – сетевые графики. При использовании сетевых моделей руководители проектов имеют возможность системно и масштабно представлять ход всех работ или оперативных мероприятий, а также управлять процессом их реализации и выделенными ресурсами.
Одной из важнейших особенностей СПУ является использование системного подхода при организации управления, когда коллективы исполнителей, принимающие непосредственное участие в реализации работ и объединенные общей конечной целью, рассматриваются с точки зрения звеньев одной организационной системы.
При использовании методов и моделей сетевого планирования сокращение сроков реализации новых проектов может уменьшиться на 15-20%, также обеспечивается рациональное использование трудовых ресурсов и техники. В основе СПУ лежит построение сетевых графиков. Сеть – бесконтурный ориентированный взвешенный граф с единственной начальной вершиной (исток) и единственной конечной вершиной (сток), каждой дуге которого приписано число, имеющее в зависимости от задачи оригинальную интерпретацию. Сетевой график – графическое изображение комплекса работ проекта с установленными между ними зависимостями в виде сети. Выделим следующие базовые понятия. Работа – производственный процесс, который требует затрат материальных ресурсов и времени и приводит к достижению результатов. Работа иначе называется операцией или задачей.
С точки зрения физической природы работу можно рассматривать как действие (пример – доставка строительных материалов, написание программного кода, изучение конкурентов), процесс (например, травление плат) и ожидание (процесс, который требует лишь затрат времени и не потребляет никаких ресурсов; может быть технологическим (твердение стяжки) или организационным (ожидание приемлемых погодных условий) перерывом между работами, которые непосредственно выполняются друг за другом).
Работы можно разделить по количеству затрачиваемого на них времени: действительные, которые обуславливаются протяжнным во времени процессом и требуют затраты ресурсов; фиктивные (или зависимостью), которые не требуют затрат времени и представляют собой связь между какими-либо работами: утверждение различных документов, передача бухгалтерской отчетности.
В сетевой модели различают следующие типы работ [27]: начальные работы, конечные работы, работы (операции) дробления, параллельные работы, последовательные работы, работы (операции) слияния.
Событие - является фактом окончания работы, необходимой и достаточной для начала последующих работ. События также устанавливают организационную и технологическую последовательность работ, ограничивают рассматриваемую работу и могут быть начальными и конечными. Исходным является событие, не имеющее предшествующих работ в рассматриваемом сетевом графике. При этом завершающим является событие, не имеющее последующих работ в рамках рассматриваемого сетевого графика. Начальное событие работы определяет е начало, а также является конечным событием для всех работ, предшествующих данной работе.
Постановка задачи исследования
Основная проблема управления проектами - учет влияния различных факторов на итоговое время выполнения, как отдельной работы, так и проекта в целом. Перечислим основные причины неопределенности при управлении проектами [19]: 1) неточность или неполнота информации, связанной с проектом; 2) колебания рыночной конъюнктуры, цен, валютных курсов и т. д.; 3) ошибки, связанные с прогнозированием параметров проекта; 4) ошибки при расчетах параметров проекта. Различные упрощения при формировании моделей сложных систем; 5) производственно-технологический риск (риск отказов оборудования и т. п.); 6) форс-мажорные обстоятельства (стихийные бедствия, войны и т. д.); 7) неточность и неполнота информации о деловой репутации предприятий и их финансовом положении (неплатежеспособность, банкротство, срыв договорных обязательств); 8) риск неблагоприятных социально-политических изменений, неопределенность политической ситуации; 9) риск, который связан с нестабильностью законодательства и текущей экономической ситуации. Изменение условий инвестиционного климата и использования полученной прибыли.
Выделяют следующие основные типы неопределенности[62]: вероятностная, интервальная и нечеткая неопределенность.
При вероятностной неопределенности известно распределение вероятностей продолжительностей операций [91]. Зададим время выполнения операции (ij) как случайную величину . Тогда для анализа выполнения данной операции нужно знать условную вероятность (в дискретном случае) или плотность распределения (в непрерывном случае) случайной величины у при условии, что узел / выполнен. При этом можно провести исследования, которые связаны с выполнением всей сети. Например, можно определить моменты распределения времени выполнения сети, с помощью которых будут вычислены математическое ожидание и дисперсия времени выполнения сети.
При интервальной неопределенности известен диапазон значений продолжительностей операций. Время выполнения операции (i,j) есть интервал [t.,7/.]. Методы расчета сетевых моделей с интервальным временем выполнения рассматриваются в [75].
При нечеткой неопределенности имеется нечеткая информация относительно продолжительностей операции, сроки выполнения работ априори плохо известны и оцениваются субъективно. Их можно естественным образом представить в виде нечетких чисел. Время выполнения операции (/,/) есть нечеткое число с определенной функцией принадлежности. В настоящее время существуют различные типы нечетких чисел, причем известно, что качество решения задачи зависит от вида функции принадлежности нечеткого числа. Сетевые модели с нечетким временем выполнения работ рассматриваются в [11,70,94].
Постановка задачи исследования
По статистике большинство проектов выходят за рамки бюджета или срывают сроки. В данной ситуации одной из важнейших проблем является учет неопределенности при задании временных параметров проекта. Поэтому для решения таких задач актуальным является разработка новых методов, а так же доработка существующих методов управления проектами. Выполненный обзор современного состояния различных задач управления проектами показал, что существующие математические модели и методы не обеспечивают учета нечеткой неопределенности в полной мере.
В частности, нечеткие оценки времени выполнения работ опираются на мнение эксперта, который может не учесть всех внешних и внутренних факторов, влияющих на время выполнения операции.
Целью работы является разработка и исследование сетевых моделей и методов расчета их временных характеристик, основанных на представлении времени выполнения операций проекта в форме параметрических нечетких чисел.
Для достижения этой цели решались следующие задачи. 1. Анализ существующих подходов к расчетам сетевых моделей в условиях неопределенности. 2. Обоснование выбора обобщенных гауссовых чисел, определение для них арифметических операций и операции сравнения. 3. Разработка численных методов и алгоритмов расчета временных характеристик сетевой модели с продолжительностями операций, заданными в виде обобщенного нечеткого гауссова числа. 4. Разработка программного комплекса для моделирования сетевых графиков и проведение вычислительного эксперимента.
В качестве объекта исследования в диссертации рассматриваются организационные проекты, так как в них присутствует явная нечеткость.
В качестве предмета исследования рассматриваются модели и методы сетевого планирования и управления. Представляется целесообразным предмет исследования сформулировать в более широком смысле как информационные технологии сетевого моделирования, включив сюда не только методы и модели сетевого управления, но и программное обеспечение для инструментальных сред сетевого планирования и управления.
Сравнение нечетких обобщенных гауссовых нечетких чисел
Полный резерв можно рассматривать как меру «критичности» работы: чем меньше полный резерв, тем ближе к критическому пути максимальный по длине путь, проходящий через данную работу. Зная полный резерв, можно определить работы, лежащие на путях, отличающихся по длине от критического не более чем на заданную величину. Такие работы будем называть подкритическими.
Будем считать, что продолжительность работы (i,j), величина 8 отклонения от критического пути заданы в виде обобщенных гауссовых чисел с функцией принадлежности вида (2.17).
Таким образом, если задана величина (S(a),A(a)), то все работы, полный резерв которых не превосходит (б(а),А(а)), будут подкритическими; они образуют подкритические пути, длина (L(a),A(a)) которых удовлетворяет неравенству: {Т№ (а),А(а)) - (S(a),A(a)) (ь{а),А{а)) (т {а),А{а)) Подкритические пути можно отыскать, если при вычислении (7J(0)(a),A0(cm и /и рядом с найденным числом записывать номера тех событий, для которых достигалось соответственно Г.(0) и ju . Тогда для определения части максимального по длине пути, проходящего через работу (/,/ ) , предшествующей этой работе, находим среди дуг, входящих в / по номерам, записанным возле Г.(0), дуги, предшествующие (/,/ ) в исконном пути. Если такой, например, оказалась дуга (/15/) (возле Г.(0) был записан номер ), то по номерам, записанным возле 7 (0), находим дуги, входящие в ix и предшествующие дуге {\J) в исконном пути, и т.д., пока не дойдем до і = 0 и тем самым восстановим часть искомого пути от 0 до /. Затем для определения части отыскиваемого пути, следующей за работой (i,j), по номерам, записанным возле ju , находим среди дуг, выходящих из j, дуги, следующие за (/,/ ) в этом пути. Если такой, например, оказалась дуга (у, j\) (возле ju был записан номер jx), то по номерам,
записанным возле ju., находим дуги, выходящие из у іи следующие за дугой СЛл)и т.д., пока не придем кпи тем самым построим часть искомого пути от j до п.
Описанным приемом мы найдем среди подкритических путей, проходящих через данную работу, только максимальные по длине. В действительности же через данную работу может проходить и подкритический путь, длина которого меньше максимальной. Но тогда либо существует другая дуга в этом пути, для которой этот путь является максимальным по длине, и мы его в конце концов определим; либо на для одной своей дуги этот путь не является максимальным, так как каждая дуга этого пути входит еще в некоторый другой путь длины, большей данного, т.е. тоже в подкритический.
Если необходимо отыскать все подкритические пути, то придется прибегнуть к перебору всех путей, составленных только из подкритических работ.
Особую важность приобретает задача определения подкритических работ и путей, когда заданный срок (т(а),А(а)) выполнения проекта меньше критического времени (Ткр{а),А{ос)). В этом случае для выполнения проекта в заданный срок /г(«),Л(ст необходимо сократить не только критические пути, но и подкритические, длина (Z(cr),A(cm которых удовлетворяет неравенствам (т(а)Ма)) Ша)Ма))ф ( )М )). Отыскиваем сначала подкритические работы. Очевидно, ими будут все работы, лежащие на путях длины (L(a),A(a)), большей (т(а),А(а)), так что относительно времени (Г(«),Л(стих полные резервы, равные т - (т(0)+ju + ttJ) = г(1) - т(0) - tv - (Ткр - Т) (где Tj1) - максимальная величина наступления событий при Тп = Т ), будут отрицательные. Определим, таким образом, все подкритические работы, можно, как указывалось выше, определить и подкритические пути. Критические пути будут образовывать работы с равными, максимальными по абсолютной величине резервами.
Полный резерв не вполне достаточно отражает меру критичности работы. С одной стороны, работы могут обладать одинаковым полным резервом, но он распространн на участках различной длины, и напряженность выполнения работ будет не одинаковая. С другой же стороны, работы могут обладать разными полными резервами, но выполняться с одинаковой напряженностью.
Исходя из этих примеров, становится ясным естественность введения нового параметра, характеризующего напряженность выполнения каждой работы (i,j), так называемого коэффициента напряженности кц.
Для определения .. работы (i,j) отыскивают на пути максимальной длины, проходящем через эту работу, ближайшие к ней слева и справа события одного и тоже критического пути и составляют отношение длины отрезка L (i,j) максимального пути между найденными событиями к длине Tкр (iJ) отрезка критического пути, заключенного между теми же событиями. Если критических путей в графике несколько, то таких отношений может быть, вообще говоря, не одно.
Алгоритм расчета подкритического пути
Сводные результаты вычислительного эксперимента представлены в табл. 4.13. На рисунке 4.7 представлены «-срезы критического времени выполнения проекта. При аппроксимации интервалов в итоге получается нечеткое обобщенное гауссово число. Но, как видно из рисунка, получены различные критические пути.
К основным выводам вычислительного эксперимента можно отнести следующее: 1. При стохастической неопределенности и расчете сетевого графика по методу PERT эксперт несет полную ответственность за результат 2. При использовании обобщенных гауссовых нечетких чисел можно настраивать параметры и выбирать «-уровень таким образом, чтобы получить оптимальное решение для конкретной внешней среды выполнения проекта. 3. При использовании обобщенных гауссовых нечетких чисел критический путь представляет собой интервал, что позволяет более гибко оценивать сроки выполнения всего проекта. 4. При использовании различных а -уровней, когда время работы задано в виде обобщенных гауссовых нечетких чисел, можно получить различные критические пути, что позволяет наиболее полно отразить все возможные риски при выполнении проекта.
Выводы четвертой главы Таким образом, в данной главе: 1. Определены требования к функциям, надежности, гибкости и масштабируемости программного комплекса. 2. Описаны преимущества выбора платформы .NET Framework для разработки программного комплекса. 3. Разработана модульная структура программного средства с учетом требований к надежности, гибкости и масштабируемости современных программных систем. 4. Визуальный интерфейс пользователя разработан в соответствии с практической применимостью программного комплекса и отвечает требованиям удобства работы с информацией. 5. Проведен вычислительный эксперимент для расчета параметров сетевой модели, в котором время выполнения работ задано в виде обобщенных гауссовых нечетких чисел. Проведено сравнение полученных результатов с результатами вычисления критического пути по методу PERT. Сделаны выводы о целесообразности использования обобщенных гауссовых нечетких чисел.
Эффективность предложенного подхода заключается в том, что использование приближенной исходной информации для расчета временных характеристик сетевой модели позволяет разработать альтернативные варианты реализации проекта и обеспечить гибкий подход к планированию работ. Преимуществом обобщенных гауссовых нечетких чисел является наличие параметров, за счет «настройки» которых можно обеспечить максимальную достоверность экспертной оценки времени выполнения операций проекта. Кроме того, являясь дифференцируемыми, гауссовы функции дают возможность проведения теоретического анализа модели.
В рамках данной работы были рассмотрены обобщенные нечеткие гауссовы числа, введены арифметические операции и операции сравнения для них, разработаны модифицированные алгоритмы и методы расчета сетевых моделей. Были решены следующие задачи:
1. Определены арифметические операции и операции сравнения для обобщенных нечетких гауссовых чисел, отличающиеся параметрическим представлением и позволяющие определить аналитические выражения для временных характеристик сетевого модели.
2. Разработаны модифицированные алгоритмы расчета критического и подкритического путей сетевой модели, в которой время выполнения операций задано в виде обобщенного нечеткого гауссова числа.
3. Разработан модифицированный алгоритм оптимизации сетевой модели по времени в условиях ограниченных ресурсов с временем выполнения операций в виде обобщенных гауссовых чисел, который позволяет за счет перераспределения ресурсов уменьшить критическое время проекта
4. Предложен алгоритм расчета GERT-сети, позволяющий учитывать различные типы входов и выходов для каждого разрешающего узла, отличительной особенностью которого является задание времени выполнения операций в виде обобщенных гауссовых чисел;
5. Реализована структура программного комплекса для расчета параметров и оптимизации сетевых моделей с продолжительностями операций в виде обобщенных гауссовых чисел, включающая модули для реализации предложенных алгоритмов и позволяющая за счет специальной подсистемы сформировать информационную среду для конкретной модели.
Похожие диссертации на Сетевое моделирование проектов с нечетким временем выполнения на основе обобщенных гауссовых чисел
