2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки


Правила форума


В этом разделе нельзя создавать новые темы.

Если Вы хотите задать новый вопрос, то не дописывайте его в существующую тему, а создайте новую в корневом разделе "Помогите решить/разобраться (М)".

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

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

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



Начать новую тему Ответить на тему На страницу 1, 2  След.
 
 Эффективное поведение в очереди
Сообщение16.09.2012, 12:25 
Заслуженный участник


29/04/12
268
Рассмотрим два поведения в очереди в супермаркете. Пусть имеется $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 мин.

 Профиль  
                  
 
 Re: Эффективное поведение в очереди
Сообщение16.09.2012, 13:22 


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

 Профиль  
                  
 
 Re: Эффективное поведение в очереди
Сообщение16.09.2012, 13:30 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 Re: Эффективное поведение в очереди
Сообщение16.09.2012, 13:32 


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

 Профиль  
                  
 
 Re: Эффективное поведение в очереди
Сообщение16.09.2012, 13:43 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 Re: Эффективное поведение в очереди
Сообщение16.09.2012, 13:48 


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

 Профиль  
                  
 
 Re: Эффективное поведение в очереди
Сообщение16.09.2012, 13:49 
Заслуженный участник


29/04/12
268
_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

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

 Профиль  
                  
 
 Re: Эффективное поведение в очереди
Сообщение16.09.2012, 14:02 


05/09/12
2587
Цитата:
Как вы получили формулу для второго случая?
Я не считаю себя опытным, но: берем одну кассу, время обслуживания $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)$

 Профиль  
                  
 
 Re: Эффективное поведение в очереди
Сообщение16.09.2012, 14:12 
Заслуженный участник


29/04/12
268
lena7 в сообщении #619510 писал(а):
и каждый обслуживается случайное (с равномерным распределением)

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

 Профиль  
                  
 
 Re: Эффективное поведение в очереди
Сообщение16.09.2012, 14:46 


05/09/12
2587
Попытался ещё чуть подумать - вполне вероятно что мои формулы задают верхний предел тормознутости первого варианта - когда в одну кассу столпились все самые долгообслуживаемые покупатели. Но если они правильные, то даже в этом искусственном случае соотношение около полутора, и то при большом разбросе $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

 Профиль  
                  
 
 Re: Эффективное поведение в очереди
Сообщение16.09.2012, 16:25 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 Re: Эффективное поведение в очереди
Сообщение16.09.2012, 16:33 
Заслуженный участник


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

 Профиль  
                  
 
 Re: Эффективное поведение в очереди
Сообщение16.09.2012, 16:37 


05/09/12
2587
Цитата:
Если ни одна касса не простаивает, то по-моему без разницы, как покупатели к ним подходят.
Правильно. Но мы рассматриваем вариант когда все покупатели сразу делятся на равное количество человек, выбирают себе кассу и не меняют её даже если соседняя уже свободна.

 Профиль  
                  
 
 Re: Эффективное поведение в очереди
Сообщение16.09.2012, 16:37 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 Re: Эффективное поведение в очереди
Сообщение16.09.2012, 16:41 


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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 23 ]  На страницу 1, 2  След.

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group