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

t£-°=4, t™ = 0 .

Теперь по формуле (4.7) определим полные резервы времени работ:

Д£1= £ п.о_£Р.н_ £ 1==0_ 0 _ 0 = 0 ,

M2= t ™ —q-H—t2= 4 —о —1=3,

Д^ю—0, Д£ц—0, Afj2—0.

Полные резервы времени Att для критических работ, как известно, равны нулю, что подтверждается и нашими рас­ четами.

Как уже указывалось, продолжительность некритиче­ ской работы можно увеличить на полный резерв времени Д£г. Однако продолжительность выполнения каждой рабо­ ты, согласно формуле (4.3), ограничена сверху величиной Di. Таким образом, временную оценку i-й работы можно увеличить только в пределах dt и , т. е. + А Тогда фактическое значение отрезка времени 6tt выразит­ ся формулой

Найдем значения 6tt для нашего примера. Величины Dt возьмем из таблицы 4.1, Att уже известны, а продолжителы ность ?£ указана в квадратах возле вершин графа G](X, V)

(рис. 4.2):

6?i=m in{D i — 1\; A £i}=m in{0 — 0; 0} = 0 ,

6f2= min{Z)2— 12; A?2}= m in { 2 — 1; 3} = 1.

Аналогично получаем:

6?з— 0, 6t4— 3, 6^5— 2, '6tf> = 0, 6?7=2, 6^8— 1)

— 0, б?ю— 0, б£ц— 0, б?12= 0.

Чтобы выбрать работу, продолжительность которой нуж­ но увеличить на btt, рассмотрим коэффициенты аг. Как сле­ дует из выражения (4.1), at означает величину, на которую уменьшается объем ресурсов, когда продолжительность ра­ боты i возрастает на единицу. Следовательно, чтобы снизить общий объем используемых ресурсов, следует увеличить продолжительность той работы, которая имеет максималь­

80

ное значение коэффициента at. С помощью данных таблицы 4.1 находим тах(а^) = а3= 5. Но работа £ = 3 является кри­ тической и 66 = 0, поэтому выбираем работу со следующим максимальным значением at. В качестве такой работы мож­

лась. Длина критического пути осталась прежней: Ткр = 1 9 . Полученный граф обозначим через G + X , V).

Для работ графа G\{{X, V) снова определяем фактиче­ ский резерв времени б*£. При этом предварительно по фор­ мулам (4.8) и (4.9) находим полные резервы времени работ A*г. Проведя все вычисления, как показано выше, имеем:

66 = 0, 66 = 0, 6*з= 0, 6*4= 3, 6*5=2, 6*6= 0, 6*7=2,

6*8=1, 6*9= 0, 6*10= 0, 6*11 = 0, 6*12 = 0.

и 6 *£, а затем увеличиваем продолжительность работы £ = = 4 на величину 6*4= 2. Тогда суммарный объем ресурсов, используемых на весь проект, принимает вид

Z ^ = Z ^ —Дг4=101 —2*3=95.

С учетом найденного значения продолжительности работы £ = 4 *4= 5 + 3 = 8 и продолжительностей работ £ = 2 и £ = 5 снова определяем фактические резервы времени 6 6 . Они равны нулю для всех работ. Это означает, что нет работы, обладающей резервом времени.

При использовании резервов времени потребление ресур­ сов можно довести до общего уровня До» т. е .

В этом случае rpacJjG^CX, V) будет искомым и действия ал­ горитма закончатся. В противном случае(Z {u>>Ro) выполня­

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

На первой итерации на шаге 3 получаем граф Gl(X, V) (рис. 4.2). На последующих итерациях имеем графы G2(X, V),. .. , Gk (X, V), где k — номер соответствующей ите­ рации (& = 1, 2, . . .).

Как уже отмечалось, критическими на графе Gl(X, V)

ку работы i= 3 увеличим на фиксированную величину Ah, значение которой задано предварительно. Пусть в нашем примере А/г= 1, тогда временная оценка работы г = 3 выра­ зится так: £3+ Д /г=3-{-1 = 4. Временные оценки всех осталь­ ных работ остаются равными dit а £3+Д/г — 3 + 1 = 4.

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

где тi — количество изменений временной оценки рассмат­ риваемой работы. Очевидно, должно быть соблюдено условие

Если mi = 0 , то по формуле (4.12)

82

Далее переходим к шагу 3 второй итерации.

Шаг 3. Применяя алгоритм В к исходному графу с но­ выми значениями (4.15), получим граф G 2(Xt F), топология которого совпадает с топологией графа на рисунке 4.2. Вы­

Длина критического пути 1->3->-6->9-^10->-11->12 равна Ткр = 2 0 . Так как условие (4.6) для работ графа G2(X, V) не выполняется (Z(2) = 1 0 6 > Л о = 6 0 ), то переходим к следую­ щему шагу.

Шаг 4. Для всех работ графа G2(X, V) по формулам (4.7)— (4.10) определяем ранние начала работ £?-н , позднее окон­

чание £Р*°, полные резервы времени АЦ и фактические ре­ зервы времени бtt. Эти величины записываем в таблицу 4.2.

Используем резервы времени 6tt прежде всего на некри­ тических работах, у которых коэффициент а* максимален.

83

В нашем случае такой работой является i= 2, так как Пг= 4 будет максимальным среди а*. Заметим, что максимальное at выбирается только для тех работ, у которых резерв вре­ мени не равен нулю, т. е. 6^ > 0 . Увеличив продолжитель­ ность работы i= 2 на 8*2= 1 , тем самым уменьшим общий объем потребляемых ресурсов на Дг2= а2-6*2 = 4-1 = 4, т. е.

Z (2)==Z(2)__дг2=106—4—102.

Продолжительность работы i= 2 станет равной *2+ 8*2= = 1 + 1 = 2. При этом топология графа не изменится, воз­ растет лишь продолжительность одной из работ на величи­ ну 6*г. Полученный граф обозначим через G 2{X, V) и для него снова вычислим фактические резервы времени работ: 8*5= 2, 6*4= 3 , 8*8= 1, 8*7 = 2. Фактические резервы време­ ни остальных работ нулевые. Увеличим продолжительность работы i= 5, так как а^= Ъ максимален. Отсюда имеем:

*5+.8*5 = 2 + 2 = 4,

Лг5= а5•8*5 = 3 •2 = 6,

Z {22)= —Дг5—-102—6=96.

После внесения изменений *5= 2 + 2 = 4 в граф G^\X, V) получаем граф G22(X, V). Вновь найденные фактические ре­

После корректировки *4= 5 + 3 = 8 имеем граф G\(X ,V), то­

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

фа G3(Х, V): 8*8= 1, 8*7 = 2. Использовав фактический ре­ зерв 8*8= 1 , получим

*8+ 6*8= 3 + 1 = 4 ,

А г 8 = а 8 * б * 8 = 2 - 1 = 2 ,

Z \2)= Z^2)—Дг8= 9 0 —2=88.

84

С учетом t8= 3+6£g = 3 + 1 = 4 формируем граф G(2\X, V).

Фактические резервы времени работ этого графа равны ну­ лю. Проверим условие (4.11): £^2)= 8 8 >»До = 60. Это условие

не выполняется, поэтому переходим к шагу 5.

Шаг 5. Рассмотрим критические работы на графе

было равно верхней границе П3(£3=1)з = 4). Поэтому увели­ чиваем продолжительность другой критической работы (i = = 6), у которой коэффициент аь имеет наибольшее значение

ны в таблице 4.3, где приняты следующие обозначения: кон­ тур I включает работы 3 и 4— для них установлен порядок сле­ дования 3-^-4; для работ контура II выбран порядок 8-»-9->-

-> 7 ; Z(k)— объем ресурсов на работах графов Gk (X , V) (k =

85