Введение в теорию массового обслуживания

Министерство образования и науки Российской ФедерацииФедеральное государственное бюджетное образовательное учреждениевысшего профессионального образованияПЕТРОЗАВОДСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТЕ. К. БелыйВведение в теорию массовогообслуживанияУчебное пособие для студентов, обучающихся по направлению«Информационные системы и технологии»ПетрозаводскИздательство ПетрГУ20141УДК 519.21ББК 22.172Д439Печатается по решению редакционно-издательского советаПетрозаводского государственного университетаИздается в рамках реализации комплекса мероприятийПрограммы стратегического развития ПетрГУ на 2012—2016 гг.Ре ц е н з е н т ы :д-р физ.-мат.

наук, профессор каф. геометрии и топологии ПетрГУС. С. Платонов;д-р эконом. наук, зав. отделом моделирования и прогнозированиярегионального развития института экономики КарНЦ РАНП. В. ДружининБ439Белый, Евгений Константинович.Введение в теорию массового обслуживания : учебное пособие длястудентов, обучающихся по направлению «Информационные системыи технологии» / Е. К. Белый. – Петрозаводск : Издательство ПетрГУ,2014. – 76 с.ISBN 978-5-8021-2203-7Учебное пособие предназначено для студентов, обучающихся понаправлению «Информационные системы и технологии», а также длявсех интересующихся теорией массового обслуживания и владеющихматематическим аппаратом в рамках вузовского курса высшейматематики и теории вероятностей.УДК 519.21ББК 22.172ISBN 978-5-8021-2203-7© Белый Е.

К., 2014© Петрозаводский государственный университет, 20142.СодержаниеВведение4Глава 1. Входящий поток9§ 1.1. Определение простейшего потока . . . . . . . . . . . . .11§ 1.2. Уравнения простейшего потока . . . . . . . . . . . . . . .12§ 1.3. Свойства простейшего потока.

. . . . . . . . . . . . . .18§ 1.4. Простейший нестационарный поток . . . . . . . . . . . .21Глава 2. Марковская модель СМО26§ 2.1. Уравнения Колмогорова . . . . . . . . . . . . . . . . . . .29§ 2.2. Одноканальная СМО с отказами . . .

. . . . . . . . . . .31§ 2.3. Дублированная СМО с восстановлением . . . . . . . . .38§ 2.4. СМО с приоритетными заявками . . . . . . . . . . . . .44Глава 3. Процессы гибели и размножения55§ 3.1. Формулы Эрланга . . . . . . . . . . . . . . . . . . . . . .56§ 3.2. Многоканальная СМО с отказами . . . . . . . . . . . . .58§ 3.3. Одноканальная СМО без ограничений на длину очереди 62§ 3.4. Одноканальная СМО с ограничением на длину очереди66§ 3.5. Одноканальная СМО с нетерпеливыми заявками .

. . .67§ 3.6. Замкнутая одноканальная СМО . . . . . . . . . . . . . .68Биографические справки72Список литературы753ВведениеТо и дело раздаются голоса, утверждающие, будто главная задача обучения математике в школе и вузе – это научить людейлогически мыслить. Отсюда чрезмерная формализация математических дисциплин, изложение их в отрыве от задач практики. Слов нет, привычка к логическому мышлению – хорошеедело, но у математики есть и другие задачи: активного вмешательства в практику, разумной организации производственныхи иных процессов. Жизнь непрерывно требует от математика ответа на вопрос, как поступить в том или другом случае,при тех или других сложившихся обстоятельствах.

И дело егочести – не уходить от этих требований в пучину абстракций,а по мере сил удовлетворять их.Е. С. ВентцельТеория массового обслуживания родилась в датском королевстве в начале XX века под именем «Теория очередей». Первыеидеи теории были высказаны директором Копенгагенской телефонной компании Фредериком Йохансоном в 1907 году в статье«Время ожидания и число вызовов».

Затем идеи были математически развиты и оформлены инженером той же компании Агнером Эрлангом. Опубликованную им в 1909 году статью «Теориявероятностей и телефонные переговоры» принято считать краеугольным камнем в фундаменте теории. В 30-х годах теориейочередей серьезно занялся Александр Яковлевич Хинчин в связис автоматизацией московской городской телефонной сети. В на4учной литературе прижился введенный тогда Хинчиным термин«теория массового обслуживания» (ТМО), а предмет исследований вскоре стали называть системами массового обслуживания(СМО). ТМО опиралась на фундаментальные работы в областитеории случайных процессов Андрея Андреевича Маркова, Андрея Николаевича Колмогорова и ряда других математиков.Хотя все началось с телефона, вскоре на ТМО обратили внимание представители ряда наук, далеких от проблем связи.

Оказалось, что в модели СМО вписываются многие реальные явления:от железнодорожных касс до противовоздушной обороны и процессов, протекающих в компьютере. С системами массового обслуживания мы сталкиваемся буквально на каждом шагу. СМО– это торговля, общественное питание, транспорт, бани, банки,страховые компании, налоговая инспекция, парикмахерские, индустрия развлечений, ремонтные мастерские, здравоохранение,образование и т. д.Что же представляет собой СМО? Это система, реализующаямногократное выполнение однотипных задач. Для любой такойсистемы характерен, по крайней мере, один входящий поток –поток заявок на обслуживание, множество каналов обслуживания и как минимум один выходящий поток – поток обслуженныхзаявок.

СМО может быть значительно сложней. Выходящие потоки обслуженных заявок, заявок, получивших отказ и заявок,обслуживание которых было по той или иной причине прервано5в свою очередь могут образовывать входящие потоки для других подсистем СМО. Так, поток пациентов на прием к терапевтуразделяется после обслуживания на выходящий поток заявок,обслуживание которых завершено, и потоки заявок на обслуживание к хирургу, кардиологу и другим специалистам.

Источниквходящего потока в зависимости от целей исследования можетрассматриваться как нечто внешнее по отношению к СМО илиже как часть системы.Насколько для организации массового обслуживания нужна теория? Действительно, во многих случаях руководящие решенияопираются на опыт и интуицию. И не всегда эти решения оказываются плохими. Однако обратимся к примеру из третьей главы:пусть пропускная способность городского травматологическогопункта – 10 пациентов в час, а в городе в этот период временислучается 9 травм в час. На первый взгляд, здесь все в порядке –травматологический пункт должен справиться с работой.

И всеже, согласно теории, средняя длина очереди у пункта составит8,1 человека, а среднее время пребывания пациента в очереди– 0,9 часа (54 минуты). При этом 10 % времени работы пунктапридется на простой. Например, если смена продолжается 6 часов, то из них 36 минут персонал простаивает. Другой пример:малое количество касс в супермаркете приведет к росту очередейв определенные периоды работы магазина и потере части покупателей, а большое – к большому простою и неэффективнымрасходам на заработную плату кассиров. Оптимальное решение6опять неочевидно.

Мы только что рассмотрели два самых простых примера. А если речь пойдет об организации работы районной поликлиники? Это уже проектирование сложной системы!В основу предлагаемого учебного пособия лег курс лекций, втечение нескольких лет читаемый автором для студентов, обучающихся по направлению «Информационные системы и технологии». Пособие призвано помочь студенту овладеть первичными навыками исследования СМО и построения их моделей.К сожалению, объем книги не позволил автору в полной меререализовать свои планы.

Однако, учитывая опыт преподаваниядисциплины, он стремился тщательно разобрать вопросы, вызывающие у студентов наибольшее затруднение, дать приводимыедоказательства достаточно подробно, сделать изложение доступным для широкого круга читателей. Небольшая книга не можетдать ответы на широкий спектр вопросов, но иногда, преждечем открыть солидную монографию, человеку нужно прочитать«тонкую» книгу, чтобы понять, кому и зачем нужна теория, ичтобы возникла заинтересованность.Пособие состоит их трех глав. Первая посвящена входящим потокам – простейшему и простейшему нестационарному.

Во второй рассматриваются уравнения Колмогорова и примеры их решения для достаточно простых СМО. Таким образом, для ряда СМО получены аналитические решения дифференциальныхуравнений, описывающих их работу. В более сложных случаях7аналитическое решение получить непросто. Однако в широкомклассе задач вероятности возможных состояний СМО быстроприближаются к некоторым предельным значениям – установившемуся решению. В третьей главе анализируются системыгибели и размножения для случая установившихся решений.Значительное влияние на структуру и содержание предлагаемого пособия оказали работы А. Я. Хинчина [8], Б. В. Гнеденко иИ.

Н. Коваленко [3], Л. Г. Лабскера и Л. О. Бабешко [7].В качестве источника задач для творческого усвоения и закрепленияпройденногоматериаламожно рекомендовать книгуО. А. Новикова и С. И. Петухова [6].Замечанияипредложенияможнонаправлятьиз адресов:belyi@petrsu.ru или kurs_belyi1@mail.ru.8поодномуГлава 1. Входящий потокУже давно в самых разных сферах человеческой деятельностидля описания процессов, протекающих во времени, широкое распространение получило понятие поток событий, которое означает последовательность событий, разделенных некоторыми интервалами времени.