Оптимальное управление потоками в сетях массового обслуживания тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

Введение

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

1.1. Оптимальное управление интенсивностями обслуживания

1.2. Оптимальное управление маршрутизацией.

1.3. Оптимальное управление потоками.

Глава 2. Оптимизация потоков в сетях массового обслуживания

2.1. Определение векторов относительных интенсивностей потоков для открытых сетей обслуживания.

2.2. Определение векторов относительных интенсивностей потоков для замкнутых сетей обслуживания.

2.3. Построение множества векторов относительных интенсивностей потоков.

2.4. Метод формирования маршрутных матриц.

Глава 3. Динамическое управление потоками в сетях массового обслуживания

3.1 Открытые сети обслуживания.

3.2. Открытые сети с параллельными системами массового обслуживания . . . ■.

3.3. Замкнутые сети обслуживания.

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

Глава 4. Исследование сетей массового обслуживания с управлением потоками.

4.1. Исследование открытых сетей обслуживания.

4.2. Исследование эффективности метода динамического управления потоками.

4.3. Исследование замкнутых сетей обслуживания.

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

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

Большой вклад в развитие теории, методов анализа, оптимизации и синтеза сетей массового обслуживания внесли А. А. Боровков, Г. П. Башарин, В. М. Вишневский, П. П. Бочаров, В. А. Ивницкий, В. В. Рыков, Ю. В. Солодянников, А. В. Печинкин. Среди зарубежных специалистов необходимо отметить таких ученых, как Дж. Джексон, Л. Клейнрок, Ф. Келли, К. Чэнди, А. Лазар, Д. Тауслей.

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

В основу диссертации положены результаты научных исследований, выполненных при участии автора в Саратовском государственном университете по темам, включенным в план НИР СГУ: «Математическое моделирование сетей передачи данных и информационно-вычислительных сетей» (шифр «Сеть», гос. per. № 01930007385), «Управление сетями массового обслуживания» (шифр «Контур», гос. per. № 01930007386), «Теория и методы управления сетями массового обслуживания» (шифр «Звено», гос. per. №01960007744), «Синтез сетей массового обслуживания с управлением» (шифр «Такт», гос. per. № 01200001098), раздел «Математические задачи синтеза сетей массового обслуживания с динамическим управлением» госбюджетной темы «Разработка и применение фундаментальных методов исследования задач математического анализа, дифференциальных уравнений, дискретной математики, теории упругости и газодинамики» (шифр «Интеграл», гос. per. № 01200002986).

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

Основными задачами, решаемыми в диссертации, являются следующие.

1. Разработка методов оптимального управления потоками в сетях массового обслуживания.

2. Разработка методов оптимизации маршрутных матриц сетей массового обслуживания.

3. Анализ сетей обслуживания с управлением потоками.

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

В диссертационной работе получены следующие основные результаты.

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

2. Разработаны методы оптимизации маршрутных матриц сетей массового обслуживания.

3. Получены основные характеристики сетей массового обслуживания с управлением потоками.

Постановка задач, методы решения и полученные результаты являются новыми.

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

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

Основные результаты диссертации опубликованы в работах [28-31, 4144]. Результаты докладывались и обсуждались на научных семинарах кафедры системного анализа и автоматического управления Саратовского государственного университета, Первом и Втором Всероссийских симпозиумах по прикладной и промышленной математике (1-6 июня 2000г., г. Петрозаводск; 1-6 июля 2001г., г. Самара), представлены и обсуждались на Четвертой международной научно-технической конференции «Математическое моделирование физических, экономических, технических, социальных систем и процессов» (10-12 декабря 2001г., г. Ульяновск), Международной научной конференции «Компьютерные науки и информационные технологии» (14-18 мая 2002г., г. Саратов).

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

Ю. И. Митрофанов, соавтор совместных публикаций [28-31], принимал участие в постановке задач, решаемых в диссертационной работе, в разработке концепций оптимального управления потоками в сетях массового обслуживания, в формировании идей доказательств некоторых утверждений.

Диссертация состоит из введения, четырех глав, заключения, списка литературы. Объем диссертации 103 страницы. Диссертация содержит 17 таблиц. Список литературы включает 79 наименований.

Заключение

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

- метод оптимального динамического управления потоками в открытых СеМО;

- метод оптимизации потоков;

- метод оптимального динамического управления потоками;

- метод формирования маршрутных матриц;

- выражения для стационарного распределения вероятностей состояний однородных открытых и замкнутых сетей обслуживания с управлением потоками.

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

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

1. Баканов A.C., Вишневский В.М., Ляхов А.И. Метод оценки показателей производительности беспроводных сетей с централизованным управлением // Автоматика и телемеханика, 2000, № 4, с. 97-105.

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

3. Башарин Г.П., Толмачев А.Л. Некоторые результаты теории сетей массового обслуживания // Методы развития теории телетрафика. М.: Наука, 1979, с. 52-65.

4. Беляков В.Г., Митрофанов. Ю.И. К исследованию замкнутых сетей массового обслуживания большой размерности // Автоматика и телемеханика, 1981, №7, с. 61-69.

5. Боровков A.A. Асимптотические методы в теории массового обслуживания. М.: Наука, 1980, 384с.

6. Боровков A.A. Предельные теоремы для сетей обслуживания // Теория вероятностей и ее применения, 1986, Т. 31, Вып. 3, с. 474-490; 1987, Т. 32, Вып. 2, с. 282-298.

7. Бочаров П.П. Приближенный метод расчета разомкнутых неэкспоненциальных сетей МО конечной емкостью с потерями или блокировками // Автоматика и телемеханика, 1987, № 1, с. 55-65.

8. Бурлаков М.В. Ситуационное управление процессами обслуживания с синхронизированными управлениями // Автоматика и телемеханика, 1993, № 8, с. 63-73.

9. Вербицкий С.Н., Рыков B.B. Численное исследование оптимальных политик управления скоростью обслуживания // Автоматика и телемеханика, 1998, № 11, с. 59-70.

10. Вишневский В.М., Ляхов А.И., Терещенко Б.Н., Моделирование беспроводных сетей с децентрализованным управлением // Автоматика и телемеханика, 1999, № 6, с. 88-99.

11. Гурьянов А.И., Митрофанов Ю.И. Определение параметров замкнутых линейных сетей систем массового обслуживания // Системное моделирование. Новосибирск: Вычислительный центр СО АН СССР, 1970, Вып. 1, с. 39-49.

12. Жожикашвили В.А., Вишневский В.М. Сети массового обслуживания. Теория и применение к сетям ЭВМ.: Радио и связь, 1988. 192 с.

13. Ивницкий В.А. О стационарных вероятностях состояний замкнутой звездообразной сети массового обслуживания при зависимости вероятностей перехода от ее состояния // Автоматика и вычислительная техника, 1994, № 6, с. 29-37.

14. Ивницкий В.А. Об инвариантности стационарных вероятностей состояний замкнутой звездообразной сети массового обслуживания при зависимости вероятностей перехода от ее состояния // Теория вероятностей и ее применения, 1997, Т. 42, № 1, с. 179-184.

15. Клейнрок Л. Теория массового обслуживания / Пер. с англ. М.: Машиностроение, 1979. 432 с.

16. Клейнрок Л. Вычислительные системы с очередями / Пер. с англ. М.: Мир, 1979. 600 с.

17. Крыленко A.B. Сети массового обслуживания с несколькими типами заявок, немедленным обслуживанием и обходами узлов заявками // Проблемы передачи информации, 1997, Т. 33, Вып. 3, с. 91-101.

18. Крыленко A.B., Малинковский Ю.В. Сети массового обслуживания с мгновенно обслуживаемыми заявками II. Модели с несколькими типами заявок // Автоматика и телемеханика, 1998, № 2, с. 62-71.

19. Кузнецов Д.Ю., Назаров A.A. Исследование сетей связи с конечным числом абонентских станций, управляемых адаптивными протоколами случайного множественного доступа в условиях перегрузки // Автоматика и телемеханика, 1999, № 12, с. 99-113.

20. Ляхов А.И. Асимптотический анализ замкнутых сетей очередей, включающих устройства с переменной интенсивностью обслуживания // Автоматика и телемеханика, 1997, № 3, с. 131-143.

21. Малинковский Ю.В. Инвариантность стационарного распределения состояний модифицированных сетей Джексона и Гордона-Ньюэлла // Автоматика и телемеханика, 1998, № 9, с. 29-36.

22. Малинковский Ю.В., Якубович О.В. Сети массового обслуживания с мгновенно обслуживаемыми заявками I. Модели с одним типом заявок // Автоматика и телемеханика, 1998, № 1, с. 92-106.

23. Митрофанов Ю.И. Метод синтеза замкнутых сетей массового обслуживания с экспоненциальным распределением длительностей обслуживания // Автоматика и вычислительная.техника, 2002, № 1, с. 77-84.

24. Митрофанов Ю.И. Основы теории сетей массового обслуживания. Саратов: Изд-во Сарат. ун-та, 1993. 116с.

25. Митрофанов Ю.И. Синтез сетей массового обслуживания. Саратов: Изд-во Сарат. ун-та, 1995. 164с.

26. Митрофанов Ю.И., Беляков В.Г., Курбангулов В.Х. Методы и программные средства аналитического моделирования сетевых систем. Препринт научного совета АН СССР по комплексной проблеме "Кибернетика", 1982. 68 с.

27. Митрофанов Ю.И., Тананко И.Е. Метод синтеза маршрутных матриц замкнутых сетей массового обслуживания // Саратов, гос. ун-т. Саратов, 1997, 13с. Рукопись деп. в ВИНИТИ 13.06.97г., per. № 1976-В97.

28. Митрофанов Ю.И., Тананко И.Е. О субоптимальном управлении эволюцией сетей массового обслуживания // Обозрение прикладной и промышленной математики, М.: Научное изд-во «ТВП», Т. 7, Вып. 1, 2000, с. 193-194.

29. Митрофанов Ю.И., Тананко И.Е. Оптимизация сетей массового обслуживания // Саратов, гос. ун-т. Саратов, 1997, 21с. Рукопись деп. в ВИНИТИ 17.02.98г., per. № 462-В98.

30. Митрофанов Ю.И., Тананко И.Е. Синтез оптимального управления потоками в сетях массового обслуживания // Саратов, гос. ун-т. Саратов,1999, 15с. Рукопись деп. в ВИНИТИ 04.06.99г., per. № 1782-В99.

31. Митрофанов Ю.И., Юдаева Н.В. Модели и анализ сетей массового обслуживания с управлением маршрутизацией // Автоматика и телемеханика,2000, №6, с. 104-113.

32. Митрофанов Ю.И., Юдаева Н.В. Управление маршрутизацией в сетях массового обслуживания // Автоматика и телемеханика, 1999, № 11, с. 4657.

33. Печинкин A.B. Стационарные вероятности состояний в системе с входящим потоком марковского типа, относительным приоритетом и раздельными очередями // Автоматика и телемеханика, 1998, № 1, с. 107-115.

34. Печинкин A.B., Рыков В.В. О декомпозиции замкнутых сетей с зависимым обслуживанием // Автоматика и телемеханика, 1999, № 11, с. 58-68.

35. Пономаренко Л.А., Меликов А.З. Оптимизация марковских непол-нодоступных сетей со сложными механизмами обслуживания // Автоматика и вычислительная техника, 1989, № 3, с.33-37.

36. Рыков В.В. Об условиях монотонности оптимальных политик управления системами массового обслуживания // Автоматика и телемеханика, 1999, №9, с. 92-106.

37. Солодянников Ю.В. О статистике систем и сетей массового обслуживания // Проблемы устойчивости стохастических моделей. Труды X Всесоюзного семинара. Куйбышевский гос. ун-т, 1987, с. 101-116.

38. Солодянников Ю.В. Робастное непараметрическое оценивание характеристик систем массового обслуживания // Автоматика и телемеханика, 1988, №4, с. 63-77.

39. Столяр A.A. Об оптимальном управлении нагрузкой сети массового обслуживания // Автоматика и телемеханика, 1989, № 5, с. 184-187.

40. Тананко И.Е. Метод оптимизации маршрутных матриц открытых сетей массового обслуживания // Автоматика и вычислительная техника, 2002, № 4, с. 39-46.

41. Тананко И.Е. О стационарном распределении сетей массового обслуживания с управлением маршрутизацией // Математика. Механика: Сборник научных трудов Саратов: Изд-во Сарат. ун-та, 2001, Вып. 3, с. 214-217.

42. Тананко И.Е. Об оптимизации открытых сетей массового обслуживания // Обозрение прикладной и промышленной математики, М.: Научное изд-во «ТВП», Т. 8, Вып. 1, 2001, с. 339.

43. Толмачев A.JL Сети обслуживания заявок с регенерирующими траекториями // Проблемы передачи информации, 1986, Т. 22, № 2, с. 59-68.

44. Уолрэнд Дж. Введение в теорию сетей массового обслуживания / Пер. с англ. М.: Мир, 1993. 336 с.

45. Alanyali М., Hajek В. Analysis of simple algorithms for dynamic load balancing // Math. Oper. Res., 1997, Vol. 22, N 4, p. 840-871.

46. Alidrisi M.M. Optimal control of the service rate of an exponential queue-ing network using Markov decision theory // Int. J. Syst. Sei., 1990, 21, N 2, p. 2553-2563.

47. Altman E., Gaujal В., Hordijk A. Balanced sequences and optimal routing // INRIA Report No. RR-3180, Sophia-Antipolis, France, June 1997.

48. Baskett F., Chandy K.M., Müntz R.R., Palacios F.G. Open, closed and mixed networks of queues with different classes of customers // J. ACM., 1975, Vol. 22, N 2, p. 248-280.

49. Boel R.K., Schuppen J.H. Distributed routing for load balancing // Discrete Event Dynamic Systems Analizing complexity and performance in the modern world Y.C. Ho ed., 1992, p. 237-248.

50. Boucherie R.J. Norton's equivalent for queueing networks comprised of quasireversible components linked by state-dependent routing // Performance Evaluation, 1998, Vol. 32, N 2, p. 83-99.

51. Bovopoulos A.D., Lazar A.A. Optimal load balancing for markovian queueing networks // 30th Midwest Symp. Circ. and Syst., Syracuse, N.Y., Aug. 17-18, 1987: Proc.-New York, 1988, p.1428-1432.

52. Buzen J.P. Computational algorithms of closed queueing networks with exponential servers // Commun. of ACM, 1973, V. 16, N 9, p. 527-531.

53. Calvert B., Solomon W., Ziedins I. Braess's paradox in a queueing network with state-dependent routing // J. Appl. Prob., 1997, Vol. 34, p. 134-154.

54. Chandy K.M., Herzog U., Woo L. Approximate analysis of general queueing networks // IBM J. Res. Dev., 1975, Vol. 19, N 1, p. 43-49.

55. Chandy K.M., Herzog U., Woo L. Parametric analysis of queueing networks // IBM J. Res. Dev., 1975, Vol. 19, N 1, p. 38-42.

56. Chandy K.M., Howard J.H.Jr., Towsley D.F. Product form and local balance in queueing networks // J. ACM., 1977, Vol. 24, N 2, p. 250-263.

57. Gibbens R., Kelly F.P., Turner S. Dynamic routing in multiparented networks // IEEE/ACM Transactions on Networking, 1993, Vol. 1, p. 261-270.

58. Gordon W.J., Nowell G.F. Closed queueing systems with exponential servers // Oper. Res., 1967, Vol. 15, N 2, p. 254-265.

59. Jakson J.R. Networks of waiting lines // Oper. Res., 1957, Vol. 5, N 4, p. 131-142.

60. Kelly F.P. Dynamic routing in stochastic networks // In Stochastic Networks (Ed. F.P. Kelly and R.J. Williams) The IMA Volumes in Mathematics and its Applications, 71. Springer Verlag. New York. 1995, p. 169-186.

61. Kelly F.P., Laws C.N. Dynamic routing in open queueing networks: Brownian models, cut constraints and resource pooling // Queueing Systems, 1993, N13, p. 47-86.

62. Korilis Y.A., Lazar A.A. On the existence of equilibria in noncooperative optimal flow control // J. ACM, May 1995, Vol. 42, p. 584-613.

63. Korilis Y.A., Lazar A.A., Orda A. Achieving network optima using stackelberg routing strategies // IEEE Transactions on Networking, February, 1997, Vol. 5,N 1,p. 161-173.

64. Kushner H.J., Ramachandran K.M. Optimal and approximately optimal control policies for queues in heavy traffic // SIAM J. Contr. and Optim., 1989, Vol. 27, N6, p. 1293-1318.

65. Mandelbaum A., Pats G. State-dependent stochastic networks, Part I: Approximations and applications with continuous diffusion limits'// Ann. Appl. Probab., 1998, 8(2), p. 569-646.

66. Martins L.F., Kushner H.J. Routing and singular control for queueing networks in heavy traffic // SIAM J. Contr. and Optim., 1990, Vol. 28, N 5, p. 12091233.

67. Mitra D., McKenna J. Asymptotic expansions for closed markovian networks with state-dependent service rates // J. ACM, 1986, Vol. 33, N 3, p. 568-592.

68. Ridder A.D. A linear programming problem in separable closed queueing network // IEEE Transaction on Automatic Control, Febr. 1989, Vol. 34, N 2, p.214-217.

69. Ross K.W. Optimal dynamic routing in Markov queueing networks // Automatica, 1986, Vol. 22, N 3, p. 367-370.

70. Ross K.W., Yao D.D. Optimal dynamic scheduling in Jackson networks // IEEE Trans. Autom. Cont., Vol. 34, N 1, January 1989, p.47-53.

71. Sracovich V.G. On decomposition in problem of Markov chain optimal control calculation by means of linear programming // Optimization, 1990, Vol. 21, N4, p. 593-600.

72. Stidham S.J., Weber R. A survey of Markov decision models for control of networks of queues // Queueing Systems, 1993, 13, p. 291-314.

73. Towsley D. Queueing network models with state-dependent routing // J. ACM, 1980. Vol. 27, N 2. p. 232-337.

74. Veatch M.H., Wein L.M. Monotone control of queueing networks // Queueing Systems, 1992, 12, p. 391-408.

75. Viniotis I., Ephremides A. Linear programming as a technique for optimization of queueing systems // Proc. 27th IEEE Conf. Decis. and Contr., Austin, Tex., Dec. 7-9, 1988. Vol. 1. New York (N.Y.), 1988, p. 652-656.

76. Weber R., Stidham S. Optimal control of service rates in networks of queues // Adv. Appl. Prob., 1987, 19, p. 202-218.

77. Yao D.D. Some properties of throughput function of closed networks of queues // Oper. Res. Letters, 1985, Vol. 3, N 6, p. 313-317.1. POCCl! HCÍIAÍ"-BuBJUiO'