Сетевое планирование и управление

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

1. Основные этапы, методы, структура и характеристики СПУ

1.1 Структурное планирование

Основными понятиями сетевых моделей являются понятия события и работы.

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

По своей физической природе работы можно рассматривать как:

действие: заливка фундамента бетоном, составление заявки на материалы, изучение конъюнктуры рынка;

процесс: старение отливок, выдерживание вина, травление плат;

ожидание: ожидание поставки комплектующих, пролеживание детали в очереди к станку.

По количеству затрачиваемого времени работа может быть:

действительной, т.е. требующей затрат времени:;

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

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

Таким образом, начало и окончание любой работы описываются парой событий, которые называются начальным и конечным событиями. Поэтому для идентификации конкретной работы используют код работы (i, j), состоящий из номеров начального (i-го) и конечного (j-го) событий, например (2,4); 3-8; 9,10 (Рис. 1).

Рис. 1

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

Рис. 2

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



Рис. 3

При построении сетевого графа необходимо следовать следующим правилам:

длина стрелки не зависит от времени выполнения работы (Рис. 4.);

Рис. 4

стрелка не обязательно должна представлять прямолинейный отрезок (Рис. 5);

Рис. 5

для действительных работ используются сплошные, а для фиктивных - пунктирные стрелки (Рис. 6);

Рис. 6

каждая операция должна быть представлена только одной стрелкой;

не должно быть параллельных работ между одними и теми же событиями, для избежания такой ситуации используют фиктивные работы (Рис. 7);

Рис. 7

следует избегать пересечения стрелок (Рис. 8);

Рис. 8

не должно быть стрелок, направленных справа налево (Рис. 9);

Рис. 9

номер начального события должен быть меньше номера конечного события (Рис. 10);

Рис. 10

не должно быть висячих событий, кроме исходного (Рис. 11);

Рис. 11

не должно быть тупиковых событий, кроме завершающего (Рис. 12);



Рис. 12

не должно быть циклов (Рис. 13).

Рис. 13

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

Какие работы необходимо завершить непосредственно перед началом рассматриваемой работы?

Какие работы должны непосредственно следовать после завершения данной работы?

Какие операции могут выполняться одновременно с рассматриваемой работой?

1.2 Календарное планирование

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

К временным параметрам событий относятся:

ранний срок наступления события i - ;

поздний срок наступления события i - ;

резерв времени наступления события i - .

- это время, необходимое для выполнения всех работ, предшествующих данному событию i.

- это такое время наступления события i, превышение которого вызовет аналогичную задержку наступления завершающего события сети.

- это такой промежуток времен, на который может быть отсрочено наступление этого события без на рушения сроков завершения разработки в целом.

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

Рис. 14

1.3 Методика расчета временных параметров событий

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

1.2 Для исходного события .

Для всех остальных событий , где максимум берется по всем работам , входящим в событие i (Рис. 15).

Рис. 15

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

1.3 Для завершающего события .

, где минимум берется по всем работам , выходящим из события i (Рис. 16).



Рис. 16

5) .

На основе ранних и поздних сроков событий можно определить временные параметры работ сети.

При составлении таблицы, для записи временных параметров работ, обычно коды работ записывают в определенном порядке. Сначала записываются все работы, выходящие из исходного, первого, события, затем - выходящие из второго события, потом - из третьего и т.д. (Таблица 1)

Код работы
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

К наиболее важным временным параметрам работы относятся:

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

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

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

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

полный резерв ;

свободный резерв .

1.4 Методика расчета временных параметров работ

;

или ;

или ;

;

;

.

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

Например, в рассмотренном сетевом графике путями являются следующие последовательности работ:

2-3, 3-4, 4-7 или 2,3,4,7;

8-9 или 8,9;

1-2, 2-3, 3-6, 6-7, 7-9, 9-10 или 1,2,3,6,7,9,10.

Полный путь - это путь от исходного до завершающего события, например 1,2,3,6,7,9,10.

Критический путь - максимальный по продолжительности полный путь.

Подкритический путь - полный путь, ближайший по длительности к критическому пути.

Работы, лежащие на критическом пути, называют критическими. Они имеют ряд особенностей:

начальные и конечные события критических работ имеют нулевые резервы событий;

временно пропустить (это касается соотношения между и , а также между и ).

временно пропустить (о значениях резервов работ).

Первую особенность критических работ можно использовать при поиске критического пути. Для этого надо выявить все события, имеющие нулевой резерв. В рассматриваемом примере это события 1,2,3,4,7,8,9,10. Но через эти события проходят три пути:

1,2,8,9,10;

1,2,3,4,7,8,9,10;

1,2,3,4,7,9,10.

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

1.5 Формализация достаточного условия для определения критического пути

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

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

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

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

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

1.6 Пример построения графика привязки

Построим график привязки для следующих исходных данных, данные представлены в таблице 2:

		Количество исполнителей
1,2	4	5
2,3	5	6
2,4	6	3
2,7	11	4
3,6	10	2
4,5	9	1
5,7	11	3
6,7	9	5
7,8	12	6

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

2. Оптимизация сетевых моделей

2.1 Оптимизация использования ресурса рабочей силы

сетевой планирование график модель

При оптимизации использования ресурса рабочей силы сетевые работы чаще всего стремятся организовать таким образом, чтобы:

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

выровнять потребность в людских ресурсах на протяжении срока выполнения проекта.

Для проведения подобных видов оптимизации необходим график загрузки.

На графике загрузки по горизонтальной оси откладывается время, например в днях, по вертикальной - количество человек, занятых работой в каждый конкретный день. Для построения графика загрузки необходимо:

на графике привязки над каждой работой написать количество ее исполнителей;

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

Для удобства построения и анализа, графики загрузки и привязки следует располагать один над другим.

2.2 Пример построения графика загрузки

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

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

Т.о. мы установили, что свободные резервы есть у работ:

; ,

а полные резервы у работ:

; .

В таблице 3 показаны результаты оптимизации по критерию «min исполнителей». Для снижения максимального количества одновременно занятых исполнителей с 13 до 9 человек достаточно работу сдвинуть на 5 дней, а работу - на 1 день (пунктирной линией - изменения на графике загрузки).

На рис. 19 показаны результаты оптимизации с целью выравнивания загрузки. Для этого необходимо чуть дальше сдвинуть указанные работы, а именно: работу сдвинуть на 6 дней, а работу - на 2 день (пунктирной линией - изменения на графике загрузки).

Проведенная оптимизация была основана на использовании свободных резервов работ, но также возможно и использование полных резервов.

		Кол-во исп.
1,2	10	2
1,3	0	1
1,5	3	8
2,3	6	2
2,4	4	1
3,6	7	3
4,5	6	1
4,6	1	2
5,6	10	1

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

Рис. 19

2.3 Оптимизация типа «время-затраты»

Целью оптимизации по критерию «время - затраты» является сокращение времени выполнения проекта в целом. Эта оптимизация имеет смысл только в том случае, когда длительность выполнения работ может быть уменьшена за счет задействования дополнительных ресурсов, что влечет повышение затрат на выполнение работ. Для оценки величины дополнительных затрат, связанных с ускорением выполнения той или иной работы, используются либо нормативы, либо данные о выполнении аналогичных работ в прошлом.

Исходными данными для проведения оптимизации являются:

- нормальная длительность работы;

- ускоренная длительность;

- затраты на выполнение работы в нормальный срок;

- затраты на выполнение работы в ускоренный срок.

Т.о. каждая работа имеет некоторый максимальный запас времени для сокращения своей длительности

.

Рис. 20

Для анализа сетевой модели в данном виде оптимизации используется коэффициент нарастания затрат (коэффициент ускорения):

,

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

2.4 Общая схема проведения оптимизации

1. Проводится расчет сети исходя из нормальных длительностей работ.

2. Определяется сумма затрат на выполнение всего проекта при нормальной продолжительности работ.

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

Для сокращения выбирается критическая работа с min коэффициентом нарастания затрат , у которой есть запас сокращения времени.

Определяется время , на которое необходимо сжать длительность работы . При этом руководствуются следующими соображениями.

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

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

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

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

В результате оптимизации строится график «Время - затраты» (Рис. 21):

2.6 Неопределенность времени выполнения операций

В описанных методах анализа сетей предполагалось, что время выполнения работ точно известно, однако на практике сроки выполнения работ обычно довольно неопределенны. В таких случаях обычно используют экспертные оценки минимальной (a), максимальной (b) и наиболее вероятной длительности (m) работ для расчета их ожидаемой продолжительности. Тогда ожидаемая продолжительность работы определяется по формуле:

.

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

3. Задача СПУ

3.1 Постановка задачи

Структура сетевой модели и оценки продолжительности работ (в сутках) заданы в таблице 4. Требуется:

а) получить все характеристики СМ;

б) оценить вероятность выполнения всего комплекса работ за 35 дней, за 30 дней;

в) оценить максимально возможный срок выполнения всего комплекса работ с надежностью 95% (т.е. р = 0,95).

Три первые графы в таблице 4, содержат исходные данные, а две последние графы - результаты расчетов по формулам.

Работа	Продолжительность	Ожидаемая	Дисперсия
(i, j)	tmin(i, j)	t max(i, j)	Продолжительность tож(i, j)	S2 (i, j)
(1.2)	5	7.5	5	0.25
(2.3)	4	6.5	5	0.25
(2.4)	3	6	3	1.00
(2.5)	1	5.5	4	0.25
(3.7)	0.5	3.5	1	0.36
(4.5)	5	7.5	6	0.25
(4.6)	3	5.5	4	0.25
(4.9)	5	10	7	1.00
(5.8)	2	4.5	3	0.25
(5.10)	7	12	9	1.00
(6.9)	0	0	0	0.00
(6.11)	3	8	5	1.00
(7.10)	4	9	6	1.00
(8.10)	2	7	4	1.00
(9.10)	1	6	3	1.00
(10.11)	8	10.5	9	0.25

3.2 Решение задачи

Исходя из данных в таблице 4, получим следующие вычисления:

t_ож(i, j)=(3t_min (i, j) + 2t _max(i, j)): 5

t_ож(1,2)=(3*5 +2*7,5):5 =6

t_ож(2,3)=(3*4 +2*6,5):5 =5

S² (i, j) = (t _max (i, j) - t _min (i, j) ²:5 ² =

= 0.04 (t _max (i, j) - t _min (i, j)²

S² (1,2) = (7,5 - 5) ²:25 =0,25

S² (2,3) = (6,5 - 4) ²:25 =0,25

Отсюда получим сетевую модель (Рис. 22):

Рис. 22

Напомним, что критическим является путь: L_кр = (1,2,4,5,10,11), а его продолжительность равна t_кр= t_ож= 33 дня.

Дисперсия критического пути составляет:

S²_Kp = S²(l, 2) + S²(2,4) + S²(4,5) + S²(5,10) + S²(10, M) =

= 0,25 + 1,00 + 0,25 + 1,00 + 0,25 = 2,75.

Для использования формулы показателя дисперсии необходимо иметь среднее квадратическое отклонение, вычисляемое путем извлечения из значения дисперсии квадратного корня, т.е. S_Kp = 1,66. Тогда имеем:

Р(t_кр <35) = 0,5 + 0,5 Ф{(35 - 33) 1,66} =

= 0.5 + 0.5 Ф (1,2)=0,5+0,5*0,77=0,885

Р(t_кр <30) = 0,5 + 0,5 Ф{(30 - 33)/1,66} = 0,5 - 0,5Ф (1,8) =

= 0,5 - 0,5 * 0,95 = 0,035.

Таким образом, вероятность того, что весь комплекс работ будет выполнен не более чем за 35 дней, составляет 88,5%, в то время как вероятность его выполнения за 30 дней - всего 3,5%.

3.3 Решение обратной задачи

Для решения второй (по существу обратной) задачи прежде всего в таблице 4 найдем значение аргумента z, которое соответствует заданной вероятности 95%. В графе Ф(z) наиболее близкое значение (0,9545 * 100%) к ней соответствует г = 1,9. Тогда получим:

Т = t_ож(L_кр) + z-S_Kp = 33 + 1,9*1,66 = 36,2 дн.

Следовательно, максимальный срок выполнения всего комплекса работ при заданном уровне вероятности р = 95% составляет 36,2 дня.

Заключение

Системы СПУ впервые были созданы в 60-х годах прошлого столетия в СССР и в США. На западе она получила название «Система PERT». Эти системы широко используются в военном деле и в космических исследованиях, в строительстве крупных народно-хозяйственных объектов и т.д.

В настоящее время создана Программное обеспечение (ПО) решающее все задачи построения и использования сетевых моделей. Наибольшее распространение получила системы моделирования Microsoft Project Expert, решающая все задачи СПУ. Основные проблемы связанные с использованием сетевых моделей - это формирование их топологий. Для практических задач характерно большое количество работы событий, что определяет большую размерность задачи. В этих условиях традиционные ручные методы построения адекватной модели труднореализуемые. Поэтому на повестке дня актуальными являются вопросы автоматизации построения сетевых моделей.

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

Список литературы

М. Эддоус, Р. Стенсфилд. Методы принятия решений. - М., Аудит, ЮНИТИ, 1997.

Е.С. Вентцель. Исследование операций. М, Советское радио, 1972.

Сетевое планирование и управление. Под ред. Д.И. Голенко. М., Экономика, 1967.

Н.М. Губин, А.С. Добронравов, Б.С. Дорохов. Экономико-математические методы и модели в планировании и управлении в отрасли связи. М., Радио и связь, 1993.

Сетевые графики в планировании. Под ред. Разумова. М., Высшая школа, 1975.

Размещено на Allbest.ru