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

005537026

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

Сидоренко Елена Александровна

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

Специальность 05.13.1S - Математическое моделирование, численные методы и комплексы программ

АВТОРЕФЕРАТ

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

7 НОЯ 2013

Воронеж - 2013

005537026

Работа выполнена в ФГБОУ ВПО «Воронежский государственный архитектурно-строительный университет».

Научный руководитель: Баркалов Сергей Алексеевич,

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

Официальные оппоненты: Колпачев Виктор Николаевич,

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

Олейникова Светлана Александровна, кандидат технических наук, доцент, Воронежский государственный технический университет, доцент кафедры автоматизированных и вычислительных систем

Ведущая организация: ФГБОУ ВПО «Воронежский

государственный университет»

Защита состоится 28 ноября 2013 г. в 1100 часов в конференц-зале на заседании диссертационного совета Д 212.037.01 при ФГБОУ ВПО «Воронежский государственный технический университет» по адресу: 394026. г. Воронеж, Московский просп., 14.

С диссертацией можно ознакомиться в научно-технической библиотеке ФГБОУ ВПО «Воронежский государственный технический университет».

Автореферат разослан «25» октября 2013 г.

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

В.Ф. Барабанов

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

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

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

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

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

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

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

Задачи исследования. Достижение цели работы потребовало решения следующих основных задач:

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

V

нения работы и невозможность возобновления в течение рассматриваемого периода (ресурсы типа I).

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

3. Построить математические модели для решения задачи оптимизации комплекса проектов по ресурсам типа мощности (ресурсов типа И).

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

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

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

Тематика работы соответствует следующим пунктам паспорта специальности 05.13.18: 3. Разработка, обоснование и тестирование эффективных численных методов с применением компьютерных технологий; 5. Комплексные исследования научных и технических проблем с применением современной технологии математического моделирования и вычислительного эксперимента; 8. Разработка систем компьютерного и имитационного моделирования.

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

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

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

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

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

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

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

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

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

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

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

Разработанные теоретические и практические результаты работы, реализованные в виде программного средства, используются в практике работы ЗАО «Воронеж-дом» и ООО УК «Жилпроект» (г. Воронеж). Эффект от внедрения заключается в сокращении времени, затрачиваемого на процесс планирования, а также в повышении производительности в среднем на 2,3 %.

Разработанные модели и алгоритмы включены в состав учебных курсов «Управление проектами» и «Инновационный менеджмент», читаемых в Воронежском государственном архитектурно-строительном университете.

Апробация работы. Основные результаты исследований и научных разработок докладывались и обсуждались на следующих конференциях: научно-практической конференции «Образование, наука, производство, управление» (Старый Оскол, 2010); Всероссийской молодежной научной школе «Инженерия знаний. Представление знаний: состояние и перспективы» (Воронеж, 2012); Международной молодежной конференции в рамках фестиваля науки «Математические проблемы современной теории управления системами и процессами» (Воронеж, 2012); 65-й Всероссийской научно-практической конференции «Инновации в сфере науки, образования и высоких технологий» (Воронеж, 2010); 64-68-х научно-технических конференциях по проблемам архитектуры и строительных наук (г. Воронеж, 2009-2013).

Публикации. По результатам исследований опубликовано 16 научных работ, в том числе 7 в изданиях, рекомендованных ВАК РФ. В работах, опубликованных в соавторстве, личный вклад соискателя состоит в следующем: в [1] -численный алгоритм оптимизации ресурсов внутри проекта; в [3, 12, 14] - математическая модель оптимального распределения ресурсов типа 1 между про-

ектами; в [5, 11, 16] - математическая модель оптимального распределения ресурсов внутри проекта; в [2, 6, 8] — математическая модель оптимизации комплекса проектов по ресурсам типа мощности; в [4, 10] - математическая модель определения оптимального набора ресурсов типа мощности; в [8, 13, 15] - численный алгоритм решения задачи оптимизации комплекса проектов с точки зрения ресурсов типа мощности.

Объем и структура работы. Диссертация состоит из введения, четырех глав, заключения, списка литературы из 152 наименований. Основная часть работы изложена на 128 страницах, содержит 13 таблиц и 27 рисунков.

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

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

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

Анализ специфики ресурсов как одного из инструментов оптимизации функционирования мультипроектных сложных систем показал, что их можно классифицировать в зависимости от степени возобновляемости после завершения очередной работы. В частности, было предложено рассматривать два типа ресурсов. К ресурсам типа I отнесены ресурсы, которые расходуются в процессе выполнения работы и не восполняются в течение рассматриваемого периода (например, финансовые ресурсы). Ресурсы типа II отличаются тем, что после завершения работы их вновь можно использовать для выполнения других работ. К таким ресурсам можно отнести, например, специалистов.

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

Для математического описания поставленной задачи предварительно введем следующие обозначения: N - количество рассматриваемых проектов; Я = [ж|,...,%] - заданные приоритеты проектов; С = [С1,...,СК] - объем ресурса,

необходимый для выполнения проектов; /ф= [г.....,(л] - время, истекшее с начала

выполнения проектов; 5дир =[£,,...,£„] - директивные сроки окончания проектов; Р = - заданные вероятности выполнения проектов; О = [г/......г/Л,] - огра-

ничения на максимальную скорость потребления ресурса; £? = [?„...,~ относительная трудоемкость выполненных работ по каждому проекту на начало планируемого периода; 0 < д < 1, / = 1, Л^; Т - величина периода планирования (год, месяц); Сг - размер ресурса, подлежащего распределению; С" - дирек-

тивное распределение суммарного ресурса по времени; X = [х„...,х„] - искомый вектор, определяющий приращение относительной трудоемкости на плановый период Т по каждому проекту; г = [г,,...,гА,] - время окончания выполнения каждого проекта, которое определяется в результате решения задачи; - рассматриваемый момент планирования; £(') - заданный случайный процесс, определяющий распределение относительной трудоемкости выполнения к -го проекта в момент времени ¡>1° + Т. Предполагаем, что

(1)

где тк(() - заданная детерминированная монотонно неубывающая функция;

- некоррелированный случайный процесс с нулевой функцией математического ожидания; сг,(() — среднеквадратичное отклонение случайной величины £,(<) в момент времени / (неубывающей функция).

Задавая по каждому к -му проекту величины хк и тк, можно вычислить вероятность его выполнения по формуле

+ + -/" -7-М (2)

Критерий оптимальности распределения ресурсов между проектами должен учитывать в прямой зависимости приоритетность лк каждого проекта, вероятность его невыполнения к моменту окончания г, и величину смещения этого срока относительно директивно заданного. В данной постановке задачи предлагается формула для критерия IV:

(3)

где Гк (хк, г,) вычисляется по формуле (2).

Для математического описания задачи обозначим через О область всех допустимых векторов х и т, характеризующих все возможные варианты распределения ресурсов между проектами, удовлетворяющих имеющимся ограничениям. Тогда требуется найти в этой области £> наилучшую пару векторов (х ,г О, которая обращает в минимум функцию вида (3):

(4)

при ограничениях

(5)

(6)

х„ <тт(1-^Л); (7)

Ф(/)= ~Р-Р&1_Ск[як +хк +4М^С'(,"+Т + 1)}<0, (8)

где 0</<г, -(/°+г).

Формулы (5) - (8) представляют собой математическую модель оптимального распределения ресурсов между проектами. В формулах (5) - (8) предполагается, что к = \,И. Неравенство (5) отражает требование, чтобы вероятность выполнения каждого проекта превосходила заданный уровень Рк. Неравенство (6) требует, чтобы планируемые приросты относительных трудоемко-стей по каждому проекту соответствовали суммарным объемам ресурсов, не превосходящим заданного значения Ст. Кроме того, приросты относительных трудоемкостей по каждому проекту не должны превосходить заданной скорости ¿к или же оставшейся относительной трудоемкости. Этот факт отражен в неравенстве (7). Ограничение по динамике потребления ресурса в момент времени / > 1° + Т отражено в неравенстве (8).

Решение поставленной задачи (4) - (8) будем находить в два этапа: первый - этап решения задачи 1 ((4) - (7), то есть без учета ограничения (8)), и второй - этап перехода к решению исходной задачи с учетом ограничения (8) (задача 2).

Численная реализация задачи 1 основана на использовании метода динамического программирования. Численная реализация задачи 2 и оптимального распределения в целом приводится в комплексном алгоритме. Прогнозирование динамики изменения оставшейся трудоемкости осуществляется на базе использования регрессионной модели процесса разработки (как правило, линейной). При определении характеристик случайного процесса £*(')> отражающего распределение относительной трудоемкости выполнения к-й разработки в момент

времени I > + Т, будем считать, что трудоемкость на отрезке

I +Т,

нарас-

тает постоянно. Другими словами, уравнение для функции математического ожидания случайного процесса, отражающего ход выполнения разработки, при I > + Т имеет линейный вид.

В алгоритме решения задачи 1 осуществлена вычислительная реализация метода динамического программирования с шагом дискретности Д. На каждом шаге распределения к вычисляется разброс возможных накопленных ресурсов J|:■Л., подлежащих распределению. Для каждого значения объема ресурсов где ] = 1,7,, просматривается множество возможных вариантов и запоминается наилучший. Множество возможных вариантов распределения после к шагов, требующих ресурсов объема у'к, определяется в результате продолжения оптимальных вариантов распределения после (¿-1)-го шага. Просмотр вариантов распределения осуществляется путем введения составного цикла, состоящего из трех вложенных друг в друга простых циклов: цикла просмотра шагов к = \,Ы, цикла просмотра различных уровней ресурса на каждом шаге у = 1,Л и цикла просмотра всех вариантов, требующих объемов ресурсов, равных у{= /Д,л = 1, . В результате работы алгоритма выдается множество оптимальных вариантов распределения после Л'-го шага, каждый из которых

+ 1.

требует различных объемов ресурсов с равным шагом дискретности, а именно

— Гс

у{. = у-Л, где ¿ = , а Jv=

д

Алгоритм решения задачи 2 реализует поиск локального экстремума х = [дг',...,дгд], отражающего оптимальное распределение ресурсов между проектами. К основным блокам рассматриваемого алгоритма можно отнести следующие: формирование исходного допустимого вектора х0, удовлетворяющего

ограничениям (5) - (8); вычисление стохастического градиента %гас1 И^') в рассматриваемой точке хк; проектирование вектора %гас1 на поверхность ограничений (5) - (8) - вычисление вектора вычисление шага продвижения вдоль вектора &(**); реализация окончания процедуры. Схема численного алгоритма оптимизационной задачи приведена на рис. 1.

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

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

Для построения математической модели системы введем следующие обозначения. Пусть б = {У,и} ~ сетевой график, определяемый следующей парой множеств; У - множество событий (вершин); и - множество работ (дуг); Тн = ¡7',;',,, гдеи\ - календарный план выполнения проекта. Здесь Тч -плановое начало выполнения работы (/,_/), - продолжительность ее выполнения. Каждой работе соответствует числовая функция С„ =/Д/), где ;е г , г. - область определения этой функции; ¿'|ир - директивный срок выполнения проекта; С - общий объем ресурсов.

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

7; +1. < для всех (/, у) е и, (10)

I 0<г<5ир. (11)

О.у Ы;

где

[1 при Тч<1< Т„ + ;

[0 в противном случае;

Т„><„, ;еУ, (12)

Рис. 1. Схема алгоритма решения оптимизационной задачи распределения ресурсов типа I между проектами

С учетом требования на равномерное распределение ресурсов в течение планового периода формулы (10) - (12) представляют собой математическую модель распределения ресурсов внутри проекта, позволяющую построить оптимальный календарный план выполнения всех работ проекта в сроки, определенные договорными обязательствами, с минимальными затратами.

В области О, описанной ограничениями (10) - (12), требуется найти план 7", который обращает в минимум целевую функцию следующего вида:

с(г)= 2X4). (13)

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

_ Задача I. Требуется найти план продолжительностей работ '* = который удовлетворяет ограничению

г, (7)-^ о (14)

и обращает в минимум целевую функцию

у.

Задача II. При заданном векторе продолжительностей /' = тре-

буется найти вектор Т' = {т:',г",(|,у)е{у}, характеризующий начало выполнения каждой работы, который удовлетворяет условию (10) и обращает в минимум целевую функцию следующего вида:

¡V (т) =

(м>С/ ',/ ¿дар

(15)

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

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

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

ограниченный сверху и заранее заданный объем финансирования по ресурсным расходам.

В работе рассмотрены обе оптимизационные задачи.

Введём следующие обозначения: « - число проектов (проектов) П,, 1<1<п, каждый из которых представлен цепочкой операций Ок, \<с<т1; т, — число операций в проекте П,; - случайная продолжительность операции 0,с; 11с - математическое ожидание случайной величины /,.с; Ук - дисперсия случайной величины 1,с; гм - мощность к -го ресурса (количество ресурсов к -го типа), используемая в процессе реализации 0,с (постоянна и задаётся заранее), 1 <к<Л\ (1 - количество потребляемых ресурсов; - суммарные к -ресурсы (общее число ресурсов к -го типа) - оптимизируемая переменная; О, — директивный срок окончания проекта П/ (задаётся заранее); Р: - допустимая вероятность окончания проекта П, в директивный срок Д (задаётся заранее); -фактическое время начала реализации операции 0,с (случайная величина; определяется в процессе решения конфликтных ситуаций при одновременной реализации нескольких проектов); Е1с - момент завершения операции Ок (случайная величина); Ь] - момент окончания выполнения /-го проекта; ^ = (случайная величина); ~ вероятность выполнения проекта П, в срок

(на основе имитационного моделирования системы) при условии, что системе выделены постоянные наличные ресурсы Д,, 1 <к<с! (/г^ - вектор ресурсов); \¥к,() - суммарная мощность задействованных ресурсов типа к в момент / при условии, что операции 01с стартуют в момент /?,(/) ~ на-

личные свободные ресурсы к -го типа, готовые к реализации новых операций; X, - стоимость аренды и содержания единицы к -го ресурса за единицу времени, 1 <к<с1 (постоянна и задается заранее); ДЛ4 - шаг поиска оптимального значения \< к <с! (задаётся заранее); £ - оценка погрешности целевой функции при поиске оптимального решения; г/, - индекс приоритета (степень важности) проекта П: (задаётся заранее); /<,,„„ - нижняя грань возможного числа ресурсов А-го типа, 1 <к<<1 (задаётся заранее); - верхняя грань возможного числа ресурсов к -го типа, 1 < к < Л (задаётся заранее).

Таким образом, необходимо определить оптимальные детерминированные значения Як, 1 <к<с! (на этапе, предшествующем реализации проектов), и случайные значения , 1</<и, 1 <с<т, (в процессе реализации проектов), с тем, чтобы минимизировать целевую функцию

(16)

с ограничениями

Л*т,„ ^ тЗХ тЗХ Г„

>ск ,

(17)

Р,

}>/>,', !</'<«, 1 <к<с1, 1 <с<т,

(19)

(20) (21)

Формулы (17) - (21) являются математической моделью оптимизации комплекса проектов по ресурсам типа мощности, учитывающей ограничения на все виды ресурсов, а также вероятности завершения проектов в директивные сроки и приоритеты проектов.

Задача (16) - (21) является сложной стохастической оптимизационной задачей, которая не имеет классического решения. Последнее может быть достигнуто только путём комбинации эвристики, имитации и покоординатных методов оптимизации.

Численный метод решения задачи (16) - (21) включает два иерархических уровня. На верхнем уровне осуществляется поиск оптимальных значений Д,, 1 <к<с1, на основе метода покоординатной оптимизации, хорошо зарекомендовавшего себя в ряде оптимальных задач сетевого планирования. На нижнем иерархическом уровне работает имитационная модель, позволяющая найти оптимальное значение целевой функции. Обобщенная схема алгоритма решения задачи представлена на рис. 2.

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

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

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

Чем меньше величина , тем более срочный характер носит обеспечение

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

(22)

(23)

Р,

Рис. 2. Схема алгоритма решения оптимизационной задачи 14

Рис. 3. Схема одного прогона имитационной модели

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

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

г,. =Рг|/Г <Ц{|-7Л(. (25)

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

Таким образом, разработан численный метод решения задачи оптимизации комплекса проектов с точки зрения ресурсов типа мощности. На верхнем уровне алгоритма используется метод покоординатной оптимизации (рис. 2), а на втором - имитационное моделирование (рис. 3).

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

Структура разработанной системы имеет вид, представленный на рис. 4.

Рис. 4. Структура системы компьютерного моделирования 16

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

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

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

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

Рис. 5. Результаты расчетов программы по распределению ресурсов внутри проекта

Аналогичным образом можно получить сводную информацию по распределению ресурсов между всеми проектами предприятия. Программный комплекс разработан в среде С#, в качестве СУБД выбрана MS Sql Server.

Программное средство внедрено в ЗАО «Воронеж-дом» и ООО УК «Жилпроект». Эффект от внедрения заключается в сокращении времени, затрачиваемого на процесс планирования, а также в повышении производительности в среднем на 2,3 %.

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

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

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

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

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

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

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

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

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

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

Публикации в изданиях, рекомендованных ВАК РФ

1. Сидоренко, Е. А. Алгоритм оптимального распределения ресурсов внутри проекта / С. А. Барканов, В. Н. Бурков, Д. И. Голенко-Гинзбург, Е. А. Сидоренко // Вестник Воронеж, гос. техн. ун-та. - 2010. - Т. 6, № 10. - С. 65-68.

2. Сидоренко, Е. А. Решение задач перспективного планирования и прогнозирования при случайных оценках продолжительности операций /

С. А. Баркалов, Д. И. Голенко-Гинзбург, И. Ф. Набиуллин, Е. А. Сидоренко // Вестник Воронеж, гос. техн. ун-та. - 2010. - Т. 6, № 3. - С. 38 — 43.

3. Сидоренко, Е. А. Задача оптимального распределения затрат между проектами, представленными сетевыми графиками / Д. И. Голенко-Гинзбург, Е. А. Сидоренко, Д. Э. Хицков // Вестник Воронеж, гос. техн. ун-та. - 2010. - Т. 6, №4.-С. 169- 172.

4. Сидоренко, Е. А. Задача минимизации времени выполнения разработки при ограничениях на интенсивность потребления ресурсов / Д. И. Голенко-Гинзбург, Е. А. Сидоренко, В. О. Скворцов // Вестник Воронеж, гос. техн. унта.-2010.-Т. 6, №4.-С. 197-201.

5. Сидоренко, Е. А. Алгоритм оптимального распределения ресурсов внутри проекта / Д. И. Голенко-Гинзбург, Е. А. Сидоренко, А. В. Никитенко // Вестник Воронеж, гос. техн. ун-та. - 2010. - Т. 6, № 4. - С. 32 - 35.

6. Сидоренко, Е. А. Построение оптимального календарного плана выполнения всех работ проекта / В. И. Алферов, И. Ф. Набиуллин, Е. А. Сидоренко // Вестник Воронеж, гос. техн. ун-та. - 2010. - Т. 6, № 6. - С. 88-91.

7. Сидоренко, Е. А. Метод «затраты-эффект» в задачах формирования многоцелевых программ / В. В. Зубарев, Е. А. Сидоренко, А. А. Христюк // Вестник Воронеж, гос. техн. ун-та. - 2011. - Т. 7, № 6. - С. 106 - 108.

Статьи и материалы конференций

8. Sidorenko, Ye. Choice of Effective Organizational and Technological Decisions under Reconstruction with Consideration for Ecological Monitoring / S. Barkalov, O. Budkov, Ye. Sidorenko // Scientific Israel — Technological Advantages.-2012.-Vol. 14, N2,3.-P. 21 -29.

9. Сидоренко, E. А. Оптимальное распределение ресурсов в задачах в задачах календарного планирования / В. И. Алферов, С. А. Баркалов, Е. А. Сидоренко // Образование, наука, производство, управление: науч.-практ. конф. преп и асп. (24—25 ноября 2010 г., Старый Оскол). - Ст. Оскол, 2010. -Т. 2.-С. 184- 187.

10. Сидоренко, Е. А. Математическая модель альтернативной сети / С. А. Баркалов, О. В. Будков, Е. А. Сидоренко // Инженерия знаний. Представление знаний: состояние и перспективы: материалы Всерос. молодежной научной школы (29 - 30 июня 2012 г.). - Воронеж: Научная книга, 2012. - С. 130 -132.

11. Сидоренко, Е. А. Задача перспективного планирования и прогнозирования потребления ресурсов / С. А. Баркалов, О. В. Будков, Е. А. Сидоренко // Инженерия знаний. Представление знаний: состояние и перспективы: материалы Всерос. молодежной научной школы (29-30 июня 2012 г.). - Воронеж: Научная книга, 2012. - С. 134 - 136.

12. Сидоренко, Е. А. Модель для определения максимального значения функции метрического обеспечения методом золотого сечения / П. Н. Курочка, Е. А. Сидоренко, О. В. Будков // Математические проблемы современной тео-

рии управления системами и процессами: материалы Междунар. молодежной конф. в рамках фестиваля науки (4 сентября 2012 г.). - Воронеж: Научная книга, 2012.-С. 235 -238.

13. Сидоренко, Е. А. Задача перспективного планирования и прогнозирования потребления ресурсов / С. А. Баркалов, О. В. Будков, Е. А. Сидоренко // Инженерия знаний. Представление знаний: состояние и перспективы: материалы Всерос. молодежной научной школы (29 - 30 июня 2012 г.). - Воронеж: Научная книга, 2012. - С. 134 - 136.

14. Сидоренко, Е. А. Методы управления в вероятностных сетевых моделях с детерминированной структурой / С. А. Баркалов, Е. А. Сидоренко, Р. Е. Пахнин, О. В. Будков // Инновации в сфере науки, образования и высоких технологий: итоги 65-й Всерос. науч.-практ. конф. - 2010. -№ 555 (CD-ROM).

15. Сидоренко, Е. А. Оптимизация комплекса сетевых моделей по стоимости / Е. А. Сидоренко, О. В. Будков, А. Р. Кашенков // Научный вестник Воронеж. гос. арх.-строит. ун-та. Серия: Управление строительством. - 2013. -Вып. № 1(4).-С. 40-45.

16. Сидоренко, Е. А. Статистические методы оптимизации сетевых моделей с детерминированными параметрами / Е. А. Сидоренко, О. В. Будков // Научный вестник Воронеж, гос. арх.-строит. ун-та. Серия: Управление строительством. -2013. - Вып. № 1(4). - С. 56 - 67.

Сидоренко Елена Александровна

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

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

Подписано в печать 24.10.2013. Формат 60*84 1/16. Усл. печ. л. 1,0.

____Бумага писчая. Тираж 120 экз. Заказ № 451.___

Отпечатано: отдел оперативной полиграфии Издательства учебной литературы и учебно-методических пособий Воронежского государственного архитектурно-строительного университета 394006 г. Воронеж, ул. 20-летия Октября, 84

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

04201 451 201

СИДОРЕНКО ЕЛЕНА АЛЕКСАНДРОВНА

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

Специальность 05.13.18 - Математическое моделирование, численные

методы и комплексы программ

ДИССЕРТАЦИЯ

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

Воронеж 2013

ОГЛАВЛЕНИЕ

Введение...................................................................................................................4

Глава 1 Особенности оптимизации многостадийных стохастических систем. 9

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

1.2 Сетевое планирование и управление как основной инструмент описания сложных систем с взаимной зависимостью между работами.... 12

1.3 Механизмы распределения ресурсов.......................................................21

1.4 Цель и задачи диссертационного исследования.....................................33

2 Математическая модель и численный алгоритм решения задачи распределения ресурсов типа I............................................................................35

2.1 Математическая модель распределения ресурсов типа I между проектами..........................................................................................................35

2.2 Численный метод и алгоритм оптимизации распределения затрат между проектами..............................................................................................41

2.3 Модель оптимального распределения ресурсов внутри проекта............48

2.4 Численные методы решения задачи распределения ресурсов внутри проекта...............................................................................................................54

2.5 Выводы........................................................................................................65

3. Математическая модель и решение оптимизационной задачи распределения ресурсов типа мощности............................................................67

3.1 Формализация задачи и математическая модель для определения ресурсов типа мощности..................................................................................67

3.2 Численный метод решения оптимизационной задачи распределения ресурсов типа мощности..................................................................................71

3.3 Модификации разработанного подхода...................................................80

3.3.1 Решение задачи минимизации общей продолжительности

проекта.............................................................................................................80

3.3.2. Обратная оптимизационная задача...............................................84

3.4 Выводы........................................................................................................89

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

ЗАО «Воронеж-Дом»............................................................................................91

4.1 Структура программного комплекса........................................................91

4.2 Структура базы данных.............................................................................97

4.3 Результаты работы программного средства..........................................109

4.4 Выводы......................................................................................................117

Основные результаты работы............................................................................119

Список использованных источников................................................................121

Введение

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

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

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

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

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

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

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

Задачи исследования. Достижение цели работы потребовало решения следующих основных задач:

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

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

3. Построить математические модели для решения задачи оптимизации комплекса проектов по ресурсам типа мощности (ресурсов типа II).

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

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

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

методы математического программирования, численные методы и теория объектно-ориентированного программирования.

Тематика работы соответствует следующим пунктам паспорта специальности 05.13.18:

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

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

8. Разработка систем компьютерного и имитационного моделирования.

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

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

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

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

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

6

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

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

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

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

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

Разработанные теоретические и практические результаты работы, реализованные в виде программного средства, используются в практике работы ЗАО «Воронеж-дом» и ООО УК «Жилпроект» (г. Воронеж). Эффект от внедрения заключается в сокращении времени, затрачиваемого на процесс планирования, а также в повышении производительности в среднем на 2,3 %. 7

Модели, алгоритмы включены в состав учебных курсов «Управление проектами» и «Инновационный менеджмент», читаемых в Воронежском государственном архитектурно-строительном университете.

Апробация работы

Основные результаты исследований и научных разработок докладывались и обсуждались на следующих конференциях: научно-практич. конф. «Образование, наука, производство, управление» (Старый Оскол, 2010); Всероссийская молодежная научная школа «Инженерия знаний. Представление знаний: состояние и перспективы» (Воронеж, 2012); Международная молодежная конференция в рамках фестиваля науки «Математические проблемы современной теории управления системами и процессами» (Воронеж, 2012); 65-я всероссийская научно-практическая конференция «Инновации в сфере науки, образования и высоких технологий» (Воронеж, 2010); 64-68-й научно-технических конференциях по проблемам архитектуры и строительных наук (г. Воронеж, 2009-2013).

Публикации. По результатам исследований опубликовано 16 научных работ, в том числе 7 - в изданиях, рекомендованных ВАК РФ. В работах, опубликованных в соавторстве и приведенных в конце автореферата, лично соискателю принадлежат: в [1] - численный алгоритм оптимизации ресурсов внутри проекта; в [3, 12, 14] - математическая модель оптимального распределения ресурсов типа I между проектами; в [5, 11, 16] - математическая модель оптимального распределения ресурсов внутри проекта; в [2, 6, 8] - математическая модель оптимизации комплекса проектов по ресурсам типа мощности; в [4, 10] - математическая модель определения оптимального набора ресурсов типа мощности; в [8, 13, 15] - численный алгоритм решения задачи оптимизации комплекса проектов с точки зрения ресурсов типа мощности.

Объем и структура работы. Диссертация состоит из введения, четырех глав, заключения, списка литературы из 152 наименований. Основная часть изложена на 128 страницах, содержит 13 таблиц и 27 рисунков.

Глава 1 Особенности оптимизации многостадийных стохастических систем

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

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

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

Неотъемлемой составляющей любой системы являются ресурсы. Под ресурсами в общем случае понимается количественная мера возможности выполнения какой-либо деятельности; условия, позволяющие с помощью определённых преобразований получить желаемый результат.

Проанализируем особенности, возникающие в процессе функционирования многостадийной стохастической производственной системы с точки зрения системного подхода [57, 94, 120].

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

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

Исходя из особенностей данной задачи, а таюке специфики работы производственных систем, рассмотрим основные возможности для оптимизации их функционирования [25, 73, 76, 80, 95]. Одним основных инструментов, позволяющих управлять предприятием в условиях стохастической неопределенности его функционирования, а таюке наличия большого числа проектов, является эффективное распределение ресурсов всех типов. Проанализируем этот инструмент более подробно. Для этого исследуем специфику используемых ресурсов.

К ресурсам систем могут относиться трудовые ресурсы, оборудование (т.е. производственные фонды), финансовые ресурсы, используемые материалы и т.д. [141].

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