Введение в теорию сетевого планирования

Проект – это список частично упорядоченных работ, направленных на достижение одной цели. Работа i предшествует работе j, если работа j не может быть начата раньше завершения работы i. Проект считается выполненным, если выполнены все работы списка. В любом проекте можно выделить подмножество критических работ, увеличение продолжительности выполнения которых приведет к увеличению времени выполнения всего проекта. При анализе проекта необходимо определить, в частности, min время его выполнения, а также найти узкие места. Проект

Сеть Для анализа проекта в теории сетевого планирования исп-ся сеть, отражающая отношения предшествования работ. Сеть S=(X, U) – это простой ориентированный ациклический граф с одним источником и одним стоком (a, b) - путь из вершины a в вершину b Вершина i предшествует вершине k, если в сети S путь (i, k). Дуга (i, k) предшествует дуге (p, q), если в сети S путь (k, p). Работа i непосредственно предшествует работе j, если i предшествует j и нет такой работы k, что i предшествует k и k предшествует j.

Сетевая модель Сеть наз. взвешенной, если её вершинам или/и дугам приписаны числа – «веса». Длиной пути (i, k), обозначим ее | (i, k)|, из вер. i в вер. k в взвешенной сети явл. весов, включенных в путь элементов. Обозн. * (i, k) самый длинный путь из вер. i в вер. k. Сетевая модель (сетевой график) – это представление списка работ проекта в виде взвешенной сети, которое позволяет адекватно отразить связи между работами проекта. 2 типа сетевых моделей: 1. «работы-вершины» 2. «работы-дуги»

Типы сетевых моделей 1. «работы-вершины»: вершина – образ работы; дуги служат для пред. отношения предшествования работ. Для построения: работе проекта вершина, имеющая вес = длительности; дуга (i, j), если работа i непосредственно предшествует работе j. 2. В моделях «работы-дуги»: работы – дуги; направление дуги отображает част. порядок на мн. работ. Вершины соответствуют событиям – моменты завершения одних работ и возможность начала выполнения других. Для построения: работе дуга, имеющая вес = длительности. Из конечной вер. дуги p проводится дуга в начальную вер. дуги q, если работа p непосредственно предшествует работе q. Дуга, которая не имеет прообраза в мн. работ и введена для задания отношения предшествования, наз. фиктивной. Не фиктивные дуги наз. фактическими.

Упрощение сети – мн. фактических дуг сети U i – подмн. фактических дуг (1, i) U i – подмн. фактических дуг (i, n) Рассмотрим пару вершин i и k: 2 сети с одинаковым мн. фактических дуг наз. эквивалентными, если они представляют одно и то же отношение предшествования фактических дуг. (1) не инцидентной им обеим фактической дуги (2) не дуг – i(p)=i(q), k(p)=i, k(q)=k; – или k(p)=k(q), i(p)=i, i(q)=k. ik i k p q i k p q

Упрощение сети Результатом склейки вер. i и k в сети S, удовлетворяющих свойствам (1) и (2), является сеть S, в кот. вер. k удалена, а все дуги, кот. были ей инцидентные в S, в S инцидентны вер. i. Если в S окажется несколько параллельных фиктивных дуг, то все они, кроме одной, удаляются. Теорема. Пусть вершины i и k удовлетворяют условиям (1) и (2). Сеть S, полученная из S в результате склеивания вершин i, k и исключения k, эквивалентна S U i = U k, или U i = U k.

Пример упрощения сети

Обозначения Сетевая модель – разреженная сеть…: j – номер дуги; i(j) – номер начальной вер. дуги j; k(j) – номер конечной вер. дуги j; j – длина дуги j (продолжительность выполнения соответствующей работы). i(j)i(j)k(j)k(j) j (j) {1, …, n} – вершины; {1, …, m} – дуги; 1 – источник; n – сток. Если первоначально в сетевой модели имеется несколько источников (стоков)…

Параметры сетевой модели Ранним временем наступления события i наз. величина Время критическое время проекта – min возможное время выполнения всего проекта Любой путь * (1, n), а также дуги (работы) и вершины (события), этому пути, также наз. критическими. Поздним временем наступления события i наз. величина Если событие i наступит не позднее моментато время выполнения всего проекта не увеличится Событие i является критическим

Резервы выполнения работ Свободным резервом выполнения работы j наз. величина кот. = max увеличению продолжительности выполнения работы j, не меняющему ранние времена наступления всех событий Полным резервом выполнения работы j наз. величина На такую величину можно увеличить продолжительность выполнения работы j, чтобы не изменилось критическое время проекта Критические работы имеют нулевой свободный и полный резервы

Ранг события Ранг R i события (вершины) i, равен max количеству дуг в { (1, i)} Алгоритм Форда: Шаг 0. вершин i=1,…,n полагаем r i = 0. Пусть в результате k 1 шагов найдены величины r i. Шаг k. Просматриваем последовательно работы-дуги j=1,…,m и пересчитываем величины r k(j) =max{r k(j), r i(j) +1}. Если на каком-то шаге k ни одна из величин r i не изменилась, то они являются рангами событий, и алг. останавливается. Иначе, полагаем k=k+1 и повторяем шаг k. T=O(mn) M=O(n)

Ранг события Теорема. В результате вып. k шагов алг. Форда вер. i: 1) r i R i ; 2) r i = R i, если ранг события i не превосходит k. Доказательство. Докажем 1) индукцией по рангу события. Для входа r 1 = 0. Предположим неравенство справедливо для событий рангов 1,…,R. Рассмотрим событие l, ранг которого R l =R+1. Пусть k(j)=l и j последняя работа, при рассмотрении кот. изменилась величина r l (т.е. r l =r i(j) +1). по предположению индукции, r l =r i(j) +1 r i(j) +1 R i(j) +1 R l. Докажем 2) индукцией по номеру шага алгоритма. На шаге 0 для един. вер. ранга 0 имеем r 1 =R 1 =0. Пусть в результате k 1 шагов величины r l = R l событий l, ранги которых не превосходят k 1, найдены. Рассмотрим событие l ранга k и работу j такую, что k(j)=l, R i(j) =k 1. По индукционному предположению и утв. 1) величина r i(j) не меняется на шаге k и равна R i(j) r l r i(j) +1=R i(j) +1=k.

Правильная нумерация вершин Нумерация вершин наз. правильной, если i(j)< k(j) дуг j=1,…,m Зная ранги событий…: вход 1; вершинам ранга 1 номера 2,…,n 1 ; вершины, имеющие ранг 2 номера n 1 +1,…,n 2 ; и т. д. выход n

Нахождение ранних времен (алгоритм Форда) Шаг 0. вершин i=1,…,n полагаем Пусть в результате k 1 шагов найдены значения Шаг k. Просматриваем последовательно дуги j=1,…,m и пересчитываем величины Если на шаге k ранние времена событий не меняются, то алг. останавливается. В противном случае увеличиваем k на единицу и повторяем шаг k

Правильное упорядочивание дуг Если дуг p и q, p (1, i(q)) выполняется неравенство p

Правильное упорядочивание дуг

Нахождение ранних времен за 1 просмотр дуг Теорема. Если дуги правильно упорядочены, алгоритм Форда находит ранние времена наступления событий за один просмотр дуг в порядке их нумерации j=1,…,m. Доказательство. Пусть дуги правильно упорядочены и величины T i, i=1,…,n, являются ранними временами, вычисленными на 1 шаге алг. Форда. Предположим, что на 2 шаге алг. не остановился. Значит, вер. l, у кот. раннее время, полученное на 1 шаге< раннего времени Пусть дуга j является 1-ой в списке, когда величина T l =T k(j) изменилась на 2 шаге алг. Тогда для вер. i(j) раннее время также изменилось на 2 шаге, т.е. Но дуги, заканчивающиеся в вер. i(j), имеют номера < j. противоречит выбору j. и изменение T i(j) на 2 шаге алг. (до просмотра дуги j) полученного на 2 шаге.

Нахождение поздних времен (алгоритм Форда) Шаг 0. вер. i=1,…,n полагаем Пусть в результате k 1 шагов найдены значения Шаг k. Просматриваем последовательно дуги j=1,…,m и пересчитываем величины Если на шаге k поздние времена событий не меняются, то алг. останавливается. В прот. сл. полагаем k=k+1 и повторяем шаг k. Теорема. В случае правильной упорядоченности дуг, поздние времена находятся с помощью алгоритма Форда за 1 просмотр дуг в обратном порядке j=m,…,1.