Software & Systems

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

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

При перегрузке накопителя такими грузами критичным оказывается некоторое значение емкости накопителя, превышение которого сопряжено с крупными экологическими и/либо материальными потерями. Такое превышение должно быть исключительно маловероятным событием. Возникает задача расчета емкости промежуточного накопителя (буфера) исходя из допустимой вероятности его переполнения, например, из Pдоп. ≤ 10–9.

Формально процесс загрузки накопителя можно представить как обслуживание поступившего требования и использовать для решения поставленной задачи аппарат теории систем массового обслуживания (СМО) [1]. Примем условно за  средний объем груза, забираемого из накопителя за один раз. Назовем этот объем пакетом. Пусть  – средний объем груза, доставленный в накопитель. Тогда среднюю наполненность накопителя можно представить в виде дискретной величины:

                                         (1)

где ëxû – ближайшее целое, не меньшее x.

Таким образом, если процесс загрузки накопителя описывать в терминах СМО, то имеем дело с особой неоднородностью потоков: заявки входного и выходного потоков суще- ственно различаются по объему поступающего в накопитель и извлекаемого из него груза. Во входном потоке заявки поступают пачками (в каждой пачке k заявок), а выходной поток состоит из одиночных заявок [2].

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

Для решения поставленной задачи представляется целесообразным использовать аналитико-статистический метод экстремальных значений (extreme values theory – EVT) [6, 7] и модель поведения очереди в буфере с ограниченной емкостью – конечном буфере (КБ).

Модель процесса потерь в буфере конечной емкости. Анализ процесса потери заявок при переполнении КБ стационарной СМО сведен к анализу наращиваний и сокращений очереди на интервале регенерации. В силу стационарности СМО анализ происходящих событий в одном промежутке занятости эквивалентен для всех промежутков. В течение интервала занятости заявки поступают в систему и покидают ее. Если во время занятости обслуживающего прибора в систему поступает более одной заявки (условие 1), то очередь в буфере начинает наращиваться. И, наоборот, очередь сокращается, если за время обслуживания в систему поступает не более одной заявки (условие 2). Сокращение очереди продолжается до тех пор, пока не наступает условие 1 либо не освобождается полностью буфер и кончается промежуток занятости. Количество процессов наращивания и процессов сокращения очереди, происходящих в одном промежутке занятости, одинаково.

Из анализа модели СМО с бесконечным буфером (ББ) [8, 9] следует, что потери в СМО с КБ определяются максимальным значением очереди, достигаемым в ББ на одном промежутке занятости независимо от траекторий развития процессов наращивания и сокращения.

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

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

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

В итоге это позволяет утверждать, что вероятность потери заявок в КБ емкостью N (ве- роятность переполнения накопителя) есть функция от хвоста распределения значений максимальной величины L, начиная со значения L = N + 1.

Следовательно, если функция распределения при L = N есть F(x), то вероятность потерь Pn(N) = f[Q(N +1)] = f[1 – F(N)].

Расчетное выражение для емкости накопителя (для экспоненциального распределения хвоста). На основе построенной модели и метода EVT получено выражение для расчетов, соответственно, малых (10-8 и менее) значений вероятностей потерь в буферах конечной емкости – в виде аналитико-статистической оценки

                                 (2)

где R – нормирующий коэффициент дискретного распределения при использовании метода экстремальных статистик, R = eDx/an; – среднее число заявок, поступающих на вход СМО за период регенерации; n – число выборочных значений в последовательностях, на которые разбивается выборочная последовательность, составленная из максимальных значений очереди на интервалах регенерации; an и bn – коэффициенты, вычисляемые по выборочным данным.

Преобразуем выражение (2), разрешая его относительно требуемого значения N, обеспечивающего значение вероятности потери P(N) и не превышающего допустимое значение Pдоп.(N). Получаем выражение для оценки емкости промежуточного накопителя:

.     (3)

Методика сбора и обработки выборочных данных [10]. Полагаем, что время моделирова- ния или объем общей выборки и признак выделения точек регенерации определены на более ранних стадиях моделирования.

Итак, в процессе сбора и обработки данных необходимо выполнить следующее.

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

2.    По всем интервалам выделить максимальные выборочные значения, которые образуют последовательность независимых значений случайной величины (длины возможной очереди в КБ) для последующей обработки методом EVT.

3.    Образовать порядковую последовательность из независимых значений длин очереди и оценить вероятности этих значений.

4.    Разделить полученную в п. 2 последовательность на M подпоследовательностей, содержащих по n выборочных значений (значение n можно принять равным 50).

5.    Образовать последовательность из максимальных значений xi,  подпоследовательностей.

6.    Образовать порядковую последовательность из максимальных значений (п. 5), оценить вероятность каждого значения в ней и построить в виде гистограммы оценку  функции распределения максимального значения выборочной последовательности (п. 2):

                         (4)

где hi – количество повторов i-го выборочного значения.

7. Образовать последовательность значений для каждого xi.

8. Оценить значение an как статистику по формуле

                                    (5)

где   J – число шагов гистограммы, и значение bn по выражению

                                           (6)

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

   (7)

                          (8)

где , 2Dx = hi – hi–1 - длительность интервала между значениями hi, hi–1 дискретной величины.

В таблице представлены результаты расчетов, выполненных по формуле (7). При расчетах использованы значения выборочных статистик  n, R, an и bn. Для каждого значения получены параметры выражения (7), вычисляемые по выборочным данным:

-     = 0,5; n = 50;  = 230; R = 1,575; an = 1,1; bn = 3,3.

-     = 0,7; n = 50;  = 310; R = 1,5; an = 1,3; bn = 4,7.

-     = 0,9; n = 50;  = 890; R = 1,1; an = 4,3; bn =12.

Значения емкости конечного буфера при допустимой вероятности потерь

The values of the final buffer capacity with a permissible probability of loss

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

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

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

Литература

1.    Карсаев О.В., Кулемин В.Ю., Морозов Б.М. Планирование доставки сборных грузов. Тр. СПИИРАН. 2014. № 6. С. 5–20.

2.    Зуева О.Н., Сидоренко А.М., Галактионов А.Д. Имитационное моделирование доставки грузов с помощью сменных кузовов // Управленец. 2017. № 6. С. 80–86.

3.    Бояршинова И.Н., Исмагилов Т.Р., Потапова И.А. Моделирование и оптимизация работы системы массового обслуживания // Фундаментальные исследования. 2015. № 9–1. С. 9–13.

4.    Задорожный В.Н. Оптимизация маршрутных матриц в сетях с очередями // Омский науч. вестн. 2016. № 6. С. 152–157.

5.    Рыжиков Ю.И. Алгоритмический подход к задачам массового обслуживания. СПб: Изд-во ВКА им. А.Ф. Можайского, 2013. 496 с.

6.    Королев В.Ю., Соколов И.А. Об условиях сходимости распределений экстремальных порядковых статистик к распределению Вейбулла // Информатика и ее применение. 2014. № 3. С. 3–11.

7.    Быков A.A. Приложения асимптотической теории вероятностей экстремальных значений к прогнозированию риска экстремальных чрезвычайных ситуаций // Проблемы прогнозирования. 2012. № 1. С. 53–64.

8.    Kutuzov O., Tatarnikova T. Evaluation and comparison of classical and fractal queuing systems. Proc. 15th Int. Sympos. Redundancy, 2016, pp. 155–157. DOI: 10.1109/RED.2016.7779352.

9.    Kutuzov O.I., Tatarnikova T.M. Model of a self-similar traffic generator and evaluation of buffer storage for classical and fractal queuing system. Proc. WS MWENT, 2018, pp. 1–3. DOI: 10.1109/mwent.2018. 8337306.

10. Bernabei F., Ferretti R., Listanti M., Zingrillo G. A tethodology for buffer design in ATM switches. J. European Transactions on Telecommunications and Related Technologies. 1991, vol. 2, no. 4, pp. 367–379.

References

1. Karsaev O.V., Kulemin V.Yu., Morozov B.M. Assorted cargo delivery scheduling. Proc. of SPIIRAS. 2014, vol. 37, no. 6, pp. 5–20 (in Russ.).
2. Zueva O.N., Sidorenko A.M., Galaktionov A.D. Multi-agent simulation for freight transportation with swap bodies. The Manager. 2017, vol. 70, no. 6, pp. 80–86 (in Russ.).
3. Boyarshinova I.N., Ismagilov T.R., Potapova I.A. Simulation and optimization of queuing systems. Fundamental Research. 2015, no. 9–1, pp. 9–13 (in Russ.).
4. Zadorozhny V.N. Optimization of transition probabilities in networks with queues. The J. Omsk Sci. Bull. 2016, no. 6, pp. 152–157 (in Russ.).
5. Ryzhikov Yu.I. Algorithmic Approach to Queuing Problems. St. Petersburg, 2013, 496 p.
6. Korolev V.Yu., Sokolov I.A. On conditions of convergence of the distributions of extremal order statistics to the Weibull distribution. Informatics and Its Application. 2014, vol. 8, no. 3, pp. 3–11 (in Russ.).
7. Bykov A.A. Applications of the asymptotic theory of probabilities of extreme values to forecasting the risk of extreme emergencies. Forecasting Problems. 2012, vol. 2, no. 1, pp. 53–64 (in Russ.).
8. Kutuzov O., Tatarnikova T. Evaluation and comparison of classical and fractal queuing systems. Proc. 15th Int. Sympos. Redundancy. 2016, pp. 155–157. DOI: 10.1109/RED.2016.7779352.
9. Kutuzov O.I., Tatarnikova T.M. Model of a self-similar traffic generator and evaluation of buffer storage for classical and fractal queuing system. Proc. WS MWENT. 2018, pp. 1–3. DOI: 10.1109/mwent.2018.
   8337306.
10. Bernabei F., Ferretti R., Listanti M., Zingrillo G. A tethodology for buffer design in ATM switches. J. Europ. Trans. on Telecommunications and Related Technologies. 1991, vol. 2, no. 4, pp. 367–379.