Файл: Учебное пособие Издательство Нижневартовского государственного гуманитарного университета 2008.pdf

100 1
2 3
4
Полный резерв времени выполне-
ния работы TF(i,
j) определяется как разность между поздним временем наступления события (j), ранним вре- менем наступления события
(i) и продолжительности работы t(i, j)
TF(i,
j)
Time Free
R
П
( )
( )
( , ).
П
П
Р
R
T
j
T i
t i j



Свободный резерв времени вы-
полнения работы FF(i,
j) определя- ется как разность между ранними временами наступления событий (j) и
(i) и продолжительностью работы t(i,
j)
FF(i,
j)
Free Full
RС(i, j)
( , )
( )
( )
( , ).
C
Р
Р
R i j
T
j
T i
t i j



Независимый резерв времени вы-
полнения работы IF(i) определяется как разность между ранним време- нем наступления события (j), позд- ним временем наступления события
(i) и продолжительностью работы t(i,
j)
IF(i)
Independ-
ence Free
RН(i)
( )
( )
( )
( , ).
Н
Р
П
R
i
T
j
T i
t i j



Продолжительность критического
пути это самый продолжительный из всех полных путей сетевой модели.
Продолжительность критического пути равна сумме продолжительно- стей всех работ, составляющих этот путь
TK
Тк
1
( , ).
j
К
i
Т
t i j



5.3.1. Сетевые модели
Наиболее распространены сетевые модели в которых события изображаются окруж- ностями, разбитыми на четыре равных сектора (диаметрами, расположенными под 90 0
)
(рис. 5.1). Значения временных параметров записываются прямо в вершины на сетевом графике следующим образом: i – индекс события;
Т
р
(i) – ранний срок наступления события (i). Это время, необходимое для выполнения самой длительной из всех работ, предшествующих данному событию;
T
n
(i) – поздний срок наступления события. Это время, превышение которого вызовет задержку всех последующих событий сети;
R(i) – полный резерв времени наступления события i.
Рис. 5.1. Узел сети
Ri
Tp(i)
Tn(i)
i

101
Табличная форма сетевой модели задается множеством {A, A(IP)}, где А – это мно- жество индексов работ, а A(IP) множество комбинаций работ, непосредственно предше- ствующих работе А (табл. 5.2).
Таблица 5.2
Табличная форма сетевой модели
{A}
{A(IP)}
A
—
B
—
C
A
D
A
E
B
F
C
G
C, D
J
E, F
Матричная форма описания сетевой модели задается в виде отношения между собы- тиями (e i
, e j
), которое равно 1, если между этими событиями есть работа (либо реальная, либо фиктивная) и 0 – в противном случае (табл. 5.3).
Таблица 5.3
Матричная форма сетевой модели
События
1
2
3
4
5
6
7
1
1 1
2
1 1
3
1 1
1
4
1 1
1
5
1 1
1
6
1 1
1
7
1 1
Временная диаграмма (график Гантта, «ленточная диаграмма») для описания сете- вой модели предполагает размещение работ в координатной системе, где по оси абсцисс
(X) откладывается время (t), а по оси ординат (Y) – работы. Точкой начала отсчета любой из работ будет момент окончания всех ее предшествующих работ. Если работе не пред- шествует ничто, то она откладывается от начала временной шкалы, т.е. с самого левого края диаграммы (рис. 5.2). Иногда на диаграмму добавляют информацию о продолжи- тельности выполнения работ или ресурсах рабочей силы.
Рис. 5.2. Диаграмма Гантта

102
Рассмотренные сетевые модели позволяют проводить:
1) расчет временных параметров событий;
2) строить графики привязки;
3) оптимизировать использование рабочей силы;
4) оптимизировать модель по критерию «затраты – время»;
5) сглаживать потребности в ресурсах.
5.4. Календарное планирование
Применение методов СПУ обеспечивает получение календарного плана, определяю- щего сроки начала и окончания каждой операции. Построение сети является лишь пер- вым шагом на пути к достижению этой цели. Вторым шагом является расчет сетевой мо- дели, который выполняют прямо на сетевом графике, пользуясь простыми правилами:
1) начало и окончание любой работы описываются па- рой событий, которые называются начальным и ко-
нечным событиями. Поэтому для идентификации конкретной работы (рис. 5.3) используют код работы
(i, j), состоящий из номеров начального (i-го) и конеч- ного (j-го) событий, например (2,4); (3,8); (9,10);
Рис. 5.3. Идентификация работ
2) взаимосвязь работ и событий изображаются стрел- ками, которые соединяют вершины, изображающие события. Работы, выходящие из некоторого события не могут начаться, пока не будут завершены все опера- ции, входящие в это событие (рис. 5.4);
Рис. 5.4. Взаимосвязь работ
3) длина стрелки не зависит от времени выполнения работы (рис. 5.5);
Рис. 5.5. Длительность работ и длина стрелок
4) стрелка не обязательно должна представлять пря- молинейный отрезок (рис. 5.6);
Рис. 5.6. Представление взаимосвязи работ криволинейными стрелками

103 5) для действительных работ используются сплошные стрелки, для фиктивных пунктирные (рис. 5.7);
Рис. 5.7. Действительные и фиктивные работы
6) операция представляется только одной стрелкой, между одними и теми же событиями не должно быть параллельных работ, для исключения такой ситуации используют фиктивные работы (рис. 5.8);
Рис. 5.8. Исключение параллельных событий
7) следует избегать пересечения стрелок и стрелок, направленных справа налево (рис. 5.9);
Рис. 5.9. Направление и пересечение стрелок
8) не должно быть циклов (рис. 5.10);
Рис. 5.10. Запрет циклов
9) не должно быть висячих и тупиковых событий, кро- ме исходного и завершающего (рис. 5.11).
Рис. 5.11. Запрет висячих и тупиковых событий

104
5.4.1. Пример построения сетевого графика
Пусть необходимо спроектировать, изготовить и сдать в эксплуатацию стенд согласно техническому заданию (табл. 5.4).
Таблица 5.4
Перечень работ по проектированию,
изготовлению и сдаче в эксплуатацию стенда
№
Содержание работ
Предше- ствующая
Парал- лельная
Последова- тельная
Длитель- ность
А
Разработка технических усло- вий на стенд. [(i,
j) – (1,2)]
—
—
—
5
В
Общая компоновка стенда.
[(i,
j) – (2,3)]
А
С
D
5
С
Разработка и выдача ТЗ на со- ставление рабочей документа- ции по эксплуатации стенда.
[(i,
j) – (2,8)]
A
B,D,E,F,H,G,I
—
3
D
Разработка технологии изго- товления электрической части стенда. [(i,
j) – (3,4)]
B
E,F
—
8
E
Разработка технологии изго- товления механической части стенда. [(i,
j) – (3,5)]
B
D,F
—
6
F
Оформление и размещение за- казов на покупные изделия, не- обходимые для сборки стенда.
[(i,
j) – (3,6)]
B
D,E
—
10
G
Изготовление электрической части стенда. [(i,
j) – (4,7)]
D
H,J
—
25
H
Изготовление механической части стенда. [(i,
j) – (5,7)]
E
G,I
—
18
I
Выполнение заказов на покуп- ные изделия. [(i,
j) – (6,7)]
F
G,H
—
15
J
Передача информации о харак- теристиках стенда для разра- ботки рабочей документации по эксплуатации стенда.
[(i,
j) – (7,8)]
G,H,I
K
—
0
K Сборка стенда. [(i,
j) – (7,9)]
G,H,I
J,L
—
12
L
Разработка рабочей документа- ции по эксплуатации стенда.
[(i,
j) – (8,9)]
J
K
—
12
M
Контрольные испытания стен- да. [(i,
j) – (9,10)]
L,K
—
—
10
Кроме того, известно, что:
1) информация о характеристиках стенда может быть получена после получения по- купных элементов в процессе создания электрической и механической частей стенда;

105 2) рабочая документация по эксплуатации стенда может быть разработана и без про- ведения сборки самого стенда;
3) контрольные испытания должны проводиться при наличии готовой документации по эксплуатации.
5.4.1.1. Расчет сетевой модели
Для расчета и записи временных параметров работ составляют таблицу (табл. 5.5), в которой обычно записываем коды работ в определенном порядке. Сначала записыва- ются все работы, выходящие из исходного, первого, события, затем – выходящие из вто- рого события, потом – из третьего и т.д.
Таблица 5.5
Расчет временных параметров
Код работы t(i,
j)
Трн(i,
j)
Tpo(i,
j)
Тпн(i,
j)
T
пo(i,
j)
Rп(i,
j)
Rc(i,
j)
1,2 5
0 5
0 5
0 0
2,3 5
5 10 5
10 0
0 2,8 3
5 8
52 43 35 35 3,4 8
10 18 10 18 0
0 3,5 6
10 16 19 25 9
0 3,6 10 10 20 18 28 8
0 4,7 25 18 43 18 43 0
0 5,7 18 16 34 25 43 9
9 6,7 15 20 35 28 43 8
8 7,8 0
43 43 55 43 0
0 7,9 12 43 55 43 55 0
0 8,9 12 43 55 43 55 0
0 9,10 10 55 65 55 65 0
0
На рис. 5.12 представлен сетевой график разработки изготовления и поставки стенда
(жирными стрелками выделен критический путь). Конечным результатом выполняемых на сетевой модели расчетов является календарный график, который иногда называют графиком привязки.
5.4.2. Сглаживание потребности в ресурсах
Потребление ресурсов находит отражение в стоимости как отдельных работ, состав- ляющих проект, так и в стоимости проекта в целом, на практике повсеместно приходится сталкиваться с ситуацией, когда потребность в том или ином виде физического ресурса в конкретный момент времени превышает имеющиеся возможности его обеспечения. Та- кие ситуации возникают в силу следующих причин:
1) Сокращение времени выполнения работ может приводить к неправильным реше- ниям в отношении выделяемых на ресурсов. Это – достаточно тривиальная ситуация, обусловленная невнимательным отношением к ограничениям по проекту.
2) Топология сетевой модели проекта оказывается причиной запараллеливания не- скольких работ, предусматривающих использование одинаковых ресурсов при соблюде- нии условия соответствия ограничениям по ресурсам в отдельной работе проекта.

106
Сглаживание потребности в ресурсах можно свести к трем основным случаям:
1) имеются четкие ограничения «по горизонтали», т.е. по срокам осуществления про- екта;
2) имеются четкие ограничения «по вертикали», т.е. по суммарной потребности в ре- сурсах;
3) имеются четкие установки относительно общей стоимости проекта, а именно, что она должна быть минимальна.
Общие принципы сглаживания потребности в ресурсах очень просты.
Первый принцип исходит из того, что, как правило, многие из параллельно заплани- рованных работ, требующих одних и тех же ресурсов, имеют резервы времени их выпол- нения. Поэтому, распараллеливание работ приводит к сглаживанию потребности в ре- сурсах (принцип распараллеливания).
Рис. 5.12. Сетевой график проектирования, изготовления и поставки стенда
Второй принцип исходит из того, что продолжительность выполнения некоторых ра- бот зависит от объема выделяемых для них ресурсов. Поэтому, если у таких работ име- ются также и резервы времени, то можно безболезненно для проекта в целом пойти на снижение интенсивности выполнения этих работ, что приведет к сглаживанию потребно- сти (принцип снижения интенсивности работ).
Однако, несмотря на простоту и понятность общих принципов, на которых строится сглаживание потребности проекта в ресурсах, расчетные алгоритмы оказываются очень и очень трудоемкими. До настоящего времени не разработано метода прямого поиска оп- тимального решения этой задачи. На практике процедуры сглаживания связаны либо с полным перебором возможных вариантов топологии проектного плана (в этом случае оказывается возможным доказать оптимальность варианта плана), либо с применением некоторых эвристических правил выстраивания квазиоптимальной топологии (например,
«наиболее короткая работа должна выполняться первой»).
0 0
0 1
0 5
2 5
5 5
0 10 3
10 8
6 3
0 10 0
18 18 4
9 5
16 25 25 18 8
20 28 6
15 12 0
55 55 9
55 55 0
9 10 12 0
65 65 10 35 43 8
8

107
5.4.3. График привязки
График привязки отображает взаимосвязь выполняемых работ во времени и строится на основе данных о ранних сроках начала и окончания работ и ресурсах используемых при выполнении этих работ (фактически это диаграмма Ганнта, дополненная информа- цией о ресурсах). Практическая ценность графика привязки заключается в том, что с его помощью можно улучшать эффективность использования ресурсов, то есть проводить оптимизацию сетевой модели.
Построим график привязки для следующих исходных данных (табл. 5.6).
Таблица 5.6
(i,
j) t(i,
j)
Количество исполнителей
1,2 5
2 2,3 5
1 2,8 3
3 3,4 8
4 3,5 6
4 3,6 10 1
4,7 25 5
5,7 18 5
6,7 15 3
7,8 0
1 7,9 12 4
8,9 12 2
9,10 10 3
5.4.3.1. Оптимизация использования ресурсов (на примере рабочей силы)
Рассмотрим применение графика привязки для частного случая оптимизации ресурса рабочей силы. При оптимизации использования ресурса рабочей силы сетевые работы чаще всего стремятся организовать таким образом, чтобы:
1) количество одновременно занятых исполнителей было минимальным;
2) выровнять потребность в людских ресурсах на протяжении срока выполнения про- екта.
Для проведения подобных видов оптимизации необходим график загрузки.
На графике загрузки по горизонтальной оси откладывается время, например в днях, по вертикальной оси – количество человек, занятых работой в каждый конкретный день.
Для построения графика загрузки необходимо:
1) на графике привязки на каждой работой написать количество ее исполнителей (рис.
5.13а);
2) подсчитать количество работающих в каждый день исполнителей и отложить на графике загрузки (рис. 5.13б).
Для удобства построения и анализа, графики загрузки и привязки располагают один над другим.
Для рассматриваемого примера (табл.5.5) свободные резервы есть у работ:
R
C
(2,8) = 35; R
C
(5,7) = 9; R
C
(6,7) = 8,

108 а полные резервы у работ:
R
П
(2,8) = 35; R
П
(3,5) = 9; R
П
(3,6) = 8; R
П
(5,7) = 9; R
П
(6,7) = 8.
Для снижения длительности одновременно занятых исполнителей достаточно увели- чить ранний срок начала работы R(6,7) на 8 дней, а работы R(5,7) на девять дней
(рис. 5.14а, 5.14б). Анализ (рис. 5.13а, 5.13б и 5.14а, 5.14б) показывает, что максимально число занятых исполнителей сократилось с 16 до 13.
Использование свободных резервов работ для оптимизации данного случая не дает уменьшения общей численности занятых в проекте. Более существенные результаты мо- гут быть получены при использовании полных резервов.
Различие в использовании свободных и полных резервов заключается в том, что при сдвиге работы, с использованием свободного резерва, моменты начала следующих за ней работ остаются неизменными (т.е. последующие работы не сдвигаются). При сдвиге ра- боты, с использованием полного резерва, все последующие работы сдвигаются.
5.4.4. Оптимизация типа «время—затраты»
Целью оптимизации по критерию «время—затраты» является сокращение времени выполнения проекта в целом. Эта оптимизация имеет смысл только в том случае, когда длительность выполнения работ может быть уменьшена за счет привлечения дополни- тельных ресурсов, что связано с ростом затрат на выполнение работ. Исходными данны- ми для проведения оптимизации являются:
― T
H
(i, j) – нормальная длительность работы;
― T
y
(i, j) – ускоренная длительность;
― C
H
(i, j) – затраты на выполнение работы в нормальный срок;
― Cy(i, j) – затраты на выполнение работы в ускоренный срок.
2 1
3 4
4 1
5 5
3 1
4 2
3 0
10 20 30 40 50 60 70
Время
1 2
3 4
5 6
7 8
9 10 11 12 13
С
о б
ы ти я
График привязки
Рис. 5.13а. График привязки

109
График загрузки
0 2
4 6
8 10 12 14 16 18 5
6 8
9 10 16 17 18 20 21 34 35 36 43 44 55 56 65
Рабочие дни
К
о л
и ч
ес тв о
з ан я
ты х
Рис. 5.13б. График загрузки
2 1
3 4
4 1
5 5
3 1
4 2
3 0
10 20 30 40 50 60 70
Время
1 2
3 4
5 6
7 8
9 10 11 12 13
С
о б
ы ти я
График привязки
Рис. 5.14а. График привязки

110
График загрузки
0 2
4 6
8 10 12 14 5
6 8
9 10 16 17 18 19 20 25 26 28 29 42 43 55 56 65
Рабочие дни
К
о л
и ч
ес тв о
з а
н я
ты х
Рис. 5.14б. График загрузки
Таким образом, каждая работа имеет некоторый максимальный запас (рис. 5.15) вре- мени для сокращения своей длительности Z
max
(i, j) = T
H
(i, j) – T
У
(i, j).
Затраты
Рис. 5.15. Оптимизация затраты продолжительность
Для анализа сетевой модели при такой оптимизации используется коэффициент на- растания затрат (коэффициент ускорения):
( , )
( , )
( , )
( , )
( , )
Cу i j
Cн i j
k i j
Tн i j
Tу i j




111
Коэффициент характеризует затраты денежных средств, необходимых для сокра- щения длительности выполнения работы (i, j) на один день (эквивалент ускорения
dV
a
dT

в физике).
Оптимизация критического пути. Оптимизация критического пути заключается в его улучшении в соответствии с принятым критерием.
В принципе, этими критериями могут быть: время, стоимость, людские и материаль- ные ресурсы и др.
Оптимизация может производиться с различными целями:
1. Если критический путь со временем Т превышает заданные сроки Т
0
, то, оптимиза- ция по времени заключается в сокращении критического пути.
2. Если Т<Т
0
, то имеется известный резерв времени R = T
0
–T, поэтому работы можно растянуть с целью экономии затрачиваемых средств. Дадим математическую постановку каждой из поставленных задач:
Задача 1.Известен критический путь Т, причём
0
i
кр
T
t
T



(5.1) где
i
кр
t

– распространяется только на критические работы;
Т
0
– заданный (директивный) срок выполнения работ.
Для сокращения критического пути, имеет смысл форсировать критические работы.
Их можно ускорить, например:
1. За счёт дополнительных сил и средств.
2. За счёт переброски сил и средств с некритических работ на критические.
Если используется пункт 1, то возникает типичная задача исследования операций: ка- кие дополнительные средства х
г
, х
2
,..., х
п
и в какие критические работы их нужно вло- жить, чтобы критический путь сталменьше директивного (Т<Т
0
), а расход дополнитель- ных средств был минимальным.
5.4.4.1. Изменение сроков за счет дополнительных сил и средств
Допустим, что при вложении дополнительных средств x
t
в работу а i
сокращает время выполнения этой работы до времени '
( )
i
i
i
i
t
f x
t


(5.2)
Таким образом, требуется определить неотрицательные значения переменных
х
1
,х
2
,...,х
n
(дополнительные вложения) при которых бы выполнялось условие:
'
0
( )
i
i
кр
T
f x
T



(5.3) где
кр

– распространяется по всем критическим работам нового критического пути
(после распределения средств); и что при этом общая сумма дополнительных средств была минимальна: min
т
i
кр
X
x



(5.4)
В общем случае ограничения (5.3 и 5.4) нелинейные, т.к. вложение каких-то средств в работу а
1
не обязательно вызывает линейное уменьшение времени, затрачиваемого на эту работу. Поэтому поставленная задача относится к классу задач нелинейного программи-