Алгоритм расчета резервов времени

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

Максимальное время задержки выполнения операции (x,y) не оказывающее влияние на время выполнения всего проекта называется полным резервом времени операции (x,y). Полный резерв времени операции (x,y) рассчитывается по формуле:

ПРВ(x,y)=L(y)-E(x)-t(x,y).

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

Резерв времени операции (x,y), не накладывающий временных ограничений на последующие операции, называется свободным резервом времени и рассчитывается по формуле:

СРВ(x,y)=E(y)-E(x)-t(x,y).

Если время выполнение операции операция (x,y) будет задержано на величину CРВ(x,y), то это наложит временные ограничения на все предшествующие операции.

Резерв времени операции (x,y), не накладывающий никаких временных ограничений ни на одну другую операцию проекта называется независимым резервом времени и рассчитывается по формуле:

НРВ(x,y)=E(y)-L(x)-t(x,y).

Очевидно, что для резервов времени каждой операции (x,y) выполняется отношение:

ПРВ(x,y)³СРВ(x,y)³НРВ(x,y).

Для критических операций (x,y) выполняется:

ПРВ(x,y)=СРВ(x,y)=НРВ(x,y)=0.

Расчет всех резервов времени сетевого графика рассмотренного в разделе 7.5.2 (см. рис.7.24) сведен в табл.7.3. Строки таблицы, соответствующие критическим операциям выделены серым цветом.

Таблица 7.3

Расчет резервов времени

Операция	Резервы времени выполнения операции
полный	свободный	независимый
(1,2)	4-0-4=0	4-0-4=0	4-0-4=0
(1,3)	7-0-3=4	5-0-3=2	5-0-3=2
(1,4)	10-0-4=6	4-0-4=0	4-0-4=0
(2,3)	7-4-1=2	5-4-1=0	5-4-1=0
(2,5)	11-4-7=0	11-4-7=0	11-4-7=0
(2,7)	16-4-8=4	16-4-8=4	16-4-8=4
(3,5)	11-5-4=2	11-5-4=2	11-7-4=0
(4,6)	12-4-2=6	12-4-2=6	12-10-2=0
(5,6)	12-11-1=0	12-11-1=0	12-11-1=0
(5,7)	16-11-3=2	16-11-3=2	16-11-3=2
(6,7)	16-12-4=0	16-12-4=0	16-12-4=0

Вопросы для повторения

1. Алгоритмы поиска элемента в неупорядоченном массиве.
2. Алгоритм поиска элемента в упорядоченном массиве.
3. Назначение и идея фонетического поиска.
4. Задача сортировки. Алгоритмы сортировки массива.
5. Сортировка массива методом пузырька.
6. Сортировка массива вставками.
7. Сортировка массива выбором.
8. Пирамидальная сортировка массива.
9. Быстрая сортировка массива.
10. Сортировка слиянием.
11. Поиск на графах. Поиск в глубину.
12. Поиск на графах. Поиск в ширину.
13. Топологическая сортировка графа.
14. Постановка задачи сетевого планирования.
15. Алгоритм расчета наиболее ранних сроков наступления событий.
16. Алгоритм расчета наиболее поздних сроков наступления событий.
17. Алгоритм расчета резервов времени.

Резюме по теме

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

Литература

Рекомендуемая основная литература

1. Шмидский Я.К. Программирование на языке C/C++: Самоучитель [Текст]. - Диалектика, 2004.
2. Подбельский В.В. Программирование на языке Си [Текст]. - Финансы и статистика, 2001
3. Ахо А., Хопкрофт Дж., Ульман Дж. Структуры данных и алгоритмы [Текст]. - Издательский дом «Вильямс», 2001.

Рекомендуемая дополнительная литература

1. Дейл Н. Программирование на С++ [Текст]. - ДМК, 2000.
2. Савич У. Программирование на C++ [Текст].- Питер : BHV, 2004.
3. Кнут Д.Э. Искусство программирования = The Art of Computer Programming [Текст].- Вильямс, 2000.
4. Арсак Ж. Программирование игр и головоломок [Текст].- Наука, 1990.
5. Муромцев В.В. Теория экономических информационных систем [Электронный ресурс]. - Белгород, БелГУ,2007.
6. Муромцев В.В.Теория экономических информационных систем [Текст].- Белгород, БелГУ, 2007.
7. Муромцев В.В.Алгоритмы на графах. [Электронный ресурс]. - Белгород, БИИММАП, 2000.
8. Муромцев В.В.Методические указания к лабораторным работам по курсу "Дискретная математика" [Электронный ресурс].- Белгород, БТИСМ, 1993.

[1] Если из контекста ясно, что рассматривается орграф, то ради сокращения речи термин "граф" употребляется вместо термина "орграф".

[2] При реализации на ЭВМ вместо бесконечности используют максимально возможное значение типа используемого для элементов матрицы.

[3] Вместо нуля можно использовать любое число, не использующееся для нумерации вершин дерева.