12 - Лекция

Задача календарного или сетевого планирования

Олимпийские игры 1992 г., Барселона, более 2000 мероприятий за 15 дней

частичный порядок на множестве событий (четверть финала, полуфинал, финал)
мощность спортивных сооружений (число одновременных соревнований на число зрителей)
транспортный проблемы и доход (максимизировать посещаемость более популярных соревнований - раздвинуть их по времени)
требования TV (минимум параллельных трансляций).
обеспечение безопасности (число полицейских ограничено)
Система поддержки решений "SUCCESS-92" Университет г. Барселоны

Задачи календарного или сетевого планирования
Pert - Program Evaluation Review Techique
1950 г., США, метод для управления разработкой и производством подводных лодок с ракетами Polaris
CPM - Critical Path Method
1957 г., разработан американской компанией DuPont производителем химических материалов

Сетевое планирование

Методы сетевого планирования используются для рационального планирования сложных, комплексных работ таких как:

строительство больших промышленных объектов (заводы, ГЭС, АЭС и т.п.);
перевооружение армии или отдельных видов вооруженных сил;
развёртывание системы масштабных медицинских или профилактических мероприятий.

Характерной особенностью таких сложных работ является то, что они состоят из ряда отдельных взаимозависимых работ
Эта взаимозависимость выражается в том, что некоторые работы не могут быть начаты до тех пор, пока не будут завершены определённые другие работы.
Например, нельзя возводить стены здания, если не готов фундамент.

Планирование комплекса работ производится с учётом следующих элементов:

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

На какие вопросы надо ответить:

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

Этапы сетевого планирования

Создание структурно-временной таблицы:
Создание списка всех работ комплекса с указанием времени их выполнения и взаимной обусловленности, то есть указание окончания каких работ требуется до начала выполнения других работ.
Создание сетевого графа:
Создание ориентированного графа, вершины которого помечаются завершёнными работами, а дуги - работами
Создание временного сетевого графа:
Создание сетевого графа, начала дуг которого соответствуют времени начала работ, а концы - их завершению
Анализ временного сетевого графа:
а. Определение минимального времени завершения всех работ;
б. Определение критических работ, то есть работ, из времени выполнения которых складывается минимальное время выполнения комплекта всех работ;
в. Определение резервов времени выполнения некритических работ (для того, чтобы отодвинуть время начала некритической работы, либо увеличить срок ее выполнения, передав часть ресурсов на выполнение критических работ, если это возможно).
Оптимизация плана комплексных работ:
Ответ на вопрос: можно ли привлечь и в каком объёме дополнительные ресурсы для сокращения времени выполнения критических работ?

Основа

Сетевая модель - ориентированный граф.
Существуют два типа сетевых моделей:

работы вершины (вершина-работа, дуги-связи между работами)
работы дуги (работы комплекса изображаются дугами)

Работа - любой процесс, происходящий во времени.

Виды работ:

Действительные работы
Действительные работы это любой трудовой процесс, требующий ресурсов и имеющий некоторую продолжительность.
Основная характеристика - объем работы.
Физическое содержание объема - трудоемкость в человеко-днях, физические размеры в различных единицах, стоимость.
Ожидание
Ожидание - процесс, не требующий ресурсов, но имеющий некоторую продолжительность (остывание металла в изложнице)
Фиктивные работы
Фиктивные работы (зависимости) - не требуют ресурсов и имеют нулевую продолжительность.
На графике - пунктирные линии.

Событие

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

На любом графике выделяют события:

исходное
промежуточное
завершающее

!МИАПРСХЕМА1

Работа

Любая работа соединяет два события, одно непосредственно предшествующее данной работе (начальное событие работы), а другое непосредственно следующее за ней (конечное события работы).

Любая работа кодируется парой чисел $(i, j)$

$i$ - начальное,
$j$ - номер конечного события работы.

Путь

Любая последовательность работ $(i_{1}, i_{2}), (i_{2}, i_{3}), . . ., (i_{n - 1}, i_{n})$ в которой конечное событие предыдущей работы является начальным событием последующей работы, называется путем, обозначается $L$ , с перечислением всех событий $L (i_{1}, i_{2}, \dots, i_{n})$

Полный путь - последовательность работ, соединяющее исходное и завершающее события.

На следующей рисунке имеются четыре пути: $L (0, 1, 4, 6), L (0, 2, 4, 6), L (0, 3, 5, 6), L (0, 2, 6)$
!МИАПРСХЕМА3

Путь предшествующий событию - последовательность работ, соединяющее исходное и рассматриваемое события.
У события 4 два предметных пути $L (0, 1, 4) и L (0, 2, 4)$

Путь, следующий за событием - последовательность работ, соединяющее рассматриваемое и завершающее события.
У события 2 сет. мод. два следующих пути: $L (2, 4, 6) и L (2, 6)$

Путь между событиями - последовательность работ, соединяющее два события, в котором ни одно не является ни исходным, ни завершающим.

На рисунке выше такой путь между 2 и 4 - $L (2, 4)$

Правила построения сетевых моделей

!МИАПРСХЕМА2

Работа $B$ начинается после завершения работа $A$
Работы $B$ и $C$ начинаются после завершения работы $A$
Работа $C$ начинается после завершения работы $A$ и $B$
Если начинается одновременно $N$ работ, то на сетевой модели вводится $N - 1$ фиктивная работа.

Распространенные ошибки:
!МИАПРСХЕМА4
Хвост: 2 исходных события
Тупик: 2 конечных события
Цикл: нет конечного или исходного события

[\begin{matrix} a_{1} & a_{2} & a_{3} & a_{4} & a_{5} & a_{6} & a_{7} & a_{8} & a_{9} \\ п р е д . & - & - & - & a_{1} & a_{1}, a_{2} & a_{1}, a_{2} & a_{3}, a_{5} & a_{4}, a_{6}, a_{7} & a_{3}, a_{5} \\ t & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \end{matrix}]

	$a_{1}$	$a_{2}$	$a_{3}$	$a_{4}$	$a_{5}$	$a_{6}$	$a_{7}$	$a_{8}$	$a_{9}$
пред.	-	-	-	$a_{1}$	$a_{1}, a_{2}$	$a_{1}, a_{2}$	$a_{3}, a_{5}$	$a_{4}, a_{6}, a_{7}$	$a_{3}, a_{5}$
$t$	1	2	3	4	5	6	7	8	9

!МИАПРСХЕМА5

Продолжительность выполнения работы $(i, j)$ обозначим $t_{i j}$

Ранний срок $t_{p} (j)$ свершения события $j$ - это самый ранний момент, к которому завершаются все работы, предшествующие этому событию:
$t_{p} (1) = 0$
$t_{p} (j) = max (t_{p} (i) + t_{i j}) по (i, j) E_{j}^{*}$
где $E_{j}^{*}$ - множество работ, заканчивающихся $j$ -ым событием;
$t_{p} (i)$ - ранний срок свершения начального события работы $(i, j); t_{i j}$ - продолжительность работы $(i, j)$ . Тогда $t_{p} (5) = t_{K_{p}}$