Лекции по "Развитию операционных систем"

Лекция 14.

 

п.14.  Элементы сетевого планирования.

 

14.1.  Сетевой график. Работа. Событие.

 

Теория графов нашла широкое применение в различных областях экономики, производства, психологии и т.д., т.е. для решения многих классов прикладных задач.

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

Существует несколько методов сетевого планирования. Так метод CPM (Critical Path Method – метод критического пути) используется для контроля выполнения проекта, когда оценки времени операций детерминированные (определены). Таким проектом может быть разработка нового производственного процесса; строительство предприятия, здания или сооружения; ремонт сложного оборудования и т.д.

Метод PERT (Program Evaluation and Review Technique – метод оценки обзора программ) применяется для контроля сроков выполнения проекта, для которых продолжительность выполнения всех или некоторых работ не удается определить точно. Он применяется при проектировании и внедрении новых систем, планировании научно-исследовательских и опытно-конструкторских разработок. [Тем, кто желает более подробно изучить метод PERT, можно порекомендовать следующие книги: 1)  Костевич Л.С. Исследование операций. Теория игр: учеб. пособие. – Минск: Выш.шк., 2008.  2)  Экономико-математические методы и модели: Учеб. пособие / Н.И. Холод, А.В. Кузнецов и др.; под общ. ред. А.В. Кузнецова. – Мн.: БГЭУ, 2000.]

 

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

Работа – это любые действия, трудовые процессы, сопровождающиеся затратами ресурсов или времени и приводящие к определенным результатам. На сетевых графиках работы изображают отрезками прямых линий с указанием направления, т.е. дугами. Договоримся, что работы будем обозначать an или , где i – начальная вершина дуги и j – конечная вершина. Рядом со стрелкой указываются числовые характеристики: время выполнения работы, расход ресурса, количество исполнителей и т.д. Также принято считать и те процессы, которые не требуют ни затрат времени, ни ресурсов. Такие процессы будем называть фиктивными работами. Они показывают, что одна работа не может совершаться раньше другой. На сетевых графиках фиктивные работы обычно изображают пунктирными стрелками.

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

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

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

 

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

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

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

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

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

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

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

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

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

 

Работа	Предшествующие ей работы	Продолжительность (дни)
а1 а2 а3 а4 а5 а6 а7	- - а1 а1, а2 а4 а4 а3, а5	2 4 3 2 5 7 3

 

Решение.  Работам a1 и a2 не предшествуют никакие работы, следовательно, на графике они изображаются дугами, выходящими из исходного события (1), которое означает момент начала выполнения проекта. Работе a3 предшествует работа a1, поэтому на графике дуга a3 непосредственно следует за дугой a1. Событие (2) означает момент окончания работы a1 и начала работ, которым она предшествует. Работе a4 предшествуют работы a1 и a2. На графике эта зависимость отражается с помощью введения фиктивной работы (2, 3). Моментом свершения события (3) будет момент, к которому будут выполнены работы a1 и a2 и может начинаться работа a4. Аналогично с учетом взаимосвязей изображаются на графике все остальные работы. Завершающее событие (6) означает момент выполнения всего проекта.

 

 

 

14.2.  Основные параметры сетевого графика.

 

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

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

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

 

Рассмотрим основные временные параметры свершения событий – это ранний и поздний сроки свершения событий, резерв времени события, которые находятся по соответствующим формулам.

Ранний срок tp(j) свершения события j - это самый ранний момент времени, к которому завершаются все работы, предшествующие этому событию:

,                        (14.2.1.)

где tp(i) - ранний срок свершения начального события работы (i, j); t(i, j) - продолжи-тельность работы (i, j). Предполагается, что tp(1)=tp(I)=0, tp(S)=tкр.

Поздний срок tп(i) свершения события i - такой предельный момент времени, после которого остается ровно столько времени, сколько необходимо для завершения всех работ, следующих за этим событием:

,                      (14.2.2.)

где tп(i) - поздний срок свершения конечного события работы (i, j). Для завершения события S предполагается, что tп(S)=tр(S)= tкр.

Резерв времени R(i) события i показывает, на какой предельно допустимый срок может задержаться свершение события i без нарушения срока наступления завер-шающего события:

.                                          (14.2.3.)

 

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

Ранний срок начала работы равен раннему сроку свершения события (i):

.                                          (14.2.4.)

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

.                                 (14.2.5.)

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

.                                            (14.2.6)

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

.                               (14.2.7.)

Полный резерв времени Rп(i,j) работы (i,j) - это максимально возможный запас времени, на который можно отсрочить начало работы или увеличить продолжительность  ее выполнения при условии, что весь комплекс работ будет завершен в критический срок:

.                            (14.2.8.)

Свободный резерв времени Rс(i,j) работы (i,j) -это максимальный запас времени, на которое можно отсрочить или (если она началась в свой ранний срок) увеличить ее продолжительность при условии, что не нарушатся ранние сроки начала всех последующих работ:

.                            (14.2.9.)

Критические работы, как и критические события, резервов не имеют.

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

1.  Проставляем в верхних секторах номера событий (в соответствии с ранжиро-ванием).

2.  Рассматриваем события  в порядке возрастания номеров, и, имея в виду, что tp(1)=0, по входящим в это событие работам определяем tp(i) и записываем в левом секторе.

3.  Начиная с конечного  события, для которого tп(n)= tкр (n – номер конечного события), для каждого события по выходящим из него работам определяем tп(i) и записываем в правом секторе.

4.  В нижнем секторе  записываем резерв времени события R(i).

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

 

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

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