Сетевые модели. Задача нахождения кратчайшего пути.

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

Сетевое планирование включает в себя 3 этапа:

1. Структурное планирование.

Определяются работы, их продолжительность и взаимосвязь. Строится сетевой график.

2. Календарное планирование.

Определяется критический путь, критические работы, их параметры. Строится календарный график.

3. Оперативное управление.

Управление работами на основе календарного графика.

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

Сетевая модель – план выполнения комплекса взаимосвязанных задач. Графическое изображение – сетевой график.

Основные элементы сетевой модели это работы исобытия.

Работа может быть:

1. Действительная работа – требует времени и ресурсов;

2. Ожидание – требует времени, но не требует ресурсов;

3. Фиктивная работа – вводится для логической связи, не требует времени и ресурсов.

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

Критический путь – полный путь наибольшей продолжительности. Критический путь дает наименьшее время выполнения всего комплекса работ.
Критический путь можно найти двумя способами.
с помощью сетевого графика

1 этап: от исходного события до завершающего определяем ранний срок событий.

2 этап: от завершающего события до исходного определяем поздний срок событий.

События, у которых ранний срок совпадает с поздним, называются критическими и не имеют резервов времени.

1. Критические работы лежат между критическими событиями.

2. Критический путь – непрерывная цепочка критических работ.

с помощью линейной диаграммы

1. Линейная диаграмма строится в декартовой системе координат и позволяет понять, какая работа в данный момент времени должна выполняться. По оси x – время, по оси y – работы.

Нахождение временных параметров
Параметры событий:
ранний срок
поздний срок
резерв времени
Параметры путей:
продолжительность пути
продолжительность критического пути
резерв пути
Параметры работ:
продолжительность
сроки свершения
ранний срок начала
ранний срок окончания
поздний срок окончания
поздний срок начала
резервы
полный резерв работы – время, на которое можно увеличить продолжительность работы, не увеличивая времени выполнения всего комплекса работ

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

резерв второго вида – свободный резерв – часть полного резерва, на которую можно увеличить продолжительность работы, не изменяя раннего срока свершения события j

независимый резерв – часть полного резерва, на которую можно увеличить продолжительность работы, не изменяя позднего срока свершения события i и раннего срока свершения события j