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

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

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


Pages:     | 1 |   ...   | 2 | 3 || 5 | 6 |   ...   | 8 |

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

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

Численная реализация задачи № 1 основана на базе использования ме тода динамического программирования. Численная реализация задачи № и оптимального распределения в целом приводится в комплексном алго ритме, который описан в конце данного параграфа в операторном виде.

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

~ Другими словами, уравнение для функции математического ожидания случайного процесса, отражающего ход выполнения разработки при t t 0 + T, имеет вид:

mk (t ) = At + B. (3.2.12) Коэффициенты A и B выбираются так, чтобы искомая прямая прохо дила через две точки, одна из которых имеет координаты (t 0 + T, qk + xk ), а другая - (S k, Qk ). Координата Qk подлежит определению, исходя из условия ( x - Qk ) 2p dx = Pk. (3.2.13) exp 2s k sk Неравенство (3.2.13) отражает требование выполнения разработки к директивно заданному сроку S k с надежностью Pk. Исходя из сказанного, формула для расчета A имеет вид:

Qk - (qk + xk ). (3.2.14) A= t k - (t 0 + T ) В случае, если на интенсивность (по трудоемкости) выполнения раз работки накладывается ограничение (меньше a ' ), то осуществляется про верка выполнения условия A - a ' 0.

Если условие не выполняется, то коэффициент A : = a '.

Таким образом, окончательная формула для расчета коэффициентов А и В имеет вид:

Стохастические Сетевые Модели Планирования и Управления Разработками A = min( A', a ' ) ;

B = qk + xk.

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

s k (t - t 0 - T ), (3.2.15) s k2 (t ) = ~ t k - (t 0 + T ) где s k2 - значение дисперсии, полученное в результате обработки получен ной статистики на базе использования регрессионной модели методом пас сивного эксперимента;

~ S k, если A = A' ;

tk = t k, если A = a ';

x - mk (t k ) * exp - dx = Pk. (3.2.16) tk = ' s k (t k ) 2p - 2s k (t k ) * * Приводим перечень используемой в алгоритме символики:

Dt - масштаб времени;

T - величина планового периода;

t 0 - момент начала планового периода;

C 0 (t ) - ограничение на динамику затрат для моментов времени t t0 + T ;

P - уровень надежности выполнения ограничений (3.2.7);

Dy - величина начального шага;

e - точность решения;

h - параметр настройки алгоритма;

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

M z - максимальное число «неудачных» шагов по статистическому градиенту при фиксированном шаге Dy ;

R3 - счетчик удачных шагов;

[ ] - оптимальный вектор приращения относительной тру X * = x1,..., x* * N доемкости;

t = [t 1,..., t N ] - время окончания выполнения проектов с заданной веро ~ ятностью Pk при распределении X * ;

w ( x*, t *) - минимальное значение критерия.

Процесс решения задачи № 1 можно представить как одномерный ди намический процесс распределения ресурса CT по N шагам, где N - коли чество разработок. Это становится возможным, если воспользоваться фор мулой (3.2.10) для расчета t k. Найденное t k соответствует минимальному значению k -го слагаемого для критерия w. Иначе говоря, существует функциональная зависимость вида:

t k = t k ( xk ). (3.2.17) Используя зависимость (3.2.17), можно переписать формулу для кри терия W следующим образом:

Глава 3. Оптимальные задачи на современном разрабатывающем предприятии N N W ( X, t ) = w k ( x k ) = p k [1 - Fk ( x k,t k {x k })][t 0 + T + t k ( x k ) - S k ]2. (3.2.18) k =1 k = Формула (3.2.18) представляет собой аддитивную функцию каждой компоненты вектора X.

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

k - номер шага, распределения (номер проекта);

X = [x1,..., xk ] - вектор, определяющий приращение относительной трудо k емкости на плановый период T до k -го шага включительно;

() y k = f X = [ y1,..., yk ] - вектор накопленных затрат, отражающий дина k k мику распределения X ;

Каждая компонента вектора y k подсчитывается по формуле:

k yk = C j x j. (3.2.19) j - [ ] W y1,..., y k - величина целевой функции, соответствующая оптималь * * ному распределению затрат X (k ).

* Использование принципа оптимальности [3.3, 3.5] приводит к сле дующему соотношению:

[ ] [ ] W y1,..., y k -1 + Wk ( x k ), k = 2,..., N, (3.2.20) W y1,...y k = * * * * min x k :x k + y k -1 = y k ;

* * x D k где область D определяется неравенствами (3.2.4-3.2.6).

Алгоритм решения задачи № 1. В алгоритме осуществлена вычисли тельная реализация метода динамического программирования [3.5] с неко торым шагом дискретности D. На каждом шаге распределения k вычисля ется разброс возможных накопленных затрат J k D, подлежащих распреде лению. Для каждого значения затрат yki = j D, где j = 1, J k, просматривается множество возможных вариантов и запоминается наилучший. Множество возможных вариантов распределения после k шагов, требующих затрат размером yki, определяется в результате продолжения оптимальных вари антов распределения после (k - 1) -го шага. Эти варианты хранятся в памяти ЭВМ. Просмотр вариантов распределения осуществляется путем введения составного цикла, состоящего из трех вложенных друг в друга простых циклов: цикла просмотра шагов k = 1, N, цикла просмотра различных уров ней затрат на каждом шаге j = 1, J k и цикла просмотра всех вариантов, тре бующих затрат, равных ykj = j D, s = 1, J k -1. В результате работы алгоритма на печать выдается множество оптимальных вариантов распределения по сле N -го шага, каждый из которых требует различных размеров затрат с равным шагом дискретности, а именно y N = j D, где j = 1, J N, а j Стохастические Сетевые Модели Планирования и Управления Разработками C J N = Т + 1. Символ [x ] определяет целую часть величины x, не превос D ходящую x.

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

Оператор L1 осуществляет присваивание k : = 1, где k - номер шага.

Оператор L2 осуществляет присваивание y0' : = 0, где y0' - величина за трат на нулевом шаге.

Оператор L3 осуществляет присваивание w0 : = 0, где w0 - величина критерия на нулевом шаге.

Оператор L4 осуществляет присваивание J 0 : = 1, где J 0 - количество возможных вариантов на нулевом шаге.

Таким образом, операторы L1 - L4 осуществляют подготовку данных для работы алгоритма.

Оператор L5 осуществляет присваивание j : = 1, где j - индекс, опре деляющий уровень затрат на k -м шаге, а именно ykj = j D.

Оператор A6 вычисляет уровень накопленных затрат на k -м шаге, со ответствующий индексу j по формуле:

ykj = j D.

Оператор L7 присваивает s : = 1, где s - индекс, соответствующий но меру варианта распределения до k -го шага включительно и приводящего к уровню затрат, равному y kj.

Оператор A8 вычисляет величину приращения относительной трудо емкости X ks, приводящей к заданному уровню затрат по формуле:

ykj - yks - X ks =.

Ck Оператор P9 осуществляет проверку выполнения условия X ks 0. Ес ли условие не выполняется, то происходит передача управления оператору L14.

Оператор P10 осуществляет проверку выполнения условия X ks D, где D - область, определяемая неравенствами (3.2.4-3.2.6). Если условие не выполняется, то происходит передача управления оператору L14.

Оператор А11 вычисляет величину критерия Bk, соответствующего s му наилучшему варианту до (k - 1) -го шага с величиной приращения X ks на k -м шаге. Величина критерия подсчитывается по формуле:

Bks = Wks-1 + Wk j (X ks ). (3.2.21) В формуле (3.2.21) Wk -1 - величина критерия, соответствующая наи s лучшему варианту распределения до (k - 1) -го шага с уровнем затрат, рав ным yks -1 ;

Wk j (X ks ) - слагаемые суммы в формуле (3.2.3).

Глава 3. Оптимальные задачи на современном разрабатывающем предприятии Оператор Р12 проверяет выполнение условия Bks - Wk j 0. Если усло вие выполняется, то s -й вариант не является наилучшим, и происходит пе редача управления оператору L14.

Оператор З13 работает в условиях, когда s -й вариант является наи лучшим, и осуществляет запоминание Wk j = Bks и уровня yks -1.

Оператор L14 осуществляет переход к просмотру очередного варианта путем присваивания очередного номера счетчика s : = s + 1.

Оператор P15 проверяет выполнение условия s yk -1. Если условие не выполняется, то это означает, что просмотрены не все варианты. Осущест вляется переход к просмотру очередного варианта на оператор A8.

Оператор L16 осуществляет переход к просмотру вариантов, приво дящих к уровню затрат ykj +1, т. е. присваивание j : = j + 1.

Оператор P17 проверяет выполнение условия j yk. Если условие не выполняется, то происходит передача управления на начало просмотра ва риантов, т.е. к оператору A6.

Оператор L18 работает в условиях, когда на k -м шаге все операции выполнены и осуществляется начало работы на (k + 1) -м шаге, т.е. осущест вляет присваивание k : k + 1.

Оператор P19 проверяет выполнение условия k N. Если условие не выполняется, то происходит передача управления на окончание процеду ры, т.е. к оператору Я 24.

Оператор А20 вычисляет границы изменения затрат на k -м шаге по формуле:

J C k min 1 - k -1, d k Ck.

J k = J k -1 + D Оператор Q21 передает управление оператору L5.

Оператор З22 запоминает пары (Wk j, ykj ), (Wks-(1j ), yks (-j1) ) для любых j.

* Оператор A23 вычисляет WNj = min WNj.

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

( ), [ ] y * = y1,..., y *, x = [x1,..., x N ], v x * N yi - yi - где xi =, i = 1, N, x0 = 0.

Ci Операторная схема алгоритма при описанных операторах имеет вид:

L1 L2 L3 L4 L5 A6 L7 A8 P9 14 A11 P - З13 L14 P 8 L16 P 6 L18 P A20Q21З22 A23 Я 24.

15 17 Стохастические Сетевые Модели Планирования и Управления Разработками Переходим к алгоритму решения исходной задачи (задачи № 2). Ввиду того, что для требуемого суммарного ресурса Сt, соответствующего решению задачи (3.2.4-3.2.6), (3.2.8), условие (3.2.7) при некоторых t может не выполнять ся, требуется осуществить оптимальное «сжатие» или «растяжение» времени выполнения проектов в зависимости от превышения или недостатка налично го ресурса С 0 (t ) над требуемым Сt.

Будем предполагать, что изменение величины приращения xk относитель ной трудоемкости на некоторую величину Dxk вызывает изменение времени выполнения на некоторую величину Dt k :

Dt k = j (Dx k ).

Задача оптимального «растяжения» времени выполнения каждого про екта сводится к отысканию такого вектора D x = [Dx1,..., DxN ] в любой момент времени t, при котором выполняется ограничение [( ] ) P Ct x + D x(t ) C 0 (t ) P (3.2.22) и критерий ] W (Dx(t )) = p k (1 - Pk )[t k0 + T + t + Dtk - S k (3.2.23) N (t ) достигает минимального значения.

В формуле (3.2.23) N (t ) представляет собой множество разработок, вы полнение которых не окончено к рассматриваемому моменту времени t.

Переходим к описанию алгоритма решения задачи № 2. Предлагаемый ниже алгоритм основан на методе получения статистического градиента функционала W (x,t ) с проектированием его на границу допустимой области, определяемой ограничениями (3.2.4-3.2.7).

Алгоритм решения задачи № 2. Алгоритм реализует поиск локального экстремума x* = [x1*,..., xN ], отражающего оптимальное распределение ресур * сов между разработками. К основным блокам рассматриваемого алгоритма можно отнести следующие: формирование исходного допустимого вектора x0, удовлетворяющего ограничениям (3.2.4-3.2.7);

вычисление стохастического гра () k диента grad W x в рассматриваемой точке xk ;

проектирование вектора ( ) на поверхность ограничений (3.2.4-3.2.7) - вычисление вектора k grad W x h (x );

вычисление шага продвижения вдоль вектора h (x );

реализация окон k k чания процедуры.

Операторная схема.

Q1 - ввод исходной информации.

A2 - вычисление вектора x0 в результате решения задачи № 1.

( ) (см. 3.2.10).

A3 - вычисление моментов окончания разработок t = t x (3.2.7) F (t, x ) при - вычисление левых частей неравенства A Глава 3. Оптимальные задачи на современном разрабатывающем предприятии t = Dt, 2Dt,..., nDt.

() P5 - проверка условия F t, x 0 0 при всех t. Если да, то переход к Я19.

: F (t, x ) = min F (t ) A6 - выделение j *,..., x 0.

j* j F F ( ) A7 - вычисление grad F t j*, x 0,t 0 = 0,.

x t ( ) A8 - вычисление h( x0 ) - проекции grad F t j*, x 0 на плоскость (3.2.5).

F F A9 - вычисление x 0 : = x 0 - a1, где a1,a 2 0.

- a t x ( ) A10 - вычисление F t j*, x 0,t 0.

( ) P - проверка условия F t j*, x 0 0. Если нет, то переход к A6.

A12 - k : = 0.

( ).

A13 - вычисление W x, t k k ) = W, tW.

( k k A14 - вычисление grad W x,t k k x ) - проекции grad W (x,t ) на плоскость, каса ( k k k k A15 - вычисление h x,t тельную к (3.2.7).

А16 - проверка ( ) k k h x,t ( ) d.

k k grad W x,t Если да, то переход к Я19.

А17 - k : = k + 1.

P - переход к A13.

Я19 - окончание работы алгоритма.

Операторная схема алгоритма имеет следующий вид Q1 A2 A3 A4 P5- 19 A6 A7 A8 A9 A10 P 6 A12 A13 A14 A15 A16 A17 Р18 Я19.

§3.3 Модель оптимального распределения ресурсов внутри проекта Задача распределения ресурсов внутри проекта возникает, как было указано выше в §3.1, на этапах управления ходом разработки, начиная с этапа аванпроекта. Эта задача лежит в основе формирования оперативного календарного плана по теме (разработке), сводного квартального темати ческого плана, планов по выпуску технической документации, постройки изделия, подготовки производства, месячных планов цехов основного про изводства. Основную цель, на выполнение которой направлено решение поставленной задачи, можно сформулировать следующим образом: «необ ходимо построить оптимальный календарный план выполнения всех работ проекта, который позволяет выполнить проект не позднее директивного срока с минимальными затратами». При этом следует выдержать ограни Стохастические Сетевые Модели Планирования и Управления Разработками чения на динамику потребления основного ресурса в течение календарного периода.

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

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

Пусть G = {Y,U } - сетевой график, определяемый следующей парой множеств;

Y - множество событий (вершин);

U - множество работ (дуг);

TH = { i, j ;

tij, где (i, j ) U } - календарный план выполнения проекта. Здесь Tij T плановое начало выполнения работы (i, j ), tij - продолжительность ее вы полнения.

Каждой работе (i, j ) U соответствует числовая функция Cij = fij (t ), где t t ij, t ij - область определения этой функции;

S дир - директивный срок вы полнения проекта;

C - плановая стоимость выполнения проекта в целом.

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

Пусть календарный план T удовлетворяет ограничениям:

Tij + tij S дир для всех (i, j ) U, (3.3.1) Cij (t ) C d ij (t ) (3.3.2) 0, 0 t S дир, tij S дир () i, j U где 1 при Tij t Tij + t ij ;

d ij (t ) = 0 в противном случае;

tij t ij ;

Tij t p, i Y, (i, j ) U. (3.3.3) В области D, описанной ограничениями (3.3.1-3.3.3), требуется найти план Т *, который обращает в минимум целевую функцию стоимости сле Глава 3. Оптимальные задачи на современном разрабатывающем предприятии дующего вида:

C (t ).

С (T ) = (3.3.4) ij ij (i, j )U Сформулированная задача (3.3.1-3.3.4) относится к задаче математи ческого целочисленного программирования [3.6]. Учитывая большую раз мерность задачи (число работ проекта может достигать нескольких тысяч), при ее решении использовалось одно упрощающее допущение. Это допу щение состояло в том, что решение исходной задачи заменялось последо вательными решениями следующих задач.

Задача I. Требуется найти план продолжительностей работ t * = { tij, (i, j ) U }, который удовлетворяет ограничению * () (3.3.5) Tкр t * - S дир и обращает в минимум целевую функцию () С t * = C ij (t ij ).

(i, j )U Задача II. При заданном векторе продолжительностей t * = {tij, (i, j ) U } * требуется найти вектор T * = { ij*, tij, (i, j )U }, характеризующий начало вы T* полнения каждой работы, который удовлетворяет условию (3.3.1) и обра щает в минимум целевую функцию следующего вида:

C W (T ) = max C ij (t ) d ij (t ) -. (3.3.6) (i, j )U t ij S дир t () Другими словами, W T = min W (T ). * Разработанные методы решения задач I и II позволяют, на наш взгляд, преодолеть трудности, связанные с большой их размерностью благодаря учету специфических особенностей топологии рассматриваемых сетевых графиков. Эти особенности состоят в возможности выделения фрагментов и замене каждого из этих фрагментов одной работой или же небольшим количеством укрупненных работ. Идея выделения фрагментов в свое вре мя широко использовалась при расчете временных параметров сетей большого размера в [3.4]. В на стоящем разделе идея обобщается на решение задачи укрупнения ис ходной информации по времени стоимости при замене фрагмента укрупненными работами.

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

Стохастические Сетевые Модели Планирования и Управления Разработками I. Последовательность («цепочка») работ. Этот тип фрагментов об ладает тем свойством, что начало выполнения любой (последующей) рабо ты (кроме первой работы цепочки) является концом выполнения только одной (предыдущей) работы. Обозначим все работы цепочки через (i, j1 ), ( j1, j2 ),K, ( jn, j ), и пронумеруем их в порядке следования.

Пусть варианты выполнения работы ( jk -1, jk ), где k = 1, n, i = jo, j = j n +1, задаются числовой функцией вида:

Сk = f k (t ), где t t k.

Далее, пусть Сij = f it (t ) - числовая функция, отражающая варианты вы полнения работы (i, j ) или цепочки в целом. Очевидно, что эта функция имеет следующую зависимость от вариантов выполнения каждой работы цепочки:

n f ij (t ) = min Ck (tk ), t [a, b], (3.3.7) t k t k = где а = min t k, b = max t k.

k k В формуле (3.3.7) минимум берется по всем наборам {t1, K, tn }, кото рые в сумме не превосходят заданного числа t и tk t k. Функция f it (t ) яв ляется монотонно невозрастающей и имеет следующий технико экономический смысл.

Каждому набору {t1,...,tn } однозначно соответствует значение длины n n цепочки t = t k и затрат C = Ck (tk ). Если каждое t k пробегает t k, то все k =1 k = наборы {t1,...,tn } отображаются в множество M точек плоскости с осями ко ординат C0t. Эти наборы можно пронумеровать для случая конечных t k.

Каждая из точек множества M представляет собой вариант.выполнения цепочки (i, j ). Однако из множества M можно удалить те ва рианты с номером P (им соответствуют пары С р, Т р ), для каждого из кото рых найдется вариант с номером q(Cq,Tq ), если выполняются условия C q C p, Tq T p.

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

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

Глава 3. Оптимальные задачи на современном разрабатывающем предприятии Например, для цепочки с количеством работ, равным 10, и одинаковым числом вариантов, равным 3, для построения функции fij (t ) требуется «просматривать» порядка 310 точек.

Для построения зависимости fij (t ) будем использовать весьма эффек тивный метод динамического программирования [3.5]. При этом вычисле ние fij для любого t сводится к последовательному вычислению на k -м шаге (k = 1, n ) значения tk t k так, чтобы получить минимальное значение n n ck (tk ) при условии t суммы t.

k k =1 k = N - Обозначим через C * (x N -1 ) = min C (t ) затраты, соответствующие k k v - t k x N -1 k = k = оптимальному распределению величины x N -1 по (N - 1) -му шагу, и через (x,..., x ) - варианты распределения накопленной суммы t N - до (N - 1) -гo * * N -1 k k = шага, запишем функциональное уравнение, которому удовлетворяет опти мальное распределение после N шагов:

С * ( xN ) = min [C * ( xN -1 ) + C N (t N )], N = 2,..., n.

+t x x N -1 N N Исходя из сказанного, запишем алгоритм вычисления f it (t ) для любо го t в пределах Tmin t Tmax.

Исходная информация для алгоритма.

1. Массивы значений (СN, t N ) - вариантов выполнения N -й работы, k k где N = 1,2,..., n, n – количество разработок.

2. Значения D.

Используемые обозначения в алгоритме.

N - номер шага выбора t N по N -й работе цепочки;

N - после (N - 1) t X N -1 - запоминаемое значение накопленной суммы k k k = гo шага для оптимального варианта;

С N -1 - соответствующее значение затрат;

k D - интервал дискретности для просмотра отрезка [Tmin, Tmax ].

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

Этап 1. N : = 1, x 0 = 0, x1 =, C 0k = 0.

N Этап 2. aN : tk, где tk = min t k.

k = N Этап 3. bN : = tk, где tk = max t k.

k = bN - aN Этап 4. Вычисление M = + 1, где [x ] - целая часть x.

D Стохастические Сетевые Модели Планирования и Управления Разработками Этап 5. m := 0.

Этап 6. k := 0, СN =.

m Этап 7. Вычисление z m := a N + m D.

Этап 8. Вычисление: d m = zm - x N -1.

k k Этап 9. Сравнение d m 0. Если нет, то переход к этапу 17.

k Этап 10. s := 1.

Этап 11. Сравнение d m - t N 0. Если нет, то переход к этапу 14.

k s Этап 12. s := s + 1.

Этап 13. Переход к этапу 11.

~m Этап 14. Вычисление СN = CN -1 + CN (t N-1 ).

k s ~m Этап 15. Сравнение СN - CN 0. Если нет, то переход к этапу 17.

m ~m m Этап 16. CN := СN ;

xN := x N -1 + t N-1.

m k s Этап 16. k : k + 1. Переход к этапу 8.

Этап 17. m : = m + 1.

Этап 18. Сравнение m M. Если нет, то переход к этапу 7.

Этап 19. N := N + 1.

Этап 20. Сравнение N n. Если да, то переход к этапу 22.

Этап 21. Переход к этапу 2.

Этап 22. Вычисление M : CN = min CN.

m m m Окончание работы алгоритма и выдача результатов: xN, CN и значе M M ния t N, CN (t N ) при N = 1,2,..., n.

k k Рис. 3.3. Множество параллельных работ Рис. 3.4. Фрагмент сети II. Множество параллельных работ, соединяющих вершины i и j.

Пусть задано множество дуг, соединяющих вершины i и j, и все дуги пронумерованы от 1 до n, как это показано на рис. 3.3.

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

Построим функцию Сij = f ij (t ), определяющую множество вариантов выполнения фрагмента, состоящего из одной работы, соединяющей i и j.

Очевидно, продолжительность t любого варианта выполнения фраг мента лежит в отрезке [Tmin, Tmax ], где Tmin = max min t, t t k k Tmax = max max t.

t t k k Глава 3. Оптимальные задачи на современном разрабатывающем предприятии Область определения t ij функции Cij (t ) состоит из всех точек t, при надлежащих теоретико-множественному пересечению двух множеств t = t U t 2 U,...,Ut n и [Tmin, Tmax ], т.е. t ij = t I [Tmin, Tmax ].

Каждой точке множества t ij соответствует значение функции n fij (t ) = Ck (tk ), k = где tk = max t '.

t ' t В качестве примера рассмотрим фрагмент вида рис. 3.4, где t 1 = {2, 3, 4} ;

t 2 = {3, 4, 5} ;

t 3 = {2, 3, 4, 5, 6} ;

f1 = {10, 8, 7} ;

f 2 = {8, 6, 5} ;

f 3 = {12, 10, 8, 7, 6}.

Тогда t ij = {3, 4, 5, 6} и fij = {26, 21, 19, 18}.

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

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

Пусть задан сетевой график G = {Y,U }, где Y - множество вершин, из которых одна не имеет входящих работ (вершина O ) и одна не имеет вы ходящих работ (вершина K ).

Каждой работе (i, j ) U соответствует числовая функция Сij = f ij (t ), где t t ij - произвольное непустое множество.

Пусть t = {tij (i, j ) U } план продолжительностей выполнения работ гра фика G. Tкр (t ) - длина критического пути графика G. Исходная задача ук рупнения информации при редукции фрагмента сводится к построению функции f (t ) следующего вида:

f (t ) = min fij (tij ). (3.3.8) {Tкр ( t } t ( ij )U В формуле (3.3.8) минимум берется по всем наборам t = {tij, i, j U }, для которых длина критического пути меньше заданного числа t. Очевидно, t [Tкр (a ) - Tкр (b)], где a = {min t i, j (i, j ) U }, b = {max t i, j (i, j ) U }.

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

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

Правило предпочтения состоит в реализации 2-х этапов:

1) вычисление функции предпочтения F (i, j ) для каждой дуги (i, j ) U ;

2) выделение дуги (i *, j * ) с наибольшим значением функции предпоч тения, т.е. F (i *, j * ) = max E (i, j ).

(i, j )U Функция предпочтения E (i, j ) учитывает в прямой зависимости отно сительную величину D(i, j ) убывания функции затрат fij на единицу увели чения t (i, j ), а также в обратной зависимости - возможную величину D' (i, j ) изменения функции затрат по всем дугам (i -1, j -1 ), лежащим на тех критиче ских путях, которые проходят через дугу (i, j ).

Например, если множество t ij конечно и в момент вычисления функ ции F (i, j ) дуга (i, j ) имела продолжительность tijk t ij, где k - номер точки множества t ij в порядке возрастания t, то () () f ij t ij - f ij t ij + k k F (i, j ) = ) - D (i, j ).

(3.3.9) (t k + -t k ' ij ij Предполагается, что в формуле (3.3.9) выполняется соотношение t t, и величина D' (i, j ) вычисляется по формуле:

k + k ij ij ( ) ( ), f pq t k ( p,pq) - f pq t k ( p, q )+ q D (i, j ) = pq (3.3.10) ' k ( p,q )+1 k ( p,q ) -t t ( p, q M pq ) pq pq где M pq = {( p, q ) L(i, j ), t k ( p, q ) max t pq };

L(i, j ) - множество путей, проходящих pq через дугу (i, j ).

Иногда в целях упрощения в качестве D' (i, j ) можно принимать коли чество дуг, входящих в L(i, j ), или количество путей множества L(i, j ).

Алгоритм построения зависимости (3.3.8) состоит из следующих эта пов.

Этап 1. Вычисление длины критического пути Т кр (а ), где а = {min t ij, (i, j ) U }.

Этап 2. Вычисление длины критического пути Т кр (b ), где b = {max t ij, (i, j ) U }.

Этап 3. Вычисление полных резервов Rполн (i, j ) для каждой работы се тевого графика G с метрикой b = {max t ij (i, j ) U }.

Глава 3. Оптимальные задачи на современном разрабатывающем предприятии () ( ), где Tкр b - Tкр a Этап 4. Вычисление D = n - заданное количество ин n тервалов разбиения.

Этап 5. m : = 0, где m - номер интервала разбиения.

Этап 6. Tm : Tкр (а ).

Этап 7. Вычисление Am = Tкр (b ) - Tm.

Этап 8. Выделение множества работ U ' = {(i, j ) : R полн (i, j ) Am }.

Этап 9. Присвоение t ij : = b ij для (i, j ) U.

* Этап 10. Выделение множества u ' ' = u \ u ' как теоретико множественной разности множеств U и U '. Количество дуг множества U " обозначим через s m.

Этап 11. Вычисление функции предпочтения F (i, j ) для каждой дуги (i, j ) U ".

Этап 12. s : = 1 ( s - номер дуги по убыванию F (i, j ) ).

Этап 13. Сравнение tis, js - tis, +1 0. Если условие не выполнено, то осу k ks s js ществляем переход к этапу 19.

Этап 14. tis, js : tis, +1.

k s js () Этап 15. Вычисление Tкр t s, где t s = {tis, js, s = 1, sm }.

(t )- T Этап 16. Проверка Tкр s m 0. Если условие не выполнено, то пере ход к этапу 19.

Этап 17. k s : = k s + 1, где k s - варианты выполнения работы по дуге s.

Этап 18. Переход к этапу 13.

Этап 19. s : = s + 1.

Этап 20. Проверка s sm. Если условие не выполнено, то переход к этапу 13.

Этап 21. m : = m + 1.

Этап 22. Проверка m n. Если выполнено, то переход к этапу 25.

Этап 23. Tm : = Tкр (а ) + m D.

Этап 24. Переход к этапу 7.

Этап 25. Остановка ЭВМ и выдача на печать значений Tm, Cm, где m = 0, n.

Операторная схема приведенного алгоритма имеет вид:

A1 A2 A3 A4 A5 A6 A7 F8 A9 F10 A11 A12 20 P- 19 A14 A15 P - A17 П18 A19 P20 13 A21 P22 25 A23 П 24 Я 25.

13 В качестве примера рассмотрим фрагмент одного из производствен ных сетевых графиков следующего вида (рис. 3.5).

Варианты выполнения работы (0,1) состоят в следующем:

t 1,1 = 1, f 01,1 = 6, t 0,2 = 2, f 02,1 = 4, t 0,1 = 3, f 03,1 = 3. Реализация этапов 1-4 ал 0 горитма приводит к результатам:

Стохастические Сетевые Модели Планирования и Управления Разработками 1. Tкр (а ) = 6.

2. Tкр (b ) = 14.

3. Значения полных резервов работ графика G с метрикой (b ) сле дующие:

(i, j ) 0,1 0,2 1,2 1,3 2,3 1, K 3, K R полн (i, j ) 0 40 3 0 8 4. D = 1 при n = 8.

Как следует из вывода для работы (1, k ) выполняется соотношение R полн (1, k ) = Tкр (b ) - Tкр (o ), поэтому ее можно не рассматривать в процессе оп тимизации, задав величину продолжительности ее выполнения максималь ной, т.е. равной 3.

Процесс вычисления коэффициента D' (i, j ) (количество путей, прохо дя-щих через дугу (i, j ) ), следующий:

(i, j ) 0,1 0,2 1,2 1,3 2,3 1, K 3, K D' (i, j ) 2 1 1 1 2 1 Результаты расчетов по вычислению зависимости затрат ресурсов от продолжительности выполнения работы (O, K ), соответствующей фрагмен ту, приведены в табл. 3.1.

Рис. 3.5. Фрагмент производственного сетевого графика.

IV. Фрагмент работ, имеющих несколько входных и несколько выходных вершин. Рассмотрим пример фрагментов общего вида, имею щих несколько входных и выходных вершин, приведенный на рис. 3.6.

Представленный на рис. 3.6 фрагмент F имеет две входные вершины ( O1 и O2 ) и две выходные ( K1 и K 2 ).

Если фрагмент F с n входами и m выходами перенумеровать, т.е.

любой его дуге присвоить конкретное число (продолжительность его вы полнения), то при укрупнении его можно заменить графом F, состоящим из работ в количестве n m. Пусть, например, продолжительности работ фрагмента, представленного на рис. 3.6, записаны в следующем виде:

Глава 3. Оптимальные задачи на современном разрабатывающем предприятии (0,1) (O2,2 ) — 2 ;

(1,2 ) — 1;

— 2;

(1,3) (1,4 ) — 2 ;

(2,3) — 1;

— 3;

(3,4 ) (4,5) — 1;

(3,6) — 2;

— 3;

(4,6) (6, K1 ) — 1;

(S, K 2 ) — 3 ;

— 2;

Тогда укрупненный фрагмент имеет вид, представленный на рис 3.7.

Таблица 3. Результаты расчетов (i, j ) 0, 1 0, 2 1, 2 1, 3 2, 3 1, К 3, K Т С t* 1 3 2 3 1 3 2 6 t * (0) 1 3 3 4 1 3 2 7 t * (1) 1 3 4 4 1 3 2 8 t * (2) 2 3 4 4 1 3 2 9 t * (3) 2 3 4 4 2 3 2 10 t * (4) 2 3 4 4 2 3 3 11 t * (5) 3 3 4 4 2 3 3 12 * t (6) t * (7 ) 3 3 4 4 3 3 3 13 t * (8) 3 3 4 4 3 3 4 14 Продолжительности работ этого фрагмента представлены так:

(O1, K1 ) (O1, K 2 ) (O2, K1 ) (O2, K 2 ) 12 12 11 Рис.3.6. Фрагмент производственного Рис.3.7. Укрупненный фрагмент сетевого графика, имеющий несколько производственного сетевого гра входных и выходных вершин фика Работе (O1, K1 ) укрупненного фрагмента соответствует максимальный путь L(O1, K1 ) исходного фрагмента, соединяющий вершины O1 и K1.

L(O1, K 1 ) : (0,1), (1,2 ), (2,3), (3,4 ), (4,5), (5,6), (6, K 1 ).

Длина пути L(O1, K1 ) равна 12 ед.

L(O1, K 2 ) : (O1,1), (1,2 ), (2,3), (3,4 ), (4,5), (5, K 2 ).

Длина пути L(O1, K 2 ) равна 12 ед.

Стохастические Сетевые Модели Планирования и Управления Разработками L(O2, K 1 ) : (O2, 2 ), (2,3), (3,4 ), (4,5), (5,6), (6, K1 ).

Длина L(O2, K1 ) равна 11 ед.

L(O2, K 2 ) : (O2, 2 ), (2,3), (3,4 ), (4,5), (5, K 2 ).

Длина L(O2, K 2 ) равна 11 ед.

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

1. Сумма затрат на выполнение всех укрупненных работ не равна (в общем случае) сумме затрат на выполнение всех работ исходного фраг мента. Сказанное можно записать в следующем виде:

f i, j (tij ) f ij (t ), pq ( i, j )L ( O p, K q ) ( i, j )U где U - множество всех работ исходного фрагмента.

2. Двум различным укрупненным работам (O p K q ) и (Or K s ), p r, или q s, могут соответствовать пути, содержащие общие работы, т. е.

L(O p, K q ) I L(Or, K s ).

Однако можно говорить о функции затрат f (t ), зависящей от вектора { } t = t O p, K q, p = 1, n, q = 1, m, или одновременно от всех его компонент, но в общем случае не являющейся аддитивной функцией компонент вектора t.

Если для всех работ исходного фрагмента заданы варианты выполне ния «затраты-время» в виде функции Cij = f ij (t ), (i, j ) U, то для укрупнен ного фрагмента функцию затрат f (t ) определим следующим образом:

f (t ) = min fij (tij ), (3.3.11) t 'M ( i, j )U где { } M = t ' : L(O1, K 1 ) t (O1, K 1 ),..., L(On, K m ) t (On, K m ), t ' = { ij (i, j ) U }.

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

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

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

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

Сущность этого принципа состоит в последовательной реализации сле дующих этапов:

1. Выделение множества фрагментов {F n }, n = 1, N, исходного сетевого графика G = {Y,U }. Если обозначить через F n = {Yn,U n }, n = 1,2,..., N, где Yn множество вершин;

U n - множество дуг, то выполняются соотношения:

U 1 U U 2 U... U U n = U, U k I U 1 = для всех k l, k, l = 1,2,..., N. (3.3.12) Совокупность фрагментов {U i } мы будем называть иногда разбиением исходного сетевого графика G.

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

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

2. Реализация укрупнения исходной информации, дифференцирован ной по типам фрагментов. Для фрагментов 1-3-го типов используются рас смотренные ранее алгоритмы. Для фрагмента 4-го типа используется алго ритм, реализованный в блоке II и описываемый ниже.

3. Построение укрупненного сетевого графика G, соответствующего данному варианту разбиения Y, и подготовка исходной информации по укрупненным работам.

4. Выполнение k -гo шага оптимизации для укрупненного графика G.

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

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

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

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

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

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

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

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

Задача 1. Пусть задана функция C = f (t ), где t t ij и t ij - некоторое конечное множество t ij = {tij }, s = 1, s. Требуется найти наилучшую в смысле s среднеквадратичного отклонения функцию f (t ) из некоторого класса по линомов Pn, где n - степень полинома.

Если обозначить f (t ) = Co + C1t +,...,Cnt n, то поставленная задача состоит в отыскании вектора С = [Сo*,...,Cn ], который обращает в минимум функцию * * вида:

[( ) ( )].

() ~ s W C = f C o, C1t,..., C n t s - f t s (3.3.13) s = Задача 1II. Пусть задан фрагмент F = {Y, U } с n входными вершинами O1,..., On и m выходными K 1,..., K m. По каждой работе (i, j ) U задана функ ция Cij = f ij (t ), где t t ij =[aij, bij ] и по фрагменту в целом задан вектор T раз мерности n m, т.е.

T = { pq } p = 1, n, q = 1, m.

T, Требуется найти вектор t = {tij, (i, j ) U }, который удовлетворяет системе ограничений Глава 3. Оптимальные задачи на современном разрабатывающем предприятии () Tкр t - T pq 0, p = 1, n, q = 1, m, (3.3.14) pq и обращает в минимум функцию следующего вида:

f (t ) = f ij (t ij ). (3.3.15) (i, j )U Решение этой задачи позволяет вычислить значение функции затрат, определенной по формуле (3.3.8), для любого плана продолжительностей T рассматриваемого фрагмента.

Задача 1III. Пусть вектор t - решение задачи 2, удовлетворяющее ус ловиям (3.3.14). Требуется для любой дуги (O p, K q ) и заданного d 0 найти приращение Dt вектора t, которое удовлетворяет следующей системе ог раничений:

Tpq (t + Dt ) - Tpq d, (3.3.16) кр Tijкр (t + Dt ) - Tij 0, (3.3.17) где i p, j q одновременно и обращает в минимум функцию следующего вида:

f pq (Dt ) = [ f ij (t ij + Dt ij ) - f (t ij )]. (3.3.18) (i, j )U Решение этой задачи позволяет найти направление g наискорейшего убывания функции затрат для укрупненного фрагмента F n. Точнее, на правление g определяется из соотношения (изложено ниже в данном пара графе):

{ () } f pq Dt, p = 1, n, q = 1, m. (3.3.19) g= d Задача 1IV. Пусть в условиях задачи 1II существует вектор t, который удовлетворяет условиям (3.3.14).

Требуется найти приращение Dt, для которого выполняются соотно шения T pq (t + Dt ) - T pq 0, p = 1, n, q = 1, m, (3.3.20) кр f (t + Dt ) - f (t ) 0. (3.3.21) Решение этой задачи позволяет отыскать допустимое направление h убывания функции затрат для укрупненного фрагмента. Точнее говоря, вектор h определяется следующим образом:

h = { pq (t + Dt ) - T pq (t ), p = 1, n, q = 1, m}.

T кр кр Задача 1V. Пусть в условиях задачи 1II функция Cij = f ij (t ) определена на некотором числовом множестве t ij, где t ij = {tij, k = 1, K }, k - номер точки k по возрастанию, K - количество точек множества t ij. Пусть далее задан некоторый вектор t {tij, (ij ) U }, где t ij [t ij,..., t ij ]. Вектор t определяет по каж 1 k дой работе (i, j ) U пару индексов p (i, j ) = {k (i, j ), k (i, j ) + 1} таких, что выпол няется условие Стохастические Сетевые Модели Планирования и Управления Разработками tij (i, j ) tij tij (i, j )+1.

k k Требуется найти для любой работы (i, j ) U номер точки так, чтобы выполнялось одно из двух условий tij (i, j ) tij tij (i, j )+ a a или tij (i, j )-1 tij tij (i, j ) a a и при этом вектор t = {tij (i, j ), (i, j ) U }, где tij (i, j ) t ij, обращает в минимум зна a a чение целевой функции f (t ) = f ij (t ).

(i, j )U Решение этой задачи позволяет наилучшим образом в смысле крите рия f (t ) округлить дробный план по каждой компоненте до целого боль шего или меньшего значения.

Алгоритмы решения задач 1I-1V отражены в блоках I-V.

Блок I позволяет вычислить наилучший вектор С * параметров поли нома n -й степени путем решения следующей системы (n + 1) -го линейного уравнения с (n + 1) -им неизвестным:

s s s n C o t i j + C k t ih + j = t i j f i (t i ), (3.3.22) i =1 i = i =1 h = где j = 0, n.

В (3.3.22) коэффициенты при неизвестных C0, C1,..., C n включают в ка честве своих слагаемых заданный набор из S точек {t i, f i (t i )}, где i = 1, s.

Блок II представляет собой алгоритм решения задачи 1II, который реа лизуется в двух этапах:

а) алгоритмы формирования начального плана (вектора) продолжи тельностей t, который удовлетворяет системе ограничений (3.3.14);

б) алгоритм последовательного улучшения вектора до момента полу чения приближенного экстремума.

Первый из алгоритмов состоит в последовательном увеличении ком понент вектора t = {aij, (i, j ) U } до момента выхода на ограничения (3.3.14) и состоит из следующих этапов:

Этап 1. Присвоение t ij := a ij ;

U 0 := U.

Этап 2. Вычисление g ij : = f ij (t ijk ), (i, j ) U k.

k Этап 2'. k := 1.

Этап 3. p := 1.

Этап 4. q := 1.

Этап 5. Вычисление t ijk = min {bij, t ijk -1 - a g ij -1 }, (i, j ) U k.

k () Этап 6. Вычисление Tкр t, где t = {t ij, (i, j ) U }.

k k pq k Глава 3. Оптимальные задачи на современном разрабатывающем предприятии ()k Этап 7. Сравнение Tкр t - Tpq 0. Если да, то переход к этапу 11.

pq Этап 8. a := a 2.

Этап 9. Проверка a - a 0. Если условие выполнено, то переход к эта пу 19.

Этап 10. Переход к этапу 5.

Этап 11. q := q + 1.

Этап 12. Проверка q m. Если не выполнено, то к этапу 6.

Этап 13. p := p + 1.

Этап 14. Проверка p n. Если нет, то к этапу 6.

Этап 15. k := k + 1.

Этап 16. Восстановление a.

Этап 17. Переход к этапу 3.

Этап 18. k := k + 1.

( ) Этап 19. Формирование множества работ M k -1 = (i, j ) Lкр t k, где Lкр pq pq путь максимальной длины, соединяющий вершины O p и K q.

Этап 20. Формирование U k = U k -1 / M k -1.

Этап 21. Проверка U k =. Если нет, то к этапу 3.

() k k Этап 22. Окончание работы и выдача параметров вектора t 0 : = t, C t.

Операторная схема описанного алгоритма имеет вид:

A1 A2 A2 ' A3 A4 A5,14 A6 P7- A8 P9- 19 P A11 P 6 A13 P 6 A15 A16 П17 3 А18Ф19Ф20 Р2113 Я 22.

12 Второй алгоритм задачи 1II (блок IIб) состоит в последовательном улучшении исходного вектора t, которое состоит в вычислении допусти мого в пределах ограничений вектора убывания целевой функции h(t ) в те кущей точке t и в переходе к очередному вектору t вдоль направления h(t ) с шагом a. Эта процедура продолжается до тех пор, пока приближенно не выполнится необходимое условие экстремума. Алгоритм состоит из сле дующих этапов:

Этап 1. Формирование исходного плана t.

Этап 2. k := 1.

() k - Этап 3. Вычисление вектора h t наискорейшего убывания целевой функции, удовлетворяющего ограничениям (3.3.14).

Этап 4. Проверка условия оптимальности вектора t, (g, h ) 0. Если k - да, то к этапу 19.

Этап 5. p := 1.

Этап 6. q := 1.

Этап 7. Вычисление t ijk = max {aij, tkij-1 - a hkij-1 }, hkij-1 0 (i, j ) U k.

k -1 k -1 k - min {bij, tij - a hij }, hij Стохастические Сетевые Модели Планирования и Управления Разработками () Этап 8. Вычисление Tкр t, где t = {t ij, (i, j ) U }.

k k pq k (t )- T k Этап 9. Сравнение Tкр pq 0. Если да, то к этапу 13.

pq Этап 10. a := a 2.

Этап 11. Проверка условия a - a 0. Если да, то к этапу 13.

Этап 12. Переход к этапу 5.

Этап 13. q := q + 1.

Этап 14. Проверка q m. Если нет, то к этапу 7.

Этап 15. p := p + 1.

Этап 16. Проверка p n. Если нет, то к этапу 13.

Этап 17. k := k + 1.

Этап 18. Восстановление a и переход к этапу 5.

() k k Этап 19. Окончание работы и выдача компонент вектора t, C t.

Блок III является алгоритмом решения задачи 1III.

Суть алгоритма состоит в выделении множества работ U pg, которые принадлежат путям L pg и не принадлежат критическим путям Lkp, соеди- kl няющими вершины Ok, K l.

Далее обращаемся к блоку IIб, где оптимизация осуществляется по ра ботам множества U pq, а неравенство (3.3.14) для рассматриваемых p, q принимает следующий вид:

Tкр (t ) - T pq d.

pq Блок IV осуществляет решение задачи 1IV путем моделирования век тора смещений Dt относительно заданного t и проверку ограничений (3.3.20-3.3.21).


Алгоритм состоит из следующих этапов:

Этап 1. Моделирование вектора x = { ij, (i, j ) U }, где x ij - случайная ве x личина, равномерно распределенная на отрезке [- 1, + 1].

Этап 2. Расчет вектора Dt = {Dt ij, (i, j ) U }, где aij + bij [ ].

signx ij bij - a ij - 2t ij Dt ij = + 2 Этап 3. Расчет вектора t + Dt.

Этап 4. Проверка выполнения условий (3.3.20-3.3.21) для вектора t + Dt. Если нет, то к этапу 1.

Этап 5. Окончание работы и выдача на печать координат вектора Dt, h = { кр (t + Dt ) - T pq (t ), q = 1, m, p = 1, n}.

кр 7 pq Блок V осуществляет решение задачи 1V, или переход от дробного плана к некоторому целому.

Он состоит из следующих этапов:

Этап 1. Округление каждой компоненты вектора t до ближайших це Глава 3. Оптимальные задачи на современном разрабатывающем предприятии лых чисел t H = {t ij (i, j ), (i, j ) U }.

a Этап 2. Вычисление F (i, j ) (функции предпочтения) для каждой дуги (i, j ) U.

Этап 3. Упорядочение множества U в порядке убывания F (i, j ).

Этап 4. Выбор дуги (i*, j *) : F(i*, j *) = max F (i, j ).

(i, j )U a (i *, j * )+ Этап 5. t i* j* : = t.

i* j* Этап 6. Проверка выполнения условий (3.3.14). Если да, то переход к этапу 8.

Этап 7. t i* j* : = t a (ji**, j*).

i* Этап 8. Формирование множества U = U \ (i*, j *).

Этап 9. Проверка условия U =. Если нет, то переход к этапу 3.

Этап 10. Окончание работы и выдача результатов. Операторная схема алгоритма имеет вид:

A1 A2 Ф 3Ф4 А5 Р6 8 А7Ф8 Р93 Я 10.

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

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

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

На первом этапе алгоритма для каждой работы (i, j ) U устанавлива ются начала выполнения всех работ TH (i, j ) в пределах полных резервов (операторы 1 - 6). Далее моменты TH (i, j ) корректируются так, чтобы не было пересечений отрезков выполнения предшествующих и последующих работ (операторы 7 - 17).

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

На втором этапе осуществляется последовательное улучшение исход ного плана T H путем моделирования смещений (операторы 18, 19). После l итераций в результате работы алгоритма определяем план T Н, близкий к m локальному экстремуму.

Алгоритм оптимизации состоит из следующих операторов:

A1 - расчет раннего t p (i ) и позднего t n (i ) сроков свершения любого со Стохастические Сетевые Модели Планирования и Управления Разработками бытия i p.

A2 - расчет полных резервов работ Rn (i, j ), где (i, j ) U.

A3 - вычисление количества работ K (i, j ) сетевого графика, имеющих резерв Rn (i, j ).

F 4 - моделирование случайного вектора h = { ij, (i, j ) U } с равномер h ным распределением на отрезке [0,1] каждой его компоненты hij.

F 5 - моделирование случайного вектора v = {vij, (i, j ) U }, каждая ком понента n ij имеет плотность распределения вероятностей Pij (x ) :

- ( x - M ij ) 2s ij, если 0 x 1, e Pij ( x ) = C 2ps ij ij 0 в противном случае.

Здесь ( ) - x - M ij 1 1 2s ij 2ps ij dx, M ij =.

, s ij = Сij = e 2 K ij 12 K ij При моделировании используется реализация случайной величины hij [3.4].

A6 - расчет моментов начала и окончания каждой работы:

tн (i, j ) = t p (i) + n (i, j ) Rn (i, j ), t 0 (i, j ) = t н (i, j ) + t (i, j ).

F 7 - k := 1, Q0 = 0, k - номер уровня работ исходного сетевого графика.

F 8 - формирование множества событий Pk :

Pk = { j : (i, j ) U, i Qk -1 }.

P9 - проверка условия Pk =. Если да, то переход к F17.

F 10 - формирование множества событий Qk' Pk, где Qk' = { j : i Qk -1, j Pk }.

F 11 - формирование Qk = Qk' U Qk -1.

P12 - проверка условия t0 (i, j ) tn ( j ) для всех i Qk -1, (i, j ) U. Если нет, то переход к A15.

P13 - проверка условия t0 (i, j ) t H ( j, l ) для всех ( j, l ) U. Если нет, то пе реход к A16.

A14 - t H (i, j ) : = t H (i, j ), переход к A17.

* A15 - t H (i, j ) : = t H (i, j ) + t H ( j ) - t0 (i. j ), переход к A16.

* A16 - t H (i, j ) : = t H (i, j ) + min t H ( j, l ) - t0 (i. j ) / * A16 - k := k + 1 и переход к F 8.

' * F17 - m := 0, TH : = T H, где m - количество итераций в случайном поиске.

Глава 3. Оптимальные задачи на современном разрабатывающем предприятии F 18 - моделирование случайного вектора h = { ij, (i, j ) U } с равномер h ным распределением на отрезке [- 1, 1] каждой его компоненты hij.

A19 - вычисление вектора x = { ij, (i, j ) U }, x h ij где x ij =.

h ij (i, j )U { } A20 - вычисление вектора TH +1 = t H +1 (i, j ), (i, j ) U, где m m t H +1 (i, j ) = t H (i, j ) + aR (i, j )xij, a - шаг продвижения по направлению x.

m m P21 - проверка условия t H +1 (i, j ) + t (i, j ) tH +1 ( j, k ) для всех (i, j ), ( j, k ) U.

m m Если да, то переход к A24.

A22 - p := p + 1 ( p - счетчик «неудачных испытаний»).

P23 - проверка условия p P. Если «нет», то переход к Я30. Если «да», то переход к F 18.

( ).

m + A24 - вычисление функционала N T H ( ) W (T ). Если «нет», то переход к A m +1 m P25 - сравнение W T H.

H A26 - m := m + 1.

P27 - сравнение m M ( M - назначаемое заранее количество испыта ний). Если «да», то переход к F 18 и p := 1.

A28 - l := l + 1.

P29 - cравнение l L. Если да, то переход к F 8.

() m m m * Я30 - конец, выдача T H, W T H, где T H » T H.

§3.4 Модели оптимизации комплекса аванпроектов разрабаты вающего предприятия с детализированными ресурсами 3.4.1 Введение Процесс управления комплексом проектов создания объектов новой техники на современном разрабатывающем предприятии начинается с эта па аванпроекта.

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

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

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

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

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

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

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

Теоретические основы и модели п.3.4 рассмотрены в [3.7-3.8, 3.12].

3.4.2 Формализация модели управлении проектами Введём следующую терминологию:

n - число проектов (аванпроектов) P i, 1 i n, каждый из которых представлен цепочкой операций Oic, 1 c mi ;

mi - число операций в проекте P i ;

t ic - случайная продолжительность операции Oic ;

t ic - математическое ожидание случайной величины t ic ;

Vic - дисперсия случайной величины t ic ;

rick - мощность k -го ресурса (количество разработчиков k -й специ альности), используемая в процессе реализации Oic (постоянна и задаётся заранее), 1 k d ;

d - количество потребляемых ресурсов;

Rk - суммарные k -ресурсы (общее число разработчиков k -й специ альности), находящиеся в распоряжении РП (оптимизируемая перемен Глава 3. Оптимальные задачи на современном разрабатывающем предприятии ная);

Di - директивный срок окончания аванпроекта P i (задаётся заранее);

Pi - допустимая вероятность окончания аванпроекта P i в директив ный срок Di (задаётся заранее);

S ic - фактическое время начала реализации операции Oic (случайная величина);

S ic определяется в процессе решения конфликтных ситуаций при одновременной реализации нескольких проектов;


Fic - момент завершения операции Oic (случайная величина);

Fi - момент окончания выполнения i -го проекта;

Fi = Sim + tim (случай i i ная величина);

pi {R k, Di } - вероятность выполнения проекта P i в срок (на основе ими тационного моделирования системы) при условии, что системе выделены постоянные наличные ресурсы Rk, 1 k d ( R k - вектор ресурсов);

Wk (S ic, t ) - суммарная мощность задействованных ресурсов типа k в момент t при условии, что операции Oic стартуют в момент S ic ;

Rk (t ) = Rk - Wk (S ic, t ) - наличные свободные ресурсы k -го типа, готовые к реализации новых операций;

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

DRk - шаг поиска оптимального значения Rk, 1 k d (задаётся зара нее);

e - оценка погрешности целевой функции при поиске оптимального решения;

h i - индекс приоритета (степень важности) проекта P i (задаётся зара нее). Если проект Пi имеет более высокую степень важности, нежели про ект Пi, имеет место hi hi Обычно имеет место hi hi pi* pi*, и наобо 2 1 2 1 2 1 рот;

Rk min - нижняя грань возможного числа разработчиков k -й специаль ности на РП, 1 k d (задаётся заранее);

Rk max - верхняя грань возможного числа разработчиков k -й специаль ности на РП, 1 k d (задаётся заранее).

Заметим, что имеют место соотношения (3.4.1) Rk min max max rick, i c mi n Rk max rick, (3.4.2) i =1 c = Rk min Rk Rk max, 1 k d. (3.4.3) Ограничение (3.4.1) очевидно, ибо в противном случае некоторые из Стохастические Сетевые Модели Планирования и Управления Разработками аванпроектов не смогут быть вообще реализованы. В случае невыполнения ограничения (3.4.2) часть разработчиков вообще не примет участие в про цессе реализации аванпроектов.

3.4.3 Прямая оптимизационная задача минимизации количества разработчиков Математическая формулировка задачи имеет следующий вид [3.7-3.8, 3.12].

Определить оптимальные детерминированные значения Rk, 1 k d, (на этапе, предшествующем реализации аванпроектов), и случайные зна чения S ic, 1 i n, 1 c mi (в процессе реализации аванпроектов), с тем, чтобы минимизировать целевую функцию a Max Fi - Min Si J 1 = Min E Rk (3.4.4) i {Rk } k =1 i с ограничениями (3.4.1-3.4.3) и Wk {Sic, t} Rk (3.4.5) "t : t Min Si1;

i { } (3.4.6) pi R k, Di pi*, 1 i n, 1 k d, 1 c mi.

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

Алгоритм решения задачи (3.4.4-3.4.6) будет изложен ниже. При этом, в целях упрощения, мы будем впредь полагать Min S i1 = 0.

3.4.4 Вспомогательная минимаксная задача (задача А) Рассмотрим постановку и решение вспомогательной задачи, исполь зуемой нами при решении обобщенной задачи (3.4.4-3.4.6). Примем, что количество наличных разработчиков Rk, 1 k d, заранее выделено систе ме управления аванпроектами и считается неизменным. Значения Rk удов летворяют ограничениям (3.4.1-3.4.2). Требуется построить расписание {S ic } случайных моментов начала выполнения всех операций {Oic } для всех аванпроектов с минимаксной целевой функцией { } p R k, Di - pi* (3.4.7) I1 = Max Min i pi* {S ic } i и с ограничением (3.4.5).

Решение задачи (3.4.5-3.4.7) основано на реализации имитационной модели, которая начинается в момент t = 0 и завершается в момент окон чания выполнения последнего проекта. Имитируются следующие проце дуры:

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

б) имитация продолжительностей выполнения операций и моментов завершения последних;

в) имитация возврата (после окончания операции) завершивших эту операцию разработчиков в группу свободных наличных ресурсов Rk (t ) ;

г) выявление новых операций, готовых к началу реализации;

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

Среди описанных выше наиболее важным представляется разработка, и имитация решающего правила: в момент времени t 0 распределить на личные ресурсы Rk (t ), 1 k d, между q операциями Oi c, Oi c,...,Oi c, гото 11 22 qq выми в момент t к началу выполнения.

Правило носит эвристический характер и состоит из этапов:

Этап 1. Для ожидающих обеспечения ресурсами операций определить вероятность выполнения соответствующих проектов в директивные сроки, при условии, что операция начнётся в момент t, и проект в дальнейшем не будет ожидать в очередях:

m i Di - t - ti r 1 r = c Pr {Fi1 Di1 } = Ф m i Vi1r r = c … (3.4.8) m iq Di - t - ti r q q r =cq Pr {Fiq Di q } = Ф mi q Viq r r =cq z x 1 где F (x ) = e dz.

2p Этап 2. Определить значения g i, 1 x q, по формуле { } x Pr Fix Dix - p * ix. (3.4.9) g ix = pi* x Этап 3. Перераспределить полученные значения g i, 1 x q, в порядке x увеличения полученных на этапе 2 значений g i. Нетрудно видеть, что чем x меньше величина g i, тем более срочный характер носит обеспечение соот x ветствующей операции ресурсами. Обозначим в новой индексации рассор тированные операции Oi f...O j f. 11 qq Стохастические Сетевые Модели Планирования и Управления Разработками Этап 4. Начиная с операции O j f, осуществляется выделение ресурсов для этой операции, т.е. имеет место проверка неравенств Rk (t ) r j f k, для всех 1 k d. Если имеет место Rk (t ) r j f k, выделяем операции просимые ресурсы, после чего оцениваем оставшиеся ресурсы Rk (t ) - r j f k ® Rk (t ), 1 k d, и переходим к операции O j f. Если хотя бы для одного k имеет место Rk (t ) r j f k, переходим к следующей операции O j f без выделения ре 11 сурсов операции O j f, и т.д. Процедура этапа завершается либо завершением всех операций, либо исчерпанием оставшихся наличных ресурсов Rk (t ).

Таким образом, процедура распределения ресурсов проста в действии и достаточно эффективна. Произведённые модельные расчёты [3.12] для ряда различных задач стохастического календарного планирования позво ляют использовать данную методику для практически любых комплексов произвольного объёма. В случае многократной реализации имитационной модели а) - д) мы в состоянии, на основе полученной представительной статистики, получить статистические оценки величин }{ } { pi R k, D i - pi* в целевой функции (3.4.7). Физический смысл вспо g i R k, Di = pi* могательной минимаксной задачи А следующий: в процессе принятия ре шений по распределению свободных ресурсов - разработчиков между ожидающими в очереди аванпроектами администрация РП прежде всего осуществляет помощь «отстающим» от своих директивных сроков проек там за счет более «сильных» проектов. В этом состоит основная идея ми нимаксного подхода, реализуемая в существенные моменты принятия ре шений: когда завершается очередная операция Oic и высвобождаются на личные ресурсы разработчиков либо когда очередная операция готова к выполнению, но простаивает из-за нехватки ресурсов. Минимаксную зада чу А следует использовать при управлении комплексом аванпроектов с одинаковыми приоритетами.

3.4.5 Вспомогательная задача с приоритетами (задача Б) [3.7-3.8, 3.12] Аналогично вспомогательной задаче А, общее количество наличных ресурсов - разработчиков Rk (t ), 1 k d, находящихся в распоряжении РП, принимается постоянным и задается заранее. Все реализуемые на РП аван проекты P i имеют различные степени важности (приоритеты) h i, 1 i n.

Требуется построить расписание {S ic } случайных моментов начала выпол нения операций {O jc } с целевой функцией [ }] { n I 2 = Max hi pi R k, Di (3.4.10) {S ic } i = Глава 3. Оптимальные задачи на современном разрабатывающем предприятии и с ограничением (3.4.5).

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

Подобно алгоритму решения задачи А, решение задачи Б основано на реализации имитационной модели, включающий подмодель распределения свободных наличных ресурсов Rk (t ) между готовыми к началу выполнения и ожидающими поступления ресурсов различными операциями аванпроек тов. Структура имитационной модели сходна с описанной выше моделью задачи А, за исключением решающего правила: на этапе 2 подмодели рас пределения ресурсов определяются значения g i, 1 x q, по формуле x g ix = Pr Fix Dix h ix.

На этапе 3 значения g i перераспределяются в порядке не увеличения, x а уменьшения;

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

В остальном структура и состав имитационной модели задачи Б по сравнению с моделью задачи А не претерпевают изменений.

3.4.6 Вспомогательная задача с минимизацией общего срока реа лизации аванпроектов (задача В) Аналогично описанным ранее двум вспомогательным задачам А и Б, значения Rk (t ), 1 k d, фиксированы и неизменны. Все аванпроекты име ют одинаковые приоритеты. Требуется построить расписание {S ic } момен тов начала выполнения операций {Oic } с целевой функцией (3.4.12) I 3 = min E max i - min i {S ic } Fi S il и с ограничением (3.4.5). Здесь E - символ математического ожидания.

Подобно задачам А и Б, решение задачи (3.4.5, 3.4.12) основано на реализации имитационной модели В со структурой, в принципе аналогич ной структурам моделей А и Б. Различие состоит в подмодели принятия решений для распределения наличных свободных ресурсов между ожи дающими ресурсов аванпроектами. Мы предлагаем [3.7-3.8, 3.12] осущест вить выбор операции для первоочередного снабжения ресурсами на основе критериев LRT либо SPT, успешно реализуемых в календарном планиро вании [3.10].

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

Иными словами, на этапе 2 подмодели распределения ресурсов осу ществляется определение значений g i, 1 x q, по формуле x mi t. (3.4.13) g ix = ix r r = cx На этапе 3 значения g i перераспределяются в порядке уменьшения.

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

Отметим, что в процессе реализации имитационной модели В инфор мация по директивным срокам окончания аванпроектов Di, доверительным вероятностям Pi * и значениям приоритетов h i не используется.

3.4.7 Решение оптимизационной задачи (3.4.3-3.4.6) (прямая зада ча) [3.7-3.8, 3.12] Алгоритм решения задачи (3.4.3-3.4.6) включает два иерархических уровня. На верхнем уровне осуществляется поиск оптимальных значений Rk, 1 k d, на основе метода покоординатной оптимизации [3.11], хорошо зарекомендовавшего себя в ряде оптимальных задач сетевого планирова ния [3.9-3.12]. Этот метод позволяет оптимизировать нелинейные системы высокой степени сложности: с большим числом связей и большим количе ством оптимизируемых переменных. Речь идет о системах, для которых использование других методов оптимизации (например, градиентного ме тода) представляется затрудненным. На нижнем иерархическом уровне ра ботает имитационная модель решения задачи А.

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

Этап 1. В качестве исходных значений Rk, 1 k d, т.е. начальной точки поиска, примем заведомо завышенные величины (например, Rk max ), обеспечивающие для всех аванпроектов P i получение доверительных ве роятностей pi R k, Di с заведомо превышающим pi* значениями. Значения pi R k, Di определяются путем многократной реализации имитационной модели задачи А, в соответствии с содержанием последующего этапа алго ритма. Отметим, что в процессе поиска оптимального набора {Rk } все век тор-точки поиска Rk (включая начальную точку поиска) подаются на вход имитационной модели.

Глава 3. Оптимальные задачи на современном разрабатывающем предприятии Если хотя бы для одного i, 1 i n, имеет место pi R k, Di pi*, это означает, что оптимизационная задача (3.4.4-3.4.6) не имеет решения, неза висимо от значений мощности ресурсов Rk. Примем, что для всех i имеет место pi R k, Di p i*, 1 i n, то есть начальная точка поиска представляет допустимое решение.

Этап 2. Фиксируем полученные на этапе 1 величины R1, R2,..., Rd. На чинаем последовательно уменьшать величину R1 на шаг DR1, оставляя зна чения R2,..., Rd неизменными. Для каждого очередного значения R1 много кратно реализуется имитационная модель, после чего осуществляется про верка истинности следующих соотношений:

- значение целевой функции (3.4.4) уменьшается в соответствии с по становкой задачи, - ограничения (3.4.6) соблюдаются.

В целях одновременной проверки обоих соотношений предлагается следующее:

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

б) на основе осуществления M прогонов ( M ~5001000) вычисляется эмпирическое значение модифицированной целевой функции по формуле 1 M * 1 d n M J1 = ( S k R k ) F ( m ) + K i d ( a ( F * (m) (3.4.14) - Di ) - pi ), i M m =1 M k =1 i =1 m = 1, если x где a (x ) =, 0, если x F (m ) - момент завершения последнего из аванпроектов в m -м имита ционном прогоне, 1 m M ;

( m) Fi - момент завершения i -го аванпроекта в m -м имитационном про гоне, Ki - весьма большое число (обычно порядка 1017 ), используемое для искусственного, практически безграничного увеличения периода функ ционирования системы в случае невыполнения, хотя бы для одного аван проекта, ограничений (3.4.6).

Таким образом, требования к монотонному снижению значения J1* на основе (3.4.14) обеспечивает выполнение условий (3.4.6) и одновременное снижение целевой функции (3.4.4).

Заметим, что в формуле (3.4.14) мы полагаем min S i1 = 0.

i Этап 3. В процессе последовательного уменьшения первой координа ты R1 на DR1 осуществляется проверка монотонности уменьшения величи Стохастические Сетевые Модели Планирования и Управления Разработками ны J1*, до тех пор, пока такое уменьшение не прекратится. В последнем случае значение R1, соответствующее минимуму J1*, фиксируется, после чего начинается последовательное уменьшение второй координаты R2 на шаг DR2. При этом координаты R1, R3, R4,..., Rd фиксированы и не меняются.

В дальнейшем осуществляется уменьшение третьей координаты R3 ( с не изменным фиксированным значением уже скорректированных R1 и R2 и еще не измененных значений R4,..., Rd ), и т.д., вплоть до последней коорди наты Rd.

В процессе изменения d -мерной точки поиска {Rk } очередной шаг по иска считается удачным, если значение J1* уменьшилось. В противном случае координата Rk фиксируется, после чего переходят к последующей, (k + 1) -й, координате Rk +1.

Этап 4. После реализации очередной итерации (получения нового на бора значений Rk, 1 k d ) фиксируется значение J 1( v ), где n означает по рядковый номер итерации. Значения всех шагов поиска DRk уменьшаются вдвое, после чего переходят к реализации последней итерации.

Этап 5. Вторая и последующие итерации отличается от первой итера ции тем, что для каждой из координат Rk, 1 k d, процесс покоординат ной оптимизации осуществляется в обоих направлениях: Rk - DRk и Rk + DRk. При этом выбирается то направление, которое обеспечивает наи большее уменьшение целевой функции J1*. Процесс поиска продолжается в этом направлении до прекращения уменьшения величины J1*.

Этап 6. В процессе реализации не менее двух последовательных ите раций J 1( v ) и J 1( v +1) происходит расчет оценки погрешности сходимости по иска по формуле J 1(v ) - J 1(v +1) D(V ) =. (3.4.15) J 1(v ) Если имеет место D(n ) e, работа алгоритма заканчивается, а значение ( v + 1) фиксируется в качестве оптимального значения целевой функции J (3.4.4). Набор соответствующих координат {Rk }, полученный в заключи тельной, (n + 1) -й, итерации, принимается в качестве решения оптимальной задачи (3.4.3-3.4.6).

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

Глава 3. Оптимальные задачи на современном разрабатывающем предприятии 3.4.8 Прямая оптимизационная задача с минимизацией общей продолжительности выполнения аванпроектов Рассматриваемая ниже задача является модификацией задачи (3.4.3 3.4.6) и имеет следующий вид [3.7-3.8, 3.12]:

Требуется определить значения суммарных ресурсов Rk, 1 k d, (за ранее, до начала хода работ по выполнению аванпроектов) и случайные моменты S ic начала выполнения операций Oic (в процессе реализации аванпроектов) с целевой функцией (3.4.4) и ограничениями (3.4.3, 3.4.5).

По сравнению с задачей (3.4.3-3.4.6) настоящая задача носит упрощенный характер, поскольку она не учитывает значений Di и pi*, 1 i n. Задача (3.4.3-3.4.5) обычно носит вспомогательный характер и будет использована нами ниже, в процессе решения обратной оптимизационной задачи с при оритетами.

Алгоритм решения задачи (3.4.3-3.4.5) включает два иерархических уровня.

На верхнем уровне осуществляется покоординатная оптимизация зна чений Rk. На нижнем уровне работает описанная выше задача В, включая основной блок задачи - имитационную модель В. Ввиду отсутствия огра ничений (3.4.6) целевая функция (3.4.4) не нуждается в модификации (3.4.14) и носит следующий упрощенный характер d M J 2 = ( S k R k ) ( F * (3.4.16) (m) ), M k =1 m = где M - количество имитационных прогонов, а m - порядковый номер прогона.

В качестве решающего правила в имитационной модели В рекоменду ется использовать правило LRT, которое более эффективно, нежели прави ло SPT [3.10-3.12].

3.4.9 Обратная оптимизационная задача с приоритетами [3.12] Рассматриваемая задача носит наиболее сложный характер и является обратной задачей относительно прямой задачи (3.4.3-3.4.6). Каждый из входящих в комплекс проектов P i, 1 i n, имеет директивный срок своего окончания Di, доверительную вероятность завершения работ по проекту в срок pi, а также приоритетный показатель h i. Каждый из проектов состоит из цепочки операций Oic, 1 c mi. Определить детерминированные значе ния Rk, 1 k d, (до начала работ) и случайные моменты S ic (в процессе выполнения проектов), максимизирующие целевую функцию [ }] { n J 3 = Max Max h i pi R k, Di (3.4.17) {R k } {Sci } i = с ограничениями (3.4.3, 3.4.5) и Стохастические Сетевые Модели Планирования и Управления Разработками [( )] d E sk R k Max Fi - Min Si1 C j, (3.4.18) k =1 i i где C - заранее заданное ограничение по объёму финансирования ресурсов - разработчиков Rk, а E - символ математического ожидания.

Сложность решения задачи (3.4.3, 3.4.5, 3.4.17-3.4.18) состоит, глав ным образом, в трудоёмкости определения начальной точки поиска {Rk } в пространстве оптимизируемых переменных.

Разработан следующий поэтапный эвристический алгоритм [3.12].



Pages:     | 1 |   ...   | 2 | 3 || 5 | 6 |   ...   | 8 |
 





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

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