Версия для печати темы Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > Центр помощи > Вопрос по Теории массового обслуживания

Автор: p0s0l 11.6.2005, 22:21

В двух словах проблема звучит так: в магазин (работает всего 1 продавец) каждые 2 минуты приходит покупатель, и обслуживается ровно 2 минуты. Загрузка продавца = 100%... Но это ведь не значит, что покупатель никогда не обслужится ? Вы согласны ? А судя по формулам, которые приведены ниже, ему придется стоять в очереди целую бесконечность... Теперь подробнее. Есть СМО (система массового обслуживания) - одноканальная, очередь - FIFO. Нужно рассчитать её характеристики. Проблемы начинаются уже в самом начале, при расчете Ro. (Коэффициент загрузки Ro определяет, какую часть времени устройство было занято на протяжении всего времени наблюдения за СМО) Дано к примеру такое: Код № заявки:      1  2  3  4  5  6  7  8  9  10 ---------------------------------------------- t прихода:      1  3  5  6  8  11 12 14 17 18 ---------------------------------------------- t обслуживания: 4  4  2  5  3  4  3  2  2  4 (навсякий случай поясню, это нужно понимать так: к примеру, вторая заявка приходит в момент времени=3, и время необходимое для её обслуживания=4)... Диаграмму работы СМО для наглядности можно посмотреть в прикрепленном рисунке, синеватый фон - промежуток времени наблюдения за СМО. Рассматриваемая СМО работала в течении ModelTime=33 единиц времени. Как видно из задания, в систему пришло Count=10 заявок. Теперь элементарнейшие расчеты: 1) Считаем среднее время обслуживания: Mean = (4+4+2+5+3+4+3+2+2+4)/10 = 33/10 = 3.3 2) Считаем интенсивность входного потока: Lambda = Count/ModelTime = 10/33 = 0.3030303... 3) Считаем коэффициент загрузки устройства: Ro = Lambda*Mean = 1 (что в принципе видно по диаграмме - устройство на протяжении всего времени наблюдения было занято, 100% загрузка) 4) Теперь самое интересное! Есть несколько формул расчета разных характеристик, и везде в знаметеле стоит (1-Ro) - т.е. получается деление на 0! Например: Среднее время ожидания: Код     Mean*Ro*(1 + C*C) w = -----------------          2*(1-Ro) (где C=Sigma/Mean=0.34 - коэффициент вариации, Sigma=1.122 - среднеквадратичное отклонение) ВОПРОС: Как быть ? Получается, что среднее время ожидания = бесконечности, как и другие некоторые параметры (среднее время пребывания в системе, среднее количество требований). Эти параметры можно посчитать по диаграмме, и они получаются далеко не бесконечностями , но нужно именно аналитическим способом, т.е. только по исходным данным! Что неправильно делаю ? В общем-то понятно, что раз время наблюдения = суммарному времени обслуживания всех заявок, то коэффициент загрузки будет единицой. Даже если я немного увеличу время наблюдения, Ro уменьшиться, то всё равно числа получатся слишком большие, нереальные... Мне не понятно, почему такие формулы? Как будто если Ro=1, то значит заявка никогда не обслужится? Помогите, кто с этим имел дело! Эту проблему надо срочно решить... Она явно из разряда простейших, просто я чего-то забыл или неучел или не те формулы использую...

Автор: esperant0 11.6.2005, 22:36

Добрый день. Одноканальная система обслуживания с неограниченной очередью т.е М\М\1, не стабильна при ро=1. То есть для нее не существуют стационарные вероятности.

Автор: p0s0l 11.6.2005, 22:46

А если я увеличу время наблюдения, ро уменьшится, будет меньше 1, тогда что ? Всё равно цифры большие получаются... И есть ли формулы тогда для этого случая (ро=1) ?

Автор: esperant0 11.6.2005, 22:48

Формулы верны, при ро=1, Среднее время ожидания равняется бесконечности Добавлено @ 22:50 Может быть это контринтуитивно, но ни синь пороха не поделаешь.

Автор: p0s0l 11.6.2005, 22:53

esperant0, ну а как тогда быть с тем примером про магазин, который я привел вначале ?... Как-то нелогично, не то что уж неинтуитивно: Цитата(p0s0l @ 11.6.2005, 22:21) в магазин (работает всего 1 продавец) каждые 2 минуты приходит покупатель, и обслуживается ровно 2 минуты. Загрузка продавца = 100%... Но это ведь не значит, что покупатель никогда не обслужится ?  Вы согласны ? А судя по формулам, которые приведены ниже, ему придется стоять в очереди целую бесконечность...

Автор: esperant0 11.6.2005, 23:04

Если бы в магазин приходил ТОЧНО один человек в минуту и он обслуживался РОВНО одну минуту - то Вы были бы правы. У нас же и время прихода и время обслуживания это пуасонновские процессы. Интуиция связана со следующим примером. Рассмотрим случайное блуждание на прямой. В начальный момент времени частица находится на луче с началом в точке 0. Если частица находится в ноле то она делает шаг вправо на одну клетку. На каждом шаге частица с вероятностью 0.5 делает шаг вправо на один и с такой же вероятностью влево на один. Нетрудно увидеть аналогию этой задачи с вашей. И так для этой задачи мат.ожидание координаты частицы при количестве шагов стремящемся к бесконечности, также равно бесконечности. А это значит что соответствующая одноканальная система, через бесконечное время может содержать бесконечное количество заявок и от сюда все ее беды.

Автор: p0s0l 11.6.2005, 23:23

Хм... Может тогда мне что-нибудь посоветуете ? Дело в том, что я делаю диплом по моделированию (лабораторный практикум), и там упор делается на моделирование одно- и многоканальных СМО. Студенту даётся задание вроде такого: Код № заявки:      1  2  3  4  5  6  7  8  9  10 ---------------------------------------------- t прихода:      1  3  5  6  8  11 12 14 17 18 ---------------------------------------------- t обслуживания: 4  4  2  5  3  4  3  2  2  4 Он строит диграмму (как в http://forum.vingrad.ru/index.php?act=Attach&type=post&id=439280 в первом моем сообщении): Дальше по диаграмме он рассчитывает характеристики СМО - это просто. Потом должен бы по идее рассчитать эти же характеристики аналитическим способом, т.е. только по исходным данным, не глядя на диаграмму... Но тут и появились эти проблемы... Как быть ? Если я сделаю времена обслуживания заявок в среднем меньше, чем промежутки между прибытиями заявок (Ro будет меньше 1) - это дело спасёт ?

Автор: esperant0 11.6.2005, 23:36

И так, поправте меня если я не прав. Исходные данные: Имеется однокональная система с одним продавцом и бесконечной очередью. М\М\1 Известно, что время обслуживания распределено экспоненциально 0.5, т.е в среднем как Вы и сказали каждые две минуты приходит покупатель. Количество покупателей приходящих за одну минуту распределено по Пуасону с параметром 0.5, т.е в среднем в две минуты приходит один покупатель. Имеется также набор наблюдений над системой - Ваша таблица и диаграмма. Требуется: Дать оценки параметров системы с помощью эксперементальных данных - таблицы. Найти аналитические выражения параметров системы, основываясь на: время обслуживания распределено экспоненциально 0.5, т.е в среднем как Вы и сказали каждые две минуты приходит покупатель. Правильно ли я Вас понял

Автор: p0s0l 11.6.2005, 23:52

Цитата(esperant0 @ 11.6.2005, 23:36) И так, поправте меня если я не прав. Исходные данные: Имеется однокональная система с одним продавцом и бесконечной очередью. М\М\1 Известно, что время обслуживания распределено экспоненциально 0.5, т.е в среднем как Вы и сказали каждые две минуты приходит покупатель. Количество покупателей приходящих за одну минуту распределено по Пуасону с параметром 0.5, т.е в среднем в две минуты приходит один покупатель. Имеется также набор наблюдений над системой - Ваша таблица и диаграмма. Требуется: Дать оценки параметров системы с помощью эксперементальных данных - таблицы. Найти аналитические выражения параметров системы, основываясь на: время обслуживания распределено экспоненциально 0.5, т.е в среднем как Вы и сказали каждые две минуты приходит покупатель. Правильно ли я Вас понял Почти да. Немного уточню: Таблица наблюдений составляется вручную преподавателем, цифры берет почти "с потолка". Диаграма - она не имеется, её однозначно строит студент по этой таблице. Распределение - студент сам считает по таблице, какое среднее время обслуживания и сколько человек в среднем приходит в минуту. Т.е. дана только таблица наблюдений, больше нет никаких известных данных...

Автор: esperant0 12.6.2005, 00:02

Ок. Данные данные Вам преподавателем не удачны, в том смысле что, оценка, полученная для ро, равняется единице. А значит система не стабильна, не имеет стационарных(предельных) вероятностей и кучи других параметров. Отсюда, если это не то, что хотел преподаватель, то надо подправить данные чтобы ро было меньше единице. Иначе аналитичиские подсчеты не уместны.

Автор: p0s0l 12.6.2005, 00:11

Хорошо. Я пробовал для данных, у которых Ро меньше 1. Получалось, что данные полученные аналитическим методом, и данные, полученные моделированем отличались в десятки раз (причем на глаз видно, что неправильно рассчитываются аналитические данные)... Хотя сейчас получше посмотрю рассчеты, может где ошибься, если не найду ничего - приведу пример тут снова...

Автор: esperant0 12.6.2005, 00:16

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

Автор: p0s0l 12.6.2005, 01:21

Все перепроверил, сделал выборку из 1000 человек (время наблюдения - около 3900), не из головы, а генерацией случайных чисел... Разница всё равно огромная... Параметры: Ro = 0.642 Среднее время обслуживания = 2.526 Среднеквадратичное отклонение = 1.203 Интенсивность входного потока = 0.254 В результате имеем: без скобок - данные моделирования, (в скобках - аналитические данные): Среднее время ожидания: w = 0.77 ( 2.781 ) Средняя длина очереди: 0.196 ( 0.707 ) Среднее время пребывания в магазине: 3.296 ( 5.307 ) Среднее количество покупателей в магазине: 0.838 ( 1.349 ) Ну уж слишком они различаются... Не должно быть такого... Добавлено @ 01:24 Вот пример полного расчета на 10 покупателей - загруженность продавца примерно 70%, почти все покупатели поступают прямо на обслуживание: Код № заявки:      1  2  3  4  5  6  7  8  9  10 ---------------------------------------------- t прихода:      1  3  5  8  12 14 17 19 22 26 ---------------------------------------------- t обслуживания: 2  1  3  1  3  1  2  3  1  2 (Диаграмма прикреплена к посту) 1) Среднее время обслуживания: Mean = (2+1+3+1+...+2)/10 = 1.9 2) Среднеквадратичное отклонение времени обслуживания: Sigma = (Sqr(2-1.9) + Sqr(1-1.9) + ... )/9 = 0.7666... 3) Коэффициент вариации: C = Sigma / Mean = 0.404 4) Интенсивность входного потока: Lambda = 10 / 27 = 0.37 (10 покупателей в течение 27 минут) 5) Коэффициент загрузки продавца: Ro = Lambda * Mean = 0.704 (это соответствует диаграмме) 6) Среднее время ожидания: Код     Mean*Ro*(1 + C*C) w = ----------------- = 2.624          2*(1-Ro) Хотя по диаграмме далеко не 2.624... Всего 1 покупатель ждал всего 1 минуту... Т.е. w = 0.1 7) Средняя длина очереди: Nq = Lambda * w = 0.972 По диаграмме: Nq = 0.37 8) Среднее время пребывания в магазине: Код                    Ro*(1+C*C) а) T = Mean * (1 + ----------) = 4.524                    2*(1-Ro) б) T = w + Mean = 4.524 По диаграмме: T = 2.0 9) Среднее количество покупателей в магазине: Код             Ro*Ro*(1+C*C) а) N = Ro + ------------- = 1.675               2*(1-Ro) б) N = Lambda*T = 1.675 По диаграмме: N = 0.741 Я конечно ожидал расхождения между результатами, но не до такой же степени! T больше чем в 2 раза отличается, w - в 26 раз(!), N - в 2 раза, Nq - в 3 раза...

Автор: esperant0 12.6.2005, 01:45

В любом случае, оценивая параметр:Среднее время ожидания по диаграмме, вы строите не смещенную оценку. При вычислении этого параметра по формуле, в которой фигурируют оценки других величин, мы скорей всего не получим несмещенную оценку. и это не очень хорошо. Хотя интуиция мне говорит, что сходимость должна быть, но сколько для этого нужно опытов не ясно. Вы уверены, что правильно генерируете величины пуасоноввского потока? Рекомендую спросить тут: http://www.nsu.ru/phorum/list.php?f=6 Добавлено @ 01:46 В любом случае нет смысла считать по формуле, лучше считать напрямую

Автор: p0s0l 12.6.2005, 01:57

Цитата Вы уверены, что правильно генерируете величины пуасоноввского потока? Я генерировал числа по экспоненциальному распределению. Цитата(esperant0 @ 12.6.2005, 01:45) Хотя интуиция мне говорит, что сходимость должна быть, но сколько для этого нужно опытов не ясно. Тут странность такая, что при увеличении числа опытов лучше не становится... Цитата Рекомендую спросить тут: http://www.nsu.ru/phorum/list.php?f=6 Еще подумаю, и если никто не поможет, спрошу... Добавлено @ 01:59 Цитата(esperant0 @ 12.6.2005, 01:45) В любом случае нет смысла считать по формуле, лучше считать напрямую Идея состояла в том, чтобы сравнить результаты моделирования с аналитическими результатами...

Автор: esperant0 12.6.2005, 02:12

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

Автор: p0s0l 12.6.2005, 11:17

Сейчас сделал замер для 10000 покупателей (время = ~81500): Nq и w - в 10 раз больше, N - в 6 раз, T - в 5 раз... Тут уж по-любому должно нормально быть, но нисколько не сходится... Вобщем-то источник проблемы я нашел . Только понять почему так и разрешить проблему опять не могу В книге написано про коэффициент вариации C: (здесь Mean - среднее время обслуживания, Sigma - среднеквадратичное отклонение времени обслуживания, Lambda - интенсивность входного потока). Цитата C = Sigma / Mean Для экспоненциального распределения С = 1, поскольку Mean и Sigma для этого закона равняется Lambda. Для регулярного детерминированного закона распределения C = 0 (т.к. Sigma = 0). У меня же в среднем получается C >= 2, т.е. всё-таки неправильное распределение... Видимо, это из-за того, что я округляю случайные величины до целых значений (ведь время прибытия и время обслуживания - целые числа): Код // времена прибытий     for i := 0 to Count-1 do       FItems[i].TimeArrive := 1 + Round(Random_Exponential*8); // времена обслуживаний     for i := 0 to Count-1 do       FItems[i].TimeProcess := 1 + Round(Random_Exponential*4); Random_Exponential выдаёт случайное дробное число от 0 до 1. Я это число привожу к целому, но видимо из-за этого получаются погрешности... (Random_Exponential распределяет числа правильно, я специально проверил, сделал генерацию 1000 чисел, не округлял их, и посчитал C = 1.015, т.е. почти 1...) В общем-то, пока временный выход я сделал следующим образом: C не рассчитывал как C=Sigma/Mean, а насильно задал C=1, тогда различия между получаемыми данными стали более приемлимы (10-20%)... Самое интересное вот что: если насильно задать C=0, то разница становиться еще меньше! (от 5 до 10%)... Почему так? Ведь C = 0 только для детерминированного закона распределения ? Почему C=0 больше подходит, чем C=1 ? Потом еще не понятно, почему пишут так: Цитата поскольку Mean и Sigma для этого закона равняется Lambda Может всё таки не Lambda, а 1/Lambda ? Хотя тоже как-то не того... Они ведь не должны быть связаны между собой (Mean и Lambda) ?

Автор: esperant0 12.6.2005, 11:33

"Видимо, это из-за того, что я округляю случайные величины до целых значений (ведь время прибытия и время обслуживания - целые числа): " Округляя случайные величины экспоненциального распределения, вы получаете величины - геометрического распределения, а это не очень хорошо. "Random_Exponential выдаёт случайное дробное число от 0 до 1" Не ясно почему не от 0 до бесконечности? "поскольку Mean и Sigma для этого закона равняется Lambda" Наверное имеется в виду закон Пуасона.

Автор: p0s0l 12.6.2005, 12:08

Цитата(esperant0 @ 12.6.2005, 11:33) Округляя случайные величины экспоненциального распределения, вы получаете величины - геометрического распределения, а это не очень хорошо. По другому я не знаю как... Цитата(esperant0 @ 12.6.2005, 11:33) "Random_Exponential выдаёт случайное дробное число от 0 до 1" Не ясно почему не от 0 до бесконечности? Блин, точно же... Эта функция выдаёт числа от 0 до бесконечности... Ладно, буду разбираться с этими распределениями/округлениями... Спасибо за участие в теме и наставлении на путь правильный !

Автор: p0s0l 12.6.2005, 15:12

Такой вопрос по распределениям возник... Вобщем-то как оказалось, округление не очень сильно влияет на "экспоненциальность", сильно же влияет "смещение" чисел (прибавление ко всем единицы)... Например: Если я сгенерирую 100 случайных чисел экспоненциальным распределенем: Код for i := 0 to n-1 do a[i] := Round(ExpRandom(4)); // числа от 0 до четырех То получается, к примеру, C = 1.023 Теперь беру эти же числа, только прибавляю ко всем единицу... Теперь уже C = 0.488... Вопрос: Как сделать, чтобы распределение было экспоненциальным, но чтобы каждое число было не меньше 1 ? Или так: можно ли в рассчете C из всех чисел вычесть единицу ?

Автор: esperant0 12.6.2005, 19:26

У Вас несколько противоречивые требования. С одной стороны, существуют сдвинутые экспоненциальные распределения. Причем для сдвинутных на параметр "а" экспо-ых распределений. Верно следующее MEAN=a+1\labmda STD=1\lambda И поэтому всегда когда есть сдвиг, Ваш параметр С, не будет равен единице. Кроме этого не совсем корректно в марковских процессах заменять экспон-ое распределение сдвинутым эксп-распределением. Мне кажется можно решить Вашу проблему уменьшив частоту дискретизации, можете ли Вы допустить, что время меняется с шагом 0.01, а не единица. При такой дискритизации и а=0.01 у Вас получится С близкое к единице. с уважением

Автор: p0s0l 12.6.2005, 22:04

Сделать шаг не целым - очень сложно... Это надо много чего перелопачивать, сейчас не представляется возможным... Мда... Значит сама идея не катит - нет аналитических формул для СМО со сдвинутым exp-распределением... Как плохо... Это большой облом для меня... Я уже столько понаписал в ПЗ про эти аналитические формулы, а теперь получается, их применять нельзя... Сложно ли самому вывести эти аналитические формулы для такого сдвинутого распределения ?...

Автор: esperant0 12.6.2005, 22:15

Формула есть вот она: f(x)=lambda*exp[-lambda(x-a)], x>=a. Только имхо этой формулой нельзя пользоватся для иммитации марковских цепей и С для такого распределения не 1. Еще один способ преодолеть проблему сдвига - брать ламбда очень маленьким.

Автор: p0s0l 12.6.2005, 23:56

Цитата f(x)=lambda*exp[-lambda(x-a)], x>=a Это функция плотности ?... Я имел в виду аналитические формулы для w, T и N. - сложно ли их вывести самому для сдвинутого эксп. распределения ? Цитата Еще один способ преодолеть проблему сдвига - брать ламбда очень маленьким. Это не подойдёт... по определенным причинам... Кстати, еще раз глянул книженцию, там сказано: Код Для системы G/G/1 среднее количество требований определяется как:          Ro*Ro*(1+C*C) N = Ro + -------------            2*(1-Ro) Т.е. эта формула должна действовать для любого распределения, в том числе и для моего сдвинутого exp-распределения ? Ведь G - это произвольное распределение... В принципе, все формулы, в которых присутствует C - это по смыслу, для универсального случая G/G/1, т.к. иначе сразу же подставили бы вместо C соответствующее значение: 1 или 0... Или я не прав ?

Автор: p0s0l 14.6.2005, 21:02

В общем-то, какой-никакой, но выход всё-таки я нашёл... Мне интересно, как это можно объяснить ? Например, беру какой-то входной поток из 10 покупателей, все они "обрабатываются" (моделируется работа СМО), строится диаграмма. Если взять время наблюдения = окончанию обработки последнего покупателя, то характеристики, получаемые путем моделирования, и характеристики, получаемые через аналитический расчет различаются очень сильно... Теперь беру просто увеличиваю время наблюдения на половину (в системе в это добавочное время не будет ниодной заявки, т.е. входной поток остаётся абсолютно этим же, наблюдаем за "пустотой")... Подсчитываю параметры обоими способами - и о! они практически идеально сходятся (различия в микронах)! Причем, я так и не понял зависимость, во сколько раз нужно увеличивать время наблюдения - оно для каждого случая своё... Единственную закономерность я уловил - чем больше Ro, тем в меньшее количество раз нужно увеличивать время наблюдения. Если Ro близко к 1 (~0.9), то увеличивать время наблюдения нужно всего где-то на 10-20%, совсем немного... Если Ro где-то 0.7, то увеличивать приходиться где-то от 500 до 1000%... По-смыслу, увеличивая время наблюдения, C и среднее время обслуживания не меняются, но уменьшается Lambda, а следовательно и Ro... На данный момент, я увеличиваю на 1 время наблюдения, сравниваю характеристики, и если они приблизились друг к другу, продолжаю увеличивать время наблюдения...

Автор: Guest 15.6.2005, 00:28

Цитата(p0s0l @ 14.6.2005, 21:02) В общем-то, какой-никакой, но выход всё-таки я нашёл... Мне интересно, как это можно объяснить ? Например, беру какой-то входной поток из 10 покупателей, все они "обрабатываются" (моделируется работа СМО), строится диаграмма. Если взять время наблюдения = окончанию обработки последнего покупателя, то характеристики, получаемые путем моделирования, и характеристики, получаемые через аналитический расчет различаются очень сильно... Какие аналитические формулы вы используете? для М\М\1 или G\G\1?

Автор: p0s0l 15.6.2005, 10:24

Цитата(Guest @ 15.6.2005, 00:28) Какие аналитические формулы вы используете? для М\М\1 или G\G\1? В общем-то я формулы взял из книжки, но там как-то непонятно написано... Я так понял, что эти формулы для G/G/1: Код     Mean*Ro*(1 + C*C) w = -----------------          2*(1-Ro)                 Ro*(1+C*C) T = Mean * (1 + ----------)                 2*(1-Ro)          Ro*Ro*(1+C*C) N = Ro + -------------            2*(1-Ro) (правильно я понял или нет ?) Еще пробовал по этим формулам, считающим по вероятностям пребывания k требований в системе: http://www.nsu.ru/matlab/Exponenta_RU/educat/systemat/gomboev/labsmo/smo1_n.asp.htm Результат где-то в 2 раза ближе к истине, но все равно различия сильные ...

Powered by Invision Power Board (http://www.invisionboard.com)
© Invision Power Services (http://www.invisionpower.com)