Сетевое планирование в условиях неопределённости

 

В случаях, когда время выполнения работ точно не известно, то есть продолжительность работы является случайной (стохастической) величиной, характеризующейся законом β-распределения с числовыми характеристиками – средним значением, или математическим ожиданием продолжительности работы t_{ож ij} и дисперсией продолжительности работы σ²_ij.

Для определения средней (ожидаемой) длительности работ на основе экспертного опроса даются три временные характеристики (оценки времени выполнения работ):

1. Оптимистическая (минимальная) оценка t_oij ;

2. Пессимистическая (максимальная) оценка t_nij ;

3. Наиболее вероятная оценка t_н.вij.

Тогда среднее (ожидаемое) время выполнения работы определяется выражением

t_oжij = ,

или, если известны только крайние оценки:

t_oжij = .

Определение степени неопределённости выполнения работ, лежащих на критическом пути для первого подхода

,

для второго подхода

.

Определение вероятности завершения комплекса работ в заданный директивный срок. Для этого необходимо найти аргумент функции нормального распределения Z по формуле

где T_дир – директивный срок завершения работ; L_кр – длительность критического пути; Sσ²_{ij кр} – суммарная дисперсия работ, лежащих на критическом пути.

Максимальный срок выполнения всего комплекса работ Т при заданном уровне вероятности р

.

Допустим, получены следующие оценки длительности работ, на основании которых рассчитано среднее (ожидаемые) время выполнения работ

t_{ож 1-2} = (4 + 4 × 5 + 7) / 6 = 5,167.

 

 

Рис. 27. Расчёт ожидаемой продолжительности работ

 

Длительность критического пути равна 51,3 дня. Для работ критического пути рассчитаем дисперсии

σ²_1-2= (7 – 4)² / 6² = 0,25;

 

σ²_2-3= 1; σ²_6-7= 0,69; σ²_7-8= 0,25; σ²_8-9= 1; σ²_9-10= 0,25.

 

При расчёте с помощью программы «Расчёт и оптимизация сетевого графика» из ППП PRIMA, оценки времени выполнения работ t_min и t_max следует располагать в двух смежных столбцах, а для трёх оценок - значения t_min , t_нв и t_max располагаются в трёх смежных столбцах, адреса которых вводятся в программу в окне Время выполнения работ.

 

 

Рис. 28. Ввод директивного срока выполнения работ

 

Допустим, директивный срок выполнения работ установлен в пределах 55 дней, тогда аргумент функции нормального распределения равен

Z = (55–51,3) / (0,25+1+0,69+0,25+1+0,25)^1/2 = 1,976.

Для определения вероятности завершения комплекса работ в заданный директивный срок используют значения функции нормального распределения Р(z):

z	P(z)	z	P(z)	z	P(z)	z	P(z)
0,0	0,50000	1,6	0,94520	-3,0	0,00135	-1,4	0,08076
0,2	0,57926	1,8	0,96407	-2,8	0,00256	-1,2	0,11507
0,4	0,65542	2,0	0,97725	-2,6	0,00466	-1,0	0,15866
0,6	0,72575	2,2	0,98610	-2,4	0,00820	-0,8	0,21186
0,8	0,78814	2,4	0,99180	-2,2	0,01390	-0,6	0,27425
1,0	0,84134	2,6	0,99534	-2,0	0,02275	-0,4	0,34458
1,2	0,88493	2,8	0,99744	-1,8	0,03593	-0,2	0,42074
1,4	0,91924	3,0	0,99865	-1,6	0,05480	0,0	0,50000

 

Используя таблицу значений функции нормального распределения и метод интерполяции, определяют вероятность выполнения комплекса работ в заданный директивный срок.

Р(z) = 0,964+(1,976–1,8)×(0,977–0,964)/(2,0–1,8) = 0,976.

Для расчёта вероятности можно использовать функцию НОРМСТРАСП из категории Статистические Excel.

 

 

Рис. 29. Расчёт вероятности выполнения

всех работ в срок

 

Максимальный срок выполнения всего комплекса работ Т при заданном уровне вероятности р = 0,95. Для получения величины Z можно использовать функцию НОРМСТОБР из категории Статистические Excel.

 

 

Рис. 30. Расчёт вероятного времени выполнения всех

работ

 

Т = 51,3+1,645× (0,25+1+0,69+0,25+1+0,25)^1/2 ≈ 54,35 дня

Таким образом, с вероятностью 0,95 комплекс работ будет завершен за 54,35 дня.

 

 

Тема 2. ЭЛЕМЕНТЫ ТЕОРИИ МАССОВОГО ОБСЛУЖИВАНИЯ

Основные понятия теории массового обслуживания. Предметом изучения теории массового обслуживания (ТМО) являются процессы, в которых, с одной стороны, возникают запросы на выполнение каких-либо работ или услуг, а с другой стороны – производится удовлетворение этих запросов. Такие процессы реализуются в системах массового обслуживания (СМО).

Та часть СМО, в которой возникают запросы, называется обслуживаемой подсистемой, а та часть СМО, которая принимает запросы и удовлетворяет их, называется обслуживающей подсистемой.

Каждый отдельный запрос на выполнение какой-либо работы называется заявкой, или требованием. Часть обслуживаемой подсистемы, которая в любой момент времени может послать только одно требование, называется источником требования, или объектом обслуживания. Обслуживанием называется удовлетворение поступившего в обслуживающую подсистему требования. Часть обслуживающей подсистемы, которая способна в любой заданный момент времени удовлетворять только одно требование, называется обслуживающим аппаратом. Обслуживающая подсистема – это совокупность однородных обслуживающих аппаратов (контролеров, наладчиков, рабочих, оборудования).

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

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

Среднее число требований, поступающих в систему обслуживания в единицу времени, называется интенсивностью поступлений (l) и определяется по формуле

l = , (2.1)

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

СМО с простейшими потоками требований обладают следующими свойствами: стационарностью, ординарностью и отсутствием последействия.

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

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

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

Если поток требований простейший, то его можно описать количественно с помощью функции Пуассона:

Р_к(t) = , (2.2)

где Р_k(t) – вероятность того, что в течение времени t в систему поступит точно k требований на обслуживание (k = 0,1,2 …).

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

lt = s², (2.3)

где lt – среднее число требований, поступивших на обслуживание за время t.

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

При показательном законе распределения времени обслуживания функция распределения F(t)_обсл, представляющая собой вероятность того, что время обслуживания будет меньше заданной величины t, описывается следующим образом:

F(t)_обсл = 1 – е^-nt, (2.4)

где n - параметр системы обслуживания, величина, обратная среднему времени обслуживания, представляет собой интенсивность обслуживания одного требования одним аппаратом:

n = , (2.5)

где - среднее время обслуживания одного требования одним аппаратом.

Параметр системы массового обслуживания a

a = , или a = l × . (2.6)

Параметр a показывает количество требований, поступающих в систему за среднее время обслуживания одного требования одним аппаратом. Поэтому количество обслуживающих аппаратов n не должно быть меньше a:

n ³ a. (2.7)

Если это требование не выполняется, то очередь будет расти и заявки не будут полностью выполнены.