Марковские модели систем обслуживания–запасания с разнотипными повторными заявками

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

Ausführliche Beschreibung

Gespeichert in:

Bibliographische Detailangaben
Datum:	2019
Hauptverfasser:	Меликов, А.З., Пономаренко, Л.А., Алиев, И.А.
Format:	Artikel
Sprache:	Russian
Veröffentlicht:	Інститут кібернетики ім. В.М. Глушкова НАН України 2019
Schriftenreihe:	Проблемы управления и информатики
Schlagworte:	Экономические и управленческие системы
Online Zugang:	https://nasplib.isofts.kiev.ua/handle/123456789/180826
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!
Назва журналу:	Digital Library of Periodicals of National Academy of Sciences of Ukraine
Zitieren:	Марковские модели систем обслуживания–запасания с разнотипными повторными заявками / А.З. Меликов, Л.А. Пономаренко, И.А. Алиев // Проблемы управления и информатики. — 2019. — № 4. — С. 125-138. — Бібліогр.: 13 назв. — рос.

Institution

Digital Library of Periodicals of National Academy of Sciences of Ukraine

id	nasplib_isofts_kiev_ua-123456789-180826
record_format	dspace
spelling	nasplib_isofts_kiev_ua-123456789-1808262025-02-23T20:27:08Z Марковские модели систем обслуживания–запасания с разнотипными повторными заявками Марковські моделі систем обслуговування–запасання із різнотипними повторними вимогами Markov models of queuing–inventory systems with different types of retrial customers Меликов, А.З. Пономаренко, Л.А. Алиев, И.А. Экономические и управленческие системы В работе предложены марковские модели системы управления запасами с мгновенным обслуживанием и двумя типами заявок. Заявки высокого приоритета получают запас и покидают систему, если в момент их поступления уровень запасов выше нуля; иначе они покидают систему без получения запаса. Заявки низкого приоритета согласно схеме Бернулли могут либо уходить в орбиту, либо покидать систему, если в моменты их поступления уровень запасов системы ниже определенного критического уровня. При этом, если в моменты поступления заявки с орбиты уровень запасов опять ниже критического уровня, то повторная заявка также согласно схеме Бернулли либо окончательно уходит с орбиты, либо остается там для повторения. Вивчається модель системи обслуговування–запасання із двома типами вимог і миттєвим обслуговуванням. Вважається, якщо в момент надходження вимоги високого пріоритету рівень запасів більший від нуля, то вона одержує запас і покидає систему. Вимога низького пріоритету отримує запас, якщо в момент її надходження рівень запасів є більшим певного критичного рівня; в іншому випадку ця вимога згідно зі схемою Бернуллі або надходить в орбіту, або не отримує запас і залишає систему. Час перебування вимог у необмеженій орбіті є випадковою величиною із показниковою функцією розподілу. Якщо в момент надходження повторної вимоги рівень запасів більший критичного, то вона миттєво отримує необхідний запас і покидає орбіту; інакше вона згідно зі схемою Бернуллі або покидає орбіту, або залишається на орбіті. Розглядається три політики поповнення запасів: політика двох рівнів, політика змінного розміру поповнення і політика, згідно з якою замовлення на поставку запасів роблять після кожного факту видачі запасів. Основними характеристиками системи є середній рівень запасів, середня інтенсивність замовлень, ймовірності відмови в обслуговуванні вимог кожного типу при надходженні в систему, середня кількість вимог в орбіті, середні інтенсивності успішного та невдалого повторення запитів з орбіти. Для математичного аналізу системи, яка вивчається, побудовано відповідний двовимірний ланцюг Маркова та подано алгоритм пошуку його твірної матриці. Знайдено сумісний розподіл рівня запасів системи та кількість вимог в орбіті, а також запропоновано формули для обчислення усереднених характеристик моделей, які вивчались. In this paper, models of queuing-inventory systems with two kinds of retrial customers and instantaneous service time are considered. It is assumed that if at the time of arrival of a high-priority customer the inventory level is greater than zero then it receives an inventory and leaves the system. Customers of low priority receive inventory if at the time of its arrival the inventory level is above a certain critical level; otherwise, this customer, according to the Bernoulli trials, either goes into orbit or does not receive an inventory and leaves the system. The sojourn time of customers in an infinite orbit is a random variable with an exponential distribution function. If at the time of receipt of the repeated customer the inventory level is more than a critical level, then it instantly receives the required inventory and leaves the orbit; otherwise, according to the Bernoulli scheme, it either leaves the orbit or remains in orbit. Three replenishment policies are considered — a two-level policy, a variable order size policy, and a policy in which an order is made to supply inventory after each inventory release act. The main characteristics of the system are the average inventory level, the average intensity of orders, the probability of failure in servicing customers of each type when entering the system, the average number of customers in orbit, the average intensities of successful and unsuccessful repetition of customers from orbit. For the mathematical analysis of the system under study, a corresponding two-dimensional Markov chain was constructed and an algorithm was given for finding its generating matrix. Joint distribution of the system's inventory level and the number of customers in orbit as well as formulas for calculating the averaged characteristics of the studied models are developed. 2019 Article Марковские модели систем обслуживания–запасания с разнотипными повторными заявками / А.З. Меликов, Л.А. Пономаренко, И.А. Алиев // Проблемы управления и информатики. — 2019. — № 4. — С. 125-138. — Бібліогр.: 13 назв. — рос. 0572-2691 https://nasplib.isofts.kiev.ua/handle/123456789/180826 519.872 ru Проблемы управления и информатики application/pdf Інститут кібернетики ім. В.М. Глушкова НАН України
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection	DSpace DC
language	Russian
topic	Экономические и управленческие системы Экономические и управленческие системы
spellingShingle	Экономические и управленческие системы Экономические и управленческие системы Меликов, А.З. Пономаренко, Л.А. Алиев, И.А. Марковские модели систем обслуживания–запасания с разнотипными повторными заявками Проблемы управления и информатики
description	В работе предложены марковские модели системы управления запасами с мгновенным обслуживанием и двумя типами заявок. Заявки высокого приоритета получают запас и покидают систему, если в момент их поступления уровень запасов выше нуля; иначе они покидают систему без получения запаса. Заявки низкого приоритета согласно схеме Бернулли могут либо уходить в орбиту, либо покидать систему, если в моменты их поступления уровень запасов системы ниже определенного критического уровня. При этом, если в моменты поступления заявки с орбиты уровень запасов опять ниже критического уровня, то повторная заявка также согласно схеме Бернулли либо окончательно уходит с орбиты, либо остается там для повторения.
format	Article
author	Меликов, А.З. Пономаренко, Л.А. Алиев, И.А.
author_facet	Меликов, А.З. Пономаренко, Л.А. Алиев, И.А.
author_sort	Меликов, А.З.
title	Марковские модели систем обслуживания–запасания с разнотипными повторными заявками
title_short	Марковские модели систем обслуживания–запасания с разнотипными повторными заявками
title_full	Марковские модели систем обслуживания–запасания с разнотипными повторными заявками
title_fullStr	Марковские модели систем обслуживания–запасания с разнотипными повторными заявками
title_full_unstemmed	Марковские модели систем обслуживания–запасания с разнотипными повторными заявками
title_sort	марковские модели систем обслуживания–запасания с разнотипными повторными заявками
publisher	Інститут кібернетики ім. В.М. Глушкова НАН України
publishDate	2019
topic_facet	Экономические и управленческие системы
url	https://nasplib.isofts.kiev.ua/handle/123456789/180826
citation_txt	Марковские модели систем обслуживания–запасания с разнотипными повторными заявками / А.З. Меликов, Л.А. Пономаренко, И.А. Алиев // Проблемы управления и информатики. — 2019. — № 4. — С. 125-138. — Бібліогр.: 13 назв. — рос.
series	Проблемы управления и информатики
work_keys_str_mv	AT melikovaz markovskiemodelisistemobsluživaniâzapasaniâsraznotipnymipovtornymizaâvkami AT ponomarenkola markovskiemodelisistemobsluživaniâzapasaniâsraznotipnymipovtornymizaâvkami AT alievia markovskiemodelisistemobsluživaniâzapasaniâsraznotipnymipovtornymizaâvkami AT melikovaz markovsʹkímodelísistemobslugovuvannâzapasannâízríznotipnimipovtornimivimogami AT ponomarenkola markovsʹkímodelísistemobslugovuvannâzapasannâízríznotipnimipovtornimivimogami AT alievia markovsʹkímodelísistemobslugovuvannâzapasannâízríznotipnimipovtornimivimogami AT melikovaz markovmodelsofqueuinginventorysystemswithdifferenttypesofretrialcustomers AT ponomarenkola markovmodelsofqueuinginventorysystemswithdifferenttypesofretrialcustomers AT alievia markovmodelsofqueuinginventorysystemswithdifferenttypesofretrialcustomers
first_indexed	2025-11-25T04:56:28Z
last_indexed	2025-11-25T04:56:28Z
_version_	1849736921875480576
fulltext	© А.З. МЕЛИКОВ, Л.А. ПОНОМАРЕНКО, И.А. АЛИЕВ, 2019 Международный научно-технический журнал «Проблемы управления и информатики», 2019, № 4 125 ЭКОНОМИЧЕСКИЕ И УПРАВЛЕНЧЕСКИЕ СИСТЕМЫ УДК 519.872 А.З. Меликов, Л.А. Пономаренко, И.А. Алиев МАРКОВСКИЕ МОДЕЛИ СИСТЕМ ОБСЛУЖИВАНИЯ–ЗАПАСАНИЯ С РАЗНОТИПНЫМИ ПОВТОРНЫМИ ЗАЯВКАМИ Ключевые слова: система обслуживания–запасания, повторные заявки, поли- тика пополнения запасов, двумерная цепь Маркова, метод расчета. Введение В последние годы интенсивно изучаются модели систем обслуживания–запа- сания (Queuing-Inventory Systems, QIS) с разнотипными заявками [1–10]. Достаточно подробный обзор работ, посвященных таким QIS, можно найти в [10]. Большой интерес к изучению QIS с разнотипными заявками объясняется тем, что в реаль- ных системах заявки отличаются друг от друга различными показателями, напри- мер объемом покупаемого запаса, важностью и т.д. В зависимости от специфиче- ской особенности в QIS применяются различные схемы введения приоритетов для входящих заявок. Наиболее часто используется следующая схема: вводится неко- торый критический уровень запасов, и когда этот уровень запасов превышен, обслуживаются заявки всех типов, а если он ниже критического, то обслужи- ваются лишь приоритетные заявки. При этом критический уровень запасов определяется исходя из принятой политики пополнения запасов. Так, напри- мер, если в системе принята политика двух уровней ),( Ss , то в качестве кри- тического уровня запасов выбирается точка заказа .s Настоящая работа идейно близка работе [9]. Здесь, как и в [9], изучается мо- дель QIS с двумя типами заявок и мгновенным обслуживанием. Однако, в отличие от [9], в этой работе полагается, что в системе могут быть использованы три различные политики пополнения запасов. Кроме того, используемый здесь подход к исследованию рассматриваемых систем отличается от подхода, при- меняемого в [9]. Он позволяет разработать простые алгоритмы расчета и оптими- зации характеристик подобных моделей. Описание моделей и постановка задачи Изучаемая система имеет склад размера SS, , для хранения определен- ных запасов. Для получения этих запасов поступают пуассоновские потоки заявок двух типов. При этом интенсивность обычных заявок (поток заявок первого типа) равна 1 , а интенсивность приоритетных заявок (поток заявок второго типа) — 2 . Считается, что время обслуживания заявок обоих типов равно нулю и разнотипные заявки являются идентичными по размеру требуемого запаса, т.е. после обслужи- вания заявки любого типа уровень запасов системы уменьшается на единицу. 126 ISSN 0572-2691 Приоритетное обслуживание заявок осуществляется согласно следующей схеме. Если в момент поступления заявки второго типа уровень запасов больше нуля, то она получает запас и покидает систему. Если в момент поступления заяв- ки первого типа уровень запасов больше критического уровня ,2/, Sss  то она также получает запас и покидает систему; если уровень запасов системы в момент поступления заявки первого типа меньше или равен ,s эта заявка согласно схеме Бернулли либо с вероятностью  уходит в орбиту в целях повторения запроса для получения запаса, либо с дополнительной вероятностью 1 не получает за- пас и покидает систему. Здесь изучаются модели с бесконечным размером орбиты, т.е. любая заявка первого типа может приниматься в орбиту. Заявки с орбиты независимо друг от друга повторяют запросы через случайные моменты времени, которые имеют об- щее показательное распределение с параметром  0, . При этом, если в момент поступления повторной заявки уровень запасов больше критического уровня ,s она мгновенно получает требуемый запас и покидает орбиту; иначе (т.е. если уровень запасов системы в этот момент меньше или равен s ) она со- гласно схеме Бернулли либо с вероятностью  уходит с орбиты, либо с дополни- тельной вероятностью 1 остается в орбите. Считается, что заказы на пополнения запасов выполняются с определенными случайными задержками, которые имеют общее показательное распределение с параметром 0 . В системе может быть использована одна из следующих политик пополнения запасов:  ),( Ss -политика, т.е. заказ для поставки запасов делается тогда, когда их уровень опускается до величины 2, Sss  , при этом объем заказа равен ;sS   политика переменного объема (Variable Order Size, VOS), т.е. заказ для по- ставки запасов делается тогда, когда их уровень опускается до величины 2, Sss  , при этом объем заказа равен mS  , где m — текущий уровень запасов;  ),1( SS  -политика, т.е. заказ для поставки запасов делается после каждого акта отпуска запасов. Задача заключается в нахождении совместного распределения уровня запасов системы и числа заявок в орбите. Требуется также найти усредненные характери- стики системы: средний уровень запасов )( avS ; среднюю интенсивность заказов )(RR ; вероятности отказа в обслуживании заявок каждого типа при поступлении в систему );,( 21 PBPB среднее число заявок в орбите )( oL ; средние интенсивно- сти успешного )(RSR и безуспешного повторения )(RuSR запросов с орбиты. Методы решения задачи При использовании каждой из указанных выше политик пополнения запасов функционирование изучаемой системы описывается двумерной цепью Марко- ва с состояниями вида ),( nm , где m — уровень запасов системы, n — число заявок в орбите. Пространство состояний (ПС) этой цепи имеет бесконечную размерность и определяется как декартово произведение двух множеств, т.е. .}...,,1,0{}...,,1,0{  SE Сначала предположим, что в системе принята ),( Ss -политика пополнения запасов. Рассмотрим задачу построения производящей матрицы данной двумер- Международный научно-технический журнал «Проблемы управления и информатики», 2019, № 4 127 ной цепи Маркова. Переход из состояния Enm ),( в состояние Enm  ),( обо- значим ),(),( nmnm  . Тогда с учетом принятой политики пополнения запасов и системы приоритетов заключаем, что искомые интенсивности определяются так:  интенсивность перехода ),1(),( nmnm  при выполнении условия sm равна  , где 21  ;  интенсивность перехода ),1(),( nmnm  при выполнении условия sm  — 2 ;  интенсивность перехода )1,(),(  nmnm при выполнении условия sm  — 1 ;  интенсивность перехода )1,1(),(  nmnm при выполнении условий 0,  nsm равна n ;  интенсивность перехода )1,(),(  nmnm при выполнении условий 0,  nsm равна n ;  интенсивность перехода ),(),( nsSmnm  при выполнении условия sm  — . Стационарную вероятность состояния Enm ),( обозначим ),( nmp (усло- вия существования стационарного режима устанавливаются ниже). Эти величины удовлетворяют следующей системе уравнений равновесия (СУР): Случай :Sms  .),()1,1()1(),1(),()( nsSmpnmpnnmpnmpn  (1) Случай :0 sm   ),1(),(),1(),())0(( 212 nmpsmnspnmpnmI .)1,()1()0()1,()( 1  nmpnnInmpsmI (2) Здесь и далее I(A) — индикаторная функция события A, ),( ji — символы Кронекера. К этой СУР (1), (2) добавляется условие нормировки: 1),( ),(  Enm nmp . (3) Искомые характеристики системы вычисляются с помощью стационарных вероятностей состояний. Так, средний уровень запасов системы определяется следующим образом: .),( 01     n S m av nmpmS (4) Средняя интенсивность заказов определяется так: .),1( 0     n nspRR (5) Заявка первого типа покидает систему без получения запасов, если в момент ее поступления уровень запасов системы меньше 1s (тогда она теряется с веро- ятностью 1 ). Отсюда заключаем, что вероятность потери заявок первого типа при поступлении в систему вычисляется следующим образом: .),()1( 0 0 1       s m n nmpPB (6) 128 ISSN 0572-2691 Заявки второго типа покидают систему без получения запасов лишь тогда, когда уровень запасов системы равен нулю, т.е. вероятность потери заявок второ- го типа при поступлении в систему определяется так: .),0( 0 2     n npPB (7) Среднее число заявок в орбите находится следующим образом: .),( 0 1       S m n o nmnpL (8) Средние интенсивности успешного и безуспешного повторений запроса вы- числяются так: .),( 1 1       S sm n nmnpRSR (9) .),( 0 1       s m n nmnpRuSR (10) Следовательно, для нахождения характеристик системы (4)–(10) потребуется найти решение СУР (1)–(3), которая представляет собой бесконечную систему линейных алгебраических уравнений. Из-за сложной структуры производящей матрицы не удается разработать эф- фективный метод нахождения точного решения указанной СУР. Исходя из этого ниже предлагается приближенный метод нахождения стационарных вероятностей состояний данной двумерной цепи Маркова. Этот метод может быть корректно применен для моделей QIS, в которых большую долю входящего потока состав- ляют заявки высокого приоритета, при этом их интенсивность существенным об- разом превышает интенсивности поступления повторных заявок с орбиты. При выполнении этого допущения интенсивности переходов между состояния- ми внутри каждого класса ...,2,1,0},...,,1,0:),{(  nSmnmEn , существенно превышают интенсивности переходов между различными классами nE и ,nE  nn  . Исходя из этого рассмотрим следующее разбиение исходного ПС:  ,,, 0 mmEEEE mm n m     (11) где ...,1,0,}...,,1,0:),{(  nSmEnmEn . Все состояния nEnm ),( объединяются в одно укрупненное состояние  n , и на исходном ПС определяется функция укрупнения EU : , где ,),( nnmU если nEnm ),( . Обозначим ....},1,0:{  nn На основе разбиения (11) можно составить бесконечное число расщепленных моделей с ПС ...,1,0, nEn , где в расщепленной модели с ПС nE учитываются лишь переходы между состояниями, входящими в nE . Исходя из описанного выше алгоритма построения производящей матрицы исходной двумерной цепи Маркова заключаем, что во всех расщепленных моде- лях с ПС nE интенсивности переходов между состояниями определяются иден- тичным образом и не зависят от индекса ...,1,0, nn . Обозначим интенсивность Международный научно-технический журнал «Проблемы управления и информатики», 2019, № 4 129 перехода из состояния nEnm ),( в состояние nEnm  ),( как ),( mmqn  . Тогда имеем            ñëó÷àÿõ. îñòàëüíûõ â0 ,,0 åñëè, ,1,0 åñëè, ,1, åñëè, ),( 2 sSmmsm mmsm mmsm mmqn (12) Вероятность состояния nEnm ),( внутри расщепленной модели с ПС nE обозначим )(mn . Поскольку эти вероятности не зависят от индекса ,n ...,1,0n , ниже индекс n у этих величин )(mn опускается. Тогда из (12) полу- чаем, что указанные величины определяются так (см. [11]):          .1åñëè),1( ,1åñëè),1( ,0åñëè),1( )( SmsSsb sSmss smsa m m m (13) Здесь и далее приняты следующие обозначения                           s sSmi is m ms m ba .; 1 2 2 1 2 2 Вероятность )1(  s находится из условия нормировки, т.е. .2)1( 1 10             m S sSm s m m basSs Исходя из описания исходной системы заключаем, что в пространстве укрупненных состояний  возможны лишь переходы  1nn и  n  1n . Интенсивность перехода  yx в пространстве  обозначим ).,(  yxq Переходы  1nn осуществляются при поступлении заявок первого типа с вероятностью  , если в этот момент система находится в одном из состоя- ний типа nEnm ),( , где sm  . Следовательно, интенсивность перехода  1nn вычисляется следующим образом: .)()1,( 0 1    s m mnnq (14) Переходы  1nn выполняются при поступлении повторных заявок с орбиты. При этом такой переход осуществляется с вероятностью единица, если в этот момент система находится в одном из состояний типа nEnm ),( , где sm ; иначе, т.е. если в этот момент sm  , переход выполняется с вероятно- стью . Таким образом, имеем .)()()1,( 01            s m S sm mmnnnq (15) 130 ISSN 0572-2691 Для упрощения дальнейшего изложения введем следующие обозначения: .)()(;)( 010 1            s m S sm s m mmm Тогда из соотношений (14), (15) получаем, что вероятности состояний укруп- ненной модели с пространством состояний  в случае линейной интенсивности поступления повторных заявок с орбиты (т.е. если число повторных заявок в ор- бите равно n , то интенсивность их поступления равна n ) совпадают со стацио- нарным распределением модели системы обслуживания // MM с нагрузкой  . Это означает, что при любых (положительных) значениях параметров системы существует стационарный режим и вероятности укрупненных состояний определяются так: ...,2,1,0, ! )(     ne n n n . (16) Замечание 1. Если предположить, что интенсивность поступления повторных заявок является постоянной величиной (т.е. независимо от числа 0n повторных заявок в орбите интенсивность их поступления равна  ), то для существования стационарного режима потребуется выполнение условия 1 (это условие при 1 может быть заменено более простым и гарантированным условием 1 ). В этом случае вероятности состояний укрупненной модели совпадают со стационар- ным распределением модели системы обслуживания /1// MM с нагрузкой  , т.е. при выполнении условия эргодичности 1 стационарные вероятности укрупненных состояний определяются так: ...,2,1,0,)1()(  nn n . (17) Используя (13) и (16) или (17), получаем, что вероятности состояний исход- ной двумерной цепи Маркова вычисляются (приближенно) следующим образом: .),(,)()(),( Enmnmnmp  (18) После определенных математических преобразований с учетом (18) из (4)–(10) получаем следующие приближенные формулы для вычисления характеристик изучаемой системы при использовании ),( Ss -политики пополнения запасов: ;)( 1    S m av mmS (19) ;)1(  sRR (20) ;)()1( 0 1    s m mPB (21) ;)0(2 PB (22) ;oL (23) ;)( 1    S sm mRSR (24) .)( 0    s m mRuSR (25) Международный научно-технический журнал «Проблемы управления и информатики», 2019, № 4 131 Замечание 2. Формулы (23)–(25) определяют значения соответствующих ха- рактеристик при линейной интенсивности поступления повторных заявок; для случая постоянной интенсивности поступления повторных заявок в этих форму- лах величина  заменяется величиной   1 . Из формул (19)–(22) видно, что средний уровень запасов системы, средняя интенсивность заказов и вероятности потери заявок не зависят от интенсивности поступления повторных заявок. Это объясняется тем, что при выводе этих приближенных формул принято допущение о том, что интенсивность поступления повторных заявок намного меньше, чем интенсивности поступления первичных заявок. Вместе с тем другие характери- стики системы, а именно среднее число заявок в орбите, а также средние интен- сивности успешного и безуспешного повторений, существенным образом зависят от всех параметров системы (см. (23)–(25)). Предложенный выше подход может быть применен и для изучения данной системы при использовании других политик пополнения запасов. Предположим, что в системе используется VOS-политика. Тогда элементы производящей матрицы соответствующей двумерной цепи Маркова также опре- деляются согласно алгоритму, описанному выше, но единственное отличие со- стоит в том, что здесь в случаях sm  в момент поступления заказа происходит переход ),(),( nSnm  с интенсивностью  . В отличие от ),( Ss -политики, объем поставляемого заказа является пере- менной величиной, и потому необходимо ввести новую характеристику — сред- ний объем заказа, avV . Эта величина определяется так:   ., 0 nmSpmV n S sSm av     (26) Замечание 3. Здесь и далее для упрощения изложения для всех параметров и характеристик системы при использовании различных политик пополнения запа- сов сохраняются одинаковые обозначения. Другие характеристики системы при использовании VOS-политики вычисляют- ся из (4)–(10). Точные значения этих характеристик также определяются через стационарные вероятности состояний системы, которые удовлетворяют соответ- ствующей СУР. Для вычисления приближенных значений вероятностей состоя- ний и характеристик системы может быть использован предложенный выше метод. Опуская подробное изложение этапов указанного метода, отметим лишь отличающиеся моменты. Так, в данной модели во всех расщепленных моделях с ПС nE интенсивности переходов между состояниями определяются аналогично (12), но с единственным отличием: в третьей строке правой части формулы (12) условие sSmmsm  ,0 заменяется Smsm  ,0 . С учетом этого находим, что в данной модели вероятности состояний внутри расщепленной модели с ПС nE определяются так (см. [12]):        ,1 åñëè),0( ,11 åñëè),0( )( Smsd smc m m (27) где                                        ;1,1 ,1,1 2 1 22 1 22 sm sm c s m m 132 ISSN 0572-2691 .1 2 1 22                 s d Вероятность )0( находится из условия нормировки, т.е. .)1(1)0( 1 1 1              s m mcdsS Далее с помощью формул (14)–(18) и (27) определяются вероятности состоя- ний модели при использовании VOS-политики, а характеристики системы вычис- ляются из (19)–(25). Новая характеристика (26) приближенно вычисляется так: )( mSmV S sSm av    . (28) Теперь предположим, что в системе используется ),1( SS  -политика попол- нения запасов. Элементы производящей матрицы соответствующей цепи Маркова также определяются согласно алгоритму, описанному выше, но единственное от- личие состоит в том, что в случаях Sm 0 в моменты поступления заказа про- исходит переход ),1(),( nmnm  с интенсивностью  )( mS . Характеристики системы при использовании ),1( SS  -политики вычисляют- ся из (4), (6)–(10). Однако при использовании данной политики средняя интенсив- ность заказов вычисляется по следующей формуле: .),(),( 1 0 2 1 0          s m n S sm n nmpnmpRR (29) В данной модели во всех расщепленных моделях с ПС nE интенсивности переходов между состояниями определяются аналогично (12), но с единственным отличием: в третьей строке правой части формулы (12) условие ,0 sm  sSmm  заменяется 1,0  mmSm , при этом интенсивность перехода ),1(),( nmnm  равна  )( mS . С учетом этого находим, что в данной модели вероятности состояний внутри расщепленной модели с ПС nE определяются так (см. [13]):                                           ,1 åñëè,0 )!( ! ,0 åñëè,0 )!( ! )( 2 2 Sms mS S sm mS S m mms m (30) где вероятность )0( находится из условия нормировки, т.е.   . )!( ! )!( ! 0 1 1220                                          mS sm sms m mS S mS S Окончательно из (14)–(18) и (30) определяются вероятности состояний модели при использовании ),1( SS  -политики и характеристики системы вычисляются из (19), (21)–(25). С учетом (30) характеристика (5) в данной модели приближенно вычисляется так: .)()( 1 2 1 mmRR s m S sm    (31) Международный научно-технический журнал «Проблемы управления и информатики», 2019, № 4 133 Численные результаты Рассмотрим результаты численных экспериментов, выполненных с помощью разработанных выше алгоритмов. При этом основными целями экспериментов являются, во-первых, сравнительный анализ характеристик изучаемой системы при использовании различных политик пополнения запасов и, во-вторых, нахож- дение оптимального значения критического уровня запасов при использовании каждой политики. Сразу же отметим, что, как и в работах [10–13], здесь нами также изучены вопросы точности разработанных приближенных формул вычисления стационар- ных распределений соответствующих двумерных цепей Маркова и характеристик системы. При этом использованы различные меры близости (подробнее об этих мерах см. [10–13]). Однако из-за ограниченности объема работы соответствую- щие результаты здесь не приводятся. Укажем только, что проведенные экспери- менты показали высокую точность приближенных алгоритмов, при этом время их выполнения практически равно нулю. Предположим, что нагрузочные параметры системы, а также размер склада системы являются постоянными величинами, и единственный регулируемый па- раметр — критический уровень запасов, т.е. s . Следовательно, приведенный ни- же сравнительный анализ характеристик изучаемой системы при использовании различных политик пополнения запасов осуществляется при изменении указанно- го параметра в отрезке  ]2,0[ S , где ][x — целая часть x . Часть результатов проводимых численных экспериментов показана на рис. 1, где символы ,  и  указывают политики ),( Ss , VOS и ),1( SS  соответствен- но. Исходные данные выбирались так: ,20,200,50,120 21 S .6,0,3,0,3  Из рис. 1, а видно, что характер и значения функции avS при использовании различных политик пополнения запасов существенным образом отличаются друг от друга. Так, при использовании ),( Ss -политики функция выпуклая, при VOS- политике — вогнутая, а при использовании ),1( SS  -политики — постоянная. Функция RR принимает близкие значения при использовании политик ),( Ss и VOS, при этом при использовании политики VOS она является постоянной и равна 2,45, а при использовании политики ),( Ss она растет с малой скоростью от 2 до 5 (рис. 1, б); при использовании политики ),1( SS  эта функция является постоян- ной и равна 250 (поскольку значения данной функции при использовании полити- ки ),1( SS  существенно больше, чем при использовании остальных политик, на графике эта линия не показана). Такая существенная разница в значениях этой функции при использовании политики ),1( SS  объясняется тем, что в этой полити- ке заказ на пополнение осуществляется после каждого акта обслуживания. При использовании политики ),( Ss функция 1PB является возрастающей, в то время как для политики VOS она становится постоянной величиной (рис. 1, в); функция 2PB является убывающей при использовании обеих политик пополнения запасов, при этом ее значения существенно меньше при использовании политики ),( Ss (рис. 1, г). Отметим, что при использовании политики ),1( SS  значения этой функции являются бесконечно малыми величинами (практически равны нулю), потому ее график при данной политике не показан на рис. 1, в, г) (далее графики соответствующих характеристик при использовании этой политики не показаны). 134 ISSN 0572-2691 Это объясняется тем, что для выбранных исходных данных в большом диапазоне изменения параметра s многие вероятности состояний )(m при использовании этой политики практически равны нулю, и лишь при нескольких значениях этого параметра, близких к максимально возможному значению  2S , некоторые веро- ятности состояний принимают достаточно большие значения (см. (30)). Функция 0L является возрастающей при использовании политик ),( Ss и VOS, при этом в обеих политиках ее значения схожи; здесь также эта функция прак- тически равна нулю при использовании политики ),1( SS  (рис. 1, д). При малых значениях параметра s для функции RSR предпочтительна по- литика VOS, однако при 35s благоприятна политика ),( Ss (рис. 1, е). В отли- чие от функции ,RSR функция RuSR является возрастающей при использовании обеих политик — ),( Ss и VOS, при этом здесь также при 40s предпочтитель- на политика ),( Ss (рис. 1, ж). Теперь рассмотрим задачу нахождения оптимального значения критического уровня запасов при использовании каждой политики. Отметим, что возможны различные постановки этой задачи. Для определенности изложения здесь рас- сматривается задача максимизации прибыли системы за счет выбора надлежащих значений параметра s . Sav 100 90 80 70 60 110 10 40 60 s 0 20 30 50 RR 3,5 2,5 2,0 10 40 60 0 20 50 3,0 4,5 5,0 4,0 s 30 а б PB1 0,08 0,04 5 0,02 10 40 60 s 0 20 30 50 0,06 0,12 0,10 0,08 0,04 5 0,02 10 40 60 s 0 20 30 50 0,06 0,12 0,10 PB2 0,00 в г Рис. 1 Международный научно-технический журнал «Проблемы управления и информатики», 2019, № 4 135 Продолжение рис. 1 0,08 0,04 5 0,02 10 40 60 s 0 20 30 50 0,06 0,12 0,10 L0 0,00 0,14 0,20 0,10 5 0,05 10 40 60 s 0 20 30 50 0,15 0,30 0,25 RSR 0,00 0,35 д е Доходы системы (RV) формируются из продажи запасов и определяются так:  ))())(1(()( 11 sRSRsPBsRV ,))(1( 2 22 1 revrev CsPBC  (32) где k revC — доходы системы от продажи единицы запаса по заявкам k-го типа, k = = 1, 2; при этом следует ожидать, что доходы от обслуживания приоритетных заявок намного больше, чем от обслу- живания обычных, т.е. 12 revrev CC  . Замечание 4. Здесь и далее в обозначениях характеристик системы и функци- оналов в скобках указан оптимизируемый параметр s . Суммарные штрафы (TC) в системе определяются следующим образом: ,)())()(()()())(()( 22 2 11 1 sPBcsRuSRsPBcsScsRRsVcKsTC llavhavr  (33) где K — фиксированная цена одного заказа; rc — цена единицы объема заказа; hc — цена хранения единицы объема запасов за единицу времени; k lc — штраф за потерю одной заявки k -го типа, 2,1k . Считается, что штрафы за потерю прио- ритетных заявок намного больше, чем за потерю обычных, т.е. 12 ll cc  . Замечание 5. При использовании ),( Ss -политики в (33) полагается ,sSVav  а при использовании ),1( SS  -политики имеем .1avV Аналогичным образом при использовании ),1( SS  -политики функция )(sRR вычисляется с помощью формулы (29) или (31), если используется приближенный подход. Задача оптимизации ставится следующим образом: для каждой политики по- полнения запасов требуется максимизировать прибыль системы за счет выбора надлежащих значений критического уровня запасов, т.е. из (32) и (33) находим, что требуется решить следующую задачу: ,)(maxarg* sPTs s  (34) 0,04 0,02 5 0,01 10 40 60 s 0 20 30 50 0,03 RuSR 0,00 ж 136 ISSN 0572-2691 где .)()()( sTCsRVsPT  Задача (34) всегда имеет решение, так как множество допустимых решений  }20{ Ss  является конечным и дискретным. Коэффициенты в функционалах (32) и (33) определяются следующим образом: .6,2,2,0,01,0,2,0,10,5 2121  llhrrevrev ccccKCC Для наглядности на рис. 2 приводятся графики всех трех функций ,TC RV и PT . Из этих графиков видно, что для выбранных исходных данных функция TC возрастает при использо- вании политики ),( Ss , в то время как функция RV убывает при этой политике; обратная картина наблюдается для этих функций при использовании политики VOS (рис. 2, а, б). Поскольку функция PT является возрастающей при ис- пользовании политики VOS, а при ис- пользовании политики ),( Ss она убы- вает, оптимальное решение задачи (34) при политике VOS равно 0* s , а при политике ),( Ss имеем 59* s (рис. 2, в). 10 40 60 s 0 20 30 50 2050 2000 2150 RV 2100 2200 10 40 60 s 0 20 30 50 2000 1900 PT 2100 2200 б в Рис. 2 Заключение В работе предложены марковские модели системы управления запасами с мгновенным обслуживанием и двумя типами заявок. Заявки высокого приоритета получают запас и покидают систему, если в момент их поступления уровень запа- сов выше нуля; иначе они покидают систему без получения запаса. Заявки низко- го приоритета согласно схеме Бернулли могут либо уходить в орбиту, либо поки- дать систему, если в моменты их поступления уровень запасов системы ниже определенного критического уровня. При этом, если в моменты поступления за- явки с орбиты уровень запасов опять ниже критического уровня, то повторная за- явка также согласно схеме Бернулли либо окончательно уходит с орбиты, либо остается там для повторения. 80 40 20 10 40 60 s 0 20 30 50 60 100 ТС 120 140 160 а Международный научно-технический журнал «Проблемы управления и информатики», 2019, № 4 137 Изучаются системы, в которых возможно использование трех политик по- полнения запасов: ),( Ss -, ),1( SS  - и VOS-политики. Во всех системах время выполнения заказов имеет показательную функцию распределения с конечным средним значением. Построены соответствующие двумерные цепи Маркова, ко- торые описывают работу изучаемых систем, и разработаны точный и приближен- ный методы расчета вероятностей состояний этих цепей. Разработаны явные формулы для приближенного вычисления характеристик изучаемых систем, на их основе выполнены численные эксперименты и решена задача максимизации при- были изучаемых систем при использовании различных политик пополнения запасов. А.З. Меліков, Л.А. Пономаренко, І.А. Алієв МАРКОВСЬКІ МОДЕЛІ СИСТЕМ ОБСЛУГОВУВАННЯ–ЗАПАСАННЯ ІЗ РІЗНОТИПНИМИ ПОВТОРНИМИ ВИМОГАМИ Вивчається модель системи обслуговування–запасання із двома типами вимог і миттєвим обслуговуванням. Вважається, якщо в момент надходження вимоги високого пріоритету рівень запасів більший від нуля, то вона одержує запас і покидає систему. Вимога низького пріоритету отримує запас, якщо в момент її надходження рівень запасів є більшим певного критичного рівня; в іншому ви- падку ця вимога згідно зі схемою Бернуллі або надходить в орбіту, або не отримує запас і залишає систему. Час перебування вимог у необмеженій орбіті є випадковою величиною із показниковою функцією розподілу. Якщо в момент надходження повторної вимоги рівень запасів більший критичного, то вона миттєво отримує необхідний запас і покидає орбіту; інакше вона згідно зі схемою Бернуллі або покидає орбіту, або залишається на орбіті. Розглядається три політики поповнення запасів: політика двох рівнів, політика змінного роз- міру поповнення і політика, згідно з якою замовлення на поставку запасів роб- лять після кожного факту видачі запасів. Основними характеристиками систе- ми є середній рівень запасів, середня інтенсивність замовлень, ймовірності від- мови в обслуговуванні вимог кожного типу при надходженні в систему, середня кількість вимог в орбіті, середні інтенсивності успішного та невдалого повторення запитів з орбіти. Для математичного аналізу системи, яка вивчається, побудовано відповідний двовимірний ланцюг Маркова та подано алгоритм пошуку його твірної матриці. Знайдено сумісний розподіл рівня запасів системи та кількість вимог в орбіті, а також запропоновано формули для обчислення усереднених харак- теристик моделей, які вивчались. Ключові слова: системи обслуговування–запасання, марковська модель, по- вторна заявка, політика поповнення запасів. A.Z. Melikov, L.A. Ponomarenko, I.A. Aliev MARKOV MODELS OF QUEUING–INVENTORY SYSTEMS WITH DIFFERENT TYPES OF RETRIAL CUSTOMERS In this paper, models of queuing-inventory systems with two kinds of retrial custom- ers and instantaneous service time are considered. It is assumed that if at the time of arrival of a high-priority customer the inventory level is greater than zero then it re- ceives an inventory and leaves the system. Customers of low priority receive invento- ry if at the time of its arrival the inventory level is above a certain critical level; oth- erwise, this customer, according to the Bernoulli trials, either goes into orbit or does not receive an inventory and leaves the system. The sojourn time of customers in an infinite orbit is a random variable with an exponential distribution function. If at the time of receipt of the repeated customer the inventory level is more than a critical 138 ISSN 0572-2691 level, then it instantly receives the required inventory and leaves the orbit; otherwise, according to the Bernoulli scheme, it either leaves the orbit or remains in orbit. Three replenishment policies are considered — a two-level policy, a variable order size pol- icy, and a policy in which an order is made to supply inventory after each inventory release act. The main characteristics of the system are the average inventory level, the average intensity of orders, the probability of failure in servicing customers of each type when entering the system, the average number of customers in orbit, the average intensities of successful and unsuccessful repetition of customers from orbit. For the mathematical analysis of the system under study, a corresponding two-dimensional Markov chain was constructed and an algorithm was given for finding its generating matrix. Joint distribution of the system's inventory level and the number of customers in orbit as well as formulas for calculating the averaged characteristics of the studied models are developed. Keywords: queuing-inventory systems, Markov model, retrial customers, replenish- ment policies. 1. Dekker R., Hill R.M., Kleijn M.J. On the (S–1, S) lost sales inventory model with priority de- mand classes. Naval Research Logistics. 2002. 49, N 6. P. 593–610. 2. Kranenburg A.A., van Houtum G.J. Cost optimization in the (S–1, S) lost sales inventory model with multiple demand classes. Operations Research Letters. 2007. 35, N 4. P. 493–502. 3. Zhao N., Lian Z. A queuing-inventory system with two classes of customers. Int. J. Production Economics. 2011. 129. P. 225–231. 4. Isotupa K.P.S. Cost analysis of an (S–1, S) inventory system with two demand classes and ration- ing. Annals of Operations Research. 2015. 233. P. 411–421. 5. Isotupa K.P.S. An (S, Q) inventory system with two demand classes of customers. International Journal of Operational Research. 2011. 12, N 1. P. 12–19. 6. Isotupa K.P.S. An (S, Q) Markovian inventory system with lost sales and two demand classes. Mathematical and Computer Modeling. 2006. 43. P. 687–694. 7. Isotupa K.P.S., Samanta S.K. A continuous review (s, Q) inventory system with priority custom- ers and arbitrary distributed lead times. Mathematical and Computer Modeling. 2013. 57. P. 1259–1269. 8. Sivakumar B., Arivarignan G. A modified lost sales inventory system with two types of custom- ers. Quality Technology and Quantitative Management. 2008. 5, N 4. P. 339–349. 9. Karthick T., Sivakumar B., Arivarignan G. An inventory system with two types of customers and retrial demands. International Journal of Systems Science: Operations & Logistics. 2015. 2, N 2. P. 90–112. 10. Melikov A.Z., Ponomarenko L.A., Aliyev I.A. Markov models of systems with two types of cus- tomers and different replenishment policies. Cybernetics and Systems Analysis. 2018. 54, N 6. P. 900–917. 11. Melikov A.Z., Ponomarenko L.A., Bagirova S.A. Analysis of queueing-inventory systems with impatience consume customers. Journal of Automation and Information Sciences. 2016. 48, N 1. P. 53–68. 12. Melikov A.Z., Ponomarenko L.A., Bagirova S.A. Markov models of queuing-inventory systems with variable order size. Cybernetics and Systems Analysis. 2017. 53, N 3. P. 373–386. 13. Melikov A.Z., Shahmaliyev M.O. A perishable queuing-inventory system with positive service time and (S–1, S) replenishment policy. Communications in Computer and Information Sciences. Springer. 2017. 800. P. 83–96. Получено 08.04.2019

Марковские модели систем обслуживания–запасания с разнотипными повторными заявками

Institution

Ähnliche Einträge