Файл: Цой, С. Синтез оптимальных сетей в системе управления горными предприятиями.pdf
ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 21.10.2024
Просмотров: 119
Скачиваний: 0
течение двух дней работы 2 и 3 будут выполняться с посто янной интенсивностью: г2= р2= 3 и гз = р 3= 5.
Таким образом, продолжительность первого фронта бу дет равна 0 = 02 = 2 .
Шаг 7. Определение объема и продолжительности остав шейся части работ. Объем работ фронта F(t), производимых с интенсивностью г* >» 0 в течение промежутка времени 0 , составляет гг»0 . Тогда объем оставшейся части работ рас считывается по формуле
(5.16)
где Vt — объем работы i перед началом фронта.
Вычислим продолжительность оставшейся части работ с учетом максимальной интенсивности использования ресур сов:
(5.17)
Если значение £/ = О (V / = 0 ), то это означает, что данная работа полностью завершена и в дальнейших итерациях нр рассматривается.
В исходном графе (рис. 5.1) с полными контурами вер шину i (работа i) вместе с выходящими из нее дугами уда
ляем. Пусть имеем оставшийся объем V / |
работы i, |
равный |
|||||
У /= 5 . Для выполнения данного объема |
может быть при |
||||||
нята максимальная |
интенсивность |
расходования ресурсов |
|||||
в единицу времени рг = |
8. Следовательно, объем |
работы |
|||||
Vi' — 5 будет произведен менее чем за единицу времени. |
|||||||
Другими словами, для завершения работы i в единицу |
|||||||
времени достаточно |
выделить интенсивность |
р* = |
У ^ = 5 . |
||||
Неиспользованная |
интенсивность, |
равная 3 = |
8— 5, может |
||||
быть направлена для выполнения других работ. |
|
|
|||||
Определим для нашего примера оставшиеся объемы для |
|||||||
работ 2 и 3 и их продолжительность: |
|
|
|
|
|
||
T V = ^ 2—r2- e = 6 —3 -2=0, |
|
Г2 = О, |
|
||||
V 3'= V 3—r3-e = 2 0 —5-2=10, f3'= |
Ь .'= Щ-=2. |
|
|||||
Значения У2 и У3 даны в таблице 5.1. |
полностью заверше |
||||||
Как видно из расчетов, работа г = 2 |
|||||||
на, т. е. v y = 0 , t2 = 0 . |
Следовательно, |
эта работа должна |
|||||
быть исключена из дальнейшего рассмотрения.
Внеся изменения для работ 1, 2 и 3 в таблицу 5.1, полу чим новую таблицу (5.2), данные которой послужат в каче
стве исходных для второй итерации. Условимся в таблицах оставшиеся объемы и продолжительность работ обозначать соответственно через У* и
Описанными действиями заканчивается шаг 7, который будет завершающим для одной итерации.
Результатом выполнения любой очередной итерации яв ляется набор следующих параметров для работ фронта F(t): 0, i, rit Будем фиксировать эти данные в таблице 5.3, каждый раз дополняя ее новыми результатами.
i Vi
Таблица 5.2 Таблица 5.3
Pi |
% |
\ |
e |
|
01=2 |
n |
|
||||
|
|
i |
n. |
Vi |
3 |
10 |
5 |
2 |
|
|
|
|
4 |
56 |
7 |
8 |
1 |
0 |
0 |
|
5 |
20 |
5 |
4 |
||||
2 |
3 |
6 |
|||||
6 |
72 |
8 |
9 |
3 |
5 |
10 |
|
7 |
4 |
4 |
1 |
|
|
|
|
8 |
12 |
3 |
4 |
В этой таблице приведены ре |
|||
9 |
18 |
6 |
3 |
||||
10 |
70 |
7 |
10 |
зультаты, полученные на пер |
|||
11 |
56 |
8 |
7 |
вом фронте. |
За промежуток |
||
12 |
0 |
0 |
0 |
||||
|
|
|
|
времени @i = |
2 для работ i = 2 , |
||
|
|
|
|
3 были произведены |
объемы |
||
работ |
V2==т*2•0 i==6 и V3 = r3-0 1 = 10. |
Продолжительность |
||
фронта 01 необходима для нахождения |
уровня |
ресурсов |
||
B(tk) |
на следующей итерации. Начальный момент времени |
|||
tjt для очередного фронта определим как сумму |
продолжи |
|||
тельностей предшествующих фронтов: |
|
|
||
|
tk ~ 0 o+ 0 r |
•+е*_1>: |
(5.18) |
|
где 0 S — продолжительность фронта работ для итерации s. В случае Vt = 0 (i-я работа полно стью закончена) ис ходный граф с пол ными контурами преобразуем удале нием из него вер шин, соответствую щих завершенным работам. Одновре менно в графе вы черкиваем и дуги, выходящие из уда
вленных вершин. Полученный таким образом граф Gi(X, U)
100
после первой итерации представлен на рисунке 5.5, и он бу дет исходным для следующей итерации. На графе введена новая фиктивная вершина — миноранта го с нулевыми оцен ками.
Располагая данными таблицы 5.2, переходим ко второй итерации.
Итерация 2
Шаг 1. Граф с полными контурами Gi(X, U) (рис. 5.5) яв ляется исходным. В результате выполнения шага 1 получа ем сетевой граф G{X2, U2) без контуров (рис. 5.6). Для работ этого графа по алго ритму В находим
ранние начала:
|
|
|
Ц‘" = Цл = 0, *Р.н= . |
|
|
|
|
= 2, |
£рн=14, *£■» = |
|
|
а |
= 4, *9Р-Н=11, J£H= |
|
И |
И |
® =14, |
fJiH=24, t\f = |
|
Рис. |
5.6. |
|
|
=31. |
Шаг 2. На основе значений |
tР-н, |
tio и р ; |
(табл. 5 .2 ) по |
|
строим временную диаграмму D2 (рис. 5.7) и график Г2 из-
161
менения суммарной интенсивности потребления ресурсов (рис. 5.8). Анализ графика Г2 показывает, что суммарные потребности в ресурсах на отрезках 2 ^Г£гс:1 0 и 1 4 ^ £ ^15 превышают Я(£) = 1 0 , поэтому переходим к шагу 3 .
Шаг 3. Находим фронт работ F(t). Из диаграммы D2 (рис.
5.7) видно, что во фронт входят работы i= 3 и i = 5, так как
*гл=*г=о-
Шаг 4. Вычислим резервы времени работ фронта по фор муле (5.7). Для этого на графе G(X2, U2) (рис. 5.6) определя ем значения длин всех путей L * от рассматриваемой вер шины до мажоранты и L;*=m ax{Z,/*}. Величины t { и £ / бе
рем из таблицы (5.2) и имеем: Д£з= 0, Д£б= 3.
Шаг 5. Так как резервы времени работ 3 и 5 разные и
Д£з<А£5» то работа 3 образует группу П\, а работа 5 входит
вгруппу П2.
Распределим интенсивности использования ресурсов в единицу времени по работам фронта. Проверим выполнение
условия (5.8 )для работ группы П\: р3= |
5 *<#(£) = |
10, поэто |
|||
му гз=рз = 5. Вычислим остаток R l(t) |
по |
формуле (5.9): |
|||
i?‘(£)=i?(£)— гз= 10— 5 = 5. |
Относительно |
этого |
остатка |
||
анализируем условие (5.12) для работ группы П2: |
p^^LR'it) |
||||
или p5= 5 = .R 1(£) = i). |
Следовательно, условие (5.12) соблю |
||||
дается, поэтому для работы i= 5 выбираем |
интенсивность |
||||
П> = Рб= 5 . |
продолжительность |
фронта. Ввиду |
|||
Шаг 6. Определим |
|||||
того, что для работ i= |
3 и i= |
5 групп 771 и П2 выделены мак- |
|||
102
симальные интенсивности, 0 3 = 0 4 = 00. Вычислим o i: ai =
=z k — f2= 00— 2 = oo. Значение 02 равно:
a9= m in |
KL = min{—3; -H5) = min 10 |
20_ |
iGF(t) |
r 3 Гь |
5 |
=m in{2; 4} = 2 .
Тогда продолжительность фронта
@= min{ai, 02, аз, 04} = m in {oo, 2 , 00, 00} = 2 .
Шаг 7. Находим объемы
ипродолжительность ос
тавшейся |
части |
работ |
(табл. 5.4). |
В таблице 5.5 |
|
даны параметры тех работ, которые выполнялись на первой и второй итераци ях.
По формуле (5.18) вычис лим момент начала фронта на третьей итерации:
|
|
|
Таблица 5.4 |
i |
Vi |
Pi |
tio |
4 |
56 |
7 |
8 |
5 |
10 |
5 |
2 |
6 |
72 |
8 |
9 |
7 |
4 |
4 |
1 |
8 |
12 |
3 |
4 |
9 |
18 |
6 |
3 |
10 |
70 |
7 |
10 |
11 |
56 |
8 |
7 |
12 |
0 |
0 |
0 |
£3— ©о |
+®1 + ©2— 0+ 2+ 2 — 4. |
В таблице 5.5 |
работа г = 3 приведена дважды, так как |
она выполнялась на двух фронтах и завершилась на второй итерации.
|
|
|
|
Таблица 5.5 |
|
0x== 2 |
|
|
®2= 2 |
|
0 |
|
|
|
i |
n |
Vt |
n |
Vi |
1 |
0 |
0 |
|
|
2 |
3 |
6 |
— |
— |
3 |
5 |
10 |
5 |
10 |
5 |
|
— |
5 |
10 |
Имеем новый исходный граф G2 (X, U) для третьей итера ции (рис. 5.9) после удаления на графе с полными контура ми (рис. 5.5) вершины i = 3 (работа 3) с выходящими из нее дугами.
103