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

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

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


Pages:     | 1 | 2 || 4 | 5 |   ...   | 8 |

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

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

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

Требуется определить сроки начала t H (k ) и окончания t 0 (k ) для работ, входящих в подмножество U DT проекта G (U DT = {k t0 tk* t0 + DT }), а для k U DT - математические ожидания M [t0 (k )], которые минимизируют функ ционалы [t (k ) - t ] * (2.2.36) J1 = H k kU DT или [t (k ) - t ] [1 + sign(t (k ) - t )] J2 = ** ** H k H H k U DT при условиях (2.2.37-2.2.41):

а) QsF (t ) Q s, s = 1,..., m;

t 0 t Tпл, (2.2.37) б) P{T Tпл } Pпл, (2.2.38) 3a k + 2bk в) t k = (2.2.39), k U DT, г) tk - случайная величина, если k U DT, (2.2.40) д) a k = f1 (rks ), bk = f 2 (rks ). (2.2.41) Идея алгоритма решения этой задачи состоит в следующем. Для работ Стохастические Сетевые Модели Планирования и Управления Разработками k (k U DT ) определяем tk по формулам (2.2.39), а для k U DT моделируем tk, распределенные на [a k, bk ] с плотностью (2.2.1). После этого решаем задачу минимизации времени выполнения проекта при заданных уровнях ресур сов и фиксированных tk, rks. Такие процедуры последовательно повторяем N раз ( N - некоторое достаточно большое число).

Тогда за искомые сроки выполнения работ ( k U DT ) принимаем t H (k ), t 0 (k ), для которых в N итерациях получено наименьшее значение (2.2.36), а за M [t 0 (k )], k U DT, принимаем средние значения t0 (k ), полученные по N розыгрышам значений tk. Заметим, что при этом должно выполняться ус ловие (2.2.38), которое мы можем проверить по N произведенным реали зациям алгоритма минимизации времени выполнения проекта при услови ях (2.2.37, 2.2.39-2.2.41). Если условие (2.2.38) не выполняется при (2.2.39), то целесообразно проверить (2.2.38) при случайных tk для всех k U с по мощью решения задачи минимизации T при заданных Qs. Если после это го получим P{T Tпл } P пл, то вместо (2.2.39) берем 2ak + bk, k U DT, tk = и снова решаем задачу минимизации (2.2.36), либо решаем задачу миними зации )[ )] ( ( n J = r s QsF - Qs 1 + sign QsF - Qs k = при условии (2.2.37-2.2.41). Последняя задача решается аналогично задаче минимизации функционала (2.2.4).

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

Будем различать три уровня управления проектом.

Первый уровень - это управление по объему выполненных работ и срокам важнейших промежуточных этапов (событий) выполнения проекта.

При этом контролируемые объемы выполненных работ оцениваются в единицах трудоемкости и стоимости.

Второй уровень - это управление фронтом работ по срокам ресурсам.

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

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

Пусть с момента начала выполнения ( t = 0 ) проекта прошло t 0 единиц времени.

Глава 2. Статистические методы оптимизации комплекса сетевых моделей Обозначим через F t фронт работ в момент времени t 0. Множество работ фронта F t разделим на два подмножества: Ft - подмножество ра 0 бот, которые к моменту t 0 уже начали выполняться, и Et - подмножество работ, которые могут начаться в момент t 0.

Введем еще обозначения F (t s ), Ft (s ), Et(s ), которые будем присваивать 0 соответствующим подмножествам работ ( F t(s ) F t ;

Ft (s ) Ft ;

Et(s ) Et ), 0 0 0 0 0 характеризующимся s -м видом ресурсов. При этом m m m U Ft(0s ) = F t0, U Ft0(s ) = Ft0, U E( ) = E, Ft 0 U Et 0 = F t 0.

s t0 t s =1 s =1 s = Возникает вопрос, какие работы из множества Et следует начать вы- полнять в момент t0?

Здесь возможны два случая.

Случай 1:

rks Qs, s = 1,..., m. (2.2.42) k F ts Случай 2:

r (2.2.43) Q s, 1 s m..

ks k F ( s ) t Сначала рассмотрим случай 1. Пусть вместе с (2.2.42) выполняются условия t H (k ) t0, k Et, (2.2.44) пл t H (k ) tH (k ), k Ft, (2.2.45) F пл где t H (k ) - плановый срок начала выполнения k -ой работы, определенный пл на этапе построения календарного плана работ;

t H (k ) - фактическое время F начала выполнения k -ой работы. Тогда проект выполняется с некоторым опережением.

В этом случае можно назначить t H (k ) = t0, k Et (2.2.46) без риска ухудшения P{T Tпл }.

Очевидно, такое же решение (2.2.46) можем принять и при невыпол нении (2.2.44) и (2.2.45), но при условиях t H (k ) t k*, k Ft, (2.2.47) F * (2.2.48) t0 tk *, k Et, * где t k** - правая граница оптимального интервала подачи ресурсов в k -й за даче (задача Б).

Теперь допустим, что ни условия (2.2.44-2.2.45), ни условия (2.2.47 2.2.48) не выполняются. Оценим вероятность события ** t 0 (k ) min t k, (2.2.49) k Стохастические Сетевые Модели Планирования и Управления Разработками где t0 (k ) - время окончания k -ой работы;

t k** - значение t k* для работы с но * мером k, следующей за k -й работой, при условии, что момент начала k -й работы известен и равен t Н (k ).

Для удобства перейдем здесь к обычным обозначениям работ парами номеров событий ((i, j ) ~ k ). Поскольку t0 (i, j ) = t H (i, j ) + tij, событие (2.2.49) эквивалентно событию tij min t jl - t H (i, j ), i j 1.

** l Положим DTij = min t ** - t H (i, j ).

jl l Тогда 0, если DTij aij, P{tij DTij } = 1, если DTij bij, (2.2.50) DTij j ( x )dx, aij DTij bij, aij где aij, bij - границы (2.2.2) распределения случайной величины tij, а j (x ) функция плотности (2.2.1) этого распределения. Так как величины tij ((i, j ) F t ) независимы, то P{t ij DTij, (i, j ) F ij } = P{t ij DTij } (2.2.51).

(i, j )F t Зафиксируем для всех работ фронта tij ((i, j ) F t ) сроки начала выпол нения, причем tH (i, j ), если (i, j) Ft F t H (i, j ) = если (i, j) Et t0, и определим по формулам (2.2.50) и (2.2.51) вероятность события P t 0 (i, j ) min t ** ( j, l ) (i, j ) F t0. (2.2.52) l Если полученная вероятность P 1 - e (e - допустимая вероятность невыполнения события (2.2.52)), то имеется реальная возможность с веро ятностью P начать все работы, последующие за работами фронта, в сроки, гарантирующие P{T Tпл } Pпл.

Аналогичным образом вычисляется и вероятность события:

t 0 (i, j ) min t H ( j, l ) (i, j ) F t0, (2.2.53) пл l где t H ( j, l ) - плановое время начала выполнения работы ( j, l ).

пл Из (2.2.50) следует, что гарантией свершения (т.е., что вероятность Глава 2. Статистические методы оптимизации комплекса сетевых моделей равна 1) события (2.2.52) являются условия min t ** - tH (i, j ) bij, (i, j ) F t 0, (2.2.54) jl l а для события (2.2.53) min t H ( j, l ) - t H (i, j ) bij, (i, j ) F t0, (2.2.55) пл l где t H (i, j ), (i, j ) Ft, F t H (i, j ) = (2.2.56) (i, j ) Et.

t Если же вероятность (2.2.51) событий (2.2.52 - 2.2.53) меньше 1 - e, то целесообразно в такой ситуации заново решить для изменившейся сетевой модели описанные выше задачи, т.е. скорректировать ранее полученные планы.

Теперь рассмотрим случай 2 для (2.2.43), т.е., как и для первого слу чая (2.2.42), рассмотрим различные ситуации в момент времени t 0.

Пусть одновременно с (2.2.43) выполняются неравенства t H (k ) t H (k ), k Ft, (2.2.57) F пл t0 t H (k ), k Et. (2.2.58) пл Эта ситуация свидетельствует о том, что проект выполняется с опере жением относительно плановых сроков. Поэтому в момент t 0 можно начи нать те работы k Et, для которых t H (k ) меньше. При этом сроки работ с пл большими t H (k ), для которых не хватило наличных ресурсов в момент t 0, пл сдвигаются вправо по оси времени.

Процедура обеспечения ресурсами может быть следующей. Выделяем из множества Et подмножества Et(s ), s = 1,2,..., m. Рассматриваем каждое под 0 множество Et(s ) и, если оно не пустое, упорядочиваем его элементы (коды работ (i, j ) или номера k ) в порядке возрастания t H (k ). В результате полу пл чим некоторую последовательность кодов (номеров) работ:

(2.2.59) k1, k 2,..., kv.

Проверяем неравенство Qs - rks rk s, k1 Et( s ). (2.2.60) 1 k Ft ( s ) Если (2.2.60) выполняется, то для работы с номером k1 ( k1 Et(s ) ) пола- гаем t H (k1 ) = t0. Одновременно работу k1 вносим в Ft и Ft (s ), а из подмноже 0 ства Et(s ) исключаем. Таким образом, мы просматриваем всю последова тельность (2.2.59).

Если для какого-либо ka Et(s ) неравенство (2.2.60) не выполняется, то пропускаем k и проверяем (2.2.60) для следующего k a +1 и т.д., пока не про смотрим всю последовательность (2.2.59). B случае невыполнения (2.2.57 2.2.58), но при условиях (2.2.47-2.2.48), также нет опасности нарушения Стохастические Сетевые Модели Планирования и Управления Разработками данного условия P{T Tпл } Рпл.

Работы, которые следует начинать в момент t0 при справедливости (2.2.47) и (2.2.48), можем определить аналогично тому, как мы это делали в случае (2.2.57-2.2.58), однако очередь обеспечения работ ресурсами в под множествах Et(s ) устанавливаем в порядке возрастания соответствующих (s ) t, k E0.

** k Рассмотрим теперь ситуацию, когда при (2.2.43) не выполняются ни (2.2.47-2.2.48), ни (2.2.57-2.2.58).

Если t H (k ), k Ft и t H (k ) = t 0, k Et лежат в пределах соответствующих F 0 интервалов (см. (2.2.8-2.2.9)) { } { } inf t H (k ), sup t H (k ), (2.2.61) min max то некоторые возможности выполнения проекта к моменту Tпл при задан ных Qs еще могут быть. Для оценки этих возможностей выполним сле дующие действия.

1. Выделяем из множества Et m подмножеств Et(s ) ( s = 1,2,..., m ).

0 2. Описанным выше способом часть работ из множества Et перево- дим в множество Ft, полагая при этом t H (k ) = t0. Очередность обеспечения ресурсами в подмножествах Et(s ) устанавливаем по неубыванию соответст ^ вующих tk**. Вновь полученные множества Ft и Et обозначим через F t и 0 ^ E t0.

^ 3. Полагаем для всех k F t tk = tk, где t k - среднее значение продол жительности k -й работы, и определяем момент t1 по следующей формуле:

{ } ^ t1 = min tH (k ) + t k (2.2.62) Ft 0 Ft 0, k Ft t ( k ), k Ft0, F tH ( k ) = H ), k Ft0 Et0.

t 4. Рассматриваем фронт работ (F t ) в момент времени t1. По сравне- нию с F t во фронт F t не входят работы k F t, для которых 0 1 t H (k ) + tk = t1, (2.2.63) и входят дополнительно те работы k U, для которых все предшествую щие работы (по предположению) будут выполнены к моменту t1.

5. Проверяем условие (2.2.42) для F t : rks Qs, s = 1,2,...m. (2.2.64) k F ( s ) t Если неравенства (2.2.64) не выполняются, то выполняем те же дейст Глава 2. Статистические методы оптимизации комплекса сетевых моделей вия, что и в случае (2.2.42) при P 1 - e (0 e 1).

При выполнении (2.2.64) оцениваем вероятность P{AB}, где A = t k min t l** - t H (k ), k F t1, (2.2.65) lH k ^ (2.2.66) B = t k t k, k Ft0, l - номер работы, непосредственно следующий за k -й работой;

H k множество работ, непосредственно следующих за k -й работой.

Исходя из равенства P{AB} = P{A B} P{B}, определим значения P{B} и P{A B}. Вероятность P{B} определяем по формуле (2.2.51). Вероятность P{A B} также определяем по формулам (2.2.50-2.2.51) при условии, что значения t H (k ) (см. (2.2.65)) определяются по формуле ( ) t H (k ), k Ft 0 Ft1, F ^ t H (k ) = t0, k F t 0 Et 0,. (2.2.67) t1, k Et1.

Если найденная вероятность P{AB} 1 - e, то в момент времени t0 на ^ чинаем все работы, входящие в множество Et - Et. При P{AB} 1 - e про 0 изводим корректировку ранее построенного расписания выполнения работ и распределения ресурсов по работам, как это будет показано ниже. Теперь рассмотрим более подробно п. 3 приведенного выше алгоритма.

В формулах (2.2.62-2.2.63) мы использовали средние значения про должительностей работ ( t k ), но не указали, как они определяются.

Заметим, что формула 3a k + 2bk (2.2.68) tk = ^ в данном случае применима не для всех работ множества F t и требует не- которого уточнения.

Пусть для работы с номером k (k Ft ) время начала фактического вы полнения равно t H (k ). Тогда возможны следующие случаи:

F 3ak + 2bk 0 t0 - tH (k ) (2.2.69) F, 3ak + 2bk t0 - t H (k ) bk, (2.2.70) F t0 - t H (k ) bk. (2.2.71) F Отсюда видим, что случай (2.2.69) особых затруднений не вызывает, и мы можем определить tk по формуле (2.2.68). Однако в случае (2.2.70) и осо бенно в случае (2.2.71) мы не можем непосредственно использовать формулу (2.2.68).

Стохастические Сетевые Модели Планирования и Управления Разработками Неравенство (2.2.71) возможно в силу разных причин. Например:

а) rks rks, где rks, rks - соответственно, фактическая и плановая интен F F пл пл сивности s -ro ресурса на k -й работе;

б) неправильно заданы экспертные оценки длительности работы (a k, bk ), и т.д.

Отсюда следует необходимость знать в каждый момент (t 0 ) контроля фронта работ (F t ), как изменились с течением времени все параметры ка ждой конкретной работы и всей сетевой модели в целом. В дальнейшем мы будем предполагать, что все происшедшие изменения нам известны, в том числе и уточненные значения a k, bk в случаях (2.2.70) или (2.2.71). При этом необходимо выполнение неравенства t0 - t H (k ) bk'. (2.2.72) F В силу последнего предположения у нас теперь возможны два случая:

3ak + 2bk' ' 0 t0 - tH (k ) F (2.2.73), 3ak + 2bk' ' t0 - tH (k ) bk'.

F (2.2.74) При справедливости (2.2.73) tk находим по формуле (2.2.68), полагая ak = ak' и bk = bk'.

В случае (2.2.74) предположим, что длительность оставшейся невы полненной части работы (Dtk ) также распределена с плотностью (2.2.1) на интервале [a k, bk ], где a k' = 1, bk'' = t H (k ) + bk' - t 0 (bk'' 0).

F ' Поскольку t k = t 0 - t H (k ) + Dt k', F то ( ) 3 + 2 t H (k ) + bk' - t F M [t k ] = t k = t0 - t (k ) + F H или 3t0 - 3t H (k ) + 2bk' + F. (2.2.75) tk = Если же нам заданы экспертные оценки ( ak' ', bk'' ) продолжительности (Dtk ) оставшейся части k -й работы, то 3ak' + 3bk'' ' t k = t0 - t (k ) + F (2.2.76).

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

Глава 2. Статистические методы оптимизации комплекса сетевых моделей Процедура корректировки плана состоит из следующих этапов.

^ Этап 1. Оцениваем для сетевой модели G (Y,U ), характеризующей не выполненную часть проекта, с учетом фактических параметров работ и фактических значений Qs, s = 1,2,..., m, вероятность Р{ Т Т пл }. Если Р{Т Т пл } Рпл, то переходим к этапу 3;

в противном случае выполняем этап 2.

Этап 2. В этом случае нужно либо пересмотреть значения Т пл, Рпл, ли бо определить минимальное количество необходимых дополнительных ре сурсов.

В первом случае вновь определяем Р{ Т Т пл }, а во втором - решаем задачу минимизации m J = (Qsф - Qs ) r s, Qsф = max Qsф (t ), (2.2.77) t 0 t Tпл s = при условиях rks rks rks, k U, 1 s m, min max As Qs Bs, s = 1, 2, K, m, ф (2.2.78) ak tk bk, k U, a = f (r ), b = f (r ), k 1 ks k 2 ks P{T Tпл } Pпл.

Задача минимизации (2.2.77) решается точно так же, как и задача А, но вместо функционала (2.2.4) берем (2.2.77).

Этап 3. Находим для оставшейся части проекта новые значения tk*, tk** (см. задачу Б).

Этап 4. Определяем заново для оставшихся работ проекта календар ный план. При этом определяем перечень работ, которые нужно начать в момент t0 при условии, что часть работ (прежнее множество Ft ) имеют o уже фиксированные времена начала ( t H (k ) ) выполнения.

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

Исходными данными для алгоритма слежения являются список всех выполняемых работ и для каждой работы (i, j ) сроки начала t н (i, j ) и окон чания t ок (i, j ), а также вид и количество ресурсов Z s (i, j ) вида s, выпол няющих эту работу. Задачей алгоритма является построение кривой Qs (t ) суммарных ресурсов вида s ( s = 1,2,..., m ), участвующих в выполнении раз работки в момент времени t. Следовательно, этот оператор дает прогноз об изменении количества потребляемых ресурсов во времени и может ис Стохастические Сетевые Модели Планирования и Управления Разработками пользоваться, в частности, для выявления «узких» мест или точек макси мума потребляемых ресурсов. Другим применением алгоритма может быть проверка планов на ограничения по наличным ресурсам.

Будем строить Qs (t ) с шагом h :

tk +1 = tk + h.

Рассмотрим момент времени t k. Так как Qs (t ) является ступенчатой функцией, то она может иметь в каждой точке два значения: правое и ле вое, которые обозначим Qs+ (t k ) и Qs- (tk ), соответственно.

Опустим в дальнейшем индекс s, так как будем рассматривать по строение ресурсов одного произвольного вида.

Значение Q - (tk ) можно определить следующим образом:

Q - (tk ) = r (i, j ), (2.2.79) C где суммирование проводится по работам, принадлежащим множеству C1 :

С1 = {(i, j ) : tн (i, j ) tk и tок (i, j ) tk }.

Аналогично для значения Q + (tk ) Q + (tk ) = r (i, j ), (2.2.80) C где С 2 = {(i, j ) : t н (i, j ) t k и t ок (i, j ) t k }.

Если шаг h настолько мал, что нас не интересуют значения Q (t ), со храняющиеся в течение времени меньшего h, то можем подсчитывать Q (tk ) по вышеприведенным формулам. Если, кроме того, требуемая точ ность по времени меньше h, то можно ограничиться одной формулой Q (tk ) = r (i, j ), (2.2.81) C где С3 = {(i, j ) : t н (i, j ) t k и t ок (i, j ) t k }.

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

Можно предложить точный способ построения Q (t ) по точкам, в ко торых изменяется количество потребляемых ресурсов. Для этого построим ступенчатые неубывающие функции H (t ) и K (t ). Значение функции H (t ) в каждой точке tн (i, j )k определяется как значение суммы H [tн (i, j )k ] = r (i, j )l, (2.2.82) Eн где Eн = {l : tн (i, j )l tн (i, j ) k }.

Аналогично определяется и функция K (t ), но уже по точкам tок (i, j )l, где Глава 2. Статистические методы оптимизации комплекса сетевых моделей K [tок (i, j ) k ] = r (i, j )l, Ek Ek = {l : toк (i, j )l tок (i, j ) k }. (2.2.83) Удобство использования функций H (t ) и K (t ) заключается в том, что их можно строить рекуррентно, для чего желательно иметь списки работ, упорядоченные по возрастанию tн (i, j ) q и tок (i, j ) p, соответственно ( q, p = 1,2,..., n ).

Определенные таким образом функции H (t ) и K (t ) сохраняют свое значение справа от точек tн (i, j ) q и tок (i, j ) p. Значит, функцию Q+ (t ) можно получить как разность функций H (t ) и K (t ). Точное значение функции Q+ (tm ) в произвольной точке t m можно получить как разность значений этих функций в ближайших слева от t m (или совпадающих с t m точках tн (i, j ) q и tок (i, j ) p ) функций H (t ) и K (t ), соответственно.

Если нас интересует максимум Q (t ), то мы должны просмотреть зна чения Q+ (t ) во всех точках tн (i, j ) q. Если же нас интересуют минимальные точки, то осуществляем просмотр во всех точках tок (i, j ) p.

§2.3 Оптимизация комплекса сетевых моделей по стоимости.

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

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

Последовательность выполнения работ задается в виде сетевой моде ли G (Y,U ) с детерминированной структурой и случайными оценками про должительности выполнения работ. Длительность t (i, j ) каждой работы (i, j ) является случайной величиной, причем параметры закона распределе ния этой случайной величины зависят от выделенного для этой работы объема стоимостных ресурсов s(i, j ), который может изменяться в задан ных пределах s min (i, j ) s (i, j ) s max (i, j ). (2.3.1) Изложим далее идею предлагаемого метода решения задачи оптими зации.

При фиксированном значении S N объема ресурсов, выделенных в сумме для всех работ сети, ищется распределение этих ресурсов по рабо там, максимизирующее вероятность P выполнения разработки в заданный Стохастические Сетевые Модели Планирования и Управления Разработками срок T Д.

Глобальный поиск осуществляется с использованием метода Монте Карло для многократного розыгрыша начальной точки и последующего локального случайно направленного поиска из каждой такой точки. Наи лучшая из точек, полученных в результате каждого локального поиска, принимается за точку глобального максимума, характеризуемого вероят ностью P * (S N ).

Затем значение S N суммарного объема ресурсов изменяется на вели чину заданного шага dS, и снова повторяется описанный выше поиск. Дви гаясь таким способом, например, снизу (т. е. увеличивая C ), остановимся, когда впервые P* (S N ) Pпл.

* В момент остановки имеем, таким образом, величину S * = S N суммар * ного объема ресурсов, минимально необходимую для выполнения разра ботки в срок T Д с вероятностью не меньшей Рпл. Кроме того, получаем и оптимальное распределение этих ресурсов по работам.

При этом предполагается, что p -квантиль длины критического пути не возрастает с увеличением Рпл и, следовательно, не убывает вероятность P * (S N ). В случае отказа от этого предположения требуется добавить еще один уровень одномерного поиска по величине S N.

Для определения вероятности P (т. е. значения оптимизируемого функционала) требуется знание интегральной функции распределения длины критического пути Tкp в произвольной точке x, координатами кото рой являются ресурсы s(i, j ), выделенные для выполнения каждой работы.

Вероятность P является значением этой функции для аргумента, равного TД.

Наибольшей точности определения P можно достигнуть методом ста тистического моделирования сети с помощью розыгрыша длительностей t (i, j ) всех работ. Параметры закона распределения t (i, j ), определяются по величине ресурсов s(i, j ). Для каждой такой реализации сети вычисляется Tкp, и по всем реализациям оценивается вероятность P как частота числа реализаций, для которых Tкp T Д.

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

Более простым способом является использование асимптотического закона, который более точно описывает распределение Tкp с увеличением числа работ в сети. Параметры этого закона, на наш взгляд, могут быть Глава 2. Статистические методы оптимизации комплекса сетевых моделей вычислены с помощью аналитического метода. В качестве такого закона может использоваться закон Фреше, детально описанный в Гл. 2 работы [2.5]. Значение его параметра q может быть определено с помощью мето дов, рассмотренных в [2.5]. Эти методы весьма просто реализуются на ЭВМ.

Отметим, что для целей случайного поиска допускается смещение оценки вероятности P, и требуется лишь сохранение отношений типа больше - меньше для оценок в различных точках. Это обстоятельство по зволяет снизить требования к точности методов расчета. Правда, при этом получаем систематическое смещение величины S * (Рпл ), если пользуемся смещенными оценками p.

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

Из вышеизложенного следует, что для всех точек случайного поиска требуется выполнение условия M s (2.3.2) = SN, l l = где sl - количество ресурсов, выделенных для работы с номером l.

Радиус-вектор X n пробной точки поиска определяется следующим образом:

Xn = Xm + XD, (2.3.3) где X m - радиус-вектор точки состояния поиска.

Так как для координат точек X m и X n должно выполняться условие (2.3.2), то на координаты dsl вектора случайного приращения X D из точки X m накладывается условие M ds = 0. (2.3.4) l l = Последнее условие является уравнением гиперплоскости, в которой должен лежать вектор X D. Вектор нормали к этой гиперплоскости имеет следующие M координат n = (1,1,...,1).

Представим вектор X D в виде h =Г, (2.3.5) XD = Г М g где Г = - длина случайного вектора;

h - шаг случайного поиска.

l Пусть мы разыграли в M -мерном евклидовом пространстве случай Стохастические Сетевые Модели Планирования и Управления Разработками ный вектор y = {x p }, конец которого равномерно распределен на поверхно сти гиперсферы с центром в точке X m. Будем искать вектор Г как проек цию вектора y на гиперплоскость (2.3.4). Тогда мы равновероятно будем выбирать в этой гиперплоскости любое направление вектора X D из точки Xm.

Определим сначала вектор R проекции вектора y на направление нормали n :

n (y, n), R= nn где (Y, Z ) - скалярное произведение векторов.

Затем из прямоугольника, построенного на векторах R и Г, получим (y, n). (2.3.6) Г =y - R =y - n n M x Так как n = M и (y, n ) =, то для координат вектора Г получим i i = формулы ) g l = xl - x, l = 1, 2,K, M, (2.3.7) ) M где x = 1 x i.

M i = Отсюда имеем Г =sB M, (2.3.8) ) M (xi - x ) - выборочное среднеквадратичное отклонение. Тогда где s B = M i = из (2.3.3) и (2.3.5) получаем ) h (xl - x ). (2.3.9) snl = sml + sB M Поскольку вектор X D определяем после нормировки Г по формуле (2.3.5), равномерное распределение на гиперсфере можно заменить розы грышем вектора y по всем направлениям в положительном гипероктанте с помощью равномерного розыгрыша координат x i на отрезке [0,1].

В целях упрощения вычислений заменим s B в (2.3.8) на теоретическое среднеквадратичное отклонение s = равномерного распределения на отрезке [0,1]. Тогда получаем ) (x l - x ). (2.3.10) snl = sml + h M Уменьшением величины h всегда можно добиться выполнения нера венств (2.3.1) для координат точки X n так как для координат точки X m они Глава 2. Статистические методы оптимизации комплекса сетевых моделей выполняются. Таким образом, чтобы не производить дополнительных ро зыгрышей, при нарушении неравенств выбираем величину h так, чтобы свести к нулю максимальное из отклонений за границы.

Предыдущая схема может быть обобщена для целей глобального по иска с помощью дополнительного розыгрыша величины h, распределен ной, например, экспоненциально. При этом можно использовать то же правило, когда точка, не попавшая в допустимую область, приводится на ее границу против направления вектора Г с помощью уменьшения разы гранной величины h. Помимо сокращения числа розыгрышей, получаемое при этом увеличение вероятности попадания разыгрываемой точки на гра ницу оправдывается также тем, что по смыслу задачи точка оптимума с большей вероятностью находится на границе области поиска. В этой схеме все же требуется для каждого значения S n иметь исходную точку (заме няемую после 1-го шага на точку X m ), для которой выполняются условия (2.3.1) и (2.3.2).

В отличие от предыдущей задачи, когда требовалось разыграть точку в h-окрестности на гиперплоскости (2.3.4), проходящей через начала коор динат с нормалью n = (1,1,...,1), рассматриваемый далее случай является обобщением на произвольную гиперплоскость.

Рассмотрим вопрос о розыгрыше методом Монте-Карло начальной точки X 0 = {S 0l } локального поиска при условии выполнения для ее коор динат равенства (2.3.2). Термин Монте-Карло означает здесь, что точка должна разыгрываться во всей допустимой области. Последнее условие требуется для возможности глобального поиска с помощью локального поиска из разных начальных точек.

При недостаточности или сложности использования априорных дан ных об оптимизируемой функции точку X 0 желательно разыгрывать рав номерно во всей допустимой области. С этой целью введем масштабы по всем координатам X0 и представим их в виде s0l = smin (i, j )l + D lwl, (2.3.11) где D l = smax (i, j ) l - smin (i, j ) l ;

wl - случайная величина, распределенная на от резке (0,1).

Тогда условие (2,3.2) можно переписать в следующем виде:

M D w - DS = 0, (2.3.12) l l l = M S min = smin (i, j )l.

где DS = Sn - S min ;

l = Последнее уравнение является уравнением гиперплоскости, в которой должна лежать случайная точка с радиус-вектором:

W 0 = {wl }.

По аналогии с методом розыгрыша случайного вектора приращения Стохастические Сетевые Модели Планирования и Управления Разработками X D, будем искать точку W как проекцию случайной точки с радиус вектором e = {e l } на данную гиперплоскость.

Уравнение гиперплоскости (2.3.12) в векторной форме запишем сле дующим образом:

( r, W ) - DS = 0, (2.3.13) где W - текущий радиус-вектор;

r = {Dt} - нормаль к гиперплоскости.

Тогда в векторной форме уравнением прямой, проходящей через точ ку e перпендикулярно к этой гиперплоскости, будет W = e + rt, (2.3.14) где t - временной параметр.

Радиус-вектор W0 точки пересечения получаем, решая совместно уравнение (2.3.13) и (2.3.14). Подставляя (2.3.14) в (2.3.13), находим D S - (r, e ) t=.

r Подставив последнее выражение в (2.3.14), получаем DS - (r, e ). (2.3.15) W0 = e + r r Для координат точки W0 получаем отсюда формулы Dl M DS - D ie i, l = 1, 2, K, M. (2.3.16) wl = e l + M D2i i = i = Тогда для координат X0 из (2.3.11) имеем D2l M DS - D ie i. (2.3.17) sol = smin (i, j )l + D le l + M D2i i = i = В качестве e l здесь могут быть взяты случайные величины, равномер но распределенные на отрезке [0,1], что, к сожалению, не гарантирует вы полнение неравенств (2.3.1).

Поэтому в данном случае более удобным представляется последова тельный алгоритм розыгрыша, по которому все точки попадают в допус тимую область. По этому алгоритму для работ в случайной последователь ности разыгрываются добавки к величинам sl уже выделенных ресурсов, начиная со значений smin (i, j )l. Величина добавки распределена равномерно в пределах разности [smax (i, j )l - sl ]. Каждая добавка вычитается из текущего значения величины DS. Розыгрыши производятся до тех пор, пока величи на очередной добавки не превышает текущего значения DS. В противном случае величина последней добавки равна этому значению.

Для упрощения алгоритма вместо случайной равновероятной выборки номера очередной работы разыгрывается один раз номер работы, для кото рой первой будет разыгрываться добавка. Затем работы выбираются в по Глава 2. Статистические методы оптимизации комплекса сетевых моделей рядке нумерации циклически, начиная с этого случайного номера. Цикли ческая выборка означает, что после последнего номера выбирается первый номер. Предварительно работы нумеруются в случайном порядке. Для ус DS корения сходимости этого алгоритма в случае производится ана M D l l = логичная процедура уменьшения выделяемых ресурсов, начиная со значе ний smax (i, j )l, до тех пор, пока их сумма не будет равна S N. Подробно алго ритм описан в работе [2.5].

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

§2.4 Имитационная модель разработки Рассмотрим задачу управления разработкой со случайными оценками продолжительности составляющих ее операций для случая, когда имею щиеся в распоряжении объекта управления ресурсы характеризуются еди ным стоимостным эквивалентом. Примем, что объект управления отобра жается детерминированной сетевой моделью G (Y,U ), где Y = ( y1,..., y N ) множество событий или вершин сети, U = (u1,..., u N ) - множество элементар ных операций или дуг сети. Допустим также, что продолжительность вы полнения операции t (i, j ) подчиняется принятому закону распределения (например, бета-распределению [2.2]), параметры которого1 связаны функ циональной зависимостью с выделяемым на проведение этой операции объемом ресурсов s(i, j ) так, как это показано на рис. 2.1. Здесь t1 " и t2 ", со ответственно, оптимистическая и пессимистическая оценки операции (i, j ) при фиксированном объеме выделенных ресурсов, соответствующем ми нимальному фронту производительной работы s min (i, j ) [2.2, 2.3];

t1 ' и t2 ' аналогичные оценки при s(i, j ) = s max (i, j ) ;

графическая зависимость t cp (i, j ) от s (i, j ) носит либо ступенчатый характер, либо может быть аппроксимиро вана непрерывной кривой.

Варьируя объемом выделяемых ресурсов в пределах smin (i, j ) s (i, j ) smax (i, j ), получим различные интервалы случайного разброса значений t ' (i, j ), t '' (i, j ).

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

Стохастические Сетевые Модели Планирования и Управления Разработками ределяемая директивным сроком Т дир, а критерием оптимизации является суммарный объем ресурсов, выделяемых на ее проведение.

Рис. 2.1. Зависимость продолжительности выполнения от объема ре сурсов Учитывая вероятностный характер выполнения разработки, задачу управления последней можно сформулировать следующим образом: необ ходимо определить минимальный объем ресурсов S, обеспечивающий за вершение разработки за планируемое время Т пл Т дир с вероятностью, не ниже заданной p пл. В дальнейшем необходимо распределить ресурсы между операциями и построить календарный план-график выполнения послед них. Таким образом, задача оптимального управления разработкой может быть сведена к решению следующих задач:

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

- перераспределения ресурсов между входящими в разработку опера циями;

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

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

Глава 2. Статистические методы оптимизации комплекса сетевых моделей Вследствие этого представляется целесообразным осуществлять комбини рованное управление разработкой [2.2]. Согласно этому принципу кален дарное планирование и соответствующее оперативное управление осуще ствляются на основе усредненных оценок (разумеется, это решение нельзя считать оптимальным), а оптимальное прогнозирование - на основе дове рительных оценок с использованием аппарата статистического моделиро вания. Точность решения последней задачи зависит от количества «розы грышей» методом Монте-Карло. Как будет показано ниже, можно постро ить алгоритм, сочетающий оптимальное (или близкое к оптимальному) прогнозирование ресурсов с распределением последних между операция ми разработки на основе метода статистической оптимизации.

Для случая детерминированных оценок t (i, j ) можно использовать ряд достаточно хорошо изученных алгоритмов распределения ресурсов типа «время - стоимость» и построения календарных планов-графиков [2.6].

Подобные алгоритмы могут эффективно использоваться и для решения за дачи распределения ресурсов на этапе построения достаточно грубого приближенного плана и соответствующего графика хода выполнения опе раций. В дальнейшем управление разработкой реализуется согласно по строенному календарному плану-графику, причем в качестве детермини рованных оценок t (i, j ) принимаются значения t cp. Для случая же дефицита ресурсов (имеется в виду невозможность завершения разработки в плано вый срок Т пл Т дир за счет перераспределения оставшихся внутренних ре сурсов) формируется корректирующая команда управления. Последняя связана с привлечением дополнительных ресурсов на основе решения за дачи оптимального прогнозирования и, тем самым, уменьшения времени выполнения оставшихся операций. Оптимальность прогнозирования за ключается в привлечении минимального количества дополнительных ре сурсов S дon, обеспечивающих завершение комплекса оставшихся операций к моменту Т пл с вероятностью p пл, уже с учетом вероятностного характера протекания процесса разработки. В дальнейшем (на основе описываемого ниже алгоритма либо алгоритма типа «время - стоимость») вновь происхо дит построение календарного плана-графика выполнения операций, после чего процесс разработки продолжается до следующего дефицита в ресур сах.

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

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

Записанный в операторной форме моделирующий алгоритм [2.2-2.5] имеет следующий вид:

F 6 A F1 A2 A3 A4, 421 F 4 5,18 7, A8 A9 A10 P19 P15 A13 P8 14, F15 A16 A17 A18 11A19 K 20 P21 A22 Я 6 5 11 12 Перечислим операторы, входящие в модель:

F1 - формирование исходных данных для сетевой модели;

A2 - правильная перенумерация сети;

A3 - решение задач оптимального прогнозирования, календарного планирования и распределения ресурсов;

A4 - расчет временных параметров сети и построение таблиц функций V (t ) ;

F 5 - формирование исходных данных и начальных условий для k -ой реализации;

F 6 - реализация случайных продолжительностей работ сети;

A7 - расчет фактических сроков работ;

A8 - вычисление значения VF (tik ) ;

A9 - вычисление DV0 (tik ) ;

A10 - выдача результатов к моменту t ;

P - проверка условия VF (tik ) - Vпл DV ;

P - проверка условия DV0 (t ik ) dv, (dv 0) ;

A13 - вычисление tik+1 ;

P - проверка условия tik+1 d t ;

F15 - формирование усеченной сетевой модели;

A16 - решение задач оптимального прогнозирования и оперативного управления;

A17 - расчет временных параметров усеченной сети и построение таблиц V (t ) ;

A18 - вычисление tik+1 по усеченной сети;

A19 - выдача результатов по k -ой реализации;

К 20 - счетчик числа реализаций;

Р21 - проверка условия k k3 ;

A22 - статистическая обработка результатов моделирования;

Я 23 - выдача результатов и конец вычислений.

Перейдем теперь к детальному описанию операторов модели.

Глава 2. Статистические методы оптимизации комплекса сетевых моделей Оператор F1 формирует исходные данные для работы всей модели. Ис ходными данными являются:

1. Сетевая модель, которая задается в виде списка работ (i, j ), где i начальная вершина работы, j - конечная вершина.

2. Для каждой работы сети (i, j ) задаются: а) граничные значения объема ресурсов, необходимые для выполнения данной работы s min (i, j ), s max (i, j ), где s min (i, j ) - минимальный объем ресурсов, необходимый для вы полнения работы (i, j ) ;

s max (i, j ) - объем ресурсов, при котором их общая производительность по выполнению работы (i, j ) максимальна;

б) зависи мость математического ожидания продолжительности выполнения работы t cp (i, j ) от объема ресурсов s (i, j ) ;

в) предельные длительности (оптимистиче ская и пессимистическая) выполнения работы (i, j ) при заданном количестве ресурсов s(i, j ) : a s (i, j ) = t1 (i, j ) и bs (i, j ) = t 2 (i, j ), a s (i, j ) bs (i, j ) ;

г) объем работы v(i, j ), который может быть задан в процентах от общего объема работ, стоимостных единицах и т. д.

3. Данные, определяющие условия и точность моделирования:

Vпл - суммарный плановый объем всех работ сети;

Т дир - директивный срок выполнения всего комплекса работ;

p пл - вероятность выполнения комплекса работ за время Т пл ;

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

k 3 - заданное количество реализаций процесса в модели;

Dt - допустимая погрешность по времени в модели;

DV - допустимая погрешность модели по объему;

dv - изменяемая константа, с помощью которой можно изменять разме ры критической области;

d t - минимальное время между двумя опросами модели.

Оператор A2 осуществляет правильную нумерацию сети [2.6]. Послед нее, как известно, означает выполнение неравенства i j для всех работ (i, j ) сетевой модели. Полезность оператора A2 объясняется тем, что алгоритмы временного расчета правильно занумерованной сети значительно проще и требуют меньше времени для своего выполнения, чем для той же сети с произвольной нумерацией. Это тем более важно, что при выполнении ос тальных операторов модели многократно производится временный расчет исходной сети или ее части для различных значений продолжительностей входящих в нее работ. Правильность же нумерации не нарушается при «усечении» сети или корректировке значений t (i, j ).

Оператор A3 осуществляет реализацию задачи оптимального прогно зирования с последующим перераспределением ресурсов на основе усред ненных оценок продолжительностей работ сети. Результатом работы алго Стохастические Сетевые Модели Планирования и Управления Разработками ритма являются плановые сроки начала и окончания t H (i, j ) и tok (i, j ), а так пл пл же плановый объем выделенных ресурсов s пл (i, j ), соответствующие опти мистической и пессимистической оценкам a s (i, j ) и bs (i, j ) - для всех работ (i, j ) сетевой модели. Методология решения оптимальных задач оператора A3 будет описана ниже.

Оператор A4 производит расчет временных параметров сети с детер минированными оценками длительностей работ t (i, j ) = a s (i, j ), на основе данных расчета табулирует функцию V0 (t ) с шагом Dt и определяет вели чину длины критического пути T0. Функция V0 (t ) описывает изменение объема выполненных работ к моменту t при оптимистическом ходе про цесса выполнения комплекса работ, т.е. при выполнении их с максимально возможной скоростью [2.2]. Легко видеть, что V0 (t ) является неубывающей функцией и V0 (T0 ) = Vпл. Однако трудность ее построения заключается в том, что эта функция может быть неоднозначной во всех точках, кроме точек V0 (0 ) = 0 и V0 (T0 ) = Vпл.

Заметим, что граничными кривыми области значении V0 (t ) являются кривые, построенные по ранним и поздним срокам начала всех работ в пре делах их резервов по времени pV0 (t ) и nV0 (t ), соответственно, причем кривая pV0 (t ) лежит выше кривой nV0 (t ), быть может совпадая с ней в некоторых точках. Следовательно, для построения однозначной кривой V0 (t ) должны быть выбраны точки начала всех работ. В настоящем алгоритме за сроки начала всех работ приняты ранние сроки свершения их начальных событий t H (i, j ) = T a (i, j ). Последнее формирует V0 (t ) = pV0 (t ), что приводит к увеличе a нию критической области.

Опишем далее общий алгоритм построения кривых V (t ) - зависимо стей объема выполненных работ от времени. Этот алгоритм реализуется в операторах A4, A17, A8.

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

Алгоритм построения V (t ).

Этап 1. Образуем множество M 0 для момента времени t0 из всех работ сети и устанавливаем начальные значения V (t0 ) = Vок (t0 ) = Vнач, m = 1.

Этап 2. Подсчитываем Vок (tm ), просматривая все работы из множества M m - Vok (tm ) = v(i, j ) + Vok (tm -1 ), Dm Глава 2. Статистические методы оптимизации комплекса сетевых моделей где сумма берется по всем работам (i, j ) из M m -1, для которых выполняется неравенство tok (i, j ) tm, M m -1 Dm = {(i, j ) : t ok (i, j ) tm }.

Этап 3. Образуем множество M m, исключая из множества M m -1 все работы множества Dm :

M m = M m -1 \ Dm.

Этап 4. Проверяем наличие работ во множестве M m. Если M m O, то // переходим к этапу 5. В противном случае - конец вычислений.

Этап 5. Просматриваем все работы множества M m и подсчитываем V (tm ) :

V (tm ) = (i, j ) [t m - t H (i, j )] + Vok (tm ), (2.4.1) Bm где { };

M m Bm = (i, j ) : t H (i, j ) tm v (i, j ) (i, j ) =.

tok (i, j ) -t H (i, j ) Этап 6. Индекс m увеличивается на единицу, после чего переходим к этапу 2.

Для упрощения алгоритма и сокращения времени его работы полезно упорядочить работы в M 0 по возрастанию t ok (i, j ) p, ( p = 1,2,..., N ).

Упорядочение означает, что tok (i, j )p tok (i, j )p +1 В этом случае упорядо чены будут и все множества M m -1, и исключается перебор всех работ этих множеств, а выбираются подряд и исключаются из дальнейшего рассмотре ния все работы до номера l, для которого последний раз выполняется tok (i, j )l tm. Таким образом, одновременно из M m -1 исключается l работ, со ставляющих множество Dm, и этап 3 выполняется одновременно с этапом 2.

В операторе A4 этот алгоритм реализуется с начальными значениями t0 = 0, Vнач = 0 и tm +1 = tm + Dt. Еще одной функцией оператора A4 является под готовка начальных условий для первой реализации фактического хода про цесса выполнения комплекса работ сети (например, установка нуля в счет чик реализаций, вычисление D 0 и t1 ).

Оператор F5 формирует массивы исходных данных и начальные усло вия для k -й реализации. В число исходных данных входят: таблица функ ции V0 (t ), сеть с данными для каждой работы (i, j ) : (t пд, v, a, b, sпл ). Начальны H ми значениями для k -й реализации являются Т 0, D 0 и время первого опро са t1. Все эти значения могут изменяться в процессе одной реализации и по этому требуют восстановления перед каждой новой реализацией.

Стохастические Сетевые Модели Планирования и Управления Разработками Оператор F 6 осуществляет случайный розыгрыш длительностей всех работ исходной сети либо усеченной сети, сформированной оператором F15.

Длительность каждой работы (i, j ) разыгрывается в пределах [a (i, j ), b(i, j )], задаваемых оператором A3 для исходной сети, либо оператором A16 для усе ченной сети с перераспределенными ресурсами.

В качестве закона распределения длительности выполнения работы принято бета-распределение с плотностью вида (1.3.7) p( x ) = (x - a )(b - x )2 (a x b ), (b - a ) где a = a(i, j ), b = b(i, j ) - изменяются от работы к работе.

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

Правило определения t H (i, j ) может быть сформулировано следующим об F разом. Любая работа (i, j ) не начинается. раньше планового срока t H (i, j ) ).

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

Алгоритм определения фактических сроков выполнения работ запи сывается следующим образом:

1. Устанавливаются начальные значения T F (0 ) = tik-1 и v = 1, где T F (m ) - фактическое время свершения события с номером m ( m = 0,1,..., N );


0, N - номера исходного и завершающего событий сети;

tik-1 время (i - 1) -ого опроса модели в k -й реализации.

2. Для вершины с номером v определяются по порядку следующие величины:

a) t H (m, v ) = max T F (m ), t H (m, v ), F пл б) t (m, v ) = t (m, v ) + t F (m, v ), (2.4.2) F F ok H в) T F (v ) = max t ok m, v, F m где m принимает значения номеров вершин, из которых идут дуги в вер шину v ( m v ), поскольку сеть правильно занумерована).

3. Значение v увеличивается на единицу.

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

Из приведенного алгоритма видно, что если в процессе реализации Глава 2. Статистические методы оптимизации комплекса сетевых моделей оператора А7 положить значения t H (i, j ) = 0, то фактический процесс вы пл полнения разработки не будет зависеть от плановых сроков. Если принять t пл (i, j ) = T b (i ), процесс пойдет по пессимистической интегральной кривой Vпс (t ), построенной на основе оценок продолжительностей t (i, j ) = b(i, j ).

Заметим, что обработка операторами F 6 и А7 всех работ заданной се ти не требуется. Достаточно включать в исходный массив лишь те работы (i, j ), для которых выполняется условие t H (i, j ) tlk. Однако принятый поря пл док, при котором обрабатываются все работы сети, вплоть до завершаю щего события, позволяет более гибко назначать любые значения t H (i, j ), а пл также дает возможность прогнозировать до конца фактический ход про цесса и, в частности, получить точное время свершения завершающего со бытия на каждом этапе опроса модели. Следует отметить, что процедура управления ходом разработки может предусматривать и более гибкую стратегию. В частности, с учетом вероятностного характера продолжи тельностей t (i, j ) может иметь место t H (i, j ) t H (i, j ), но не более чем на за F пл ранее выбранную величину Dпл (i, j ), меняющуюся от работы к работе.

Иными словами, вместо ограничения t H (i, j ) t H (i, j ) имеет место F пл t H (i, j ) t H (i, j ) - Dпл (i, j ). Значение Dпл (i, j ) может быть определено на основе F пл задания доверительных вероятностей [2.2] или из иных соображений.

Оператор А8 производит расчет фактически выполненного к моменту tl объема работ VF (tlk ). Для этого используется приведенный выше алго k ритм расчета V (t ), причем в операторе А8 реализуются лишь этапы 2, 3, 5.

Остальные этапы в несколько видоизмененном виде реализуются другими операторами. В частности, начальные условия (этап 1) устанавливаются оператором F5 (Vнач = 0, t0 = 0), либо операторами A17 и A18 Vнач = VF (tik-1 ), t0 = tik-1.

Множество M 0 задается либо оператором F5, либо оператором F15, а оче редной момент времени tm +1 (этап 6) выдается оператором A13 (t m +1 = t ik+1 ).

Функции этапа 6 выполняет оператор P11, который проверяет выполне ние условия VF (tik ) - Vпл DV. Невыполнение этого условия означает конец k -ой реализации, после чего управление передается оператору A19, который выдает результаты этой реализации. Если условие выполняется, управление, в конце концов передается оператору A8, который вычисляет новое значе ние VF (tik+1 ).

Заметим, что оператор A8 может, после реализации оператора А7, вы полнить алгоритм построения V (t ) полностью, например, с шагом Dt, с це лью получения полной таблицы функции VF (t ik ). Тогда нужно добавить оператор выборки из этой таблицы значения VF (tik ), к которому управление должно передаваться от операторов A8 и P14.

Стохастические Сетевые Модели Планирования и Управления Разработками Оператор A9 выбирает из таблицы V0 (t ) значение для момента времени (tik - D 0 ), т.е. определяет значение функции V0 (t ), сдвинутой вправо на D 0 0. Значение D 0 устанавливается оператором F5 либо A18 (для «усечен ной» сети) и определяется операторами A4 или A17 из условия прохожде ния сдвинутой кривой через точку с координатами (Tпл, Vпл ) :

V0 (Tпл - D 0 ) = Vпл.

Поскольку V0 (T0 ) = Vпл, то отсюда D 0 = Т пл - Т 0. После выборки оператор А определяет значение DV0 (t ik ) = VF (t ik ) - V0 (t ik - D 0 ). (2.4.3) Оператор A10 выдает результаты, полученные к моменту tik.

Оператор P12 проверяет выполнение условия DV0 (tik ) dv (dv 0 ), где dv - изменяемая константа, с помощью которой меняется величина критической зоны [2.1-2.5] Значение dv может выбираться, исходя из за данной вероятности pпл выполнения комплекса работ в срок Tпл, а также из требуемой «жесткости» управления с целью удержания процесса в преде лах плановой кривой.

Выполнение условия оператора P12 означает, что перераспределения и привлечения дополнительных ресурсов не требуется, и управление может быть передано оператору А13. Невыполнение этого условия означает, что точка (tik,VF (tik )) попала в критическую зону и для выполнения объема работ Vпл в срок Tпл требуется принять необходимые меры. В этом случае опера тор P12 передает управление оператору F15.

Оператор F15 осуществляет формирование усеченной сети из работ, оставшихся невыполненными к моменту tik. Для всех работ усеченной сети выполняется условие tok (i, j ) tik. F Заметим, что те из них, для которых выполняется также условие t H (i, j ) tik, уже начались. Эти работы выполняются при вычислении значе F ния VF (t i к ) на этапах 3 и 5 алгоритма построения V (t ), что может быть ис пользовано оператором F15. Таким образом, все работы усеченной сети со держатся во множестве M i, а все начатые работы из этого множества со держатся во множестве Bi (индекс множества совпадает с индексом мо мента опроса ti ). С уже начатыми работами оператор F15 производит сле дующие операции:

1. В качестве начальной вершины работы (i, j ) записывается номер начальной вершины сети ( 0 ) вместо номера i.

2. Устанавливаются пределы длительности работы (i, j ) a y (i, j ) = b y (i, j ) = tok (i, j ) - tik F Глава 2. Статистические методы оптимизации комплекса сетевых моделей и, таким образом, фиксируется длительность этой работы.

3. Из объема v(i, j ) исключается уже выполненная часть t ok (i, j ) - t ik F v (i, j ) = v(i, j ) F y.

t ok (i, j ) - t H F 4. Устанавливаются новые плановые сроки t H (i, j ) = t ik, t ok (i, j ) = t ok (i, j ), F пл пл тем самым жестко закрепляются сроки исполнения «урезанных» работ.

С помощью этих операций координаты начального события по объе му и времени смещаются в точку (tik,VF (tik )) для всех последующих операто ров. В частности, оператор F 6 не изменяет длительности, а оператор A7 сроки завершения урезанных работ, так как a(i, j ) = b(i, j ) и T F (0 ) = tik.

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

Оператор A13 вычисляет очередной момент опроса tik+1. Этот момент определяется из тех соображений, чтобы за время до очередного опроса фактический ход процесса не успел попасть в зону дефицита ресурсов да же при нулевой производительности выполнения работ [2.2-2.3]. Значение tik+1 определяется как решение уравнения V0 (tik+1 - D 0 ) = VF (tik ), где D 0 = Tпл - T0.

Отсюда получаем формулу [ ( )] (2.4.4) t ik+1 = V0-1 VF t ik + D 0, где V0-1 - функция, обратная V0 (t ).

Учитывая, что общая производительность не может быть равной нулю (максимальная длительность каждой работы b(i, j ) ), можно уменьшить число опросов [2.2-2.5]. Тогда tik+1 будет решением уравнения ( ) () V0 ~+k1 - D 0 = Vпс ~+k1 + D1 t ik, (2.4.5) ti ti () где D1 ti определяется из уравнения k () () Vпс t ik + D1 t ik = VF t ik и, следовательно, [ ( )] () (2.4.6) D1 t ik = Vпс VF t ik - t ik.

- Функция Vпс (t ) определяется аналогично V0 (t ) на основе пессимистиче ских оценок продолжительностей работ b(i, j ).

Для определения очередного момента опроса из уравнения (2.4.5) тре буется дополнительно построить таблицы функции Vпс (t ) в операторах A4 и Стохастические Сетевые Модели Планирования и Управления Разработками A17.

Оператор A18 определяет значение первого опроса усеченной сети, ко торый является очередным (i + 1) -м опросом модели. Поскольку для усе ченной сети имеет место () () ( ), V0 t ik = Vпс t ik = VF t ik на основе формулы (4.3.4) получаем tik+1 = tik + Dy0 ;

на основе формул (2.4.6) и (2.4.5) получаем последовательно при тех же начальных условиях D1 (tik ) = 0, ( ) ( ).

V0 ~+k1 - Dy0 = Vпс ~+k ti ti Здесь D = T - T0y определяются на основе усеченной сети.

y y 0 пл Для исходной же сети имеем начальные условия V0 (t0 ) = Vпс (t0 ) = VF (t0 ) = 0 и t0 = и, соответственно, получаем, исходя из формул (2.4.1-2.4.6) t1 = D 0 = Tпл - T0, D1 (t0 ) = 0, V (~ - D ) = V (~ ).

t t 0 1 0 ПС Значение t1 вычисляется оператором A4 и сохраняется неизменным для всех реализаций (восстанавливается оператором Fs ).

Оператор A17 выполняет функции, аналогичные функциям оператора A4. Однако для усеченной сети начальные условия при построении V0y (t ) будут Vнач = VF (tik ) и t0 = tik.Таким образом, таблица V0 (t ) корректируется, на чиная с момента tik с шагом Dt.

Заметим, что операторы A4 и A17 могут быть объединены в один опера тор, если выделить отдельный оператор для расчета t1 и Dt и добавить еще условный оператор передачи управления оператору A18 во всех случаях, кроме первого прохода программы через объединенный оператор, когда управление должно передаваться оператору F5.

Оператор P14 проверяет условие tik+1 - tik d t.

В случае выполнения условия значение tik восстанавливается, и управ ление передается оператору F15. Этот случай означает, что в момент tik процесс близок к критической зоне по координате времени. В противном случае управление передается оператору А8.

Оператор К 20 подсчитывает число реализаций процесса.

Оператор Р21 сравнивает число реализаций с заданным k k3 и при по ложительном результате передает управление оператору A22.


Глава 2. Статистические методы оптимизации комплекса сетевых моделей Оператор A22 осуществляет статистическую обработку результатов всех реализаций процесса.

Оператор Я 23 выдает результаты моделирования на печать и заверша ет работу алгоритма.

В заключение параграфа опишем оптимальную задачу прогнозирова ния минимального дополнительного объема ресурсов S дoп, обеспечиваю щего выполнение разработки в плановый срок с вероятностью pпл. Выше уже отмечалось, что необходимость решения такого рода задачи на стадии оперативного управления возникает лишь в случае несоответствия факти ческого состояния разработки плановому, когда VF Vпл. На наш взгляд, ал горитм решения должен быть основан на способе статистической оптими зации согласно методике, описанной в §2.3 настоящей главы.

На этапе 1 решения задачи оптимального прогнозирования устанавли ваем объем ресурсов S, заведомо обеспечивающий решение поставленной задачи. В частности, значение S может быть определено по формуле S = s max (i, j ), где G ' (Y,U ) - усеченная сеть, построенная на момент об (i, j )G ' (Y,U ) ращения к оператору A16 в описанной выше имитационной модели.

Второй этап состоит в распределении методом Монте-Карло суммар ного объема ресурсов S между работами (i, j ) сетевой модели G ' (Y,U ) с целью получения начальной точки поиска (разумеется, в пределах интер валов [smin (i, j ), smax (i, j )]). Алгоритм распределения может быть использован в сочетании с эвристическими методами;

он описан в ряде работ, например [2.1-2.5].

На этапе 3 в соответствии с ранее распределенными между работами (i, j ) G ' (Y,U ) ресурсами s(i, j ) многократно моделируем продолжительно сти выполнения работ (i, j ) методом Монте-Карло с последующим опреде лением доверительной вероятности p, соответствующей плановому сроку окончания разработки Tпл. Алгоритм статистического моделирования сетей со случайными временными оценками изложен в [2.1-2.5]. При p p пл пе реходим к последующему этапу. В противном случае управление переда ется на этап 6.

Этап 4 осуществляет локальный случайный поиск в пространстве s (i, j ) (из полученной на этапе 2 начальной точки) с целью максимизации доверительной вероятности p, соответствующей Tпл. Алгоритм этого эта па, подобно предыдущим, описан в ряде монографий и работ [2.4, 2.7], вследствие чего мы не будем останавливаться на его подробном изложе нии. Если в результате проведения случайного поиска значение коэффици ента доверия p окажется не менее pпл, управление передается на этап 6. В противном случае переходим к реализации последующего этапа.

На этапе 5 подсчитываем число k неудачных результатов поиска и Стохастические Сетевые Модели Планирования и Управления Разработками сравниваем это число с предельным k зад. В случае k = k зад управление пере дается на этап 2. При k = k зад работа алгоритма оканчивается, а управление передается на завершающий этап 7.

Этап 6 реализует итеративный процесс уменьшения значения S на шаг DS. После этого счетчик k на этапе 5 очищается, а управление переда ется на этап 2. Таким образом, последовательное уменьшение объема ре сурсов S происходит до тех пор, пока соответствующий Tпл коэффициент доверия не станет меньше pпл. На этапе 7 происходит определение потреб ных дополнительных ресурсов S доп = S min - Sнал, где S min определяется на этапе 6, a S нал - наличный объем ресурсов в момент обращения к решению опти мальной задачи.

Заметим, что изложенный алгоритм позволяет определить не только минимальный дополнительный объем ресурсов S доп, но и распределить суммарный объем S = Sнал + S доп по оставшимся операциям разработки. Что касается задачи построения календарного плана-графика, то здесь мы сталкиваемся с теми же трудностями, что и при построении кривых V0 (t ) и Vпс (t ) в процессе работы оператора A4 моделирующего алгоритма. По ' скольку ресурсы уже распределены, мы в состоянии при построении ка лендарных планов-графиков варьировать лишь резервами времени для ра бот резервной и промежуточной зон [2.2]. В частности, можно устанавли вать плановые начала выполнения работ t H (i, j ), исходя из ранних сроков пл свершения начальных событий или из каких-либо иных соображении.

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

Глава 3. Оптимальные задачи на современном разрабатывающем предприятии Глава 3. Оптимальные задачи на современном разрабатывающем предприятии §3.1 Технико-экономическая постановка задач В предыдущей главе мы рассматривали задачи моделирования и оп тимизации на сетевых графиках. Процессы управления комплексом разра боток на современном разрабатывающем предприятии (РП) могут отобра жаться более широким спектром математических моделей. Процесс вы полнения разработок (объектов новой техники) проходит этапы:

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

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

На этом этапе проводятся также лабораторное макетирование и все основ ные теоретические расчеты;

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

4) изготовление опытного образца, а также ряд стендовых испыта ний;

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

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

Уровень неопределенности поведения объекта на первой фазе значи тельно выше, чем на второй. Если для изделия, находящегося на этапе аванпроекта, дальнейший ход его разработки можно описывать лишь веро ятностными категориями, то на этапах второй фазы уже существует сете вой график разработки изделия. Исходя из сказанного, динамическими мо делями объекта управления комплексом разработок могут быть модели одного из двух типов: 1) модели, включающие уровень неопределенности объекта;

2) сетевые модели.

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

При этом предполагается возможная иерархия укрупнения работ по каж дому проекту.

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

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

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

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

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

§3.2 Вопросы оптимального распределения затрат между проек тами [3.

3] При формировании сводного тематического плана на определенный Глава 3. Оптимальные задачи на современном разрабатывающем предприятии плановый период T (год, квартал и т. д.) возникает задача оптимального распределения выделенного на этот период суммарного ресурса CT между отдельными разработками. В рассматриваемой ниже постановке задачи под суммарным ресурсом, подлежащим распределению, подразумевается суммарный объем всех ресурсов, выраженный в виде единого эквивалента - в стоимостных единицах. Учитывая то, что директивные сроки выполне ния каждой из разработок могут (в общем случае) превосходить конец планового периода, необходимо заложить в критерий оптимизации степень реализуемости проектов в заданные сроки. При распределении затрат не обходимо также выдерживать ряд ограничений на динамику потребления затрат не только в течение рассматриваемого планового периода T, но также и после планового периода - до момента окончания всех разработок.

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

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

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

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

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

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

Способы построения характеристик этих процессов рассмотрены ниже.

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

N - количество рассматриваемых разработок;

П = [p 1,...,p N ] - заданные приоритеты разработок;

C = [C1,...,C N ] - полные стоимости разработок;

t F = [t1,...,t N ] - время, истекшее с начала выполнения разработок;

S дир = [S1,..., S N ] - директивные сроки окончания разработок;

P = [P,..., PN ] - заданные вероятности выполнения разработок;

D = [d1,..., d N ] - ограничения на максимальную скорость потребления ресурса;

Q = [q1,..., q N ] - относительная трудоемкость выполненных работ по ка ждой разработке на начало планируемого периода;

0 q 1, t = 1, N ;

T - величина периода планирования (год, месяц);

CT - размер ресурса, подлежащего распределению;

C 0 - директивное распределение суммарного ресурса по времени;

X = [x1,..., xN ] - искомый вектор, определяющий приращение относи тельной трудоемкости на плановый период T по каждой разработке;

t = [t 1,...,t N ] - времена окончания выполнения каждой разработки, ко торые определяются в результате решения задачи;

t 0 - рассматриваемый момент планирования;

x (t ) - заданный случайный процесс, определяющий распределение от носительной трудоемкости выполнения k -й разработки в момент времени t t0 +T.

Предполагается, что x k (t ) = mk (t ) + e k (t ), (3.2.1) где mk (t ) - заданная детерминированная монотонно неубывающая функция;

e k (t ) - некоррелированный случайный процесс с нулевой функцией мате матического ожидания;

s k (t ) - средне-квадратичное отклонение случайной величины e k (t ) в момент времени t.

Предполагается также, что функция s k (t ) является неубывающей.

В работе при оценке параметров рассмотренного случайного процесса Глава 3. Оптимальные задачи на современном разрабатывающем предприятии (3.2.1) будем ограничиваться лишь первыми его двумя моментами.

Задавая по каждой k -й разработке величины xk и t k, можно вычис лить вероятность ее выполнения по формуле:

Fk ( x k,t k ) = P{q k + x k + x k (t k - t 0 - T ) 1}. (3.2.2) Формула (3.2.2) позволяет вычислить вероятность того, что случай ный процесс, имеющий в ка честве начального состояния точку G с координатами (t 0 + T, qk + xk ) (рис. 3.1), в мо мент времени t k выйдет из полосы единичной ширины.

Критерий оптимальности распределения затрат между проектами должен учитывать в прямой зависимости при оритетность p k каждой разра Рис.3.1 Оценка параметров случайного ботки, вероятность ее невы процесса полнения к моменту оконча ния t k и величину смещения этого срока относительно директивно задан ного. В данной постановке задачи предлагается формула для критерия W :

W (x,t ) = k =1p k [1 - Fk ( xk,t k )](t k - S k ), N (3.2.3) где Fk (xk,t k ) вычисляется по формуле (3.2.2).

Переходим теперь к математической постановке исходной задачи.

Пусть область D всех допустимых векторов x и t, характеризующих всевозможные варианты распределения затрат между проектами, опреде ляется следующими неравенствами:

Fk ( xk,t k ) - Pk 0 ;

(3.2.4) N x Ck - CT 0 ;

(3.2.5) k =1 k xk min (1 - qk,d k ) ;

(3.2.6) { )} ( ~ F (t ) = P - P k =1 Ck [qk + xk + xk (t )] C 0 t 0 + T + t 0, N (3.2.7) где 0 t t k - (t 0 + T ).

В формулах (3.2.4-3.2.7) предполагается, что k = 1, N. Неравенство (3.2.4) отражает то требование, чтобы вероятность выполнения каждой разработки превосходила заданный уровень Pk. Неравенство (3.2.5) требу ет, чтобы планируемые приросты, относительных трудоемкостей по каж дой разработке соответствовали суммарным затратам, не превосходящим заданного значения СТ.

Кроме того, приросты относительных трудоемкостей по каждой раз работке не должны превосходить заданной скорости d k или же оставшейся Стохастические Сетевые Модели Планирования и Управления Разработками относительной трудоемкости. Этот факт отражен в неравенстве (3.2.6). Ог раничение по динамике потребления ресурса в момент времени t t 0 + T отражено в неравенстве (3.2.7).

) ( * * Требуется найти в области D наилучшую пару векторов x,t D, которая обращает в минимум функцию вида (3.2.3). Другими словами, должно выполняться соотношение:

) ( W x, t = min W (x,t ).

* * (3.2.8) ( x,t )D Прежде чем переходить к описанию алгоритмов решения задачи (3.2.4-3.2.8), остановимся подробнее на свойствах функции F (x,t ), вид ко торой представлен в (3.2.2). При конструировании алгоритмов нас будут интересовать условия, налагаемые на случайный процесс x (t ), при выпол нении которых функция F (x,t ) является для любого x неубывающей функцией t.

При любом t 0 выражение для F (x,t ) имеет вид:

( z - M (t )) F ( x,t ) = s (t ) 2p exp - dz.

2s 2 (t ) z - M (t ) Используя преобразование j (z,t ) =, перепишем выражение для s (t ) F ( x,t ) в следующем виде:

j2 F ( x,t ) =,t ) exp - 2 dj.

' 2p j ( Формула для вычисления производной интеграла, зависящего от па раметра t, приводит к выражению для Ft' (x,t ), j 2 (1,t ) Ft' ( x,t ) = - jt' (1,t ) exp -.

2p - M 's - (1 - M )s ' Так как jt' (1,t ) =, то условие, накладываемое на пара s метры случайного процесса e (t ), которое приводит к монотонному неубы ванию по t функции F (x,t ), состоит в следующем:

M ' (t ) s (t ) [M (t ) - 1] s ' (t ).

Очевидно, условию (3.2.9) удовлетворяют широко используемые на практике случайные процессы с линейными функциями M (t ), s (t ).

При выполнении условия (3.2.9) каждое слагаемое функции W (x,t ) в формуле (3.2.3) при заданном x k достигает минимального (нулевого) зна чения при t k = S k - (t 0 + T ). Если же на t k накладывается ограничение (3.2.4), то каждое слагаемое W (x,t ) достигает минимального значения при [ ] t k = max S k - t 0 - T, b, (3.2.10) где b удовлетворяет соотношению:

Глава 3. Оптимальные задачи на современном разрабатывающем предприятии ( ) 1 - M t 0 + T + b (3.2.11) F = Pk + 2, ( ) s t +T +b y x 1 где F (x ) = e dy - функция Лапласа.

2p Разработанные и описанные ниже алгоритмы позволяют найти реше ние поставленной выше задачи (3.2.4-3.2.8) в два этапа: а) этап решения задачи №1 (3.2.4-3.2.8) без учета ограничения (3.2.7) и б) этап перехода к решению исходной задачи с учетом ограничения (3.2.7) - задача № 2.



Pages:     | 1 | 2 || 4 | 5 |   ...   | 8 |
 





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

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