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

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

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

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

1.Сети, в которых работам комплекса сопоставлены вершины, а дуги отражают отношения предшествования между работами (сети типа «работы-вершины») (рис.1.1.)

 

 

 

Рис.1.1. Сетевая модель типа «работы-вершины»

 

Рисунок 1.1. предполагает следующую информацию: работа 1 является исходной и она предшествует работам 2 и 3. Все характеристики работ, такие как продолжительность, стоимость и пр., содержатся в прямоугольнике, а дуга, связывающая прямоугольники-вершины, не несет в себе количественных характеристик, а является только связующим звеном. Работе 4 предшествуют работы 2 и 3. Завершающей работой является работа 5, которой предшествует результат работы 4.

 

2.Сети, в которых работам комплекса сопоставлены дуги, а вершины соответствуют некоторым событиям (сети типа «работы-дуги») (рис.1.2)

 

 

 

Рис.1.2. Сетевая модель типа «работы-дуги»

 

Информация, отображенная на рис.1.2., та же самая, что и на рис.1.1. Но на данной сетевой модели каждая дуга отображает процесс – работу и, следовательно, работа (i₀– 1) является по содержанию той же работой, что и работа 1 на рис.1.1., но вся информационная и количественная характеристика работы лежит на дуге, и таким образом, дуга (i₀–1) говорит о том, что работа начинается в событии (точке) i₀ и заканчивается событием 1; в свою очередь имеет продолжительность во времени. Далее работы (1-2) и (1-3) начинаются после окончания предшествующей работы (i₀–1) и т.д.

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

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

ü цель разработки;

ü данные о производственных условиях бизнеса, завода, перспективе развития;

ü основные положения по технологии и организации выполнения работ (т.е. логическая схема)

 

 

Построение сетевой модели

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

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

По своему содержанию и изображению в сетевом графике работа подразделяется (рис.1.3.) на:

ü работу, требующую затрат времени и труда (изображается на графике сплошной линией со стрелкой);

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

ü ожидание, или работу, требующую затрат времени, но не требующую затрат труда (изображается на графике сплошной линией со стрелкой).

 

Работа Зависимость

Ожидание

Рис.1.3.Изображение работ в сетевом графике

 

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

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

В частности, признаками ошибок, допущенных при построении сети, являются циклы (контуры) и тупики (рис.1.4.)

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

наличие событий, не являющихся исходными событиями и не имеющих входящих работ (тупики первого рода –событие B на рис.1.4.);

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

наличие замкнутых путей-контуров (1-2-3-1 на рис.1.4.)

 

 

 

Рис.1.4.Пример сети с тупиками и контурами

 

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

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

 

Тупики в сети могут появиться, например, в результате того, что:

ü в исходной информации о сети пропущены некоторые работы;

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

Все ошибки (тупики и контуры) должны быть устранены.

 

 

Таким образом, сетевая модель будет иметь следующий вид (рис.1.5.)

 

событие

 

 

работа

 

 

фиктивная работа

Рис.1.5.Сетевая модель

 

Таким образом, можно сформулировать основные свойства работ и событий сетевой модели:

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

2. Ко всем работам, имеющим своим началом некоторое событие, можно приступить только тогда, когда окончены все непосредственно предшествующие ему (событию) работы.

 

Рассмотрим пример составления сетевой модели.

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

Перечень необходимых задач, которые необходимо решить для этого, их взаимосвязь и время даны в таблице 1.1. Составить сетевой граф.

 

 

Таблица 1.1.Исходные данные

Задачи	Время, недель	Предшествующие задачи
А. Создание новой продукции		-
В. Создание упаковки		-
С. Подготовка производственной мощности		А
D. Получение сырья и материалов		А
E. Выпуск опытной партии продукции		C,D
F. Упаковка		B
G. Принятие решения о выборе пробного рынка сбыта		-
H. Упаковка опытной партии		E,F
I. Поставка продукции на пробный рынок сбыта		H,G
J. Продажа продукции на пробном рынке сбыта		I
K. Оценка результатов внедрения продукции на рынок		J
L. Планирование выпуска продукции на национальном уровне		K

 

 

Рис.1.6.Сетевая модель типа «работа-вершина»

 

 

 

Рис.1.7.Сетевая модель типа «работа-дуга»

 

 

Расчет сетевой модели

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

 

{i-j} – топология

{t(ij)} – метрика, где

(i-j) – коды работ, в которых

i – код начала работы, j- код окончания работы;

t(ij) – время выполнения работы (дни, часы, недели, месяцы и пр.).

 

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

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

1.4.1.Временные параметры событий сетевой модели

Ранний срок наступления событий характеризует самое раннее возможное наступление любого события i относительно времени наступления i₀. Согласно алгоритму Форда ранний срок наступления события можно определить в варианте прямой прогонки сетевой модели (от i₀ до i_n), в основе которого лежит соотношение (1.1)

 

0, если i = i₀

Т^p_i = max [T^p_k + t(ki)], если i ≠i ₀ (1.1)

	kiЄUвi

По формуле (1.1) рассчитываются ранние сроки наступления всех событий сетевой модели. Необходимо иметь в виду, что для расчета надо учитывать порядок предшествования.

Полученные {Т^p_i} для всех событий представляют собой абсолютные значения времени наступления событий, т.е. через сколько единиц времени наступит событие i, начиная от точки i₀. Для перевода сроков наступления событий в календарные даты необходимо задать дату наступления исходного календарного события сетевой модели.

Значение Т^p_i показывает длину максимального пути, предшествующего событию i – t[L_{max предш}(i)]. Следовательно, значение Т^p_in показывает самый длинный по продолжительности путь в сетевой модели; он называется критическим путем Ткр и показывает минимально возможное время выполнения всех работ сетевой модели. Указанное соображение характеризуется рисунком 1.8.

 

 

 

Ткр

 

Рис.1.8.Фрагмент сетевой модели

 

Событию i предшествуют следующие пути:

1) I₀ -1 –2 – i (длина пути равна 16)

2) I₀ - 3 – i (длина пути равна 9)

3) I₀ - 4 – i (длина пути равна 27)

Следовательно, t[L_{max предш}(i)] = 27. Если рассчитать сетевую модель по алгоритму Форда, то Т^p_i = 27.

 

 

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

 

 

 

Рис.1.9.Фрагмент, характеризующий связь «событие – то, что ему непосредственно предшествует».

 

Поздний срок наступления событий характеризует самое позднее время наступления события i. Расчет поздних сроков наступления событий осуществляется в варианте обратной прогонки алгоритма Форда (от i_n до i₀) по соотношению (1.2)

 

Т^p,если i=i_n

Т^п_i = min [Tⁿ_j -t(ij),если i≠i_n (1.2)

	ijЄUиi

Согласно алгоритму Форда и формуле (1.2) для каждого события рассматривается фрагмент, изображенный на рис.1.10.

 

Рис.1.10. Фрагмент, характеризующий связь «событие – то, что из него непосредственно исходит»

 

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

R (i) = T^п_i –T^p_i (1.3)

 

Рассмотрим пример расчета сетевой модели

Исходная информация для построения топологии сетевой модели и продолжительности работ дана в таблице 1.2.

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

 

 

Таблица 1.2. Исходная информация

Код работы i-j	Наименование работы	Продолжительность работы (i-j), дни
1-2	Исследование внутреннего рынка
1-4	Исследование зарубежного рынка
2-4	Определение сегмента внутреннего рынка
4-6	Определение политики освоения сегментов внутреннего и зарубежного рынков
1-5	Исследование качества выпускаемого товара
5-4	Разработка программы по адаптации товара к сегментам рынка
5-7	Разработка рекламной политики по продвижению товара на рынке
2-3	Разработка программы услуг по передвижению товара
3-6	Выбор посредников
7-6	Разработка политики оптовой и розничной торговли
8-8	Разработка торговой марки и упаковки
6-8	Определение ценовой политики
7-8	Разработка программы сервисного обслуживания

 

Рис.1.11.Сетевая модель, отображающая процесс маркетингового исследования

Произведем расчет параметров T^p_i, T^п_i и R(i).

 

Расчет T^p_i:

T^p_io = T^p₁ = 0

T^p₂ = T^p₁ + t(1-2) = 0+3 = 3

T^p₅ = T^p₁ + t(1-5) = 0+5 = 5

T^p₄ =max [T^p₂ + t(2-4); T^p₅ + t(5-4); T^p₁ + t(1-4)] = max [3+4; 5+8; 0+7] = 13

2-4

5-4

1-4

 

T^p₃ = T^p₂ + t(2-3) = 3+6 =9

T^p₇ = T^p₅ + t(5-7) =5+3 = 8

T^p₆ = max [T^p₃ + t(3-6); T^p₄ + t(4-6); T^p₇ + t(7-6)] = max [9+2; 13+2; 8+10] = 18

3-6

6-8

7-6

T^p₈ = max [T^p₃ + t(3-8); T^p₆ + t(6-8); T^p₇ + t(7-8)] = max [9+4; 18+7; 8+8] = 25

3-8

6-8

7-8

Следовательно, Ткр = Т^р₈ = 25. Это означает, что все работы сетевой модели по маркетинговому исследованию могут быть выполнены не менее, чем за 25 дней.

Расчет Т^п_i:

T^п_io = T^п₈ = 25

T^п₆ = Т^п₈ – t(6-8) = 25-7 = 18

T^п₇ = min [T^п₆ – t(7-6); T^п₈ – t(7-8)] = min [18-10; 25-8] = 8

7-6

7-8

T^п₃ = min [T^п₈ – t(3-8); T^п₆ – t(3-6)] = min [25-4;18-2] = 16

3-8

3-6

T^п₄ = T^п₆ – t(4-6) = 18-2 = 16

T^п₅ = min [T^п₄ – t(5-4); T^п₇ – t(5-7)] = min[16-8; 8-3] = 5

5-4

5-7

T^п₂ = min [T^п₃ – t(2-3); T^п₄ – t(2-4)] = min [16-6; 16-4] = 10

2-3

2-4

T^п₁ = min [T^п₂ – t(1-2); T^п₄ – t(1-4); T^п₅ – t(1-5)] = min [10-3; 16-7; 5-5] = 0

1-2

1-4

1-5

Если задать дату исходного события, то можно получить календарные даты наступления каждого события. Пусть дата i₀ будет 1.01.2001г. Будем считать, что все дни – рабочие. (Если учитывать праздничные и выходные дни, то их надо удалить из рассматриваемой шкалы). Тогда результаты расчета можно свести в таблицу 1.3.

 

Таблица 1.3. Временные параметры и резервы времени событий

 

Код события i	Ранний срок наступления события Трi	Поздний срок наступления события Тпi	Резерв времени события R (i)
1.01.2001.	1.01.2001.
3.01.2001.	10.01.2001.
5.01.2001.	5.01.2001.
13.01.2001.	16.01.2001.
9.01.2001.	16.01.2001.
8.01.201.	08.01.2001.
18.01.2001.	18.01.2001.
25.01.2001.	25.01.201.

 

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

 

Теорема 1. Длина критического пути в сетевой модели равна величине Т^п_io:

т.е. Ткр = t [L_{max предш} (i_n)] = T^p_in = T^п_in. (1.4)

 

Теорема 2. Длина максимального пути, следующего за некоторой вершиной i, равна разности Ткр и соответствующей величины Т^п_i:

т.е. t [L_{max след} (i)] = Ткр – Т^п_i (1.5)

 

Теорема 3. Если некоторая величина i принадлежит критическому пути, то величины Т^р_i и Т^п_i равны между собой:

т.е. i Є Lкр => Т^р_i = T^п_i

 

Теорема 4. Если событие принадлежит критическому пути, то резерв данного события равен 0:

т.е. i Є Lкр => R(i) = 0

Обратимся к таблице 1.3. События 1, 5, 7, 6, 8 принадлежат критическому пути

 

1.4.2. Временные параметры работ сетевой модели

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

 

Т^р.н. _{i j} = Т^р _i (1.6)

 

Соответственно, раннее окончание работы будет равно:

 

Т^р.о. _{i j} = T^р.н._ij +t(ij) = T^p _i +t(ij) (1.7)

 

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

 

Позднее допустимое время окончания работы (i-j) будет определяться из следующего соображения: оно должно быть таким, чтобы успеть закончить все работы, следующие за этой работой в срок Ткр. Следовательно, позднее допустимое время окончания работы (i-j) может быть вычислено как разность между Ткр и максимальным путем, следующим за этой работой. Изобразим это на фрагменте (рис.1.12)

 

 

 

L_{max след}(i)

Ткр

 

Рис.1.12. Фрагмент сетевой модели

 

Таким образом, используя теорему 2, можно написать:

Т^п.о._{i j} = Ткр – t[L_{max след}(j)] = Ткр – Ткр + Т^п _j;

Т^п.о._ij = Т^п_j (1.8)

 

Соответственно,

Т^п.н._{i j} = Т^п.о._ij – t(ij) = T^п _j – t(ij) (1.9)

 

Как видим, для расчета экстремальных характеристик времени начала и окончания работ сетевой модели необходимо осуществить алгоритм Форда и получить для каждого события T^p_i и Т^п_i.

 

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

 

R^п_(ij) = Т^п.н._ij – Т^р.н_ij = Т^п.о._ij – Т^р.о._ij = Т^п_j - Т^р_i – t(ij) (1.10)

 

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

 

i t(ij) j R^п

 

R^п

 

 

0 Т^р.н._ij Т^п.н._ij Т^р.о._ij Т^п.о._ij t

Рис.1.13. организационно-экономический смысл R^п(ij)

 

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

R^п (ij) = 0 <=> ij Є Lкр

 

На практике работы критического пути являются «узким местом» и требуют дополнительного внимания. Для оперативного управления ходом выполнения работ вычисляется еще один резерв времени работы – свободный резерв времени работы, который равен разности значений раннего срока свершения конечного события j работы (i-j) и значения раннего срока ее окончания:

 

R^c (ij) = Т^р_j – Т^р.о._ij = Т^р_j – Т^р_i – t(ij) (1.11)

 

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

 

 

i j → j k

R^c

 

 

Т^р.н._jk t

Рис.1.14. Организационно-экономический смысл R^c (ij)

 

Теорема 6. Если работа принадлежит критическому пути, то ее свободный резерв равен нулю:

ij Є Lкр => R^c(ij) = 0

 

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

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

 

Таблица 1.4. Результаты расчета

Коды работ i-j	t(ij)	Тр.н.ij	Тп.о.ij	Тп.н.ij	Rпij	Rcij
1-2
1-4
2-4
1-5
5-4
2-3
4-6
5-7
3-6
7-6
3-8
6-8
7-8

Таким образом, расчет математической модели маркетингового исследования показал:

Общее время исследования (Ткр) равно 25 дням.

Если начать исследование 01.01.01 г., то к 26 января исследование должно быть закончено.

Каждая отдельно взятая работа (i-j) дает ее исполнителю полную картину плановых ориентиров. Например, работы (5-7) по разработке рекламной политике выпускаемого товара является работой критического пути, «узким местом», т.е. она среди всех работ общего комплекса имеет только один срок начала – 5 января и не имеет резервов во времени. А работу, например, (3-8) по разработке торговой марки товара можно начать 9 января, а можно 21 января, и при этом окончательный срок всего комплекса работ не изменится, т.е. эта работа имеет резерв 12 дней, что говорит о более «выгодных» условиях для исполнителей этой работы.

 

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

 

 

Теорема 7

 

Если продолжительность работы (ij) увеличить на величину R^п_ij, то:

_a) Т^р.н._jk^* = Т^р.н._jk + R_j

_b) R^п_jk^* = R^п_jk - R_j

_c) T^п.о._si^* = T^п.о._si - R_i

_d) R^п_si^* = R^п_si - R_i

 

 

Рис.1.15.

 

Теорема 8. Если продолжительность работы (ij) увеличить на величину, подчиненную следующим ограничениям, то:

 

α ≤ R^c_ij => Т^р.н._jk = const

 

α >R^c_ij => Т^р.н._jk^* = Т^р.н._jk + (α -R^c_ij)

 

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

 

Например, по результатам табл.1.4. можно сказать, что работа (2-4)имеет два резерва: R^п(2-4) = 9; R^c(2-4) = 6. Это значит, что максимально возможно увеличить продолжительность работы на 9 дней и при этом Ткр не изменится, но работа, которая непосредственно следует за (2-4), а именно (4-6), изменит свой первоначальный ранне возможный срок начала на 3 единицы, так как α=9; α -R^c(ij) =9-6 =3. Если бы работа (2-4) увеличивалась по продолжительности ровно на величину свободного резерва, т.е. на R^c(2-4) = 6 дней, то можно было бы утверждать (согласно теореме 7), что Т^р.н._4-6 не изменилось бы.

Таким образом, все резервы работ являются для исполнителя инструментом управления ходом выполнения работ.