Исследование систем массового обслуживания с отрицательными заявками и бункером для вытесненных заявок тема диссертации и автореферата по ВАК РФ 01.01.05, кандидат физико-математических наук Разумчик, Ростислав Валерьевич

• Разумчик, Ростислав Валерьевич
• кандидат физико-математических наук
• 2011

Оглавление диссертации кандидат физико-математических наук Разумчик, Ростислав Валерьевич

Введение

1 Одноканальная экспоненциальная система массового обслуживания с отрицательными заявками и бункером для вытесненных заявок

1.1. Описание системы.

1.2. Стационарное распределение вероятностей состояний

1.3. Стационарное распределение времени ожидания начала обслуживания.

2 Стационарные характеристики в экспоненциальных системах массового обслуживания с различными ограничениями на емкости накопителя и бункера, и на число приборов

2.1. Случай бесконечного накопителя и конечного бункера

2.2. Случай конечного накопителя и бесконечного бункера . 5R

2.3. Случай конечного накопителя и конечного бункера

2.4. Случай нескольких приборов.

3 Одноканальная марковская система массового обслуживания с отрицательными заявками и бункером для вытесненных заявок в дискретном времени

3.1. Описание системы.

3.2. Стационарное распределение вероятностей состояний . 9U

3.3. Стационарное распределение времени ожидания начала обслуживания.

3 ак лючение

Введение диссертации (часть автореферата) на тему «Исследование систем массового обслуживания с отрицательными заявками и бункером для вытесненных заявок»

Считается, что первой, математической работой по теории массового обслуживания, является работа А.К. Эрланга "Теория вероятностей и телефонные разговоры1' ("The Theory of Probabilities and Telephone Conversations") [1]. Работы А.К. Эрланга и других ученых двадцатых и тридцатых годов были посвящены в основном решению практических проблем, связанных с управлением нагрузкой в телефонных сетях. В течение следующих двадцати лет, в результате того, что все больше ученых проявляли интерес к изучению данных проблем, были разработаны модели, которые позволяли исследовать более сложные явления и системы. Среди ученых того времени, которые уделили значительное внимание развитию теории массового обслуживания, необходимо отметить Г.П. Башарина [2]-[3], А. А. Боровкова [4], Б.В. Гнеденко [о], Д. Кен дал л а [б], А. Колмогорова [7], Д. Кокса [8], К. Д. Кроммелин [9], К. Пальма [10], Ф. Поллачека [10], Ю. Прохорова [22], Т. Саати [12], Б.А. Севастьянова [13], В. Смита [14], JL Такача [15], В. Феллера [16], Ф. Фостера [17], А.Я. Хинчина, [18].

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

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

Для анализа влияния на систему дополнительных (внешних и внутренних) факторов в работе [23] была введена концепция отрицательных заявок и связанных с ними сетей и систем массового обслуживания, которые получили название соответственно С-сети и С-системы. Суть отрицательных заявок заключается в следующем. Отрицательная заявка при поступлении в СМО или некоторых узел СеМО "убивает" (разрушает) одну обычную заявку, ожидающую в очереди, после чего обе заявки мгновенно покидают систему, уменьшая число ожидающих положительных заявок на единицу. В дальнейшем понятие отрицательной заявки было распространено на случай, когда она может "убивать" группу заявок из очереди или полностью опустошать очередь (катастрофы), были также введены понятия триггера, выталкивающего положительную заявку из одного узла сети в другой, и сигнала, который с заданной вероятностью может быть либо отрицательной заявкой (в традиционном смысле), либо триггером. Подробный обзор публикаций до 2003 года в области исследования СеМО и СМО с отрицательными заявками, включая известные обобщения, содержится в обзорах [20, 26].

Сейчас С-системы и С-сети остаются актуальным предметом исследований. Среди прикладных и теоретических работ, опубликованных после 2003 года, можно упомянуть [27]—[38]. В работе [29] показано как системы с отрицательными заявками и катастрофами могут применяться в телефонии для моделирования работы call-центров. Работа [36] иллюстрирует использование G-систем при анализе систем инвентаризации. Связь генетических и G-сетей подробно исследуется в [38]. Приложению системы с отрицательными заявками к анализу механизмов балансировки нагрузки в сети MPLS посвящена работа [39].

Отдельно необходимо упомянуть исследования G-систем, функционирующих в дискретном времени. Известно (см. [40, 41]), что СМО в дискретном времени играют важную роль в оценке производительности систем и сетей связи, поскольку позволяют учитывать дискретных характер передаваемой информации и дискретность функционирования реальных систем. Поэтому неудивительно, что исследование G-систем в дискретном времени уделялось и уделяется по прежнему значительное внимание (см, например, [42]-[45]).

Диссертация продолжает работы в области G-систем. В ней вводится новый вид отрицательной заявки. Рассматриваемые в рамках всей диссертационной работы отрицательные заявки не 'убивают" заявки, ожидающие в очереди, а вытесняют их в другую очередь. При этом, переместив заявку из одной очереди в другую, сама отрицательная заявка покидает систему. Системы подобного вида являются актуальным предметом исследований и имеют практическую ценность, поскольку позволяют создавать аналитические модели, применимые для следующих целей: моделирование различных стадий процессов планирования, управления и контроля движения материальных, информационных и финансовых ресурсов в различных областях деятельности (например, системы храпения скоропортящихся товаров или грузов). моделирование случаев отката транзакций в распределенных базах данных. Для обеспечения целостности данных при внесении изменений в базы данных применяются механизмы двухфазной фиксации. На первой фазе происходит уведомление и подготовка всех баз данных, участвующее в транзакции. А на второй выполняется либо фиксация транзакции, либо ее откат, если ее фиксация невозможна в любой из баз данных, вследствие внутренних сбоев сервера на котором установлена база данных или сбоя программного обеспечения. После отката выполнение транзакции не отменяется, а откладывается на некоторое случайное время, по истечению которого предпринимается очередная попытка. В данном случае внесение изменений в базы данных есть процесс обслуживания, тогда как выход из строя сервера или сбои программного обеспечения означают приход отрицательной заявки, которая откладывает (путем перемещения в бункер) выполнение транзакции; моделирование систем с параллельной обработки информации, где необходима синхронизация выполненных заданий для завершения очередного этапа вычислений. В накопитель поступают выполненные задания, которые требуют синхронизации, а поступление отрицательной заявки откладывает синхронизацию задания, фактически означая, что при выполнении задачи на одном из компьютеров произошел случайный сбой, приведший к увеличению времени выполнения задания.

Кратко остановимся на содержании диссертации.

Заключение диссертации по теме «Теория вероятностей и математическая статистика», Разумчик, Ростислав Валерьевич

Заключение

В диссертационной работе решены следующие задачи:

1. в главе 1 для модели одноканальной экспоненциальной СМО с отрицательными заявками и бункером для вытесненных заявок с очередями в накопителе и бункере неограниченной емкости найдено совместное стационарное распределение числа заявок в накопителе и бункере; стационарные маргинальные распределения очередей в накопителе и бункере; стационарное распределение в терминах ПЛС времени ожидания начала обслуживания заявки при восьми различных комбинациях выбора заявок на обслуживания и выбивания заявок из накопителя.

2. в главе 2 для экспоненциальных СА40 с различными ограничениями на емкости накопителя, бункера, и на число приборов с помощью теории эргодических процессов, матрично-геометрических методов, методов производящих функций, а также специальных функций (многочленов Чебышева. и Гегенбауэра) найдено совместное стационарное распределение числа заявок в накопителе и бункере; стационарные маргинальные распределения числа заявок в накопителе, бункере;

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

Для всех рассмотренных СМО разработаны программы для численного расчета, по предложенным алгоритмам и в приложении представлены сравнительные результаты численных расчетов и имитационного моделирования.

Список литературы диссертационного исследования кандидат физико-математических наук Разумчик, Ростислав Валерьевич, 2011 год

1. U. Narayan Bhat An introduction to queueing theory. Birkhauser Boston, 2007.

2. Батарин Г.П., Харкевич, А.Д., Шнепс. A.M. Массовое обслуживание в телефонии. М.: Наука, 1968.

3. Башарин Г.П., Бочаров П.П., Коган А.Я. Анализ очередей в вычислительных сетях. Теория и методы расчёта. М.: Наука, 1989.

4. Borovkov A.A. Asymptotical methods in queueing theory // Proc.of Winter Meeting in Probab. and Statistics. Ushgorod. 1964. P. 3-40.

5. Гнеденко Б.В., Коваленко И. Н. Гнедепко Б. В., Коваленко И. Н. Введение в теорию массового обслуживания. М.: Наука, 1966.

6. Kendall D.J. Stochastic processes occurring in the theory of queues and their analysys by the method of the embedded Markov chains // Ann. Math. Stat. 1953. № 24. P. 338-354.

7. Колмогоров A.H. Sur le probleme d'attente. Матем. сб. 1931. 38:1-2. С. 101-106.

8. Cox D.R. The analysis of non-Markovian stochastic processes by the inclusion of supplementary variables. Proc. Camb. Phil. Soc. 51. 1955.

9. Crommelin C. D. Delay probability formulae when the holding times are constant. Post Office Electrical Engineer's Journal. 1932. V.25. P. 41-50.

10. Palm C. Palm C., Intensitatsschwankungen im Fernsprechverkehr. Ericsson Technics. 1943. № 44. P. 1-189.

11. Pollaczek, F. Ueber eine Aufgabe der Wahrscheinlichkeitstheorie. Mathematische Zeitschrift. 1930. № 32. P. 64-100.

12. Saaty T. Elements of Queueing Theory. McGraw-Hill, 1961.

13. Севастьянов Б. А. Эргодическая теорема для марковских процессов и ее приложение к телефонным линиям с отказами // Теория вероятностей и ее прим. 1957. Т.2. № 1. С. 106-116.

14. Smith W.L. On the distribution of queueing times. Proc. Camb. Phil. Soc. 49. 1953.

15. Takacs L. Investigations of Waiting Time Problems by Reduction to Markov Processes // Acta Math. Acad. Sci. Hung. 1955 V.6. P. 101129.

16. Feller W. An Introduction to Probability Theory and its Applications, Volume one. John Wiley, 1950.

17. Foster F.G. On stochastic matrices associated with certain queueing processes. Ann. Math. Statist. 24. 1953. P. 355-360.

18. Хинчин А.Я. Математическая теория стационарной очереди. Матем. сб. 1932. 39:4. С. 73-84.

19. Бочаров П.П., Печинкин А.В. Теория массового обслуживания. М.: Изд-во РУДН, 1995.

20. Бочаров П.П., Вишневский В.М. G-сети: развитие теории мультипликативных сетей // АиТ. 2003. № 5.

21. Kleinrock L. Queueing Systems: Volume I Theory. Wiley Interscience, 1975.

22. Prohorov Y. V. Transient phenomena in queueing processes. Liet. Mat. Rink. 1963. № 3. P. 199-206.

23. Gelenbe E., Glynn P., Sigman K. Queues with negative arrivals // Journal of Applied Probability. 1991. V.28. P. 245-250.

24. Gelenbe E. Random neural networks with negative and positive signals and product form solution // Neural Computation. 1989. V.l. № 4. P. 502-510.

25. Gelenbe E. G-nctworks: an unifying model for neural and queueing networks // Annals of Operations Research. 1994. V.48. № 1-4. P. 433-461.

26. Artalejo J.R. G-networks: A versatile approach for work removal in queueing networks. Eur. J. Oper. Res. 2000. V.126. P. 233-249.

27. Krishna Kumar В., Arivudainambi D., Krishnamoorthy A. Some results on a generalized M/G/l feedback queue with negative customers // Ann. Oper. Res. 2006. № 143. P. 277-296.

28. Соколов И.А., Печинкин А.В., Чаплыгин В.В. Стационарные характеристики многолинейной системы массового обслуживания с ненадежными приборами // Обозрение прикладной и промышленной математики. 2007. Т. 14. № 5. С. 27-39.

29. Yang Woo S. Multi-server retrial queue with negative customers and disasters // Queueing Syst. 2007. № 55. P. 223-237.

30. Чаплыгин В. В. Система массового обслуживания G/MPS/n/r с потоком отрицательных заявок // Информационные процессы. 2005. Т. 5, № 1. С. 1-19.

31. Бочаров П., Д'Апиче Ч., Мандзо Р., Печинкин А. В. Анализ многолииейной марковской системы массового обслуживания с неограниченным накопителем и отрицательными заявками // Автоматика и телемеханика. 2007. № 1. С. 93-104.

32. Печинкин А. В. Марковская система обслуживания с конечным накопителем и отрицательными заявками, действующими на конец очереди // Информационные процессы. 2007. Т.7. С. 138-152.

33. Qua,n-Lin L., Yiqiang Q. Z. A MAP/G/1 Queue with Negative Customers // Queueing Systems. 2004. № 47. P. 5-43.

34. Kim C., Klimenok V.I., Orlovsky D.S. Multi-Server Queueing System with a Batch Markovian Arrival Process and Negative Customers // Automation and Remote Control. 2006. № 12. P. 106-122.

35. Manuel Paul, Sivakumar B., and Arivarignan G. Perishable Inventory System with Postponed Demands and Negative Customers // Journal of Applied Mathematics and Decision Sciences. 2007.

36. Gym,ez-Corral A., Martos M. E. Marked Markovia.n Arrivals in a Tandem G-Network with Blocking // Methodol. Comput. Appl. Probab. 2009. P. 621-649.

37. Arnon Arazia, Eshel Ben-Jacobb, Uri Yechialia Bridging genetic networks and queueing theory // Physica. Ser., A. V.232. 2004. P. 585-616.

38. Ram Chakka, Tien Van Do The MMJ2k=oCPPt>-/GE/c/L G-Queue and its Application to the Analysis of the Load Balancing in MPLS Networks // Proceedings of the 27th Annual IEEE Conference on Local Computer Networks (LCN02), 2002.

39. Herwig Bruneel, Byung G. Kim. Discrete-Time Models for Communication Systems Including ATM. Kluwer Academic Publishers, 1992.

40. Woodward M.E. Communication and Computer Networks: Modelling with Discretetime Queues, IEEE Computer Society Press, 1994.

41. Atencia I., Moreno P. The discrete-time Geo/Geo/1 queue with negative customers and disasters. Computers and Operations Research. 2004. V. 31. № 9, P. 1537-1548.

42. Atencia I., Moreno P. A single-server G-queue in discrete-time with geometrical arrival and service process. Performance Evaluation. 2005. V. 59. № 1. P.85-97.

43. Li Ma A Class of Geom/Geom,/1 Discrete-time Queueing System with Negative Customers. Int.J.NonlincarSci. 2008. V. 5. № 3. P.275-280.

44. Hyun Min Parka, Won Seok Yangb, Kyung Chul Chaea The Geo/G/1 Queue with Negative Customers and Disasters. Stochastic Models. 2009. V. 25. Issue 4.

45. Neuts M.F. Matrix-geometric solutions in stochastic models. An algorithmic approach. Baltimore and London, The Johns Hopkins Univ. Press, 1981.

46. Latouche G. a,nd Taylor P. G. Level-Phase Independence for GI\M\1 Type Markov Chains // J. Appl. Prob. 2000. V. 37. P. 984-998.

47. Гантмахер Ф. M. Теория матриц. M.: Наука, 1966.

48. Favati P. and Meini B. On Functional Iteration Methods for Solving Nonlinear Matrix Equations Arising in Queueing Problems // IMA J. Numer. Anal. 1999. № 19. P. 39-49.

49. Guo C.-H. On the Numerical Solution of a Nonlinear Matrix Equation in Markov Chains // Linear Algebra Appl. 1999. № 288. P. 175-186.

50. Latouche G. Newton's Iteration for Non-Linear Equations in Markov Chains // IMA J. Numer. Anal. 1994. № 14. P. 583-598.

51. Latouche G. Algorithms for Evaluating the Matrix G in Markov Chains of Ph\G\l Type // Cahiers Centre Etudes Rech. Oper. 1994. № 36. P. 251-258.

52. Meini B. New Convergence Results on Functional Iteration Techniques for the Numerical Solution of M\G\1 Type Markov Chains // Numer. Math. 1997. № 78. P. 39-58.

53. Neuts M. F. Moment Formulas for the Markov Renewal Branching Process // Adv. in Appl. Probab. 1976. № 8. P. 690-711.

54. Ye Q. High Accuracy Algorithms for Solving Nonlinear Matrix Equations in Queueing Models // Advances in Algorithmic Methods for Stochastic Models. 2000. P. 401-415.

55. Latouche G. and Ramaswami V. A Logarithmic Reduction Algorithm for Quasi-Birth-Death Processes // J. Appl. Probab. 1993. № 30. P. 650 -674.

56. Корн Г., Корн Т. Справочник по математике. М.: Наука. 1974.

57. Bocharov P.P. , D'Apice C., Pechinkin A.V., Salerno S. Queueing Theory. Utrecht, Boston: VSP, 2004.

58. Erdelyi A. and Bateman H. Higher transcendental functions. Volume II. Robert E. Krieger Publishing Company, 1985.

59. Мандзо Р., Касконе Н., Разумчик Р.В. Экспоненциальная система массового обслуживания с отрицательными заявками и бункеромдля вытесненных заявок // Автоматика и телемеханика. 2008. № 9. С. 103-113.

60. Печинкин А.В., Разумчик Р.В. Система массового обслуживания с отрицательными заявками и бункером для вытесненных заявок в дискретном времени // Автоматика и телемеханика. 2009. № 12. С. 109-120.