Построение оптимального графика работы касс, при помощи математических инструментов

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

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

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

Задача теории массового обслуживания — установить зависимость результирующих показателей работы системы массового обслуживания (вероятности того, что заявка будет обслужена; математического ожидания числа обслуженных заявок и т. д.), от входных показателей (количества каналов в системе, параметров входящего потока заявок и т. д.). Результирующими показателями или интересующими нас характеристиками СМО являются — показатели эффективности СМО, которые описывают, способна ли данная система справляться с потоком заявок. Системы массового обслуживания могут быть одноканальными или многоканальными.

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

Каждая задача оптимизации обязательно должна иметь три компоненты:

• — неизвестные (что ищем, то есть, план);
• — ограничение на неизвестные (область поиска);
• — целевая функция (цель, для которой ищем экстремум).

Математическая модель — та, которая определена с помощью математических формализмов. Математическая модель не является точной, а является идеализацией.

Определение параметров состояния — задача моделирования. Определение переменных проектирования — задачи проектирования или задачи оптимизации.

Функционирование любой системы массового обслуживания можно представить через все возможные состояния ее и интенсивность перехода из одного состояния в другое. Основными параметрами функционирования СМО являются вероятности ее состояния, то есть возможности наличия n требований в системе — Рn.

Важным параметром функционирования СМО является также среднее число требований, находящихся в системе Nsyst, то есть в очереди на обслуживание, а также средняя длина очереди Noch. Исходными параметрами, характеризующими систему массового обслуживания, являются: число каналов обслуживания — n; число требований — m; интенсивность поступления одного требования на обслуживание — л, то есть число поступлений требований в единицу времени; интенсивность обслуживания требований — м.

Рассмотрим n-канальную СМО с отказами. Будем нумеровать состояния системы по числу занятых каналов (или, что в данном случае то же, по числу заявок, связанных с системой). Состояния будут:

S0 — все каналы свободны, S1 — занят ровно один канал, остальные свободны, Sk — заняты ровно k каналов, остальные свободны, Sn — заняты все n каналов.

Граф состояний СМО представлен на рис. 1. Разместим граф, т. е. проставим у стрелок интенсивности соответствующих потоков событий. По стрелкам слева на право, систему переводит один и тот же поток — поток заявок с интенсивностью l.

Рисунок 1 — Граф состояний СМО Если система находиться в состоянии Sk (занято k каналов) и пришла новая заявка, система переходит (перескакивает) в состояние Sk+1.

Определим интенсивности потоков событий, переводящих систему по стрелкам справа налево.

Пусть система находиться в состоянии S1 (занят один канал). Тогда, как только закончиться обслуживание заявки, занимающей этот канал, система перейдет в S0; значит, поток событий, переводящий систему по стрелке S1 < S0, имеет интенсивность m. Очевидно, если обслуживанием занято два канала, а не один, поток обслуживаний, переводящий систему по стрелке S2 < S1, будет вдвое интенсивнее (2m); если занято k каналов — в k раз интенсивнее (km). Проставим соответствующие интенсивности у стрелок, ведущих справа налево. Из рисунке 1 видно, что процесс, протекающий в СМО, представляет собой частный случай процесса гибели и размножения. Пользуясь общими правилами, можно составить уравнения Колмогорова для вероятностей состояний:

Уравнения (1) называются уравнениями Эрланга. Естественными начальными условиями для их решения являются:

p0(0)=1; p1(0)=p2(0)=…=pn (0)=0 (в начальный момент система свободна).

Интегрирование системы уравнений (1) в аналитическом виде довольно сложно; на практике такие системы дифференциальных уравнений обычно решаются численно, на ЭВМ. Такое решение дает нам все вероятности состояний p0(t), p1(t),…, pn (t) как функции времени.

Естественно, нас больше всего будут интересовать предельные вероятности состояний p0, p1 ,…, pk ,…, pn, характеризующие установившийся режим работы СМО (при t > Ґ). Для нахождения предельных вероятностей воспользуемся уже готовым решением задачи, полученным для схемы гибели и размножения. Согласно этому решению,.

В этих формулах интенсивность потока заявок l и интенсивность потока обслуживаний (для одного канала) m не фигурируют по отдельности, а входят только своим отношением l /m. Обозначим это отношение l /m=r, и будем называть величину r «приведенной интенсивностью» потока заявок. Физический смысл ее таков: величина r представляет собой среднее число заявок, приходящих в СМО за среднее время обслуживания одной заявки. С учетом этого обозначения, формулы (2) примут вид:

Формулы (3) называются формулами Эрланга. Они выражают предельные вероятности всех состояний системы в зависимости от параметров l, m и n (l — интенсивность потока заявок, m — интенсивность обслуживания, n — число каналов СМО).

Зная все вероятности состояний p0, p1 ,…, pk ,…, pn, можно найти характеристики эффективности СМО: относительную пропускную способность q, абсолютную пропускную способность, А и вероятность отказа Pотк.