Сетевые графики

Курсовой проект - Компьютеры, программирование

Другие курсовые по предмету Компьютеры, программирование

Скачать Бесплатно!
Для того чтобы скачать эту работу.
1. Пожалуйста введите слова с картинки:

2. И нажмите на эту кнопку.
закрыть



ачала) работы v, то есть такой срок, который не увеличивает срок Т реализации всего проекта.

Значения возможных и допустимых сроков выполнения работ позволяют определить резервы времени для выполнения той или иной работы. Полный резерв (иногда его называют суммарный) времени выполнения работ определяется по формуле:

PE3EPB(v)=ПHAЧ(v)-PHAЧ(v).

Значение PE3EPB(v) равно максимальной задержке в выполнении работы v, не влияющей на плановый срок Т. Понятно, что справедливо и такое равенство: РЕЗЕРВ(v)=ПВЫП(v)-РВЫП(v).

Работы, имеющие нулевой резерв времени, называются критическими. Через любую такую работу проходит некоторый максимальный s-p-путь в сети G. Критические работы характеризуются тем, что любая задержка в их выполнении автоматически ведет к увеличению времени выполнения всего проекта.

 

Приведем запись алгоритма, непосредственно вычисляющего характеристики ПВЫП и ПНАЧ.

 

АЛГОРИТМ 2.

 

Данные: Сетевой график G работ V, заданный списками ПРЕДШ(v), vV, плановый срок окончания проекта Т.

 

Результаты: Наиболее поздние допустимые сроки выполнения и начала работ ПВЫП(v) и ПНАЧ(v).

  1. Объявить для всех работ vV значение наиболее позднего срока выполнения работ равным Т значению планового срока окончание проекта и вершину vp фиктивной работы p объявить текущей vk.
  2. Присвоить значение ПНАЧ текущей работы vk равным значению ПВЫП работы и вычесть время выполнения текущей работы.
  3. Присвоить значению ПВЫП(v) для всех работ vПРЕДШ(v) предшествующих текущей работе vk минимальное значение из значений ПВЫП выполнения роботы v или ПНАЧ выполнения текущей работы vk, если таковых нет перейти в Шаг 4.
  4. Если имеется предыдущая вершина (работа) к текущей, то объявить её текущей, иначе перейти в Шаг 6.
  5. Перейти в Шаг 2.
  6. Выдать наиболее поздние допустимые сроки выполнения и начала работ ПВЫП(v) и ПНАЧ(v), конец работы алгоритма.

Проиллюстрируем работу приведенных алгоритмов на следующих примерах:

 

Пример 1: Проект гаража для стоянки автопогрузчиков.

 

nНаименование работыПредшеству-ющие работыВремя вы-полнения t(vk)1Начало проекта (фиктивн. работа)Нет02Срезка растительного слоя грунта153Монтаж каркаса2304Обшивка стен профнастилом3155Кровля из профнастила3126Заполнение проема воротами457Масляная окраска ворот и профнастила5,6108Щебёночное основание под полы739Асфальтовое покрытие8310Уборка строительного мусора после строит.7311Конец проекта (фиктивная работа)9,100

Рис 1. Проект гаража для стоянки автопогрузчиков.

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

 

Шаг nДействия выполняемые шагом1Объявление значений РНАЧ(v) и РВЫП(v), vV равными нулю. Текущая вершина vk=1.2Вершин предшествующей первой нет.

РВЫП(1)=РНАЧ(1)+t(1). {РНАЧ(1) стало равным 0}3Текущая вершина vk=2.4Переход в Шаг 2.2РНАЧ(2)=МАКС{РВЫП(1),РНАЧ(2)} {РНАЧ(2) стало равным 0}

РВЫП(2)=РНАЧ(2)+t(2) {РВЫП(2) стало равным 5}.3Текущая вершина vk=3.4Переход в Шаг 2.2РНАЧ(3)=МАКС{РВЫП(2),РНАЧ(3)} {РНАЧ(3) стало равным 5}

РВЫП(3)=РНАЧ(3)+t(3) {РВЫП(3) стало равным 35}.3Текущая вершина vk=4.4Переход в Шаг 2.2РНАЧ(4)=МАКС{РВЫП(3),РНАЧ(4)}{РНАЧ(4) стало равным 35}

РВЫП(4)=РНАЧ(4)+t(4) {РВЫП(4) стало равным 50}.3Текущая вершина vk=5.4Переход в Шаг 2.2РНАЧ(5)=МАКС{РВЫП(3),РНАЧ(5)}{РНАЧ(5) стало равным 35}

РВЫП(5)=РНАЧ(5)+t(5) {РВЫП(5) стало равным 47}.3Текущая вершина vk=6.4Переход в Шаг 2.2РНАЧ(6)=МАКС{РВЫП(4),РНАЧ(6)}{РНАЧ(6) стало равным 50}

РВЫП(6)=РНАЧ(6)+t(6) {РВЫП(6) стало равным 55}.3Текущая вершина vk=7.4Переход в Шаг 2.2РНАЧ(7)=МАКС{РВЫП(5),РНАЧ(7)}{РНАЧ(7) стало равным 47}

РНАЧ(7)=МАКС{РВЫП(6),РНАЧ(7)}{РНАЧ(7) стало равным 55}

РВЫП(7)=РНАЧ(7)+t(7) {РВЫП(7) стало равным 65}.3Текущая вершина vk=8.4Переход в Шаг 2.2РНАЧ(8)=МАКС{РВЫП(7),РНАЧ(8)} {РНАЧ(8) стало равным 65}

РВЫП(8)=РНАЧ(8)+t(8) {РВЫП(8) стало равным 68}.3Текущая вершина vk=9.4Переход в Шаг 2.2РНАЧ(9)=МАКС{РВЫП(8),РНАЧ(9)}{РНАЧ(9) стало равным 68}

РВЫП(9)=РНАЧ(9)+t(9) {РВЫП(9) стало равным 71}.3Текущая вершина vk=10.4Переход в Шаг 2.2РНАЧ(10)=МАКС{РВЫП(7),РНАЧ(10)}{РНАЧ(10) стало равным 65}3Текущая вершина vk=11.4Переход в Шаг 2.2РНАЧ(11)=МАКС{РВЫП(9),РНАЧ(11)}{РНАЧ(11) стало равным 71}

РНАЧ(11)=МАКС{РВЫП(10),РНАЧ(11)}{РНАЧ(11) стало равным 71}3Переход в Шаг 5.5Конец работы алгоритма, выдача значений наиболее раннего начала и выполнения работ.

Таблица результатов работы алгоритма.

n1234567891011РНАЧ(v)0053535505565686571РВЫП(v)05355047556568716871

Получили, что минимальное время, требуемое для выполнения проекта равно Т=РВЫП(11), Т=71. Теперь найдем посредством алгоритма 2 значение времени наиболее позднего начала и выполнения работ. Работу алгоритма изложим в виде последовательности выполняемых шагов.

 

Шаг nДействия выполняемые шагом1Объявление значений ПВЫП(v), vV равным Т.

Текущая вершина vk=11.2ПНАЧ(11)=ПВЫП(11)-t(11) {ПНАЧ(11) стало равным 71}.3ПВЫП(9)=МИН{ПВЫП(9),ПНАЧ(11)}{ПВЫП(9) стало равным 71}

ПВЫП(10)=МИН{ПВЫП(10),ПНАЧ(11)}{ПВЫП(10) стало равным 71}4Текущая вершина vk=10.5Переход в Шаг 2.2ПНАЧ(10)=ПВЫП(10)-t(10) {ПНАЧ(10) стало равным 68}3ПВЫП(7)=МИН{ПВЫП(7),ПНАЧ(10)}{ПВЫП(7) стало равным 68}4Текущая вершина vk=9.5Переход в Шаг 2.2ПНАЧ(9)=ПВЫП(9)-t(9) {ПНАЧ(9) стало равным 68}3ПВЫП(8)=МИН{ПВЫП(8),ПНАЧ(9)}{ПВЫП(8) стало равным 68}4Текущая вершина vk=8.5Переход в Шаг 2.2ПНАЧ(8)=ПВЫП(8)-t(8) {ПНАЧ(8) стало равным 65}3ПВЫП(7)=МИН{ПВЫП(7),ПНАЧ(8)}{ПВЫП(7) стало равным 65}4Текущая вершина vk=7.5Переход в Шаг 2.2ПНАЧ(7)=ПВЫП(7)-t(7) {ПНАЧ(7) стало равным 55}3ПВЫП(5)=МИН{ПВЫП(5),ПНАЧ(7)}{ПВЫП(5) стало равным 55}

ПВЫП(6)=МИН{ПВЫП(6),ПНАЧ(7)}{ПВЫП(6) стало равным 55}4Текущая вершина vk=6.5Переход в Шаг 2.2ПНАЧ(6)=ПВЫП(6)-t(6) {ПНАЧ(6) стало равным 50}3П

s