Курсовая работа: Сетевые графики
🛑 👉🏻👉🏻👉🏻 ИНФОРМАЦИЯ ДОСТУПНА ЗДЕСЬ ЖМИТЕ 👈🏻👈🏻👈🏻
Многие крупные проекты, такие как строительство дома, изготовление станка, разработка автоматизированной системы бухгалтерского учета и т.д., можно разбить на большое количество различных операций (работ). Некоторые из этих операций могут выполняться одновременно, другие — только последовательно: одна операция после окончания другой. Например, при строительстве дома можно совместить во времени внутренние отделочные работы и работы по благоустройству территории, однако возводить стены можно только после того, как будет готов фундамент.
Задачи планирования работ по осуществлению некоторого проекта состоят в определении времени возможного окончания как всего проекта в целом, так и отдельных работ, образующих проект; в определении резервов времени для выполнения отдельных работ; в определении критических работ, то есть таких работ, задержка в выполнении которых ведет к задержке выполнения всего проекта в целом; в управлении ресурсами, если таковые имеются и т.п.
Пусть некоторый проект W состоит из работ V 1
,...,V n
; для каждой работы V k
, известно, или может быть достаточно точно оценено время ее выполнения t(V k
). Кроме того, для каждой работы V k
известен, возможно пустой, список ПРЕДШ(V k
) работ, непосредственно предшествующих выполнению работы V k
. Иначе говоря, работа V k
может начать выполняться только после завершения всех работ, входящих в список ПРЕДШ(V k
).
Для удобства, в список работ проекта W добавим две фиктивные работы s и p, где работа s обозначает начало всего проекта W. а работа p — завершение работ по проекту W. При этом будем считать, что работа s предшествует всем тем работам vÎW, для которых список ПРЕДШ(v) пуст, иначе говоря, для всех таких работ vÎW положим ПРЕДШ(v)={s}. Положим далее ПРЕДШ(s) =Æ, ПРЕДШ(p)={vÎW: v не входит ни в один список ПРЕДШ(w)}, то есть считаем, что работе p предшествуют все те работы, которые могут выполняться самыми последними. Время выполнения работ s и p естественно положить равными нулю: t(s)=t(p)=0.
Весь проект W теперь удобно представить в виде сети G=(V,E,c). Ориентированный взвешенный граф G=(V,E,c) называется сетью. Сеть может быть представлена матрицей весов дуг, массивами смежностей СЛЕД или ПРЕДШ, или списками СЛЕД[v] или ПРЕДШ[v]. При этом записи в списках смежности состоят из трех компонент: поля имени узла, поля веса соответствующей дуги и поля ссылки на следующую запись), где сеть G=(V,E,c) определим по правилам:
1. V=W, то есть множеством узлов объявим множество работ;
2. E={(v,w) : vÎПРЕДШ(w)}, то есть отношение предшествования задает дуги в сети;
Так построенную сеть G часто называют сетевым графиком выполнения работ по проекту W. Легко видеть, что списки смежностей этой сети ПРЕДШ[v] совпадают с заданными для проекта списками предшествующих работ ПРЕДШ(v).
Понятно, что сетевой график любого проекта не должен содержать контуров. Действительно, пусть узлы V k
1
,V k
2
,...,V kr
=V k
1
образуют контур в сети G. Это означает, что работа V k
2
не может начаться раньше, чем будет завершена работа V k
1
, работа V k
3
— раньше, чем завершится работа V k
2
, и т.д., и, наконец, V kr
= V k
1
— раньше, чем будет завершена работа V kr
-1
. Но тогда никакая из работ V k
1
,...,V kr
никогда не сможет быть выполнена. А каждый реальный проект должен допускать возможность его завершения. Следовательно, в сетевом графике нет контуров.
Отсутствие контуров в сети G позволяет пронумеровать работы проекта W таким образом, чтобы для каждой дуги (V i
,V j
) сети G выполнялось условие i= РВЫП(V n
+1
).
Через ПВЫП(v) (соответственно ПНАЧ(v)) обозначим наиболее поздний допустимый срок выполнения (начала) работы v, то есть такой срок, который не увеличивает срок Т реализации всего проекта.
Значения возможных и допустимых сроков выполнения работ позволяют определить резервы времени для выполнения той или иной работы. Полный резерв (иногда его называют суммарный) времени выполнения работ определяется по формуле:
Значение PE3EPB(v) равно максимальной задержке в выполнении работы v, не влияющей на плановый срок Т. Понятно, что справедливо и такое равенство: РЕЗЕРВ(v)=ПВЫП(v)-РВЫП(v).
Работы, имеющие нулевой резерв времени, называются критическими. Через любую такую работу проходит некоторый максимальный s-p-путь в сети G. Критические работы характеризуются тем, что любая задержка в их выполнении автоматически ведет к увеличению времени выполнения всего проекта.
Приведем запись алгоритма, непосредственно вычисляющего характеристики ПВЫП и ПНАЧ.
Данные: Сетевой график G работ V, заданный списками ПРЕДШ(v), vÎV, плановый срок окончания проекта – Т.
Результаты: Наиболее поздние допустимые сроки выполнения и начала работ ПВЫП(v) и ПНАЧ(v).
Шаг 1. Объявить для всех работ vÎV значение наиболее позднего срока выполнения работ равным Т – значению планового срока окончание проекта и вершину v p
фиктивной работы p объявить текущей v k
.
Шаг 2. Присвоить значение ПНАЧ текущей работы v k
равным значению ПВЫП работы и вычесть время выполнения текущей работы.
Шаг 3. Присвоить значению ПВЫП(v) для всех работ vÎПРЕДШ(v) предшествующих текущей работе v k
минимальное значение из значений ПВЫП выполнения роботы v или ПНАЧ выполнения текущей работы v k
, если таковых нет перейти в Шаг 4.
Шаг 4. Если имеется предыдущая вершина (работа) к текущей, то объявить её текущей, иначе перейти в Шаг 6.
Шаг 6. Выдать наиболее поздние допустимые сроки выполнения и начала работ ПВЫП(v) и ПНАЧ(v), конец работы алгоритма.
Проиллюстрируем работу приведенных алгоритмов на следующих примерах:
Пример 1: Проект гаража для стоянки автопогрузчиков.
Масляная окраска ворот и профнастила
Уборка строительного мусора после строит.
Рис 1. Проект гаража для стоянки автопогрузчиков.
Найдем значения наиболее раннего начала и выполнения работ проекта посредством алгоритма 1. Работу алгоритма изложим в виде последовательности выполняемых шагов.
Объявление значений РНАЧ(v) и РВЫП(v), vÎV равными нулю. Текущая вершина v k
=1.
РВЫП(1)=РНАЧ(1)+t(1). {РНАЧ(1) стало равным 0}
РНАЧ(2)=МАКС{РВЫП(1),РНАЧ(2)} {РНАЧ(2) стало равным 0}
РВЫП(2)=РНАЧ(2)+t(2) {РВЫП(2) стало равным 5}.
РНАЧ(3)=МАКС{РВЫП(2),РНАЧ(3)} {РНАЧ(3) стало равным 5}
РВЫП(3)=РНАЧ(3)+t(3) {РВЫП(3) стало равным 35}.
РНАЧ(4)=МАКС{РВЫП(3),РНАЧ(4)}{РНАЧ(4) стало равным 35}
РВЫП(4)=РНАЧ(4)+t(4) {РВЫП(4) стало равным 50}.
РНАЧ(5)=МАКС{РВЫП(3),РНАЧ(5)}{РНАЧ(5) стало равным 35}
РВЫП(5)=РНАЧ(5)+t(5) {РВЫП(5) стало равным 47}.
РНАЧ(6)=МАКС{РВЫП(4),РНАЧ(6)}{РНАЧ(6) стало равным 50}
РВЫП(6)=РНАЧ(6)+t(6) {РВЫП(6) стало равным 55}.
РНАЧ(7)=МАКС{РВЫП(5),РНАЧ(7)}{РНАЧ(7) стало равным 47}
РНАЧ(7)=МАКС{РВЫП(6),РНАЧ(7)}{РНАЧ(7) стало равным 55}
РВЫП(7)=РНАЧ(7)+t(7) {РВЫП(7) стало равным 65}.
РНАЧ(8)=МАКС{РВЫП(7),РНАЧ(8)} {РНАЧ(8) стало равным 65}
РВЫП(8)=РНАЧ(8)+t(8) {РВЫП(8) стало равным 68}.
РНАЧ(9)=МАКС{РВЫП(8),РНАЧ(9)}{РНАЧ(9) стало равным 68}
РВЫП(9)=РНАЧ(9)+t(9) {РВЫП(9) стало равным 71}.
РНАЧ(10)=МАКС{РВЫП(7),РНАЧ(10)}{РНАЧ(10) стало равным 65}
РНАЧ(11)=МАКС{РВЫП(9),РНАЧ(11)}{РНАЧ(11) стало равным 71}
РНАЧ(11)=МАКС{РВЫП(10),РНАЧ(11)}{РНАЧ(11) стало равным 71}
Конец работы алгоритма, выдача значений наиболее раннего начала и выполнения работ.
Таблица результатов работы алгоритма.
Получили, что минимальное время, требуемое для выполнения проекта равно Т=РВЫП(11), Т=71. Теперь найдем посредством алгоритма 2 значение времени наиболее позднего начала и выполнения работ. Работу алгоритма изложим в виде последовательности выполняемых шагов.
Объявление значений ПВЫП(v), vÎV равным Т.
ПНАЧ(11)=ПВЫП(11)-t(11) {ПНАЧ(11) стало равным 71}.
ПВЫП(9)=МИН{ПВЫП(9),ПНАЧ(11)}{ПВЫП(9) стало равным 71}
ПВЫП(10)=МИН{ПВЫП(10),ПНАЧ(11)}{ПВЫП(10) стало равным 71}
ПНАЧ(10)=ПВЫП(10)-t(10) {ПНАЧ(10) стало равным 68}
ПВЫП(7)=МИН{ПВЫП(7),ПНАЧ(10)}{ПВЫП(7) стало равным 68}
ПНАЧ(9)=ПВЫП(9)-t(9) {ПНАЧ(9) стало равным 68}
ПВЫП(8)=МИН{ПВЫП(8),ПНАЧ(9)}{ПВЫП(8) стало равным 68}
ПНАЧ(8)=ПВЫП(8)-t(8) {ПНАЧ(8) стало равным 65}
ПВЫП(7)=МИН{ПВЫП(7),ПНАЧ(8)}{ПВЫП(7) стало равным 65}
ПНАЧ(7)=ПВЫП(7)-t(7) {ПНАЧ(7) стало равным 55}
ПВЫП(5)=МИН{ПВЫП(5),ПНАЧ(7)}{ПВЫП(5) стало равным 55}
ПВЫП(6)=МИН{ПВЫП(6),ПНАЧ(7)}{ПВЫП(6) стало равным 55}
ПНАЧ(6)=ПВЫП(6)-t(6) {ПНАЧ(6) стало равным 50}
ПВЫП(4)=МИН{ПВЫП(4),ПНАЧ(6)}{ПВЫП(5) стало равным 50}
ПНАЧ(5)=ПВЫП(5)-t(5) {ПНАЧ(5) стало равным 43}
ПВЫП(3)=МИН{ПВЫП(3),ПНАЧ(5)}{ПВЫП(3) стало равным 43}
ПНАЧ(4)=ПВЫП(4)-t(4) {ПНАЧ(4) стало равным 35}
ПВЫП(3)=МИН{ПВЫП(3),ПНАЧ(4)}{ПВЫП(3) стало равным 35}
ПНАЧ(3)=ПВЫП(3)-t(3) {ПНАЧ(3) стало равным 5}
ПВЫП(2)=МИН{ПВЫП(2),ПНАЧ(3)}{ПВЫП(2) стало равным 5}
ПНАЧ(2)=ПВЫП(2)-t(2) {ПНАЧ(2) стало равным 0}
ПВЫП(1)=МИН{ПВЫП(1),ПНАЧ(2)}{ПВЫП(1) стало равным 0}
ПНАЧ(1)=ПВЫП(1)-t(1) {ПНАЧ(1) стало равным 0}
Конец работы алгоритма, выдача значений времени наиболее позднего начала и выполнения работ.
Дадим таблицу результатов работы алгоритма с результатами предыдущего алгоритма и сосчитаем резерв времени для каждой работы по формуле PE3EPB(v)=ПНАЧ(v)-PHAЧ(v) или РЕЗЕРВ(v)=ПВЫП(v)-РВЫП(v).
Из таблицы видно, что критическими работами являются 1, 2, 3, 4, 6, 7, 8, 9, 11, которые и образуют в сети G критический путь. Расчеты выполнены при Т=71.
Пример 2: Проект склада сажи и других материалов в помещение производственного цеха.
Монтаж металлоконструкций нижней обвязки каркаса
Обшивка стен и кровли волнистым листом
Устройство асфальтобетонных покрытий
Рис 2. Проект склада сажи и других материалов в помещение производственного цеха.
Найдем значения наиболее раннего начала и выполнения работ проекта посредством алгоритма 1. Работу алгоритма изложим в виде последовательности выполняемых шагов.
Объявление значений РНАЧ(v) и РВЫП(v), vÎV равным нулю.
РНАЧ(2)=МАКС{РВЫП(1),РНАЧ(2)} {РНАЧ(2) стало равным 0}
РВЫП(2)=РНАЧ(2)+t(2) {РВЫП(2) стало равным 5}.
РНАЧ(3)=МАКС{РВЫП(2),РНАЧ(3)} {РНАЧ(3) стало равным 5}
РВЫП(3)=РНАЧ(3)+t(3) {РВЫП(3) стало равным 8}.
РНАЧ(4)=МАКС{РВЫП(3),РНАЧ(4)} {РНАЧ(4) стало равным 8}
РВЫП(4)=РНАЧ(4)+t(4) {РВЫП(4) стало равным 18}.
РНАЧ(5)=МАКС{РВЫП(4),РНАЧ(5)} {РНАЧ(5) стало равным 18}
РВЫП(5)=РНАЧ(5)+t(5) {РВЫП(5) стало равным 23}.
РНАЧ(6)={РВЫП(2),РНАЧ(6)} {РНАЧ(6) стало равным 5}
РВЫП(6)=РНАЧ(6)+t(6) {РВЫП(6) стало равным 12}.
РНАЧ(7)=МАКС{РВЫП(6),РНАЧ(7)} {РНАЧ(7) стало равным 12}
РВЫП(7)=РНАЧ(7)+t(7) {РВЫП(7) стало равным 19}.
РНАЧ(8)=МАКС{РВЫП(6),РНАЧ(8)} {РНАЧ(8) стало равным 12}
РВЫП(8)=РНАЧ(8)+t(8) {РВЫП(8) стало равным 24}.
РНАЧ(9)=МАКС{РВЫП(7),РНАЧ(9)} {РНАЧ(9) стало равным 19}
РВЫП(9)=РНАЧ(9)+t(9) {РВЫП(9) стало равным 24}.
РНАЧ(10)=МАКС{РВЫП(8),РНАЧ(10)} {РНАЧ(10) стало равным 24}
РВЫП(10)=РНАЧ(10)+t(10) {РВЫП(10) стало равным 29}.
РНАЧ(11)=МАКС{РВЫП(9),РНАЧ(11)} {РНАЧ(11) стало равным 24}
РНАЧ(11)=МАКС{РВЫП(10),РНАЧ(10)}{РНАЧ(11) стало равным 29}
РВЫП(11)=РНАЧ(11)+t(11) {РВЫП(11) стало равным 29}.
Конец работы алгоритма, выдача значений наиболее раннего начала и выполнения работ.
Таблица результатов работы алгоритма.
Получили, что минимальное время, требуемое для выполнения проекта равно Т=РВЫП(11), Т=29. Теперь найдем посредством алгоритма 2 значение времени наиболее позднего начала и выполнения работ. Работу алгоритма изложим в виде последовательности выполняемых шагов.
Объявление значений ПВЫП(v), vÎV равным Т.
ПНАЧ(11)=ПВЫП(11)-t(11) {ПНАЧ(11) стало равным 29}.
ПВЫП(9)=МИН{ПВЫП(9),ПНАЧ(11)}{ПВЫП(9) стало равным 29}
ПВЫП(10)=МИН{ПВЫП(10),ПНАЧ(11)}{ПВЫП(10) стало равным 29}.
ПНАЧ(10)=ПВЫП(10)-t(10) {ПНАЧ(10) стало равным 24}.
ПВЫП(8)=МИН{ПВЫП(8),ПНАЧ(10)}{ПВЫП(8) стало равным 24}
ПНАЧ(9)=ПВЫП(9)-t(9) {ПНАЧ(9) стало равным 24}.
ПВЫП(7)=МИН{ПВЫП(7),ПНАЧ(9)}{ПВЫП(7) стало равным 24}.
ПНАЧ(8)=ПВЫП(8)-t(8) {ПНАЧ(8) стало равным 12}.
ПВЫП(6)=МИН{ПВЫП(6),ПНАЧ(8)}{ПВЫП(6) стало равным 12}.
ПНАЧ(7)=ПВЫП(7)-t(7) {ПНАЧ(7) стало равным 17}.
ПВЫП(6)=МИН{ПВЫП(6),ПНАЧ(7)}{ПВЫП(6) стало равным 12}.
ПНАЧ(6)=ПВЫП(6)-t(6) {ПНАЧ(6) стало равным 5}.
ПВЫП(2)=МИН{ПВЫП(2),ПНАЧ(6)}{ПВЫП(2) стало равным 5}.
ПНАЧ(5)=ПВЫП(5)-t(5) {ПНАЧ(5) стало равным 24}.
ПВЫП(4)=МИН{ПВЫП(4),ПНАЧ(5)}{ПВЫП(4) стало равным 24}.
ПНАЧ(4)=ПВЫП(4)-t(4) {ПНАЧ(4) стало равным 14}.
ПВЫП(3)=МИН{ПВЫП(3),ПНАЧ(4)}{ПВЫП(3) стало равным 14}.
ПНАЧ(3)=ПВЫП(3)-t(3) {ПНАЧ(3) стало равным 11}.
ПВЫП(2)=МИН{ПВЫП(2),ПНАЧ(3)}{ПВЫП(2) стало равным 5}.
ПНАЧ(2)=ПВЫП(2)-t(2) {ПНАЧ(2) стало равным 0}.
ПВЫП(1)=МИН{ПВЫП(1),ПНАЧ(2)}{ПВЫП(1) стало равным 0}.
ПНАЧ(1)=ПВЫП(1)-t(1) {ПНАЧ(1) стало равным 0}.
Конец работы алгоритма, выдача значений времени наиболее позднего начала и выполнения работ.
Дадим таблицу результатов работы алгоритма с результатами предыдущего алгоритма и сосчитаем резерв времени для каждой работы по формуле PE3EPB(v)=ПHAЧ(v)-PHAЧ(v) или РЕЗЕРВ(v)=ПВЫП(v)-РВЫП(v).
Из таблиы видно, что критическими работами являются 1, 2, 6, 8, 10, 11, которые и образуют в сети G критический путь. Расчеты выполнены при Т=29.
Пример 3: Проект водоснабжения и наружной канализации при застройки квартала по ул. Токарей-Синяева в г. Екатеринбурге.
Разработка грунта экскаваторами с ковшом 0.5 м 3
с погрузкой на автомобили-самосвалы.
Зачистка дна и стенок с выкидкой грунта.
Монтаж плит перекрытий из легкого бетона.
Пробивка в бетонных стенах и полах отверстий.
Оклейка плит рубероидом и гидроизолом на нефтебитуме в 1 слой.
Заделка сальников при проходе труб через фундаменты или стены подвалов.
Рис 3. Проект водоснабжения и наружной канализации при застройки квартала по ул. Токарей-Синяева в г. Екатеринбурге.
Найдем значения наиболее раннего начала и выполнения работ проекта посредством алгоритма 1. Работу алгоритма изложим в виде последовательности выполняемых шагов.
Объявление значений РНАЧ(v) и РВЫП(v), vÎV равным нулю.
РНАЧ(2)=МАКС{РВЫП(1),РНАЧ(2)}{РНАЧ(2) стало равным 0}
РВЫП(2)=РНАЧ(2)+t(2) {РВЫП(2) стало равным 16}.
РНАЧ(3)=МАКС{РВЫП(2),РНАЧ(3)}{РНАЧ(2) стало равным 16}
РВЫП(3)=РНАЧ(3)+t(3) {РВЫП(3) стало равным 26}.
РНАЧ(4)=МАКС{РВЫП(1),РНАЧ(4)}{РНАЧ(4) стало равным 0}
РВЫП(4)=РНАЧ(4)+t(4) {РВЫП(4) стало равным 32}.
РНАЧ(5)=МАКС{РВЫП(3),РНАЧ(5)}{РНАЧ(5) стало равным 26}
РВЫП(5)=РНАЧ(5)+t(5) {РВЫП(5) стало равным 47}.
РНАЧ(6)=МАКС{РВЫП(5),РНАЧ(6)}{РНАЧ(6) стало равным 47}
РВЫП(6)=РНАЧ(6)+t(6) {РВЫП(6) стало равным 52}.
РНАЧ(7)=МАКС{РВЫП(5),РНАЧ(7)}{РНАЧ(7) стало равным 47
РВЫП(7)=РНАЧ(7)+t(7) {РВЫП(7) стало равным 61}.
РНАЧ(8)=МАКС{РВЫП(5),РНАЧ(8)}{РНАЧ(8) стало равным 47}
РВЫП(8)=РНАЧ(8)+t(8) {РВЫП(8) стало равным 57}.
РНАЧ(9)=МАКС{РВЫП(6),РНАЧ(9)}{РНАЧ(9) стало равным 52}
РВЫП(9)=РНАЧ(9)+t(9) {РВЫП(9) стало равным }.
РНАЧ(10)=МАКС{РВЫП(9),РНАЧ(10)}{РНАЧ(10) стало равным 59}
РВЫП(10)=РНАЧ(10)+t(10) {РВЫП(10) стало равным 64}.
РНАЧ(11)=МАКС{РВЫП(7),РНАЧ(11)}{РНАЧ(11) стало равным 61}
РНАЧ(11)=МАКС{РВЫП(8),РНАЧ(11)}{РНАЧ(11) стало рвным 61}
РНАЧ(11)=МАКС{РВЫП(10),РНАЧ(11)}{РНАЧ(11) стало равным 64}
РВЫП(11)=РНАЧ(11)+t(11) {РВЫП(11) стало равным 64}.
Конец работы алгоритма, выдача значений наиболее раннего начала и выполнения работ.
Таблица результатов работы алгоритма.
Получили, что минимальное время, требуемое для выполнения проекта равно Т=РВЫП(11), Т=64. Теперь найдем посредством алгоритма 2 значение времени наиболее позднего начала и выполнения работ. Работу алгоритма изложим в виде последовательности выполняемых шагов.
Объявление значений ПВЫП(v), vÎV равным Т.
ПНАЧ(11)=ПВЫП(11)-t(11) {ПНАЧ(11) стало равным 64}.
ПВЫП(7)=МИН{ПВЫП(7),ПНАЧ(11)}{ПВЫП(7) стало равным 64}
ПВЫП(8)=МИН{ПВЫП(8),ПНАЧ(11)}{ПВЫП(8) стало равным 64}
ПВЫП(10)=МИН{ПВЫП(10),ПНАЧ(10)}{ПВЫП(9) стало равным 64}.
ПНАЧ(10)=ПВЫП(10)-t(10) {ПНАЧ(10) стало равным 59}.
ПВЫП(9)=МИН{ПВЫП(9),ПНАЧ(10)} {ПВЫП(9) стало равным 59}.
ПНАЧ(9)=ПВЫП(9)-t(9) {ПНАЧ(9) стало ранвым 52}.
ПВЫП(6)=МИН{ПВЫП(6),ПНАЧ(9)}{ПВЫП(6) стало равным 52}.
ПНАЧ(8)=ПВЫП(8)-t(8) {ПНАЧ(8) стало равным 54}.
ПВЫП(5)=МИН{ПВЫП(5),ПНАЧ(8)}{ПВЫП(5) стало равным 54}.
ПНАЧ(7)=ПВЫП(7)-t(7) {ПНАЧ(7) стало равным 50}.
ПВЫП(5)=МИН{ПВЫП(5),ПНАЧ(7)}{ПВЫП(5) стало равным 50}
ПВЫП(4)=МИН{ПВЫП(4),ПНАЧ(7)}{ПВЫП(4) стало равным 50}.
ПНАЧ(6)=ПВЫП(6)-t(6) {ПНАЧ(6) стало равным 47}.
ПВЫП(5)=МИН{ПВЫП(5),ПНАЧ(6)}{ПВЫП(5) стало равным 47}.
ПНАЧ(5)=ПВЫП(5)-t(5) {ПНАЧ(5) стало равным 26}.
ПВЫП(3)=МИН{ПВЫП(3),ПНАЧ(5)}{ПВЫП(3) стало равным 26}.
ПНАЧ(4)=ПВЫП(4)-t(4) {ПНАЧ(4) стало равным 18}.
ПВЫП(1)=МИН{ПВЫП(1),ПНАЧ(4)}{ПВЫП(1) стало равным 18}.
ПНАЧ(3)=ПВЫП(3)-t(3) {ПНАЧ(3) стало равным 16}.
ПВЫП(2)=МИН{ПВЫП(2),ПНАЧ(3)}{ПВЫП(2) стало равным 16}.
ПНАЧ(2)=ПВЫП(2)-t(2) {ПНАЧ(2) стало равным 0}.
ПВЫП(1)=МИН{ПВЫП(1),ПНАЧ(2)}{ПВЫП(1) стало равным 0}.
ПНАЧ(1)=ПВЫП(1)-t(1) {ПНАЧ(1) стало равным 0}.
Конец работы алгоритма, выдача значений времени наиболее позднего начала и выполнения работ.
Дадим таблицу результатов работы алгоритма с результатами предыдущего алгоритма и сосчитаем резерв времени для каждой работы по формуле PE3EPB(v)=ПHAЧ(v)-PHAЧ(v) или РЕЗЕРВ(v)=ПВЫП(v)-РВЫП(v).
Из таблицы видно, что критическими работами являются 1, 2, 3, 5, 6, 9, 10, 11, которые и образуют в сети G критический путь. Расчеты выполнены при Т=64.
1. Асанов М. О. «Дискретная оптимизация», УралНАУКА, Екатеринбург 1998.
Название: Сетевые графики
Раздел: Рефераты по информатике
Тип: курсовая работа
Добавлен 03:08:18 13 января 2010 Похожие работы
Просмотров: 30
Комментариев: 22
Оценило: 2 человек
Средний балл: 5
Оценка: неизвестно Скачать
Срочная помощь учащимся в написании различных работ. Бесплатные корректировки! Круглосуточная поддержка! Узнай стоимость твоей работы на сайте 64362.ru
Если Вам нужна помощь с учебными работами, ну или будет нужна в будущем (курсовая, дипломная, отчет по практике, контрольная, РГР, решение задач, онлайн-помощь на экзамене или "любая другая" учебная работа...) - обращайтесь: https://clck.ru/P8YFs - (просто скопируйте этот адрес и вставьте в браузер) Сделаем все качественно и в самые короткие сроки + бесплатные доработки до самой сдачи/защиты! Предоставим все необходимые гарантии.
Привет студентам) если возникают трудности с любой работой (от реферата и контрольных до диплома), можете обратиться на FAST-REFERAT.RU , я там обычно заказываю, все качественно и в срок) в любом случае попробуйте, за спрос денег не берут)
Да, но только в случае крайней необходимости.
Курсовая работа: Сетевые графики
Итоговое Сочинение 100 Баллов Пример
Курсовая работа по теме Распространение антициклонов на территории Беларуси
Реферат по теме Питание и контроль за массой тела при различной двигательной активности
Реферат: Трудовой договор, его значение и особенности в современных экономических условиях. Скачать бесплатно и без регистрации
Реферат На Тему Жилишно-Комуннальное Хозяйство
Курсовая работа по теме Технология работы сортировочной станции
Профилактика Повышенной Чувствительности Твердых Тканей Зубов Реферат
Реферат: Глобальными и региональными процессами социального и экономического разв ития прогнозно-аналитический центр год семьи, Год молодёжи… Год учителя: опять чиновничье пустословие?
Реферат Обработка На Протяжных Станках
Реферат: Что можно сделать при помощи генетических модификаций
Курсовая работа по теме Характеристика лексики А.С. Пушкина в повести "Дубровский", при сопоставлении русского с белорусским переводом
Сочинение О Новых Профессиях
Реферат по теме Особенности, принципы, методы и структура управления природопользованием
Контрольные Работы Со Спецификацией
Учебное пособие: История искусств Западноевропейское искусство
Доклад: Теория установки (Д.Н.Узнадзе)
Как Делать Заключение В Курсовой
Черная Курица Мини Сочинение
Дипломная работа по теме Управління банківськими ризиками (на прикладі ВАТ КБ "Іпобанк")
Реферат: Организационная структура компании
Реферат: Socrates Vs Gilgamesh Essay Research Paper Sarah
Реферат: Female Genital Mutilation Essay Research Paper Female
Реферат: Значение банковской системы в современной экономике