Лекция

Модели сетевого планирования

1. Основные понятия и определения

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

За рубежом система СПУ известна как система PERT (program Evaluation and review Technique – метод анализа и оценки программ) или CPM (Critical Path Method – метод критического пути).

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

Математический аппарат СМ – теория графов.

Граф – это совокупность двух конечных множеств: множества точек (х₁, х₂, …, x_n), которые называются вершинами, и множества пар вершин, которые называются ребрами.

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

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

Основные понятия СМ: событие, работа, путь.

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

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

Работа не может начаться раньше, чем свершится начальное событие. Каждая работа имеет свою длительность t(i, j)=t_ij. Работы на графах обозначаются дугами (стрелками), фиктивные работы (t_ij^фикт=0) – пунктирными стрелками.

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

Событие совершается в момент, когда заканчивается последняя работа, входящая в него. На графе события изображаются кружками, внутри которых записывается номер события. В моделях СПУ имеется одно исходное (начальное) событие (номер 0 или 1), одно конечное (завершающее) событие (номер N) и промежуточные события (номер i).

В графической интерпретации СМ работы представляются дугами, а события – вершинами графа.

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

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

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

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

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

Требования к СМ:

1. отсутствие событий с одинаковыми номерами;

2. для каждой работы (i, j) должно выполняться i < j.

3. наличие только одного начального и одного конечного события;

4. отсутствие циклов – замкнутых путей.

При выполнении этих требований можно приступать к вычислениям числовых характеристик СМ. Исходные числовые данные СМ представляются в виде таблицы длительности выполнения каждой работы.