Модели

Рассмотрим следующую таблицу, описывающую проект: \r\nРабота Непосредственно предшествующие работы Время выпол-нения\r\nА — \'А\r\nВ — t„\r\nС В \'с\r\nD А, С \'D\r\nВ первом столбце указаны наименования всех работ проекта.

На основе этой таблицы может быть построено графическое описание проекта (рис. 1).

Рис. 1

На рис. 1 проект представлен в виде графа с вершинами 1,2, 3, 4 и дугами А, В, С, D. Каждая вершина графа отображает событие. Событие 1 означает начало выполнения проекта. Иногда такое событие обозначают буквой s (start). Событие 4 означает завершение проекта. Для обозначения такого события иногда используют букву f(finish). Любая работа проекта — это упорядоченная пара двух событии. Например, работа А есть упорядоченная пара событий (1, 3)(см. рис. 1). Работа D — упорядоченная пара событий (3,4). Событие проекта состоит в том, что завершены все работы, «входящие» в соответствующую вершину.

Рассмотрим другой проект, представленный следующей таблицей:

\r\nРабота Непосредственно предшествующие работы Время выпол-нения\r\nА — \'А\r\nВ — H\r\nС В \'с\r\nD А, С H\r\nЕ С H\r\nF С H\r\nG D,E,F Графическое описание проекта, построенное по этой таблице, имеет вид, показанный на рис. 2.

В этом графическом описании проекта, кроме тех работ, которые указаны в таблице, использованы две «фиктивные» работы (3, 4) и (5, 6). На рисунке они показаны штриховыми линиями. Эти работы не требуют времени на их выполнение и используются в графическом представлении проекта лишь для того, чтобы правильно отобразить взаимосвязь между работами. Получив графическое представление проекта, мы обеспечили себе возможность провести расчеты методом СРМ.

Определения:

Путь — последовательность взаимосвязанных работ, ведущая из одной вершины проекта в другую вершину. Например, {A, D, G} и {В, С, Е, С} — два различных пути, ведущие из вершины 1 в вершину 7 (см. рис. 2).

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

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

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

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

Пусть i и j — вершины, или события, проекта, (ij) — работа проекта, s — событие «начало проекта» (start), f— событие «окончание проекта» (finish), Т — длина критического пути.

Введем следующие обозначения:

t(ij) — время выполнения работы (i, j);

ES(ij) —наиболее раннее время начала работы (ij);

EF(i,j) —наиболее раннее время окончания работы (i,j);

LS(i,j) —наиболее позднее время начала работы (i,j),

LF(i,j) — наиболее позднее время окончания работы (ij),

Ei — наиболее раннее время наступления события i;

Li — наиболее позднее время наступления события i;

R(i,j) — полный резерв времени на выполнение работы (i,j) (время, на которое может быть отложена работа (i,j) без увеличения продолжительности выполнения всего проекта);

r(ij) — свободный резерв времени на выполнение работы (i,j) (время, на которое может быть отложена работа (i,j) без увеличения наиболее раннего времени Е наступления последующего события j).

Если (i,j) — работа проекта, то имеют место соотношения:

для любого j ES(i,j) = Е;

для любого i LF(i,j) = Lj.

Для того чтобы использовать метод СРМ для нахождения критического пути, необходимо для каждой работы (ij) определить наиболее раннее время начала и окончания работы (ES(i,j) и EF(i,j)) и наиболее позднее время начала и окончания работы (LS(ij) и LF(ij)).

Метод СРМ описывается следующими соотношениями:

ES(sJ) = 0 (1)

для любой работы (sj), выходящей из стартовой вершины 5 проекта;

Щи) = Щш + Чи)= еІ + hu)> (2)

т.е. наиболее раннее время окончания любой работы (ij) превышает наиболее раннее время начала этой работы (время наступления предшествующего события і) на время ее выполнения;

Щ<и) = т*хЩі,9) = Е1> (3)

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

Т = max Щ л = Ер (4)

т.е.

Щі.Л = Т\' (5)

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

Щи) = Щи) - ku) = Lj~4u) > (6)

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

Щ,я) = т{?Щя,»= 1я> (7)

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

-(8)

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

ru,j) = LJ - Щи) - Чи) = h - Щи) = LJ - Ei ~ Чи У (9)

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

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

Длина критического пути равна Т.

Если R(i,j) = 0, то работа (i,j) лежит на критическом пути;

если R(i,j) > 0, то работа (i,j) не лежит на критическом пути.

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

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