Теория массового обслуживания, или теория очередей

ВОЗНИКНОВЕНИЕ
Оказалось, что потоки покупателей посещающих гипермаркеты носят очень неравномерный характер. В начале рабочего дня количество покупателей относительно небольшое. Далее этот поток начинает стремительно нарастать и к полудню достигает своего пика. К обеду поток постепенно снижается, а после обеда опять начинает нарастать достигая через несколько часов своего второго пика, после чего плавно снижается и к концу рабочего дня становиться опять сравнительно небольшим. Как бороться с этой «стихией природы», компании не знали.

Даниэль Бернар первый начал разрабатывать систему массового обслуживания
Кроме полной компьютаризации всех участков работы гипермаркетов была введена в эксплуатацию система планирования графиков работы кассиров, позволяющая составлять эти графики таким образом, что количество фактически работающих кассиров в точности соответствовало их потребности для магазина на каждом небольшом промежутке времени. Таким образом, на протяжении всего рабочего дня, никогда не возникало нехватки кассиров и никогда не было их избытка, что позволяло экономить до половины фонда оплаты труда кассиров и полностью исключить образование длинных очередей у кассовых узлов.

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

Подробнее о СМО
Система состоящая из покупателей, с одной стороны, и из кассовых узлов (кассиров), с другой стороны, является не чем иным как - системой массового обслуживания. Таким образом, в терминах этой теории покупатели являются - потоком заявок, а кассиры - каналами обслуживания.
Первые задачи теории массового обслуживания были рассмотрены сотрудником Копенгагенской телефонной компании датским ученым А.К. Эрлангом в период между 1908 и 1922 гг.

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

Задачи теории массового обслуживания встречаются буквально нам каждом шагу и в самых различных областях окружающей нас действительности. Вполне естественно, что круг задач этой теории весьма обширен, но для нас важно то, что некоторые задачи, из казалось бы совершенно различных областей нашей жизни, с точки зрения математика являются эквивалентными. То есть, они подчиняются одинаковым математическим закономерностям и описываются одинаковыми уравнениями, неравенствами и т.п. Поэтому обсуждая систему массового обслуживания «покупатель - кассир», мы будем опираться на знания и статистические данные, полученные не только непосредственно для этой области, но и полученные в других областях человеческой деятельности. В частности, из такой традиционной области задач теории массового обслуживания, как телефония, а точнее - организация центров обслуживания вызовов (call-центров)

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

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

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

Имеющиеся 36 вертикальных полосок соответствуют 18-ти часовому рабочему дню гипотетического гипермаркета. То есть, высота каждой полоски означает количество покупателей, посетивших магазин за полчаса его работы.

Причины неравномерности потока покупателей
Длительные наблюдения за потоком покупателей на различных торговых предприятиях и анализ соответствующих статистических данных свидетельствуют о том, что характер указанных диаграмм является весьма устойчивым

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

Расчет
На интуитивном уровне понятно, что потребность в кассирах пропорциональна количеству покупателей, посетивших магазин за некоторый промежуток времени. Чем больше покупателей, тем больше потребность в кассирах. Причем количество кассиров должно быть таким, чтобы у кассовых узлов не образовывалось длинных очередей, а длительность ожидания непосредственного расчета с кассиром не превышала, например, трех минут. Или длинна очереди у кассового узла не превышала 2-х - 3-х человек.

Возникает вопрос - каким образом определить эту потребность? На первый взгляд задача кажется достаточно простой. Если мы знаем, что каждый кассир за одни час работы может обслужить 30 покупателей и мы знаем, что за этот час магазин посетило, например, 300 человек, то достаточно 300 разделить на 30 и мы получим искомое число - 10 кассиров
Обратим внимание на то, что в нашем расчете никак не присутствует такой показатель как длинна очереди из ожидающих обслуживания.

На самом деле, расчет потребности в кассирах при известном потоке покупателей и известной производительности труда кассиров является не такой простой задачей. Как показывает и теория и практика (статистические данные) при таком методе расчета у кассовых узлов будут образовываться длинные очереди.
Но для нас сейчас это не важно. Важно то, что диаграмма потребности в кассирах будет «весьма точно» (в смысле своих пропорций) повторять диаграмму суточного потока покупателей. На следующем рисунке 4 такая диаграмма изображена.

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

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

Бригадный метод
Суть этого метода достаточно проста, чем он и привлекателен. Например, руководством магазина принимается решение о создании трех бригад кассиров для работы в две смены. Пока первая бригада работает утром а вторая вечером, у третьей бригады выходной. На следующий день вторая бригада работает утром, а третья вечером. Первая соответственно отдыхает. Далее процесс планирования, если его так можно назвать, симметрично продолжается.

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

Теперь коротко перечислим список недостатков такого метода планирования.
Еще раз внимательно посмотрим на рисунок 4 с изображением потребности в кассирах на протяжении суток. Вычислим площадь прямоугольника одна сторона которого равна количество интервалов времени, а другая сторона равна максимальной потребности в кассирах. Далее сравним вычисленную площадь с площадью фигуры изображенной на этом же рисунке. Площадь фигуры составляет всего 60% от площади прямоугольника, общитанного нами. А это означает, что 40% времени кассиры не заняты обслуживанием покупателей. Что в свою очередь означает - сорок процентов фонда оплаты труда расходуется в пустую.

Далее обратим внимание на то, что после первых четырех часов работы всем кассирам, причем одновременно, нужно обедать. Это их законное право. А покупателей (еще раз посмотрим на рисунок 4) становиться все больше и больше.
Как было отмечено выше, в конце рабочего дня из-за малой загруженности, кассиры в основном заняты обсуждением последних новостей или внимательным разглядыванием потолка торгового зала, а по законодательству с 22 часов их работа оплачивается с повышающим коэффициентом как ночная.

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

Вариант первый. Назовем его условно - забота о покупателях. Это, как было описано выше, поддерживать количество кассиров в бригадах на уровне достаточном для покрытия (качественного обслуживания) пикового потока покупателей. Выше нами было установлено, что 40% фонда оплаты труда при таком выборе будет расходоваться в пустую. Но обратим внимание на то, что мы еще не анализировали последствия графиков изображенных на рисунке 1 и 2. С учетом сезонных и недельных колебаний потока покупателей потери могут превышать и более половины фонда оплаты труда, а моральное разложение коллектива может достигнуть неприемлемого состояния.

Вариант второй. Назовем его условно - экономика должна быть экономной (а эффективность эффективной). Это сокращение до среднего арифметического количества кассиров в бригадах (т.е. уменьшение на 40% по сравнению с предыдущим вариантом). Более точно среднее арифметическое можно вычислить учитывая сезонные и недельные колебания потока покупателей. В этом случае мы будем иметь следующую картину.

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

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

Инновационный выбор
В странах с развитой рыночной экономикой уже давно используется метод планирования индивидуальных графиков работы. Суть этого метода, «Назначение нужных работников с нужными навыками и умениями на необходимую работу в нужное время».

Технология планирования работы по индивидуальным графикам, как правило, включает в себя следующие элементы:
Прогноз потребностей - чтобы знать, какое количество работников и с какими навыками и умениями потребуется предприятию в будущем;
Составление расписания - чтобы количество работников, их навыки и умения всегда полностью соответствовали потребности предприятия;
Учет времени - для точного учета рабочего времени работников предприятия;
Анализ и текущий контроль - чтобы видеть, соответствует ли текущая ситуация плану предприятия, и в случае отклонений от этого плана, быстро и эффективно внести коррективы.

Как показала обширная и длительная практика стран с развитой рыночной экономикой, применение технологии планирования работы по индивидуальным графикам приводит к следующим позитивным последствиям:
Снижению затрат на персонал, так как исключается планирование излишней рабочей силы, исчезает непродуктивное время простоя и ненужные сверхурочные работы. Кроме того, исключены неправильные выплаты персоналу, происходящие из-за ошибок в расчетах, так как постоянно ведется учет фактически отработанных часов;

Росту производительности труда и мотивации персонала, поскольку осуществляется вовлечение работников в процесс планирования, где учитываются их предпочтения относительно рабочих часов. В результате планирования, ориентированного на индивидуальные графики работы, производительность труда работников возрастает до 25%, и, следовательно, в том числе и по этой причине, затраты на персонал значительно уменьшаются;

Снижению затрат на управление, поскольку трудоемкие административные процессы автоматизированы и почти нет необходимости в бумажной работе, а исправления и расчеты в ручную, приводящие к ошибкам, исключены;
Более справедливому распределению заданий и рабочих часов, так как этот процесс является результатом беспристрастного и открытого распределения популярных и менее популярных рабочих часов, а также заданий и мест в соответствии с нормативными требованиями и договорными обязательствами;

Снижению затрат на информационные технологии, в результате объединения и централизации локальных систем, предназначенных для планирования персонала и управления рабочим временем в одном универсальном решении;
Уменьшению текучести кадров и, следовательно, снижению затрат на подбор, расстановку и обучение персонала, так как мотивация работников растет;

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

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

Как показали проведенные социологические исследования, в последнее время наметилась заметная тенденция миграции персонала магазинов где используются графики 2/2 (фактически 13-ти часовой рабочий день) и 2/1 с циклическими выходными, в те места где используются индивидуальные графики работы. По проведенным опросам, подавляющее большинство персонала готова даже на некоторое снижение зарплаты с тем чтобы иметь продолжительность рабочей смены не более восьми - девяти часов в удобное для них (и выгодное для предприятия) время. То есть с тем, что бы работать по индивидуальным рабочим графикам.

Таким образом гипермаркеты, использующие систему индивидуальных графиков, получают значительное конкурентное преимущество при найме на работу квалифицированного персонала по сравнению с организациями работающими по старинке. Кроме того, индивидуальные графики работы позволяют использовать категорию работников которые хотели бы трудиться в режиме сокращенного рабочего дня или в режиме сокращенной рабочей недели, что также является дополнительным конкурентным преимуществом при формировании трудового коллектива.
Многочисленные случаи (у нас в стране) перехода кассиров на работу в гипермаркеты «Ашан», где с успехом используются индивидуальные рабочие графики, из других магазинов, где такие графики не используются, наглядное и яркое тому подтверждение.

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

Интуитивная формулировка задачи
Итак, для заданного интервала времени (горизонта планирования), например, 28 суток, на весь этот интервал времени, требуется построить, для каждого кассира, индивидуальный график выхода на работу, имея в качестве исходных данных:

Список принятых на работу кассиров, при условии, что их количество достаточно для построения индивидуальных графиков. Это количество нужно рассчитать заранее;
Для каждых суток, заданного интервала времени, получасовую потребность гипермаркета в кассирах

Это значит, что для каждого кассира и каждого суточного интервала времени требуется указать:
Работает ли в данный суточный интервал времени кассир;
Время начала работы кассира;
Время начала обеда
Время окончания обеда
Время окончания работы
Рабочее место за которым будет работать кассир

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

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

В минимально возможных количествах допускаются короткие выходы на работу продолжительностью от четырех до шести часов;
Кассиры могут быть разделены на три категории - а) работающие только в обычную смену, б) работающие только в короткую смену, в) работающие и в обычную, и в короткую смену;
Для некоторых кассиров может быть установлена сокращенная рабочая неделя, например, - 3/4 или 2/5;

Главное ограничение. В течении каждого планируемого гипермаркетом промежутка времени, на которые разделен суточный интервал, суммарное количество работающих кассиров должно точно соответствовать заданной потребности в кассирах. То есть, фигурам такого же типа, что изображены на рисунке 4;
Для каждого кассира, начало каждой последующий смены должно постепенно смещаться с утренних часов к обеденным и далее к вечерним с периодическим повторением указанного цикла;

Часть времени, на которое составляется расписание, кассир может находиться в очередном отпуске;
На протяжении всего периода планирования кассиры распределяются по рабочим местам тем или иным оптимальным образом, например, все кассовые узлы должны быть заполнены работниками равномерно, а каждый кассир должен поработать на всех рабочих местах за некоторый промежуток времени одинаковое количество раз

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

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

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

Поток без последействия
Поток без последействия, если число событий любого интервала времени (t
, t+x) не зависит от числа событий на любом другом не пересекающемся с нашим (t, t+x) интервале времени

Стационарный поток
Поток заявок стационарен, если вероятность появления n событий на интервале времени (t,t+x) не зависит от времени t, а зависит только от длины a этого участка.

Мгновенная плотность

Выбор СМО зависит как от числа каналов n, так и от допустимой длины очереди m. По указанным признакам различается ряд типов СО, перечисленных в таблице.

По числу обслуживающих каналов различают одноканальные и многоканальные СО.
В зависимости от целочисленного значения m используются следующие названия в классификации типов СО:
m = 0 – без очереди;
m > 0 – с очередью.
Если число мест в очереди m является конечным, то в СО могут происходить отказы в предоставлении обслуживания некоторым заявкам. В связи с этим СО указанного типа называются системами с отказами. Отклоняются от обслуживания те заявки, в момент прихода которых все места в очереди случайно оказались занятыми, или, если m =0, все каналы оказались занятыми. Считается, что заявка, получившая отказ в обслуживании, навсегда теряется для СО. Таким образом, пропускная способность СО этого типа всегда меньше 100%.

Если m не ограничено, что иногда условно записывают как m = ∞ , то соответствующая СО называется системой с ожиданием. В СО данного типа пришедшая заявка при отсутствии возможности немедленного обслуживания ожидает обслуживания, какой бы длинной ни были очередь и продолжительность времени ожидания.

Примеры задач для многоканальных СМО
Пример 1. АТС имеет k линий связи. Поток вызовов - простейший с интенсивностью λ в минуту. Среднее время переговоров составляет t минут. Время переговоров имеет показательное распределение. Найти: а) вероятность того, что все линии связи заняты; б) относительную и абсолютную пропускные способности АТС; в) среднее число занятых линий связи. Определить оптимальное число линий связи, достаточное для того, чтобы вероятность отказа не превышала α.
k = 5; λ = 0.6; t = 3.5, α = 0.04

Решение. Исчисляем показатели обслуживания многоканальной СМО:
Интенсивность потока обслуживания:
μ = 1/3.5 = 0.29
1. Интенсивность нагрузки.
ρ = λ • tобс = 0.6 • 3.5 = 2.1
Интенсивность нагрузки ρ=2.1 показывает степень согласованности входного и выходного потоков заявок канала обслуживания и определяет устойчивость системы массового обслуживания.

Вероятность, что канал свободен (доля времени простоя каналов).

Доля заявок, получивших отказ.

Вероятность обслуживания поступающих заявок.

Среднее число занятых линий связи

Коэффициент занятости каналов обслуживанием.