Алгоритм расчета параметров сетевого графика

Контроль знаний

1. В чем общая сущность всех методов дискретного программирования? 2. Опишите кратко сущность метода ветвей и границ.

3. Опишите алгоритм метода ветвей и границ.

4. Опишите использование Поиска решения для задач о назначениях. 5. Где может использоваться задача о назначении?

Лабораторная работа № 7

Тема: СетеваямодельтехнологическогопроцессаЦельработы:

ƒ освоить сетевое планирование и управление в электронных таблицах Excel; ƒ изучить встроенные функции управления базами данных;

ƒ выработать навыки расчета основных параметров сетевого графика. Времяработы: 4 часа

Задание

1. Построить сетевой график технологического процесса; 2. Рассчитать основные параметры сетевого графика.

Табличный расчет сетевого графика основан на алгоритме, который включает два этапа:

1. алгоритм прямого хода, 2. алгоритм обратного хода.

Сущность прямого алгоритмического хода состоит в определении ранних сроков на-ступления событий и заканчивается определением длины критического пути. Алгоритм обратного хода связан с поздними сроками наступления событий и заканчивается опреде-лением полных резервов работ.

1.Алгоритм прямого хода,

1.1.Раннее начало работ (Т РН), начинающихся от истока равно нулю.

((

1.2.Ранее окончание (Т РО) любой работы (i, j) равно сумме раннего начала и времени выполнения работы t (i, j).

(

PH

TPOi, j) TPHi, j)+ t (i, j) (7.1) 1.3.Ранее начало T i, j) других работ, начинающихся i -м событием, определяется

максимальным ранним окончанием TPO (i − k, i) тех работ, которые заканчиваются

() {)}

i -м событием. Количество таких работ равно К.

K

TPYi, j max TPOi k, i (7.2)

Для подсчета времени раннего начала работы необходимо:

1.3.1. Для рассматриваемой работы зафиксировать событие, которым оно начина-ется.

1.3.2. Найти по таблице работы, которые заканчиваются зафиксированным собы-тием.

1.3.3. Выписать их ранние окончания (Т РО).

1.3.4. Из выписанных ранних окончаний найти максимальное значение и записать его в качестве раннего начала рассматриваемой работы.

{)}

1.4.Подсчитываем длину критического пути, как максимальное значение из ранних окончаний всех работ в сети.

tKP = max TPOi, j (7.3)

2.Алгоритм обратного хода. Если на этапе прямого хода заполнение таблицы шло сверху вниз, то на этапе обратного хода наоборот: снизу вверх.

)

2.1.Работы, оканчивающиеся в стоке, имеют позднее окончание (Т ПО) равное длине критического пути.

TПОi, N = tKP (7.4)

() ()

2.2.Позднее начало (Т ПН) для всех работ определяется как разность между поздним окончанием и временем выполнения работы

(

TПНi, j TПОi, j − t (i, j) (7.5) 2.3.Позднее окончание TПОi, j) других работ, оканчивающиеся j -м событием, опреде-

))}

ляется минимальным поздним началом TПН (j, j + m) тех работ, которые начинаются j -м событием. Количество таких работ равно M.

M

TПОi, j = min TПН j, j + m (7.6)

2.3.1. Для рассматриваемой работы зафиксировать событие, которым оно закан-чивается.

2.3.2. Найти по таблице работы, которые начинаются зафиксированным событи-ем.

2.3.3. Выписать их поздние начала (Т ПН).

2.3.4. Из выписанных поздних начал найти минимальное значение и записать его в качестве позднего окончания рассматриваемой работы

Дата добавления: 2014-11-25