<<
>>

Задача определения продолжительности проекта

(управление временем). Легко видеть, что продолжительность проекта определяется путем максимальной длины, называемым критическим путем. Методы поиска пути максимальной длины описаны выше.
Критический путь в сети на рисунке 6 выделен двойными дугами и равен 16.

Рис. 6. Поиск критического пути

Рис. 6. Поиск критического пути

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

Алгоритм 9. Предположим, что выполнение комплекса операций (проекта) начинается в нулевой момент времени. Обозначим Q0 - множество событий, не требующих выполнения ни одной из операций, то есть входы сети; Qi - множество событий, непосред-ственно предшествующих событию i, то есть множество вершин j сети, для которых существует дуга (j; i). Положим

t- = max j t- = max (t- + j).

' jeQo ' jQ 1

Величина t- называется ранним моментом (временем) свершения i-го события и характеризует время, раньше которого это событие произойти не может. Длина критического пути

T = max t-

i

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

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

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

U = max (lj + tj).

J^Ri

Положим t+ = T - lit i = 1, n .

Для завершения проекта за время T необходимо и достаточно,

чтобы событие i произошло не позднее момента t+, i = 1,n .

Полным резервом Ati события i называется разность между его поздним и ранним моментами свершения, то есть

At, = t+ - t:, i = 1,n.

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

<< | >>
Источник: В.Н. Бурков, Д.А. Новиков. ЭЛЕМЕНТЫ ТЕОРИИ ГРАФОВ. 2001

Еще по теме Задача определения продолжительности проекта:

  1. 4.3 Метод диагностического определения потребительной стоимости.
  2. 2.1 Постановка и математическая модель задачи
  3. Задача определения продолжительности проекта
  4. Определение 2.
  5. 2.3. Задача календарного планирования при учете совмещения агрегированных операций
  6. 3. СПЕЦИФИКА ДОГОВОРНЫХ ОТНОШЕНИЙ ВУПРАВЛЕНИИ ПРОЕКТАМИ
  7. Управление научными проектами.
  8. 1.2. Общая характеристика научных проектов
  9. 3.4.3. Организационный механизм реализации образовательного проекта
  10. Глава шестнадцатая. Социалистический проект
  11. 7.5. ОЦЕНКА ЭФФЕКТИВНОСТИ ИНВЕСТИЦИОННЫХ ПРОЕКТОВ РАЗВИТИЯ ЖЕЛЕЗНОДОРОЖНОГО ТРАНСПОРТА
  12. ЧАСТЬ IV В чем наша задача?
  13. Раздел  II. ПРАВО (Общая теория права. Право: общетеоретические понятияи определения)
  14. Определение стоимости инвестиционного проекта.
  15. Оценка эффективности инвестиционных проектов
  16. 2.3. Определение современной и будущей величины денежных потоков
  17. Планировка линии и определение рабочих мест, создание связанных и синхронизированныхпроцессов
  18. Задачи [31]
  19. Какие же существуют проекты календаря?