Диплом, курсовая, контрольная работа
Помощь в написании студенческих работ

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

Диссертация: Оптимальное управление потоками в сетях массового обслуживания
ДиссертацияПомощь в написанииУзнать стоимостьмоей работы

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

Содержание

  • Глава 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. № 1 930 007 385), «Управление сетями массового обслуживания» (шифр «Контур», гос. per. № 1 930 007 386), «Теория и методы управления сетями массового обслуживания» (шифр «Звено», гос. per. № 1 960 007 744), «Синтез сетей массового обслуживания с управлением» (шифр «Такт», гос. per. № 1 200 001 098), раздел «Математические задачи синтеза сетей массового обслуживания с динамическим управлением» госбюджетной темы «Разработка и применение фундаментальных методов исследования задач математического анализа, дифференциальных уравнений, дискретной математики, теории упругости и газодинамики» (шифр «Интеграл», гос. per. № 1 200 002 986).

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

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

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., Muntz 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. 12 091 233.
  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! HCIIAI"-BuBJUiO'
Заполнить форму текущей работой

На отлично!