Файл: Цой, С. Синтез оптимальных сетей в системе управления горными предприятиями.pdf

(4.4), на каждую работу в этом случае будет направлено

—aiDi ресурсов. Значения г*, min приведены в таб­

лице 4.1.

Рис. 4.1.

Суммарный объем ресурсов на весь проект определяется выражением

12

£ < °)= 2 rf,min= 55. i=i

Эта величина является нижней границей потребности в ре­ сурсах для данного проекта. Следовательно, для завершения рассматриваемого комплекса работ необходимо, чтобы за­ пасы ресурсов Ro удовлетворяли условию Z (0)^i?o- Тогда задача имеет решение, в противном случае нужно увеличить запасы ограниченных ресурсов до величины Z (0). Все последу­

76

ющие шаги осуществляются при соблюдении этого условия.

В нашем случае Z (Q)=bb<iRQ==Q0.

Шаги 1 и 2 подготовительные. Они выполняются только один раз в начале алгоритма. Итерационный процесс начи­ нается с шага 3.

Шаг 3. Полагаем временные оценки tt для всех pa6oi i графа G(X, U) (рис. 4.1) равными нижней границе ti, min=

—dt (табл. 4.1). К полученному графу применяем алгоритм

В— алгоритм построения оптимального сетевого графа. В результате синтезируется графбг1 (X , V), представленный на

рисунке 4.2. Значения ti,min= d i указаны в квадратах воз­

4.1 и формулы (4.1) легко подсчитать объем потребляемых ресурсов на всех работах проекта:

В противном случае переходим к следующему шагу. Так как Z (1) = 1 1 1 60, то выполняем шаг 4.

Шаг 4. Вычисление резервов времени работ и пересчет ресурсов. Действиями шага 4 попытаемся уменьшить объем используемых ресурсов Z1. Чтобы сократить объем ресурсов на некоторой работе, согласно формуле (4.1), необходимо

77

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

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

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

k, из которых выходят дуги, оканчивающиеся в вершине г. В вершинах k должны быть известны значения Ц-Нл Ран­

нее начало работы i = i o = l полагаем равным нулю. Позднее окончание tp-° находим по формуле

(4.9)

78

Для вычисления tf-° по этой формуле необходимо, чтобы величины *у*° в вершинах j, где оканчиваются дуги, выхо­

дящие из i, были уже определены. Позднее окончание по­ следней работы проекта — мажоранты считаем равным !ГКр.

Рассчитаем *Р-Н и Щ‘° для работ, представленных на

графе Gl(X, V) (рис. 4.2). Найдем сначала ранние начала ра­ бот по формуле (4.8), согласно которой раннее начало работы io= l — миноранты — принимается равным нулю. Зная эту величину, определяем ранние начала работ 2 и 3:

fP.H= *P.H_j_Ji==()-M )=0,

*з=*Гн+ * 1 = 0 + 0 = 0 .

На основе этих расчетов вычислим

£P*H=max{£P-H-H 2; ^•H+ ? 3}= n ia x {0 + l; 0 + 3 }= 3 .

По формуле (4.9) находим поздние окончания работ на гра­

можно рассчитать поздние окончания всех остальных работ:

^11°=^Г2°—*12=3 9—0—19,

*5-°—t?!0—tii= i9 —5—14*

t£-o=*”-°—*n= 1 9 —5=14.

Позднее окончание работы г = 8 пока нельзя определить, так как неизвестно позднее окончание работы г = 9:

*£-°=min{*™—*t0; f?'°—M =m in{14—3; 14—1}=11.

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

79