Организация очереди и подсчет средней длины очереди

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

,

где n – количество заявок.

Пусть в одноканальную систему поступила i-я заявка в момент t_i. Пусть L[I - 1] – количество заявок в очереди на момент t_i-1. В очереди находятся заявки, которые могут дождаться и пройти обслуживание. Заявка либо обслуживается, либо стоит в очереди, либо получила отказ.

Пусть ТН[J] – J = 1, L[I --1], ТН[J] – момент поступления заявки, находящейся в очереди с момента t_i-1. Пусть t^обсл – момент времени поступления заявки, которая обслуживается в момент t_i. Тогда время начала обслуживания заявки определяется как

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

Будем считать основанием для включения в очередь само появление заявки. Сколько заявка находится в очереди? Пока не дойдет до начала обслуживания. В момент начала обслуживания принимается решение об обслуживании или исключении, т. е. в момент заявка исчезает из очереди, она либо начинает обслуживаться, либо попадает в отказ. То есть при появлении заявки t_i – она запоминается в очереди ТН(J) = t_i, L[I] = L[I - 1] + 1. В момент , L[I] = L[I] - 1, т. е. очередь увеличивается в момент поступления нового t_i и уменьшается в момент начала обслуживания, точнее, принятия решения об обслуживании или исключении. На первом шаге для t₁ очереди нет и канал свободен.

Важно, что происходит раньше появление t_i+1 или принятие решения . Если t_i+1 раньше, то очередь растет, если раньше, то очередь убывает.

Вывод. Точками изменения очереди являются не только t_i, но и , т. е. формулу для среднего надо изменить.

Может быть случай, когда L[I] = 0 – заявки поступают редко и успевают обслуживаться, очереди нет, или заявки поступают часто, что приводит к образованию очереди. Алгоритм должен все это обрабатывать.

Свойства очереди.

1. Каждая заявка попадает сначала в очередь.

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

3. Длина очереди изменяется в момент поступления очередной заявки и в момент принятия решения об обслуживании или отказе.

Заявки. t[I] – моменты появления заявок , t[I] Î [t₀, t₀ + T], t[I + 1] > t[I]. По реализации можно сформировать массив t^н[I] – моментов начала обслуживания I-й заявки, которая будет обслужена и массив N[I] – номеров заявок, которые будут обслужены.

.

Если

.

Нужно сформировать объединенный массив и каждому сопоставить количество заявок в очереди.

Для очереди нужен массив моментов рассмотрения i-й заявки t^р[I], i-я заявка рассматривается после (i - 1)-й и в тот момент, когда для нее подойдет момент начала обслуживания, т. е. от t_i до t^н[I] заявка в очереди.

8. Программная реализация алгоритмов
имитационного моделирования систем

Поиск по сайту: