авторефераты диссертаций БЕСПЛАТНАЯ БИБЛИОТЕКА РОССИИ

КОНФЕРЕНЦИИ, КНИГИ, ПОСОБИЯ, НАУЧНЫЕ ИЗДАНИЯ

<< ГЛАВНАЯ
АГРОИНЖЕНЕРИЯ
АСТРОНОМИЯ
БЕЗОПАСНОСТЬ
БИОЛОГИЯ
ЗЕМЛЯ
ИНФОРМАТИКА
ИСКУССТВОВЕДЕНИЕ
ИСТОРИЯ
КУЛЬТУРОЛОГИЯ
МАШИНОСТРОЕНИЕ
МЕДИЦИНА
МЕТАЛЛУРГИЯ
МЕХАНИКА
ПЕДАГОГИКА
ПОЛИТИКА
ПРИБОРОСТРОЕНИЕ
ПРОДОВОЛЬСТВИЕ
ПСИХОЛОГИЯ
РАДИОТЕХНИКА
СЕЛЬСКОЕ ХОЗЯЙСТВО
СОЦИОЛОГИЯ
СТРОИТЕЛЬСТВО
ТЕХНИЧЕСКИЕ НАУКИ
ТРАНСПОРТ
ФАРМАЦЕВТИКА
ФИЗИКА
ФИЗИОЛОГИЯ
ФИЛОЛОГИЯ
ФИЛОСОФИЯ
ХИМИЯ
ЭКОНОМИКА
ЭЛЕКТРОТЕХНИКА
ЭНЕРГЕТИКА
ЮРИСПРУДЕНЦИЯ
ЯЗЫКОЗНАНИЕ
РАЗНОЕ
КОНТАКТЫ


Pages:     | 1 || 3 | 4 |   ...   | 8 |

«Институт проблем управления Университетский Центр им. В.А.Трапезникова РАН Самарии (Москва, Россия) (Ариэль, Израиль) Д.И. ...»

-- [ Страница 2 ] --

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

В работах [1.3-1.6] показано, что в сети, состоящей из работ, продол жительности выполнения которых случайны и подчинены определенному закону распределения, не существует «самого длинного пути» и сама по становка такого вопроса с вероятностной точки зрения является необосно ванной.

Что касается вопроса относительно вероятности для определенной, фиксированной работы (i, j ) в случае реализации всего сетевого проекта (всех работ в сети) оказаться на критическом пути, то есть обладать ко эффициентом напряженности, равным единице, то такая постановка явля Глава 1. Вероятностные сетевые модели с детерминированной структурой ется вполне корректной.

В [1.4, 2.6 и др.] рассмотрены сети с детерминированными оценками продолжительности выполнения входящих в них работ. Работа (i, j ) счита лась относящейся к критической зоне, если значение ее коэффициента на пряженности k H (i, j ) было больше 1 - h (h 0 ).

Для случая работ со случайными оценками продолжительности их выполнения мы в состоянии лишь оценить вероятность pij того, что работа (i, j ) после ее выполнения будет иметь коэффициент напряженности, больший 1 - h, то есть будет принадлежать к критической зоне. Действуя аналогичным образом в отношении всех входящих в сетевую модель ра бот, мы выделим группу работ, имеющих тенденцию лежать в критической зоне, и, наоборот, группу работ, которые не попадают, как правило, на на пряженные пути. Разбиение работ, входящих в сетевую модель, на «на пряженные» и «ненапряженные» может быть проведено методом стати стического моделирования (методом Монте-Карло) по следующей методи ке, описанной в работе [1.3]. Зафиксируем две вероятности p1 и p 2, причем p 2 p1. Установим, что если вероятность pij для работы (i, j ) оказаться критической (то есть иметь коэффициент напряженности больше 1 - h ), превосходит значение p1, то работа (i, j ) относится к «напряженной» зоне.

Если же значение pij меньше величины p 2, относим работу (i, j ) ко второй, «ненапряженной» зоне. При наличии неравенства p 2 p ij p1 работа (i, j ) должна быть отнесена к третьей, «промежуточной» зоне.

Моделируем продолжительность выполнения всех работ (i, j ), входя щих в сетевой проект, после чего определим, какие из этих работ (в детер минированной сети с фиксированными продолжительностями выполне ния) имеют коэффициент напряженности, больший 1 - h. Все эти работы будем считать «напряженными» и относящимися к «напряженной» зоне для случая одного «розыгрыша».

Многократно повторяя аналогичный «розыгрыш» ( N раз), получаем для каждой работы (i, j ) относительную частоту ее попадания в «напря N ij женную» зону p lj =, где N ij – количество случаев (из N «розыгрышей»), N когда работа (i, j ) имеет значение k H (i, j ), большее 1 - h. На основе теории проверки статистических гипотез сопоставляем величины p lj, p1 и p2 и принимаем решение, относить ли работу (i, j ) к первой группе, входит ли она во вторую или относится к третьей, промежуточной зоне. Эта задача может быть решена на основании применения интегральной теоремы Му авра-Лапласа и описана в [1.3].

Использование новых статистических понятий в системах сетевого планирования и управления может быть легко перенесено и на резервы Стохастические Сетевые Модели Планирования и Управления Разработками времени событий, работ и путей в сетевых моделях. Введем [1.3] понятие p -квантильного полного резерва времени для работы (i, j ), вычисляемого по формуле Ppп (i, j ) = W1- p {Pп (i, j )}, (1.5.4) где W1- p {Pп (i, j )} - (1 - p) -квантильная оценка эмпирического распределения величины Pп (i, j ), вычисляемого при каждом «розыгрыше» по формуле полного резерва времени для детерминированной сети Pп (i, j ) = tп ( j ) - t р (i ) - t (i, j ), широко известной из учебников по сетевому планированию (например [1.4], [2.6] и др.).

Аналогично определяется p -квантильный свободный резерв времени для работы (i, j ), вычисляемый по формуле Ppс (i, j ) = W1- p {Pс (i, j )}, (1.5.5) где Pс (i, j ) оценивается по формулам Pс ( i, j ) = t p ( j ) - t п ( i ) - t ( i, j ), Pс (i, j ) = Pп (i, j ) - P(i ) - P( j ), широко известным из аналогичных справочных монографий [2.6].

P -квантильный резерв времени для входящего в сетевую модель со бытия i определяется по формуле Pp (i ) = W1- p {P(i )}, где резерв времени P(i ) события i оценивается по формуле P(i ) = tп (i ) - t p (i ).

Наконец, p -квантильный резерв пути L определяется по формуле P p п ( L ) = W 1 - p { P ( L )}, (1.5.6) где P( L) = t kp - t ( L).

Заметим, что при увеличении коэффициента доверия p значения p квантильных резервов времени Ppп (i, j ), Pp (i), Ppп ( L) уменьшаются, не при нимая, однако, отрицательных значений (величины Pп (i, j ), P(i ) и Ppп ( L) в детерминированной сети всегда неотрицательны и равны нулю лишь в случае попадания на критический путь). Это имеет прямой технико экономический смысл: при увеличении степени уверенности (гарантии) выполнения проекта в намеченный срок мы не вправе перебрасывать «слишком много» ресурсов с имеющих зависимые резервы времени работ, чтобы не поставить ход разработки под угрозу срыва соответствующих плановых сроков (если коэффициент доверия равен p, то в случае пере броса более чем Ppп (i, j ) резервов времени с работы (i, j ) вероятность срыва планового срока становится больше величины 1 - p ).

Описанные выше p -квантильные резервы времени Ppп (i, j ), Pp (L), яв Глава 1. Вероятностные сетевые модели с детерминированной структурой ляются теоретико-вероятностными аналогами полных резервов времени, определяемых в детерминированных сетях с фиксированными временны ми оценками.

Возможен и другой подход к определению вероятностных резервов времени. Обозначим W p (i ) p -квантильную оценку самого раннего срока свершения события i. Аналогичную оценку можно получить и для после дующего события j, то есть W p ( j ).

Рассмотрим формулу Pp (i, j ) = W p ( j ) - Wp (i ) - tпл (i, j ), (1.5.7) где tпл (i, j ) обозначает плановое время выполнения работы (i, j ). В случае, когда время выполнения работы (i, j ) определяется детерминированной нормативной оценкой tнорм (i, j ), имеет место равенство tпл (i, j ) = tнорм (i, j ) ;

ес ли продолжительность выполнения работы (i, j ) есть случайная величина, в качестве величины tпл может быть принята p -квантильная оценка этой случайной величины, короче говоря, в каждом конкретном случае испол нителю работы (i, j ) задается ее плановая продолжительность. В некоторых случаях, формула (1.5.7) может быть использована при оптимизации сете вой модели.

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

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

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

Расчетный срок завершения работ по созданию нового комплекса для случая стохастической сетевой модели или детерминированной сетевой модели со случайными оценками работ определяется прибавлением к дате Стохастические Сетевые Модели Планирования и Управления Разработками начального события не продолжительности критического пути, а величины соответствующего p -квантиля. Одновременно, согласно описанной в §1. методике, основанной на теории статистического моделирования, оцени ваются вероятности выполнения всех работ по объекту в директивный срок и фиксируется соответствующий коэффициент доверия р Д. Если зна чение коэффициента р Д меньше заданного р Д (или в случае, если величи на р Д вследствие ее малого значения не может гарантировать выполнения хода разработки в намеченный директивный срок), руководство проекта проводит детальный анализ сетевой модели и, в необходимых случаях, ее оптимизацию. Рассмотрим некоторые способы анализа временных оценок сетевых моделей со случайными оценками работ.

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

Рассмотрим следующие четыре различных случая, которые могут иметь место при сопоставлении продолжительности критического пути с p -квантильными оценками [1.3]:

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

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

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

б) либо ответственные исполнители по каким-либо из этих работ про явили необъективность и сознательно расширили области определения времени выполнения этих работ.

В любом случае необходимо установить наименование этих работ и Глава 1. Вероятностные сетевые модели с детерминированной структурой исследовать возможность сужения интервала (a, b ), где a и b – соответст венно, оптимистическая и пессимистическая оценки. Заметим, что число такого рода работ может быть велико.

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

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

III. p -квантильные оценки при различных коэффициентах доверия существенно отличаются друг от друга;

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

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

IV. p -квантильные оценки отличаются несущественно, а длины кри тического и подкритического путей – существенно.

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

1. На самом напряженном пути (в смысле вероятности для него быть критическим) лежат работы с большими математическими ожиданиями продолжительности их выполнения, чем работы, лежащие на менее напря женных путях, но последние имеют большие дисперсии – разброс возмож ных значений времен их выполнения. А поскольку p -квантильные оценки зависят от математических ожиданий и дисперсий, в отличие от оценок длин критического пути, которые зависят только от средних значений, для значений p -квантильных оценок при различных p может иметь место из вестная нивелировка: уменьшение математических ожиданий (средних) компенсируется возрастанием дисперсий. Разумеется, этот случай нужда ется в детальном анализе составляющих сетевую модель работ с целью выяснения объективности оценок, задаваемых исполнителями работ.

2. Иногда может иметь место случай, когда постулируемый нами за кон распределения времени выполнения ряда работ на самом деле не имеет места. Тогда применение метода статистического моделирования поможет Стохастические Сетевые Модели Планирования и Управления Разработками это выявить. В этом случае необходимо более детально (на основе норма тивных данных) установить законы распределения времени выполнения работ, после чего вновь рассчитать квантильные оценки.

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

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

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

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

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

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

Рассмотрим в качестве примера форму аналитической документации, разработанную для одной из систем СПУ [1.3] (см. таб. 1.1).

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

Графы 1-5 формы не нуждаются в объяснении. В графе 6 записывает ся доверительная вероятность р Д, соответствующая директивному сроку для базисного варианта сетевой модели, а в графе 7 – аналогичная характе ристика для анализируемого варианта. Сопоставление граф 6 и 7 показы Глава 1. Вероятностные сетевые модели с детерминированной структурой вает, насколько повысилась мера гарантии выполнения хода разработки в директивный срок в результате оптимизации сетевого графика. Графа показывает ожидаемое время свершения основных событий для базисного варианта сетевой модели при заданном p3. Графа 9 оценивает аналогичные сроки, но уже для анализируемого варианта. Сопоставление граф 8 и 9 по зволяет оценить выигрыш во времени хода разработки при одинаковом ко эффициенте доверия p3.

Таблица 1. Статистическое моделирование в системе СПУ № варианта рас- Дата за Ожидаемые сроки свершения полнения Стр.

чета Шифр системы Анализи- основных событий (при p3 =...) Всего Базисного руемого стр.

Основные собы Сроки свершения Шифр тия этапа Приме Директивные Ожидаемые № п/п разра- чание Наиме- Вероятное р Д Дата Шифр ботки нование Дата Было Стало Было Стало 1 2 3 4 5 6 7 8 9 Контролер ВЦ Стадия разработки исходного плана должна оканчиваться построени ем календарного план-графика и доведением его до ответственных испол нителей.

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

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

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

В настоящее время можно выделить три основных направления реше ния этой проблемы [1.3, Гл.6, §5]:

Стохастические Сетевые Модели Планирования и Управления Разработками Аналитический метод усреднения задания календарного план-графика в системах СПУ предусматривает расчет календарных сроков начала и окончания работ, а также резервов времени и других временных парамет ров без использования статистического моделирования, на основе приме нения аналитического теоретико-вероятностного аппарата. К этому на правлению относится рассмотренный выше, в §1.4 настоящей главы, метод усреднения, применяемый в системах СПУ типа РЕRТ. Согласно этому методу, продолжительности всех работ сети, имеющие случайный харак тер, приравниваются соответствующим математическим ожиданиям, в ре зультате чего получается детерминированная сетевая модель с детермини рованными оценками.

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

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

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

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

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

Рассмотрим характер управляющих воздействий при оперативно календарном управлении системой СПУ. Основные виды управляющих воздействий следующие:

а) перераспределение материальных, людских или стоимостных ре сурсов внутри работ сетевой модели;

б) дополнительное привлечение ресурсов извне (для наиболее напря женных работ сети);

в) изменение топологии сетевой модели, приводящее к сохранению целевых функций проекта, но связанное с сокращением сроков его выпол нения;

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

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

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

II. Вторым направлением является применение методов статистиче ского моделирования для оценки плановых сроков свершения всех входя щих в сеть событий и, в соответствии с этим, установление плановых сро ков начала и окончания работ. Рассмотрим процедуру расчета календарно го план-графика [1.3-1.5].

После утверждения директивного срока вычислительный центр опре деляет соответствующие, p d -квантильные оценки самого раннего срока свершения входящих в сетевой график событий. Полученные оценки должны задаваться в качестве планового времени свершения всех событий и работ, входящих в сетевую модель. Иными словами, p -квантильная оценка самого раннего срока свершения события i должна служить плано вым сроком окончания всех работ (k, i ), оканчивающихся событием i. От дельные входящие в сетевой проект работы будут при этом, разумеется, обладать резервами времени (теперь уже вероятностными), рассмотрен Стохастические Сетевые Модели Планирования и Управления Разработками ными выше, в §1.5.

Итак, каждая работа (i, j ) сетевого графика получает плановые кален дарные сроки начала и окончания – соответственно, р Д -квантильные оценки величин t ран (i ) и t ран ( j ) в календарной шкале времени. Рассматри ваемая методика не претерпевает никаких принципиальных изменений, ес ли р Д -квантильные оценки самых ранних сроков заменить соответствую щими p -квантильными оценками самых поздних сроков. Доверительная р Д -квантильная оценка самого позднего срока свершения события i равна W1- p [t поз (i )] t,где W p ( x ) обозначает p -квантиль случайной величины x.

д Если p -квантильные оценки сроков свершения событий (ранних или поздних), принятые за директивные сроки, позволяют построить сетевую модель, имеющую топологию, совпадающую с исходной, то оценки про должительностей работ в такой сети, обеспечивающие выполнение уста новленных сроков свершения событий, могут быть определены из [ ] [ ] t (i, j ) = W p t ран ( j ) - W p t ран (i ) (1.6.1) либо [ ] [ ] t (i, j ) = W1- p t ран ( j ) - W1- p t ран (i ). (1.6.2) В том случае, если целью управления является соблюдение срока вы полнения проекта, установленного по p -квантильной оценке, и любая ра бота в сети в процессе выполнения проекта начинается в момент сверше ния события, непосредственно ей предшествующего, вычисленные по формулам (1.6.1) или (1.6.2) продолжительности работ в модели в случае смещения сроков событий, предшествующих работам, подлежащим вы полнению, дают представление о том, на какую величину эти работы должны быть уменьшены для компенсации допущенного ранее отклоне ния. Команды управления, направленные на компенсацию допущенного отклонения, как и в случае детерминированной модели, на критических путях должны реализоваться немедленно в том случае, если фактический срок свершения события превысил p -квантиль самого раннего (или самого позднего) допустимого срока. В случае невозможности такой немедленной реализации управление передается на работы, непосредственно за ними следующие. К недостатку рассмотренного направления относится невоз можность в полной мере использовать топологию сетевой модели: ведь все p -квантильные оценки свершения событий оцениваются по самым ранним (или по самым поздним, что принципиально одно и то же) срокам. Кроме того, сроки выполнения более ранних работ могут быть при этом методе необоснованно завышены, а более поздних, - наоборот, занижены.

III. Третье, комбинированное направление основано на следующем принципе. Управление системой СПУ ведется на основе аналитических Глава 1. Вероятностные сетевые модели с детерминированной структурой оценок, а контроль управления - на основе доверительных оценок, полу ченных методом статистического моделирования. На наш взгляд, сегодня эта методика представляется наиболее обоснованной.

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

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

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

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

*) При этом особое внимание необходимо обратить на работы, лежащие в р Д квантильной критической зоне.

Стохастические Сетевые Модели Планирования и Управления Разработками Глава 2. Статистические методы оптимизации ком плекса сетевых моделей §2.1 Статистические методы оптимизации сетевых моделей с де терминированными параметрами Разработанные в настоящее время задачи статистической оптимиза ции сетевых моделей можно (разумеется, достаточно приближенно) раз бить на три класса в зависимости от критерия оптимизации:

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

2. Оптимизация сетевых моделей по времени (оценка минимального времени сетевого проекта или комплекса сетевых проектов) при ограниче ниях на ресурсы.

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

I. Оптимизация сетевых моделей на основе минимизации отклонения наличных ресурсов от потребных связана с использованием резервов вре мени, входящих в сетевую модель работ. Для случая сетей с вероятност ными оценками работ можно использовать описанные в разделе 1.5 веро ятностные резервы времени. Задача сводится к использованию вероятно стных резервов времени, определяемых по формуле Pp (ij ) = W p ( j ) - W p (i ) - t пл (ij ), где W p (i ) и W p ( j ) - p -квантильные оценки самых ранних сроков свершения событий i и j, соответственно, tпл (ij ) - запланированное время выполнения работы (i, j ), p -коэффициент доверия, соответствующий заданному дирек тивному сроку выполнения всего проекта;

иными словами, p = РД.

Для каждой работы, входящей в сетевой график, предельные сроки начала и окончания работы (i, j ) установлены p -квантильными оценками самых ранних сроков свершения событий i и j. Следовательно, мы вправе варьировать сроками начала (окончания) работы (i, j ) только в пределах (Wp (i ),W p ( j )). Если считать, что наличные ресурсы на протяжении всего хода разработки постоянны, то задачу оптимального перераспределения време ни выполнения работ в пределах имеющихся у них вероятностных резер вов времени при введении критерия минимизации отклонения распределе ния трудоемкости от равномерного можно решить с помощью комбинации метода Монте-Карло и случайного шагового поиска. Заметим, что полное или частичное использование вероятностных резервов времени у одних работ не влияет на аналогичную процедуру у других работ. Поэтому мож но считать, что эти резервы времени Pp (ij ) независимы, и можно модели Глава 2. Статистические методы оптимизации комплекса сетевых моделей ровать времена начала и окончания каждой из работ независимо друг от друга.

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

Иными словами, на основе использования p -квантильных оценок лучше вести контроль управления, а не само управление. Вследствие этого целе сообразнее усреднить вероятностные оценки работ с использованием в дальнейшем зависимых резервов времени уже для вполне детерминиро ванной сетевой модели. В последнем случае эта задача имеет несколько модификаций [2.3-2.5]: а) случай оптимизации одного графика проведения работ (однотемная задача) потребляющего ресурсы одного вида;

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

В первом случае рассмотрим сетевую модель, состоящую из N работ (i, j ), для каждой из которых считаются заданными: а) t (i, j ) – время вы полнения этой работы;

б) n(i, j ) – интенсивность ресурса, необходимая для выполнения работы (i, j ).

Для разработки в целом заданы: а) T Д.H. – директивный срок начала разработки, т.е. такой срок, раньше которого разработка не может быть на чата;

б) T Д.O. – директивный срок окончания разработки, т.е. такой срок, позже которого разработка не может быть закончена.

1. Будем считать, что длина критического пути K, соединяющего на чальное и конечное события сети, меньше разности T Д. H. - T Д.O., так как в противном случае задача не имела бы решения. Разобьем весь период T Д. H. - T Д.O. на f календарных периодов. На каждом из f интервалов дли ны t q известна интенсивность наличных ресурсов Fq, q = 1, 2,... f.

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

Наиболее распространены следующие две формы функционала I :

I = (Qq ), f q = I = max (Qq ), (2.1.1) q 0 при Fq nq, n - F где Qq = q q при nq Fq 0.

Fq A при nq Fq = Здесь константа A – заранее фиксированное достаточно большое чис ло;

nq - потребная трудоемкость q -ого календарного периода;

Fq - налич ная трудоемкость.

Если обозначить через t H (i, j ) искомый срок начала выполнения рабо ты (i, j ), то срок окончания этой работы определится по формуле t0 (i, j ) = tH (i, j ) + t (i, j ).

Иными словами, алгоритм не предусматривает наличие перерыва в работе. Очевидно, что с целью получения искомого набора t H (i, j ) необхо димо минимизировать функционал, оценивающий степень близости ука занных эмпирических распределений интенсивностей.

Алгоритм оптимизации состоит из двух самостоятельных частей. В первой части определяются точка начала случайного поиска и соответст вующее этой точке значение функционала I. На первый взгляд может по казаться, что в качестве значений координат точки начала поиска в n мерном пространстве значений t H (i, j ) удобно выбрать сроки начала вы полнения всех работ t H (i, j ) по формуле t H (i, j ) = TД.Н. - tран (i ), где t ран (i ) - самый ранний срок свершения события i, начиная с момента выполнения проекта. Однако выбор такого рода начальной точки поиска не является рациональным, хотя в этом случае набор значений t H (i, j ) удов летворяет условиям задачи. При таком выборе начальной точки поиска приходится проводить поиск оптимального графика из точки, находящейся на границе области, что приводит к увеличению количества шагов поиска.

Гораздо удобней в этом случае начальную точку поиска «разыграть» мето дом статистических испытаний.

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

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

Глава 2. Статистические методы оптимизации комплекса сетевых моделей Наиболее интересен случай нескольких проектов с несколькими ре сурсами. Имеется N проектов, причем r -й проект (l r N ) состоит из M r работ. Будем считать, что все проекты выполняются одновременно.

Впредь будем обозначать работу (i, j ), принадлежащую r -му проекту, символом (i, j )r, продолжительность такой работы - t (i, j )r, интенсивность ресурсов, необходимых для выполнения этой работы, - n(i, j )r.

Алгоритм строится в предположении, что каждая работа потребляет только один вид ресурсов. Примем, что для r -го проекта (1 r N ) заданы (r ) (r ) TД.Н - директивный срок начала r -го проекта;

TД.О - директивный срок окончания r -го проекта.

Если K r – длина критического пути r -го проекта, то должно иметь место неравенство (r ) (r ) K r TД.О - TД.Н.

Разобьем календарный период от t H =[TД.Н ]min до t 0 =[TД.O ]max на f част (r ) (r ) ных календарных периодов q и каждого шифра ресурсов m ( m = 1,2,..., S ) задается Fmq - суммарная наличная интенсивность. Мера отклонения по требной интенсивности ресурсов от наличной оценивается функционалом следующего вида.

Обозначим символом mmq потребную суммарную интенсивность по m -му шифру ресурса в q -м календарном периоде, 1 m S, 1 q f. Опре делим функцию Qmq согласно формуле 0 при Fmq nmq, n - Fmq (2.1.2) = mq при nmq Fmq Qmq Fmq A при nmq Fmq = 0, где A – достаточно большое число (константа A выбирается заранее). Зна чение функционала I может быть определено по следующим формулам:

I = Qmq, (2.1.3) m q I = max Qmq. (2.1.4) m q Разумеется, нет никаких оснований утверждать, что эти формулы да ют единственно возможную форму записи функционала I. Алгоритм оп тимизации календарного графика справедлив и для функционалов иного вида.

В результате локального случайного поиска [2.7] мы получаем ло кальный оптимум. Для получения глобального оптимума процедуру алго ритма повторяют l раз (число l фиксируется заранее) и получают при этом различные значения t Hk +1) (i, j )r и t0(k +1) (i, j )r. После этого выбирают тот набор ( Стохастические Сетевые Модели Планирования и Управления Разработками t Hk +1) (i, j )r и t0k +1) (i, j )r, который соответствует минимальному из значений ( ( функционала I, получаемого на финальном шаге случайного поиска и фиксируют его в качестве «глобального» оптимума – оптимального иско мого календарного графика.

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

Необходимо сформулировать задачу оптимизации календарного гра фика работ t H (i, j )r и t0 (i, j )r, 1 r N, таким образом, чтобы распределение наличной интенсивности ресурсов максимально отклонялось от распреде ления потребной интенсивности, при условии, что наличная интенсивность всегда превышает потребную. В этом случае функционалы типа (2.1.3) или (2.1.4) неприменимы. Хорошие результаты дает применение функционалов следующих видов:

I = Vmq, (2.1.5) m q или I = min Vmq, (2.1.6) m q где Vmq = (Fmq - nmq ) (2.1.7).

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

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

а) Задача с переменными интенсивностями ресурсов. При решении этой задачи применяются два типа показателей работ:

1) продолжительность t (i, j ) выполнения работы (i, j ) (например, в днях);

2) трудоемкость работы F (i, j ) (в человеко/часах или человеко/днях).

Глава 2. Статистические методы оптимизации комплекса сетевых моделей Обозначим символом n(i, j ) интенсивность ресурса, который может быть использован при выполнении работы (i, j ). Тогда зависимость между продолжительностью t (i, j ) и трудоемкостью F (i, j ) работы (i, j ) может быть выражена формулой F(i, j ) t (i, j ) = C (2.1.8), n(i, j ) где C – коэффициент пропорциональности, постоянный для всех работ.

Заметим, что каждая работа (i, j ) может потреблять различное количество ресурсов. При этом существуют наибольшее nmax (i, j ) и наименьшее nmin (i, j ) значения интенсивности ресурсов, производительно используемых при выполнении работы. Эти значения nmax и nmin иногда называют максималь ным и минимальным фронтом производительной работы [2.5]. Каждое значение n(i, j ) находится в интервале [n min (i, j ), n max (i, j )], и ему соответству ет продолжительность t (i, j ), определяемая по формуле F(i, j ) t (i, j ) = C.

n(i, j ) Задача оптимизации по времени ресурсов сетевой модели состоит в получении оптимального набора значений n(i, j ) и сроков начала и оконча ния всех работ разработки, минимизирующего время выполнения всех ра бот и удовлетворяющего наличным ресурсам.

Рассмотрим разработку, состоящую из N работ (i, j ). Пусть для каж дой работы (i, j ) заданы значения nmin (i, j ) и nmax (i, j ). Если F (i, j ) – трудоем кость работы (i, j ), а tmin (i, j ) и tmax (i, j ) - минимальная и максимальная про должительности работы (i, j ), соответственно, то имеет место равенство nmin (i, j ) tmax (i, j ) = nmax (i, j ) tmin (i, j ) = CF (i, j ).

Пусть при выполнении разработки используется S видов ресурсов.

Для того чтобы указать, какой вид ресурсов потребляет данная работа (i, j ), введем нижний индекс l. Иными словами, символ (i, j )l означает, что рабо та (i, j ) использует l -й вид ресурса (1 l S).

Примем, что наличные ресурсы для каждой из S специальностей рас пределены равномерно по всем m календарным периодам. Обозначим nl наличные ресурсы l -го вида для всех календарных периодов, тогда для любого l (1 l S ) nl max [n min (i, j )l ]. (2.1.9) i, j Невыполнение этого неравенства означает, что при данных наличных ресурсах разработка не может быть выполнена за конечный срок.

Строятся функционалы, которые будут использоваться при выяснении вопроса, удовлетворяют ли наличные ресурсы потребным или нет. Обо значим nlp максимальное количество ресурсов l -ого вида, одновременно Стохастические Сетевые Модели Планирования и Управления Разработками потребляемых в p -м календарном периоде, а m – число периодов. Тогда указанные функционалы имеют вид S m I = qlp, (2.1.10) l =1 p = m I = max qlp, (2.1.11) l p = qlp = (1 - sign Alp ), (2.1.12) Alp = nl - nlp.

Пространством решений поставленной задачи называют множество n(i, j ) значений начала и окончания работ t H (i, j ) и t O (i, j ), для которых ожидаемые ресурсы не превосходят наличные, что эквивалентно равенству нулю функционала I. Очевидно, что если хотя бы для одного l (1 l S ) имеет место неравенство n(i, j )l nl, (2.1.13) то набор значений интенсивностей ресурсов n(i, j )l не принадлежит про странству решений. Поэтому рассматриваются только наборы nl, удовле творяющие неравенству nmin (i, j )l n (i, j )l min {nt, nmax (i, j )l }, и в пространстве решений ищется оптимальное решение, для которого время выполнения разработки будет минимальным.

Оптимальное решение получается сочетанием методов Монте-Карло и случайного поиска путем использования поэтапной процедуры [2.7]. Для случая переменных интенсивностей ресурсов, помимо постепенного уве личения времени и решения оптимальной задачи, модифицируем метод статистической оптимизации следующим образом. Сначала фиксируем на бор интенсивностей ресурсов по каждой из работ сети (в дальнейшем по этим показателям будет осуществлять случайный поиск). Получив для функционального набора интенсивностей наименьшее значение продол жительности разработки (идея такого рода минимизации изложена нами выше), мы осуществляем случайный поиск в пространстве интенсивно стей, минимизирующий локальный временный минимум, соответствую щий частному набору интенсивностей. Иными словами, мы получаем одну из точек пространства решений, а в дальнейшем осуществляем поиск в этом пространстве, определяя глобальный минимум продолжительности разработки.

Рассмотренный в [2.3] случай нескольких разработок, выполняемых практически одновременно, приводит к решению аналогичной оптималь ной задачи. Пусть имеется L (L 1) разработок, каждая из которых содер жит N r работ (l r L ). Все остальные условия совпадают с условиями рас смотренной задачи оптимизации односетевой модели, и для всех проектов L указано время TД.Н. Необходимо найти такой набор значений n (r ) (i, j )l, t Hr ) (i, j )l, t 0r ) (i, j )l, который соответствует минимальному времени заверше ( ( Глава 2. Статистические методы оптимизации комплекса сетевых моделей ния всех разработок, при условии равноправия всех разработок. Под рав ноправием всех разработок понимается отсутствие приоритета одной раз работки перед другой.

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

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

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

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

Допустим, что комплекс состоит из общего числа K проектов, причем первая группа содержит K1 проектов, вторая – K 2 проектов, третья – K проектов, а K1 + K 2 + K 3 = K. Предположим, что все проекты в группе могут выполняться практически одновременно. Оптимизируя план для первой группы разработок, найдем такое расписание работ t H (i, j )k и t 0 (i, j )k (1 k K 1 ), при котором общее время выполнения всех K1 разработок, начиная с фик сированного директивного срока, становится минимальным. Для этого применяем изложенный алгоритм к первым K1 проектам, считая в качестве наличных ресурсов все ресурсы предприятия.

По окончании работы алгоритма для первой группы проектов получа ем оптимальный план-график t H (i, j )k и t0 (i, j )k. Задача оптимизации кален дарного плана для второй группы разработок может быть решена с исполь зованием того же алгоритма, что и для первой группы. Разница состоит лишь в том, что вместо полного объема начальных ресурсов в качестве на Стохастические Сетевые Модели Планирования и Управления Разработками личных используются те ресурсы, которые остались после выделения ре сурсов разработкам первой группы в результате окончания работы алго ритма построения календарного плана работ для разработок первой груп пы.

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

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


Процедура оптимизации для каждой из групп разработок сводится к оптимизации календарного графика работ t H (i, j )k и t 0 (i, j )k, 1 k K i, i = 1,2,3, посредством реализации соответствующего алгоритма. Полученное реше ние t H (i, j )k и t 0 (i, j )k, 1 k K i, i = 1,2,3, будем условно называть «глобальным».

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

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

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

Рассмотрим сложный комплекс, состоящий из K разработок, для каж дой из которой построена сетевая модель, содержащая N работ (i, j )r (1 r K ), причем для каждой сетевой модели зафиксированы дирек тивные сроки начала Т Дr.)Н. Обозначим n S - интенсивность общих суммар ( ных ресурсов s -го вида (1 s S ), имеющихся в наличии на разрабатываю Глава 2. Статистические методы оптимизации комплекса сетевых моделей щем предприятии и подлежащих распределению между разработками, Qmr s - потребная интенсивность ресурса вида s, потребляемая r -й разработкой в m -м календарном периоде в соответствии с терминологией предыдущего алгоритма), а Qrs - выделенная r -й разработке наличная интенсивность s го вида ресурса на всем протяжении хода этой разработки. Кроме того, для каждой работы (i, j )r, потребляющей ресурсы вида s, зададим минималь ную и максимальную интенсивности ресурсов - nmin (i, j )r и nmax (i, j )r, а также s s трудоемкость работы q s (i, j )r, причем имеет место равенство q s (i, j )r t (i, j )r = C (2.1.14), n s (i, j )r где t (i, j )r - продолжительность работы (i, j )r, а C - коэффициент пропор циональности, который мы примем постоянным.

Будем называть пространством решений множество Qrs и n s (i, j )r (1 r k, 1 s S ) значений сроков начала и окончания работ t H (i, j )r и t 0 (i, j )r, для которых потребные ресурсы не превосходят наличные. Это эк вивалентно равенству нулю одного из функционалов I :

S M I = Gsm, (2.1.15) s =1 m = или M I = max Gsm, (2.1.16) s m = где G = 1 - sign Asm, Asm = Qrs - max Qrm. (2.1.17) s Нам необходимо в пространстве решений найти такое оптимальное решение, для которого будет достигаться минимум наибольшей из длин критических путей для всех разработок.

Очевидно, имеет смысл рассматривать только те наборы n s (i, j ), для которых выполнено неравенство nmin (i, j ) r n s (i, j )r min{ nr, nmax (i, j ) r }.

s s В приведенном в [2.5] алгоритме последовательно решаются две зада чи: а) ресурсы распределяются между разработками;

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

При решении первой задачи для определения начальной точки поиска ресурсы предприятия эвристическим образом делятся между разработками пропорционально интенсивности потребления этого вида ресурса. В пер вом приближении интенсивность ресурса вида s, выделяемую на r -ю раз работку, можно считать равной n s max Qmr s (2.1.18) Q= (1 s S ), (1 r K ), (1 m M ).

s m max Qmr r s m Стохастические Сетевые Модели Планирования и Управления Разработками Можно предложить и другие методы получения начальной точки по иска для задачи распределения ресурсов между разработками. В частности, распределение ресурсов можно считать пропорциональным суммарной ин тенсивности ресурса вида s, используемого на разработке r.

Идея алгоритма заключается в проведении локального поиска в про странстве интенсивностей Qrs - интенсивности s -гo вида ресурсов, выде ляемой r -й разработке. Для каждой точки поиска решается экстремальная задача нахождения по заданной интенсивности ресурсов Qrs оптимального набора интенсивностей n s (i, j ) и сроков начала и окончания всех работ r -й разработки, минимизирующих время Т z(r ) выполнения ( z - номер шага по иска). Иными словами, на этом этапе интенсивность ресурса Qrs, выделяе мая r -й разработке, распределяется для всех видов ресурсов между рабо тами соответствующей сети, в результате чего составляется план-график выполнения работ таким образом, чтобы общее время выполнения разра ботки было минимальным. Методом Монте-Карло разыгрывается ряд на чальных точек поиска в пространстве интенсивностей. В процессе поиска ищется min Tz( r ), которое фиксируется в качестве локального оптимума.

Глобальный оптимум фиксируется на основе сравнения локальных опти мумов, полученных методом Монте-Карло.

III. Минимизация объема потребляемых ресурсов [2.3, 2.5].

Рассмотрим сложный комплекс, состоящий из K разработок, выпол няемых практически одновременно, причем r -я разработка (1 r K ) со стоит из N r работ (i, j ) r. Обозначим символом n r (i, j ) s интенсивность ре сурса вида s (1 s S ), используемого для выполнения работы (i, j )r, сим волом t (i, j ) r - продолжительность работы (i, j )r, а символом g r ( i, j ) s - тру доемкость этой работы. Для удобства изложения будем считать, что каж дая отдельная работа производится ресурсом одного и того же вида.

Заметим, что обычно имеет место приближенное равенство g r (i, j ) s » n r (i, j ) s t r (i, j ) s.

Зададим для каждого из проектов r (1 r K ) директивный срок нача ла Т д. н и директивный срок окончания Т д.r )о r -го проекта. Очевидно, что для (r ) ( каждой сетевой модели продолжительность критического пути K r не должна превышать разности Т д.r )о - Т д.r )н (1 r K ).

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

На каждом разрабатывающем предприятии всегда можно выделить из множества ресурсов такие, которые представляют большую ценность, вследствие чего им следует приписать больший вес, нежели представляю Глава 2. Статистические методы оптимизации комплекса сетевых моделей щим меньшую ценность. Ввиду этого при решении задачи оптимизации календарного плана комплекса сетевых моделей мы стремимся для каждо го из проектов создать такое расписание работ, не выходящих за дирек тивные сроки, при котором суммарная взвешенная интенсивность достига ла 6ы минимума. Если обозначить ns – интенсивность ресурса вида s, ис пользуемого при выполнении всех разработок, a r s – вес ресурса вида s на данном предприятии, то задача состоит в минимизации функционала S I = r s ns. (2.1.19) s = Отметим, что в качестве значений ns целесообразно брать приведен ные показатели (либо взятые в единицах какого-либо эталона, который для каждого из видов ресурса может быть различным). Если же это по каким нибудь причинам сделать невозможно, необходимо обратить особое вни мание на достоверность отбора приоритетных показателей r s.

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

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

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

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

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

1) Минимизация объема потребляемых ресурсов при ограничении на время и стоимость выполнения проекта. Рассмотрим задачу оптими зации, описываемую нами с учетом ограничений на время и стоимость разработки. Алгоритм основан на минимизации мощности самого интен сивного ресурса по всем видам ресурсов и всем частным календарным пе Стохастические Сетевые Модели Планирования и Управления Разработками риодам, считая, что распределение ресурсов по этим периодам имеет вид ступенчатой функции.

Рассмотрим сетевую модель, содержащую N работ (i, j ), каждая из которых характеризуется продолжительностью t (i, j ), интенсивностью по требления n s (i, j ) ресурса вида s и трудоемкостью работы q s (i, j ). Предпо ложим, что на каждой работе используется только один вид ресурса (всего при выполнении разработки участвуют S видов невзаимозаменяемых ре сурсов) и каждая из работ не может быть прервана при ее выполнении.


При этом имеют место очевидные соотношения:

a) q s (i, j ) = n s (i, j ) t (i, j ), б) tmin (i, j ) t (i, j ) tmax (i, j ), где t min (i, j ) и tmax (i, j ) - минимально и максимально допустимое время вы полнения работы;

в) nmin (i, j ) n s (i, j ) nmax (i, j ), s s где nmin (i, j ) и nmax (i, j ) - минимально и максимально возможные интенсив ности, используемые при выполнении работы (i, j ) ;

г) n s (i, j ) t (i, j ) nmin (i, j ) t max (i, j ) nmax (i, j ) tmin (i, j ).

s s Обозначим стоимость работы (i, j ) символом C (i, j ) и примем справед ливым соотношение C (i, j ) = A(t ) t (i, j ) + B, где A(t ) – величина, зависящая от времени, а B – величина, не зависящая от времени. Стоимость всей разработки обозначим С = С (i, j ).

(i, j ) Будем считать, что планируемый интервал времени разбит на M ин тервалов с переменным индексом m (1 m M ).

В ряде различных разработок представляет интерес для каждой из ра бот сетевой модели определить время начала t H (i, j ), окончания t O (i, j ) и интенсивность потребления ресурсов n s (i, j ) таким образом, чтобы дости гался минимум функционала L = max max Qm r s, (2.1.20) s s m где Q – интенсивность потребления ресурсов вида s на интервале m, r s – s m вес ресурса вида s на данном предприятии, а также выполнялись бы огра ничения на:

1) стоимость разработки С = C (i, j ) C ', (i, j ) где C ' – заданная величина;

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

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

Рассмотрим сетевую модель с принятыми в предыдущем разделе предпо ложениями. Поставим задачу определения для каждой из работ (i, j ) сете вой модели: продолжительности t (i, j ), интенсивности – n s (i, j ) потребляе мого ресурса вида s, времени начала – t H (i, j ) и времени окончания – t O (i, j ) работы (i, j ) таким образом, чтобы минимизировать общее время выполне ния разработки со следующими ограничениями:

а) по всем видам ресурсов s (1 s S ), на каждом планируемом пе риоде времени m (1 m M ) суммарная трудоемкость по всем работам се тевой модели Qm не должна превосходить заданных ограничений по дан s ному виду ресурса F s ;

б) стоимость разработки не должна быть больше наперед заданной величины C '. Иными словами, должны быть выполнены неравенства:

1) max Qm F s, s m C (i, j ) C '.

2) C = (2.1.21) (i, j ) Задача решается в предположении, что имеет место очевидное нера венство nmin (i, j ) F s (1 1 S, 1 m M ), а ограничения на ресурс задаются s в виде постоянной величины.

3) Минимизация стоимости разработки при ограничении на ре сурсы и время выполнения. Допустим, что задана сетевая модель и сде ланные ранее предположения имеют место. Ставится задача определения для всех работ (i, j ) сетевой модели времени начала их выполнения - t H (i, j ) и времени окончания - t O (i, j ), продолжительности - t (i, j ), а также интен сивности - n s (i, j ) потребления ресурса вида s таким образом, чтобы общая стоимость разработки, соответствующей рассматриваемой сетевой модели, была минимальной и выполнялись бы следующие два ограничения:

1) ТкрТдир, т. е. длина критического пути должна быть ограничена директивными сроками;

2) потребность в ресурсе s на интервале m (1 s S ), обозначаемая нами символом Qm, не должна превышать F s - ограничения, накладывае s мого на ресурс вида s.

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

Стохастические Сетевые Модели Планирования и Управления Разработками § 2.2 Оптимизация разработок со случайными оценками продол жительности операций для случая детализированных ресурсов Рассмотрим сетевую модель проекта G (Y,U ), где Y - множество всех вершин (событий), а U - множество дуг (работ) сетевого проекта.

Предположим, что все работы проекта (i, j ) U, i Y, j Y, пронуме рованы числами натурального ряда от 1 до n. В дальнейшем наряду с об щепринятым обозначением работ (i, j ) будем пользоваться обозначением k (1 k n), где k - порядковый номер соответствующей дуги (i, j ).

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

На процесс выполнения каждой работы накладывается условие не прерывности, а продолжительности работ t k, k = 1,2,..., n, считаются случай ными величинами, описываемыми -функциями распределения с плотно стью [2.2] ( x - ak )(bk - x )2. (2.2.1) j ( x) = (bk - ak ) Параметры a k и bk для каждой работы с номером k определяются из заданных функциональных зависимостей:

ak = f1 (rks ), bk = f 2 (rks ), (2.2.2) rks rks rks, 1 s m, min max где a k - минимальное значение продолжительности t k при определенной интенсивности ( rks ) потребления s -го ресурса на k -й работе;

bk - макси мальное значение t k при интенсивности rks ;

rks, rks - соответственно, ми min max нимальное и максимальное допустимое значение интенсивности s -го ре сурса на k -й работе. Суммарные максимальные интенсивности (уровни) потреблений ресурсов Qs ( s = 1,2,..., m ) могут изменяться в пределах от As до Bs, т. е.

Аs Qs Bs, s = 1, 2,..., m. (2.2.3) Кроме этого, заданы еще Tпл - плановый срок выполнения проекта;

r s приоритетные коэффициенты, определяющие либо дефицит, либо стои мость s -x ресурсов.

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

Задача А. Требуется определить такие значения rks (k = 1,2,..., n ) и Qs ( s = 1,2,..., m ), которые минимизировали бы функционал m J = Qs r s (2.2.4) s = при условиях Глава 2. Статистические методы оптимизации комплекса сетевых моделей P{T Tпл } Pпл, (2.2.5) Аs Qs Bs, s = 1, 2,..., m, (2.2.6) rks rks rks, k = 1,2,..., n, 1 s m. (2.2.7) min max Допустим, что коэффициенты r s отображают стоимость аренды или эксплуатации s -x ресурсов. Тогда задачу можно сформулировать следую щим образом: определить минимальный объем ресурсов (в стоимостных единицах измерения), обеспечивающий выполнение проекта за время (T ), не превышающее плановое время ( Tпл ) с вероятностью, не ниже заданной ( Pпл ).

Задача может быть решена на основе алгоритма, построенного на со четании методов направленного и ненаправленного случайного поиска.

Необходимыми условиями существования решения задачи А являют ся:

а) rks Bs, k = 1,2,..., n ;

1 s m ;

min б) при rks = rks, k = 1,2,..., n и Qs = Bs, P{T Tпл } Pпл.

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

Задача AI: минимизировать время выполнения проекта при фиксиро ванных продолжительностях работ ( t k ) и интенсивностях потребления ре сурсов на работах ( rks ), а также при заданных уровнях ресурсов ( Qs ). Алго ритм решения этой задачи рассмотрен в работе [2.5].

Задача АII: определить вероятность P{T Tпл }, где T - продолжитель ность выполнения проекта, при заданных ограничениях на ресурсы и при случайных длительностях работ ( t k ). Алгоритмизация этой задачи рас смотрена в работах [2.3-2.5].

Задача AIII: определить набор rks (rks rks rks ), максимизирующих min max P{T Tпл } при заданных значениях уровней потребления ресурсов ( Qs ). Ре шение задачи AIII может быть легко реализовано путем использования ме тодов направленного случайного поиска, причем задачи AI и АII решаются во внутреннем цикле также с использованием методов случайного поиска в сочетании с методом Монте-Карло.

Предположим, что задача А решена. Однако решение этой задачи (значения rks и Qs ) еще не дает ответа на вопрос, в какие сроки нужно обеспечить все работы проекта необходимыми ресурсами, чтобы гаранти ровать выполнение проекта к плановому сроку Tпл с заданной вероятно стью Pпл. Последнее может быть получено путем решения задачи Б.

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

Стохастические Сетевые Модели Планирования и Управления Разработками Допустим, что нам известен закон распределения случайной величины t H (i, j ) - времени начала выполнения работы (i, j ). Минимальный отрезок, на котором O Ft (t ) = P{tн (i, j ) t} 1, н обозначим через t нmin (i, j ), t нmax (i, j ) или t нmin (k ), t нmax (k ). Очевидно, что этот интервал зависит от процедуры моделирования значений t H (i, j ). Поэтому мы вправе ожидать, что для некоторых работ (i, j ) U, имеющих значи тельный резерв времени относительно Tпл, длина интервала t нmin (k ), t нmax (k ) и его границы могут меняться при изменении условий розыгрыша t H (k ).

Из всех возможных вариантов t нmin (k ), t нmax (k ) наибольший интерес для нас представляют интервалы inf{ t н (k )}, inf{ t н (k )}, (2.2.8) min max sup{t н (k )}, sup{t н (k )}. (2.2.9) min max Если (2.2.8) и (2.2.9) соответствуют условиям P{T Tпл } P пл, (2.2.10) P{Qs (t ) Qs, s = 1, 2,..., m} = 1, (2.2.11) Ф где Qs (t ) - эпюра, описывающая фактическую потребность в s -м ресурсе Ф на интервале [0, Tпл ], и если в процедуре розыгрыша значений t H (k ) следо вать условию t н (k ) sup t нmin (k ) + Dt (Dt 0), то это неизбежно приведет к на рушению условия (2.

2.10). Введение же в процедуру розыгрыша t H (k ) ус ловия tн (k ) inf{tн (k )} - Dt (Dt 0) min приведет к нарушению условия (2.2.11). Последнее вытекает из того, что мы предполагаем начало выполнения проекта в момент t = 0. Следствием из вышесказанного является то, что наиболее приемлемое время начала выполнения любой работы (i, j ) U (в смысле соблюдения условий (2.2.10) и (2.2.11)) лежит в интервале [inf{tнmin (k )}, sup{tнmin (k )}]. Отсюда вытекает и целесообразность выбора срока обеспечения работы (i, j ) необходимыми ресурсами также в интервале [inf{tн (i, j )}, sup{tн (i, j )}] ~ [inf{tн (k )}, sup{tн (k )}].

min min min min Введем обозначения:

inf{ tн (k )} = t * (i, j ) = tk, (2.2.12) min * sup{tн (k )} = t * *(i, j ) = t k, (2.2.13) min ** где k - порядковый номер работы (i, j ).

Глава 2. Статистические методы оптимизации комплекса сетевых моделей Примем tk* за наиболее ранний срок, a t k* - за наиболее поздний срок * подачи ресурсов к работе с номером k. Таким образом, задача Б сводится к определению для всех работ k U значений tk* и tk**.

Решение задачи проводится в три этапа. На первом этапе многократно моделируем значения длительностей работ tk [ak, bk ], распределенных по -закону с плотностью (2.2.1). После каждого розыгрыша набора значений t k решаем задачу AI (минимизация времени выполнения проекта при фик сированных продолжительностях работ ( t k ), интенсивностях rks и уровнях Qs ), а также задачи АII и AIII.

Проведение первого этапа дает нам N наборов { t H (k ), k = 1,2,..., n } и последовательность N значений Tl, l = 1,2,..., N, где t H (k ) - время начала вы полнения k -й работы;

Tl - время выполнения проекта при l -м розыгрыше значений t k.

Решение задачи Б мы проводим после решений задачи А и поэтому можем быть уверены, что условие (2.2.10) выполняется. Условие (2.2.11) вытекает из неравенств Qsф (t ) Qs, s = 1, 2..., m;

0 t Tпл, которые соблюдаются при каждом решении задачи А.

Построим n последовательностей:

(t н (k ), tн (k ),..., tн (k )), k = 1, 2,..., n, (2.2.14) (1) (2) (N) где tн (k ) - время начала k -й работы при l -м розыгрыше ( l = 1,2,..., N ).

(1) Упорядочив каждую последовательность (2.2.14) по неубыванию, мо жем построить для каждой работы с номером k вариационный ряд и соот ветствующий интервал (tнmin (k ), (tнmax (k )) изменения признака.

Обозначим через X 0 набор {tнmin (k ), k = 1, 2,..., n}, а через Z 0 {tн (k ), k = 1, 2,..., n}.

max На втором этапе находим для всех работ интервалы (2.2.8). Границы inf{ t н (k )}, inf{t н (k )} определяем, организуя направленный случайный по min max иск в пространстве значений переменных Lk с минимизацией функционала Lk - tн (k ) min n J = (2.2.15) ( k ) - t н (k ) max min k =1 t н при условиях tн (k ) Lk tн (k ), k = 1, 2,..., n, (2.2.16) min max Q (t ) Qs, s = 1,..., m;

0 t Tпл, ф s где Qsф (t ) - функция времени, описывающая фактическую потребность в s -м ресурсе. Значения Lk, минимизирующие (2.2.15), принимаем за inf{ tн (k )}.

max За начальную точку поиска в пространстве значений Lk выбираем точку Z 0 = {tнmax (k ), k = 1, 2,..., n}. На каждом шаге поиска в пространстве зна Стохастические Сетевые Модели Планирования и Управления Разработками чений { Lk } для проверки условия (2.2.16) решаем некоторое фиксирован ное число С раз (для C различных наборов значений длительностей работ { t k }) задачу минимизации уровней потребления ресурсов, т.е. минимиза ции функционала ( ) max Qsф (t ) - Qs m J1 = t 1 + sign(max Qs (t ) - Qs ) Qs s =1 t при заданном времени выполнения T = Tпл. При решении задачи минимиза ции J 1 значения t H (k ) моделируем таким образом, чтобы выполнялись ус ловия t н ( k ) L k, k = 1, 2,..., n. (2.2.17) Если min J 0 хотя бы для одного из C наборов { t k }, то разыгранные Lk не могут служить оценкой inf{ tн (k )}.max Искомыми значениями tk* считаем значения min t н (k ), определенные по C реализациям минимизации J 1 для последнего удачного розыгрыша (в процессе поиска) значений Lk.

Третий этап решения задачи Б – это определение tk * = sup{tн (k )}.

* min Значение t k* определяем, применяя направленный случайный поиск в * пространстве значений M k c минимизацией функционала tн ( k ) - M k max n J = (2.2.18) ( k ) - t н (k ) max min k =1 t н при условиях tk M k tн (k ), k = 1, 2,..., n, (2.2.19) * max Qsф (t ) Qs, s = 1, 2,..., m;

0 t Tпл, (2.2.20) tн (k ) M k, k = 1, 2,..., n, (2.2.21) P{T Tпл } Pпл. (2.2.22) За начальную точку поиска выбираем точку X 0 = {tH (k ), k = 1,..., n} или min X 0 = {t H, k = 1,..., n}. На каждом шаге поиска для проверки условий (2.2.20) и (2.2.22) решаем некоторое большое число ( C ) раз задачу минимизации времени выполнения проекта при постоянных tk и tks. Эта задача отличает ся от ранее описанной задачи А условием (2.2.21) и может быть успешно реализована на основе алгоритма [2.4] с модифицированной процедурой розыгрыша t H (k ) таким образом, чтобы выполнить условие (2.2.21).

Каждый j -й розыгрыш значений M k считается удачным, если J j J j -1, где J j, J j -1 - значения функционала (2.2.18) на j -м, ( j - 1 )-м шагах поиска.

Искомыми значениями tk** = sup{t H (k )} считаем M k, минимизирующее min Глава 2. Статистические методы оптимизации комплекса сетевых моделей (2.2.18), при условиях (2.2.19-2.2.22).

Заметим, что полученные tk* и t k* по описанным выше алгоритмам для * каждой k -й работы такие, что tk* t k*. Найдем для каждого k величину Rk :

* Rk = t k * - t k. (2.2.23) * * Величина Rk характеризует резерв времени подачи ресурсов к k -й ра боте, а значит в некотором смысле, и критичность k -й работы.

Задачи календарного планирования. Вследствие случайного харак тера длительности работ tk построение календарного плана разработки вы зывает большое количество трудностей. В работах [2.1-2.5] предлагается проводить комбинированное управление разработкой со случайными дли тельностями: оптимальное прогнозирование - на основе доверительных экспертных оценок, а календарное планирование и управление - на основе усредненных оценок продолжительностей работ.

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

а) QsTпл rks t k, s = 1,2,..., m, (2.2.24) kU s где tk - средняя оценка продолжительности работы ( tk ), определяемая по формуле:

3a k + 2bk ;

tk = U s - множество работ проекта, требующих для проведения s -й вид ресурса;

б) tкр Tпл, где tкр - длина критического пути сети при tk = tk, k = 1,2,..., n.

Покажем, что условие (2.2.24) выполняется, если при решении задачи (2.2.4) получено оптимальное решение (rks, Qs, k = 1,2..., n;

s = 1,2,..., m ) и tk = M [tk ], (2.2.25) где M [t k ] - математическое ожидание случайной величины tk.

Доказательство.

(2.2.26) rks tk = w ks, где wks - объем k -й работы при tk = t k.

Из условия (2.2.25) и (2.2.26) вытекает w ks = M [w ks ].

Тогда по теореме сложения математических ожиданий M [w ] = M w = M [Vs ], r (2.2.27) t= ks k ks ks k U s kU s k U s где Vs – объем работ проекта по s -му ресурсу.

Стохастические Сетевые Модели Планирования и Управления Разработками В алгоритме решения задачи А для всех j -х моделируемых наборов {k} j (1 j N ) строго соблюдалось условие Q(s j) (t ) Qs, (2.2.28) где Qs (t ) - функция загрузки s -х ресурсов при j -м наборе {tk }j.

( j) Функция Qs( j) (t ) - кусочно-постоянная, а переменная t - дискретная, принимающая значения 0,1,..., Tпл. По определению Qs( j ) (t0 ) - это значение Qs( j ) (t ) на отрезке (t 0 - 1, t 0 ). Следовательно, в силу (2.2.28) Tпл Q ( ) (t ) Q T (2.2.29), 1 j N.

j s s пл t = Просуммируем неравенства (2.2.29) для всех j и поделим на N.

Тогда Tпл N Q( ) (t ) Q T (2.2.30) j, s s пл N j =1 t = Qs( j ) (t ) Tпл Tпл Tпл N N Qs( j) (t ) = = Vs (t ), N N j =1 t =1 t =1 j =1 t = где Vs (t ) - среднее значение объема работ по s -му ресурсу на отрезке (t - 1, t ).. Отсюда Tпл V (t ) = V. (2.2.31) s s t = По теореме Чебышева при N ® Vs ® M [Vs ]. (2.2.32) p Из (2.2.30-2.2.32) следует M [Vs ] QsTпл, а так как имеет место (2.2.27), то наше утверждение (2.2.24) доказано.

Допустим, что нами получены такие rks и Qs, что условие (2.2.24) вы полнятся.

Ранее было показано, что наиболее приемлемое время начала выпол нения k -й работы (в смысле гарантии условий (2.2.10) и (2.2.11)) находит ся в интервале t k*, t k(**. В этой связи задачу определения t H (k ) и t 0 (k ) дадим в следующем виде.

Требуется определить сроки начала и окончания всех работ проекта ( t H (k ), t 0 (k ), k = 1,2,..., n ), минимизирующие функционалы [ ] n J1 = t H (k ) - tk (2.2.33) * k = или J 2 = [t H (k ) - t k * ] [1 + sign(t H (k ) - tk** )] n * k = при ограничениях QsF (t ) Qs, s = 1,2,..., m;

1 t Tпл, (2.2.34) Глава 2. Статистические методы оптимизации комплекса сетевых моделей T = Tпл, 3ak + 2bk tk =, (2.2.35) 5 () ak = f1 (rks ), bk = f 2 rks, k = 1,2,..., n. Схема решения этой задачи следующая. Фиксированное число C раз решаем задачу минимизации QsF - Qs [ )], ( J = s = m 1 + sign QsF - Qs Qs где QsF, Qs - соответственно, физический и заданный уровни потребления s -ого ресурса при условиях (2.2.25). Из C полученных решений (при усло вии J = 0 ) выбираем наилучшее по критерию (2.2.33).

Представляет интерес также получение t H (k ) и t 0 (k ) при tk = mk ( mk мода распределения случайной величины t k {t k [a k, bk ]}). В этом случае больше шансов получить значения J 1 и J 2 лучшими, так как в случае зако на (2.2.1) имеют место неравенства mk tk.



Pages:     | 1 || 3 | 4 |   ...   | 8 |
 





 
© 2013 www.libed.ru - «Бесплатная библиотека научно-практических конференций»

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