Основные понятия

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

1.1 Понятие сети.

Если элементам графа поставить в соответствие некоторые параметры, то получим сеть.

Параметры могут быть заданы вершинами или (и) дугами графа.

Орграф превращается в сеть, если каждой вершине U_i поставлено в соответствие некоторое число d_i, называемое интенсивностью вершины, а каждой дуге (V_i,V_j) – неотрицательное число r_ij, называемое ее пропускной способностью.

Понятие сети лежит в основе системы сетевого планирования и управления (СПУ).

1.2 Сетевая модель и ее элементы

Сетевой график – это ориентированный граф без контуров, дуги которого имеют одну или несколько числовых характристик.

Дугами изображаются работы, а вершинами – события.

Работа – любой трудовой процесс или действие, сопровождающиеся затратами времени и ресурсов.

Под работами подразумеваются:

· Не только реальные хоз. или технологические процессы, требующие затрат времени и ресурсов, но и

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

На сетевых графиках фиктивные работы обычно изображаются пунктирными стрелками (- - →).

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

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

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

Отсюд а, событие обладает свойством «сшивания» предыдущих работ с последующими.

Предполагается, что событие не имеет продолжительности и совершается как бы мгновенно.

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

События изображаются точками, кружками, ромбами и т.д. – это вершины соответствующего графа.

Событие считается совершившимся только тогда, когда будет закончена самая длинная из всех входящих в него работ.

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

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

Здесь важно:

· Ни один путь не может проходить дважды одно и то же событие;

· любой путь может проходить по холостой работе;

· несколько путей могут проходить через одной и то же событие;

Длина пути – определяется суммой продолжительности лежащих на нем работ.

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

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

Все работы, лежащие на критическом пути, также являются критическими.

Они – потенциально узкое место плана.

В сети можно найти несколько критических путей.

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

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

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

Наличие резервов времени у некритических работ дает возможность свободно маневрировать внутренними ресурсами и этим ускоряет выполнение критических и подкритических работ – это главное в сетевом методе планирования и управления.

1.3 Виды сетевых моделей

Могут быть использованы 3 основных вида сетевых моделей:

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

2) в терминах работ, в которых работы будут вершинами графа, а дуги показывают взаимосвязь отдельных работ;

3) в терминах работ и событий, - в которых работы – это дуги, а события – вершины.

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

1.4 Построение сетевых графиков

Существует несколько общих правил построения сетевых графиков:

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

б) от середины к концу и началу

в) от конца к началу.

Чаще всего – наиболее распространенный метод – а) – от начала к концу, слева направо.

Каждое событие с большим порядковым номером показывается несколько правее предыдущего номера.

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

Приступая к составлению сети, необходимо установить, какие работы:

· должны быть завершены раньше, чем начнется данная (предшествующая работа);

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

· могут выполняться одновременно с данной работой.

При построении сети обязательно составляется черновой вариант.

Далее ее можно упорядочить. При этом в нее часто приходится добавлять так называемые «забытые» работы.

При построении сетевых графиков встречаются сложные комплексные связи. Например:

Ø две или более работ имеют общие начальные и конечные события.

Эти работы выполняются параллельно (совмещено), но продолжительность их разная.

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

рис.1

Ø для выполнения одной из работ, например (5,6) (рис.2) необходимо предварительно выполнить работы (2,5), (3,5), (4,5), а для другой (5,7) - выполнение только (4,5)

рис.2

В этом случае изображение а) – неверное, так как получается, что выполнение работы (5,7) зависит от (2,5), (3,5) и (4,5). Нужно: ввести в сеть дополнительное событие (4') и фиктивную работу (4',5) - б).

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

рис.3

Иногда изображаются орг.связи (пунктирные стрелки с полотнами – для отличия от фиктивных работ)

Ø двусторонние связи изображаются введением фиктивных работ.

Напр., пусть имеются 3 процесса А, В, С.

При этом окончание С зависит от результатов А и В. В данном случае возникают двусторонние зависимости (рис.4).

рис.4

Ø При построении сетевых графиков иногда бывает целесообразно укрупнить работы путем замены их совокупности данной «агрегатной», если какая-то группа имеет одно начальное и одно конечное событие (рис.5)

рис.5

При проверке правильности составления сети выясняют:

1) нет ли на графике работ, имеющих одинаковые кода. Если они есть, то следует ввести дополнительные события и фиктивные работы;

2) в сети не должно быть «тупиков», т.е. событий, из которых не выходит ни одна работа (кроме последнего);

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

4) нельзя допускать, чтобы два смежных события были связаны двумя или большим количеством работ;

5) в сети не должно быть замкнутых контуров;

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

7) правильность изображения частично (дифференциально) зависимых работ.

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

Составление сетевых графиков ведется в 3 этапа:

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

II этап – заключается в составлении структурной схемы разработки, или так наз. «дерева разработки», которые должны наглядно показывать объём и этапы работ.

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

III этап – составление перечня работ в каждом звене и формирование их временных оценок.

5 Определение продолжительности работ.

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

Достоверность расчетных параметров сетевого графика обуславливается достоверностью исходных данных.-

Известна, длительность выполнения работ тесно связана с использованием ресурсов (> ресурсов, как правило, → < продолжительность работы).

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

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

При этом оценки работ следует рассматривать вразброс, т.е. независимо от оценок предшествующих и последующих работ.

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

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

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

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

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

Наиболее широко применимые системы: трёх и двух вероятностных оценок времени.

В системе с 3-мя оценками от отв. исполнителя получают минимальную (t_min), максимальную (t_max) и наиболее вероятную (t_н.в.) оценки времени.

Минимальное (t_min) – это необходимое для выполнения работ время при

наиболее благоприятном стечении обстоятельств.

Вероятность выполнения за такое время мала (≈ 0.01).

Эта оценка наз. оптимистической.

Максимальное (t_max) – пессиместическая оценка – это время, необходимое

для выполнения работ при наиболее неблагоприятном

стечении обстоятельств (за исключением аварий и

стих. бетствий).

Вероятность её выполнения за такое время также мала

(≈ 0.01).

Наиболее вероятная оценка – возможное время выполнения данной работы

при отсутствии неожиданных трудностей.

Оценки t_min, t_max, t_н.в служат исходными данными для расчёта ожидаемого времени (t_ож.) выполнения работы.

Величина t_ож. – математическое ожидание случайной величины продолжительности выполнения работы.

Но матем. ожидание, как правило, не даёт полной характеристики времени выполнения.

Для более полной характеристики t_ож. используется понятие дисперсии.

Дисперсия – это мера неопределённости, рассеивания случ. величины вокруг её математ. ожидания.

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

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

Случайная величина полностью задаётся с помощью функции распределения.

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

Наиболее часто встречается нормальноераспределение.

ƒ(t)

t₀ t

рис. 6

Это распределение симметрично относительно мат. ожидания t₀ , которое часто наз. центром рассеивания.

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

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

Это распределение, как правило, обладает положительной ассиметрией, т.е. единственный максимум кривой смещен влево относительно линии, делящей площадь под кривой на две равные части (рис. 7).

ƒ(t)

t_min t₀ t

рис. 7

Она более круто поднимается при удалении от t_min и полого опускается при приближении к верхнему пределу t_max.

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

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

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

Функция плотности β-распределения имеет вид:

ƒ(t)=c*(t- t_min)^α * (t_max –t)^γ

где ƒ(t) – вероятность принятия продолжительности работ значения t,

c – постоянная величина(c=const),

α,γ – параметры распределения.

В системе СПУ предполагается, что

σ _t = (t_max - t_min)/6

При этом можно показать, что

t_ож = (t_min + t_н.в + t_max)/6 (1)

Если α=1, γ=2, то

t_ож = (3* t_min+2* t_max)/5; σ _t = (t_max - t_min)/5 (2)

Формулы (1) и (2) служат для оценки продолжительности работ.

6 Расчёт параметров сетевого графика

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

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

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

Путь от исходного события до любого события (i) предшествует данному событию.

Предшествующий событию путь, имеющий наибольшую длину, наз. максимальным предшествующим, обозначим его L₁(i), а его продолжительность t[L₁(i)].

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

Такой путь с наибольшей длиной до завершающего события наз. максимально последующим – обозначим его L₂(i), а его продолжительность t[L₂(i)].

Мы уже говорили, что среди полных путей сетевого графика особое значение имеет наиболее продолжительный из них – критический. В графике их может быть несколько.

Полные пути, отличные от критических – ненапряженные (их продолжительность < критич.).

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

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