Человеческий фактор. Том 3. Часть 1 - Сальвенди Г.
ISBN 5-03-001815-8
Скачать (прямая ссылка):
Стохастические сетевые модели
259
мер очереди в каждом узле п конечен; 6) по завершении обработки заявки в узле ng она может или поступить на обработку в узел nh с вероятностью rgh, или покинуть систему с вероятностью rg.
Аналогично случаю стохастической сети типа PERT, для получения числовых характеристик сети Джексона необходимо сначала преобразовать ее в соответствующую ДПСП, после чего вычисление числовой характеристики, например ожидаемого времени завершения обслуживания, выполняется достаточно просто.
Диаграмма порядка следования процессов
Для построения ДПСП введем новые обозначения. Разобьем все множество заявок в любой момент времени на пять классов А—Е:
А — заявки, не вошедшие в систему;
В — заявки, покинувшие систему;
С — заявки, обрабатываемые в системе;
D — заявки, ожидающие обслуживания в одной из очередей;
Е — заявки, только поступившие в систему из внешней среды. Очевидно, что множества А, В, С, D, Е изменяются во времени. Введем для каждого указанного разбиения множества заявок единый идентифицирующий индекс. Будем говорить, что система (сеть) при обработке заявок находится в состоянии s*, если заданы множества С„ Д-, поскольку этих трех множеств достаточно для анализа в рассматриваемом примере.
Обозначим заявки через г/ь г/г. •••, Упч- Обозначим элементы множества С* через ckg. Наличие элемента Chg в множестве С* означает, что заявка yh обрабатывается в узле ng. Аналогично, наличие элемента dug в множестве ?>* означает, что заявка уи ожидает в очереди в узле ng, а наличие элемента ekg в множестве Ei означает, что заявка уи поступила из внешней среды на узел ng системы. Переход за один шаг из состояния Si в состояние Sj происходит тогда, когда завершение ровно одного процесса обработки в состоянии s* ведет к разбиению, соответствующему СОСТОЯНИЮ Sj.
Различные состояния и пути (последовательности состояний) ациклической сети Джексона с конечным числом входов можно представить с помощью диаграммы порядка следования процессов [21]. Заявки, которые уже обрабатываются или только что вошли в систему, помещаются в верхней половине прямоугольника, изображающего состояние. Дуга, соединяющая два соседних состояния, помечается тем процессом обработки, завершение которого ведет к переходу из состояния в состояние. Вероятности rg и rgh также связаны с соответствующими дугами. Рассмотрим для примера сеть Джексона, показанную на рис.
230 Глава 4
4.14, а. Соответствующее ей ДПСП приведено на рис. 4.14, б. В состоянии Si в систему в узле ti\ входит заявка у\ (Ci,=0, Di=0, ?i = {0it}). В состоянии s2 в систему в узле tii входит заявка у2, а заявка у\ обрабатывается в том же узле П\(С2 — = {сц}, -02=0, ?,2={e2i}). Если обработка заявки у\ завершается до того, как заявка у% входит в систему (т. е. си завершается прежде 621), то с вероятностью г, происходит переход в состояние S3, в котором заявка у\ выходит из системы, и с вероятностью г а происходит переход в состояние s4, в котором начинается обслуживание заявки ух в узле п2. Если же заявка уг входит в систему до того, как обработка заявки у\ завершается (т.е. ец завершается прежде с2г), то происходит переход в состояние sg, в котором заявка у2 помещается в очередь на обслуживание в узле Пи поскольку имеющееся в этом узле единственное обслуживающее устройство оказывается занятым.
Допустим, что заявка может перейти в новый узел ng тогда и только тогда, когда в очереди qg есть свободные места, а в противном случае заявка теряется. Так, например, в состоянии
заявка находится на обслуживании в узле п2у а заявка у2— в узле «1 (С7={сц, С2]}, ?>7=0, ?7=0). Если следующим событием будет завершение обработки у2 в узле пи то заявка у2 будет потеряна даже в том случае, когда она будет направлена на обслуживание в узел п2, так как этот узел занят. Это отражено в соответствующем состоянии (C9={ci2}, -D9=0, ?9 = 0).
После того как ДПСП построено, вычисление числовых характеристик исходной сети производится достаточно просто. Приведем здесь выражения для среднего времени обслуживания и для вероятности Р(о{) выбора пути о,-.
Вычисление среднего времени обслуживания
Рассмотрим квадратную матрицу Q размерностью noXti0, аналогичную рассмотренной выше матрице Р. Положим, что
1) Q = 0, если состояние Sj не является прямым потомком
СОСТОЯНИЯ Si’,
2) Q = P, если при переходе из состояния s,- в состояние s, заявка ук не переходит из одного узла в другой и не покидает системы;
3) (fij=p{jrgh, если при переходе из состояния s< в состояние Sj заявка у\ переходит из узла tig в узел
4) qi3=pifgh, если при переходе из состояния s* в состояние Sj заявка покидает систему.
Так, для диаграммы на рис. 4.14, б имеем
— Q25 ~ Р25 = vi)> Ян ~ p2iri-z ~
= [МШ + v,)] ги; <7зз = Р23Г1 = IMPi + vi)l ri-
Стохастические сетевые модели
261
После того как матрица Q определена, можно переходить к вычислению среднего времени обслуживания [83].
Теорема 2
Поскольку вычисление среднего времени обслуживания по теореме 2 аналогично вычислению среднего времени реакции по теореме 1, само вычисление здесь опущено.
