Лекция №1 (стр. 2 )

Возникают вопросы : Какова вероятность того, что фактическое время выполнения всего комплекса работ Т не превзойдет Т0 (заданной величины). Как следует организовывать комплекс работ для того чтобы величина Т не превзошла Т0 с достаточной вероятностью. Рассмотрим 1-ый вопрос.

Предположим, что времена выполнения работ t1, t2, ... , tn - представляют собой случайные величины с известным законом распределения.

Пусть эти случайные величины независимы и их плотности вероятности равны : f1(t), f2(t) , ... , fn(t) Общее время выполнения всего комплекса

Т = ti

Поставленная задача будет решена, если удастся найти функцию распределения случайной величины Т : F(t) = P(T < t) Тогда подставляя вместо t величину Т0, найдем искомую вероятность. Если на критическом пути стоит достаточно большое количество работ (порядка 5-6 и более), то на практике можно считать величину Т распределенной нормально. (При сложении большого числа независимых случайных величин, распределенных по " законам и сравнимых между собой по порядку дисперсии на основании центральной предельной теоремы з-н распределения ® нормальному).

Тогда мат. ожидание будет равно :

mt = m ti где m ti - мат. ожидание времени выполнения i - ой работы.

st = - среднее квадратичное отклонение времени выполнения i - ой работы.

Если mt и st известны, то вероятность выполнения комплекса в срок Т0 находится

Р(Т < T0) = Ф(Т0 - mt /st) + 0,5 где Ф - функция Лагранжа.

Пример. При выполнении комплекса работ a1, a2, ... , an критическими оказываются работы a1, a2, a3, a4, a5, a6. Времена которых есть случайные величины : t1, t2, t3, t4, t5, t6 с мат. ожиданием mt1 = 10; mt2 = 20; mt3 = 10; mt4 = 5; mt5 = 7; mt6 = 10 и средним квадратичным отклонением : st1 = 1; st2 = 1; st3 = 0,5; st4 = 0,3; st5 = 0,5; st6 = 1. Случайные отклонения времен выполнения работ от их мат. ожидания не изменяют критического пути. Задан срок выполнения комплекса Т0 = 65. Имеем mt = mt i = 62 st = = » 1,9 Тогда Р(Т < 65) = Ф(65 - 62/1,9) + 0,5 = Ф(1,58) + 0,5

Р(Т < 65) » 0,94

Если при случайных изменениях ti может изменяться критический путь, то в случае когда число работ мало, тогда задачу можно решить аналитически. При большом числе работ в комплексе применяют метод Монте-Карло. При этом разыгрывается значения случайных времен ti и для каждой совокупности полученных значений определяется время Т выполнения комплекса работ тем способом, которым применяется для детерминированных времен. Получив достаточно большое число N таких реализаций, можно найти мат. ожидание, дисперсию и среднее квадратичное отклонение величины Т. Что касается з-на распределения, то он в большинстве случаев оказывается близким к нормальному.

Лекция Календарное планирование программ сетевыми способами

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

строительство большого промышленного объекта;

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

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

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

Организованное управление программами стало новой областью теоретических и прикладных исследований благодаря разработке 2-х аналитических методов структурного и календарного планирования, а также оперативного управления программами. Эти методы, разработанные почти одновременно в 1956-1958 гг. двумя различными группами, получили название метод критического пути (МКП) и метод оценки и пересмотра программ (ПЕРТ). Метод критического пути был предложен фирмой E. I du Pont de Nemours & Company для управления программами в строительстве, а затем развит и обобщен фирмой Mauchly Associates. Метод ПЕРТ был разработан консультивной фирмой по заказу военно-морского министерства США для календарного планирования научно-исследовательских работ программы создания ракет "Полярис".

В методах ПЕРТ и МКП основное внимание уделяется временному аспекту планов. Хотя методы были разработаны независимо друг от друга, они отличаются поразительным сходством. Самым существенным отличием было то, что в методе МКП оценки продолжительности операций предполагались детерминированными величинами, а в методе ПЕРТ - случайными. В настоящее время оба метода составляют метод сетевого планирования и управления СПУ программами. Сетевое планирование и управление программами включает 3 основных этапа : структурное планирование, календарное планирование, оперативное управление. Планирование любого комплекса работ должно производиться с учетом следующих элементов : ¾ времени, на выполнение всего комплекса работ и его отдельных звеньев; ¾ стоимости всего комплекса работ и его отдельных звеньев; ¾ сырьевых , энергетических и людских ресурсов.

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

При планировании небольших по объему (количеству звеньев) комплексов работ ответ на такие вопросы дает руководитель, причем без специальных математических расчетов, на основе своего опыта. Однако, когда речь идет об очень сложных, дорогостоящих комплексах работ, состоящих из большого числа звеньев, такие приемы недопустимы.

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

Будем называть такой список структурной таблицей комплекса работ.

Таблица 1.

N n/n	Работа	Опирается на работы
1.	a1	¾
2.	a2	a1, a3
3.	a3	¾
4.	a4	a1, a2 , a3
5.	a5	¾
...	....	...
15 .	a15	a10

Далее, структурную таблицу упорядочивают. При упорядочивании работам придается некоторая новая нумерация (каждая работа может опираться только на работы с меньшими порядковыми номерами). Для упорядочивания все работы ранжируются (присваиваются ранги). Работа называется работой первого ранга, если для ее выполнения не требуется выполнения никаких работ. Работа называется работой второго ранга, если она опирается на одну или несколько работ первого ранга. Работа называется работой k-го ранга, если она опирается на одну или несколько работ не выше (k - 1)-го ранга, среди которых есть хотя бы одна работа (k - 1)-го ранга.

Для примера произведем упорядочивание работ полученных в таблице 1.1.

Таблица 1.1.

N n/n	Работа	Опирается на работы	Ранг	Новое обозначение
1.	a1	¾	1	b1
2.	a2	a1 , a3	2	b5
3.	a3	¾	1	b2
4.	a4	a1, a2, a3	3	b6
5.	a5	¾	1	b3
6.	a6	¾	1	b4
7.	a7	a1, a4, a6	6	b12
8.	a8	a1, a2	2	b7
9.	a9	a3, a4, a5	5

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

Таблица 1.2.

	N n/n	Работа	Опирается на работы
	1.	b1	¾
	2.	b2	¾
	3.	b3	¾
4.	b4	¾
	5.	b5	b1, b2
	6.	b6	b1, b5, b2
	7.	b7	b1, b5
	8.	b8	b1, b5
	9.	b9	b2, b6, b3
	10.	b10	b9
	11.	b11	b9
	12.	b12	b1, b6, b11
	13.	b13	b6, b3, b11
	14.	b14	b11
	15.	b15	b12, b8

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