Allmath.ru

Вся математика в одном месте!

 

 

 

 



Rambler's Top100


Задачи по исследованию операций (СОДЕРЖАНИЕ)

 8. РАСЧЕТ И АНАЛИЗ СЕТЕВЫХ МОДЕЛЕЙ

8.1. Теоретическое введение

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

Расчет сетевой модели начинают с временных параметров событий, которые вписывают непосредственно в вершины сетевого графика (рис.8.1):

·         – ранний срок наступления события i, минимально необходимый для выполнения всех работ, которые предшествуют событию i;

·         – поздний срок наступления события i, превышение которого вызовет аналогичную задержку наступления завершающего события сети;

·         – резерв события i, т.е. время, на которое может быть отсрочено наступление события i без нарушения сроков завершения проекта в целом.

Рис.8.1. Отображение временных параметров событий на сетевом графике

Ранние сроки свершения событий  рассчитываются от исходного (И) к завершающему (З) событию следующим образом:

1)     для исходного события И ;

2)     для всех остальных событий I

,

где максимум берется по всем работам , входящим в событие i;  – длительность работы (k,i) (рис.8.2).

Рис.8.2. Расчет раннего срока  свершения события i

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

1)     для завершающего события З ;

2)     для всех остальных событий

,

где минимум берется по всем работам , выходящим из события i;  – длительность работы (k,i) (рис.8.3).

Рис.8.3. Расчет позднего срока  свершения события i

Временные параметры работ определяются на основе ранних и поздних сроков событий:

·         – ранний срок начала работы;

·         – ранний срок окончания работы;

·         – поздний срок окончания работы;

·         – поздний срок начала работы;

·         – полный резерв работы показывает максимальное время, на которое можно увеличить длительность работы  или отсрочить ее начало, чтобы не нарушился срок завершения проекта в целом;

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

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

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

8.2. Методические рекомендации

Задача №8.01

Компания разрабатывает строительный проект. Исходные данные по основным операциям проекта представлены в табл.8.1. Постройте сетевую модель проекта, определите критические пути модели и проанализируйте, как влияет на ход выполнения проекта задержка работы D на 4 недели.

Таблица 8.1

Исходные данные задачи №8.01

Название

Непосредственно предшествующие

операции

Длительность,

недели

A

4

B

6

C

A,B

7

D

B

3

E

C

4

F

D

5

G

E,F

3

Решение

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

·        необходимое условие – нулевые резервы событий, лежащих на критическом пути;

·        достаточное условие – нулевые полные резервы работ, лежащих на критическом пути.

Согласно необходимому условию два полных пути сетевой модели (см. рис.8.3)  и  могут быть критическими. Проверим достаточное условие критичности для работ (1,2) и (1,3)

;

.

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

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

Работа D или (2,5) не является критической, ее полный резерв равен 3-м неделям. Это означает, что при задержке работы в пределах 3-х недель срок выполнения проекта не будет нарушен. Поэтому если согласно условию работа D задержится на 4 недели, то весь проект закончится на 1 неделю позже.

Рис.8.3. Сетевой график задачи №8.01

Задача №8.02

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

Таблица 8.2

Исходные данные задачи №8.02

(i,j)

1,2

1,3

1,4

1,5

2,3

3,6

3,7

4,5

4,6

5,7

6,7

t(i,j), дни

3

3

2

10

2

5

9

10

6

1

4

Общие рекомендации

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

Из вышеприведенных соображений следует способ определения критического пути на графике привязки (все найденные работы выписываются последовательно справа налево):

1)     найти на графике привязки и выписать работу (i,j), которая заканчивается позже всех остальных. Это будет последняя работа критического пути (ее конечное событие иметь номер завершающего события сети);

2)     из всех работ сети (k,i), конечное событие которых i совпадает с начальным событием i работы (i,j), найденной в п.1), выбрать и выписать ту, которая на графике вплотную примыкает к работе (i,j);

3)     из всех работ сети (l,k), конечное событие которых k совпадает с начальным событием k работы (k,i), найденной в п.2), выбрать и выписать ту, которая на графике вплотную примыкает к работе (k,i);

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

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

Решение

I. Поиск критических путей

1)     Построим график привязки (рис.8.4).

Рис.8.4. График привязки задачи №8.02

2)     Начнем поиск критических путей (справа налево) с работ, завершающих проект. На графике привязки (см. рис.8.4) две работы (6,7) и (3,7), которые заканчиваются позже остальных в завершающем событии №7. Записываем работы, определенные как критические справа налево

     ;

(8.1)

.

3)     Найдем критическую работу из , предшествующую (6,7). Код этой работы должен оканчиваться на 6. Таких работ две – (4,6) и (3,6). Но только одна из них, работа (3,6) по времени своего окончания вплотную "примыкает" на графике к началу работы (6,7). Допишем слева найденную критическую работу (3,6) к выражению (8.1)

.

(8.2)

4)     Найдем критическую работу из , предшествующую (3,6). Код этой работы должен оканчиваться на 3. Таких работ две – (2,3) и (1,3). Но только одна из них, работа (2,3) по времени своего окончания вплотную "примыкает" на графике к началу работы (3,6). Допишем слева найденную критическую работу (2,3) к выражению (8.2)

.

(8.3)

5)     Найдем критическую работу из , предшествующую (2,3). Код этой работы должен оканчиваться на 2. Работа (1,2) по времени своего окончания вплотную "примыкает" на графике к началу работы (2,3). С этой работы начинается критический путь

.

6)     Аналогичный поиск работ критического пути  приводит к результату .

В другой форме записи  и .

7)     Для наглядности выделим на графике привязки критические работы жирной линией.

II. Поиск резервов работ

1)     Для всех найденных критических работ впишем в табл.3 нулевые значения свободного и полного резервов. Рассмотрим некритические работы, начиная с конца табл.8.3.

Таблица 8.3

Резервы работ из задачи №8.02

Критичность

1,2

3

0

0

Критическая

1,3

3

2

2

1,4

2

0

1

1,5

10

2

3

2,3

2

0

0

Критическая

3,6

5

0

0

Критическая

3,7

9

0

0

Критическая

4,5

10

0

1

4,6

6

2

2

5,7

1

1

1

6,7

4

0

0

Критическая

2)     Работа (5,7), согласно графику привязки (см. рис.8.4) заканчивается в 13-й день, а завершающее событие 7 сети, в которое она входит, наступает лишь в 14-й день. Т.е. если работа (5,7) задержится на 1 день, то это не повлияет на срок выполнения проекта ( дней). Поскольку (5,7) завершающая работа сети, то ее полный и свободный резервы равны .

3)     Работа (4,6) заканчивается в 8-й день, в то время как последующая работа (6,7) начинается в 10-й день. То есть, работа (4,6) может задержаться на 2 дня и это никак не повлияет на время начала последующей работы (6,7), т.е. .

Правило №8.1

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

За работой (4,6) следует только критическая работа (6,7) с нулевым полным резервом. Поэтому .

4)     Работа (4,5) заканчивается в 12-й день, в этот же день начинается следующая работа (5,7), т.е. любая задержка выполнения работы (4,5) приведет к задержке начала работы (5,7). Это означает, что работа (4,5) не имеет свободного резерва . Но если сдвинуть во времени работу (4,5) на 1 день, то работа (5,7) также сдвинется на 1 день и это не нарушит срок выполнения проекта, т.к. у работы (5,7) есть временной резерв. Таким образом согласно правилу №8.1

5)     Работа (1,5) заканчивается в 10-й день, в то время как последующая работа (5,7) начинается в 12-й день. Т.е. работа (1,5) может задержаться на 2 дня и это никак не повлияет на время начала последующей работы (5,7), т.е. . Кроме того, поскольку последующая работа (5,7) имеет резерв в 1 день, то, в общем, работу (1,5) можно сдвинуть на 3 дня и это не нарушит сроков проекта (см. рис.8.4), т.е.

6)     Работа (1,4) заканчивается во 2-й день, и в этот же день начинаются следущие работы (4,5) и (4,6). Т.е. работа (1,4) не имеет свободного резерва времени . Поскольку после работы (1,4) следуют две работы с различными полными резервами, то согласно правилу №8.1

7)     Работа (1,3) заканчивается в 3-й день, а следующие за ней работы (3,6) и (3,7) начинаются в 5-й день, т.е. . Поскольку обе последующие работы критические, то полный и свободный резерв работы (1,3) совпадают

.

8)     Ненулевые свободные резервы работ обозначены на графике привязки фигурными скобками (см. рис.8.4).


Хотите публиковаться на портале? Присылайте свои предложения, книги, статьи на info@allmath.ru.

[Школьная математика][Высшая математика][Прикладная математика][Олимпиадная математика][Услуги][Лучшие книги][Ссылки]

 

Copyright (c) 2004, Allmath.ru. e-mail: info@allmath.ru