Эффективное поведение в очереди

[lena7]

Рассмотрим два поведения в очереди в супермаркете. Пусть имеется $n$ касс, $m$ покупателей и каждый обслуживается случайное (с равномерным распределением) время $t\in\mathbb N$ (пускай минут), $1\le t \le T$.

1) Покупатели изначально разделились на $n$ равных куч и тупо идут каждый к своей кассе.
2) Покупатели образуют единую очередь. При освобождении любой кассы первый в очереди её занимает и т. д.

(Оффтоп)

В реальном супермаркете, конечно, используется смесь обоих методов, ибо покупатели подходят не все сразу. А когда подходят, выбирают наименьшую очередь.

Тут сказано, что в случае с тремя кассами второй способ эффективнее примерно в 3 раза.

Если это верно, то как можно доказать? Я не соображу. Более того, я написала простую программку, моделирующую две очереди, но второй метод лишь слегка обыгрывает первый. Варьировала $n,m,T$ -- то же. Есть вероятность, что программу написала не верно, хотя вроде всё проверила.

(Оффтоп)

Для $n=3$, $m=30$, $T=10$ по первому методу получается в среднем 72 минут, по второму -- 57.
Для $n=3$, $m=90$, $T=20$, соответственно 371 и 318 мин.

[_Ivana]

У меня получается примерно в полтора раза. Во втором случае среднее время обслуживания всей толпы равно $0.5m(T+1)/n$, в первом $m/n + 0.75(m(T - 1)/n)$ Прогоните ваш алгоритм в цикле побольше раз и сравните полученные значения с моими формулами.

[gris]

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

[_Ivana]

Цитата:

В реальной жизни так не бывает.

Ну мы же не про реальную жизнь а про сферические очереди в вакууме. Хотя, запросто можно представить ситуацию в МФЦ - взял талончик в определенное окно - будешь стоять только в него :)

[gris]

Брал совсем недавно талончик в расчётный центр по квартплате. Там номер очереди, а на табло высвечивается номер окошка для этого номера по мере освобождения. Наверное, они Вас прочитали и перешли на более эффективный путь обслуживания

[_Ivana]

Небольшое уточнение - волшебное число $0.75$ в моей второй формуле получается как $1 - 1/(n + 1)$ - раз я пишу в общем виде для любого количества касс, то надо это уточнить :)

[lena7]

_Ivana
Как вы получили формулу для второго случая?

(Оффтоп)

_Ivana в сообщении #619536 писал(а):

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

$n=3$, $m=300$, $T=10$, среднее за 1000 итераций:
1) 674.647
2) 552.158
Повторюсь, что программа может содержать ошибку. Была бы рада, если бы кто-то поопытней в программировании промоделировал оба метода.

(Оффтоп)

gris в сообщении #619550 писал(а):

Брал совсем недавно талончик в расчётный центр по квартплате. Там номер очереди, а на табло высвечивается номер окошка для этого номера по мере освобождения. Наверное, они Вас прочитали и перешли на более эффективный путь обслуживания

У нас такая система давно в тех местах, где очереди медленные и длинные. Например, в очереди на субсидию на оплату услуг ЖКХ.

Недавно такую же штуку сделали в ближайшем сбербанке.

(Оффтоп)

ADDED. Вот лог работы программы для $n=3$, $m=10$, $T=5$ с единой очередью. Первый массив -- это состояния касс: число означает, через сколько минут (тиков) касса будет свободна. Второй массив -- это массив покупателей. Они представляются числом минут, требуемых для их обслуживания.

#######
# tick 1

[0, 0, 0]
[1, 3, 3, 4, 3, 1, 1, 4, 3, 1]

#######
# tick 2

[0, 2, 2]
[4, 3, 1, 1, 4, 3, 1]

#######
# tick 3

[3, 1, 1]
[3, 1, 1, 4, 3, 1]

#######
# tick 4

[2, 0, 0]
[3, 1, 1, 4, 3, 1]

#######
# tick 5

[1, 2, 0]
[1, 4, 3, 1]

#######
# tick 6

[0, 1, 0]
[4, 3, 1]

#######
# tick 7

[3, 0, 2]
[1]

#######
# tick 8

[2, 0, 1]
[]

#######
# tick 9

[1, 0, 0]
[]

9.0

Вроде криминала нет?

[_Ivana]

Цитата:

Как вы получили формулу для второго случая?

Я не считаю себя опытным, но: берем одну кассу, время обслуживания $x$ покупателей у нас равновероятно распределено от $1\cdot x$ до $T\cdot x$, среднее время обслуживания - среднее арифметическое. А если мы формируем группу из трех независимых обслуживаний на такой кассе, то максимальное время обслуживания будет равно $x + (1 - 1/(3 + 1))(T\cdot x - x)$ Проще говоря - если у на с есть равномерно распределенная от 0 до 1 случайная величина, мы просуммируем её значения много раз и поделим на количество этих раз - получим $0.5$. А если будем брать по $3$ значения, суммировать их максимум и делить на количество троек - получим $0.75$. А если по $n$ значений ($n$ касс), то $1 - 1/(n + 1)$

[lena7]

lena7 в сообщении #619510 писал(а):

и каждый обслуживается случайное (с равномерным распределением)

Кстати, а есть какие-нибудь статистические данные по этому поводу? Может и не равномерное вовсе. Мне интересно, откуда Bill Hammack взял трёхкратный выигрыш.

[_Ivana]

Попытался ещё чуть подумать - вполне вероятно что мои формулы задают верхний предел тормознутости первого варианта - когда в одну кассу столпились все самые долгообслуживаемые покупатели. Но если они правильные, то даже в этом искусственном случае соотношение около полутора, и то при большом разбросе $T$.

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

$n = 3, m = 30, T = 10 : t_1 = 62, t_2 = 55$
$n = 3, m = 90, T = 20 : t_1 = 340, t_2 = 315$
$n = 3, m = 300, T = 10 : t_1 = 572, t_2 = 550$

(Оффтоп)

n = 3;
m = 300;
T1 = 1;
T2 = 10;

N = 10000;
t_max_N_1 = 0;
t_max_N_2 = 0;

for i_N = 1:N
    
    t_max_1 = 0;
    for i_n = 1:n
        t = 0;
        for i_m = 1:m/3
            t_i = T1 + (T2 - T1)*rand();
            t = t + t_i;
        end
        t_max_1 = max(t_max_1, t);
    end
    t_max_N_1 = [t_max_N_1, t_max_1];
    
    t_max_2 = 0;
    for i_m = 1:m
        t_i = T1 + (T2 - T1)*rand();
        t_max_2 = t_max_2 + t_i;
    end
    t_max_N_2 = [t_max_N_2, t_max_2/3];
    
end

t_max_N_1(1) = [];
t_max_N_2(1) = [];

t_S_1 = 0;
t_S_2 = 0;
for i_N = 1:N
    t_S_1 = t_S_1 + t_max_N_1(i_N);
    t_S_2 = t_S_2 + t_max_N_2(i_N);
end
t_p_1 = t_S_1/N;
t_p_2 = t_S_2/N;
t_p_1
t_p_2

[alisa-lebovski]

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

[Padawan]

Если ни одна касса не простаивает, то по-моему без разницы, как покупатели к ним подходят.

[_Ivana]

Цитата:

Если ни одна касса не простаивает, то по-моему без разницы, как покупатели к ним подходят.

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

[gris]

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

[_Ivana]

Если в моем коде заменить равномерное распределение каждой кассы на нормальное, то легко получаются результаты и для этого случая. Более того - можно всем трем кассам задавать распределения с разными параметрами (зависящими от квалификации кассира, например).