Оценка показателей и оптимизация производственных процессов с использованием моделей сетей очередей

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

Для построения алгоритма использованы методы декомпозиции, баланса заявок и двухмоментной аппроксимации узла сети типа GI/G/m. Для улучшения сходимости итерационной процедуры, используемой в алгоритме, применяется метод Вегстейна. Алгоритм программы реализован на языке программирования Python, корректность и практическая применимость подтверждены путем анализа погрешностей расчета значений разных показателей сетей с использованием имитационного моделирования в среде GPSS World. Погрешность расчета показателей сетей разных рассмотренных классов замкнутых немарковских сетей очередей не превышает 10 – 15. Поставлены и решены задачи оптимизации сети, путем назначения оптимальных интенсивностей обслуживания с учетом ограничения на стоимость оборудования. Проведен анализ времени работы программ расчета и оптимизации для сетей различного размера.

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

СОДЕРЖАНИЕ

ПЕРЕЧЕНЬ УСЛОВНЫХ ОБОЗНАЧЕНИЙ, ТЕРМИНОВ И СОКРАЩЕНИЙ .. 8

ВЕДЕНИЕ ................................................................................................................. 9

ГЛАВА 1. ТЕОРЕТИЧЕСКИЕ ОСНОВЫ. АНАЛИЗ СУЩЕСТВУЮЩИХ ПРИБЛИЖЕННЫХ МЕТОДОВ РАСЧЕТА ......................................................... 11

1.1. Роль сетей СМО в моделировании производственных процессов ............... 11

1.2. Классификация сетей СМО ............................................................................ 13 1.3. Методы расчета показателей сетей СМО ...................................................... 15

1.3.1. Точные методы ................................ ................................ .............................. 15

1.3.2. Приближенные методы ................................ ................................ ................ 16

1.3.3. Метод декомпозиции сети ................................ ................................ ............ 17

1.3.4. Приближенный двухмоментный метод оценки времени ожидания в узле GI/G/m ....... 18

1.3.5. Метод баланса заявок ................................ ................................ ................... 21

1.3.6. Метод Вегстейна ................................ ................................ ........................... 23

ГЛАВА 2. ПОСТАНОВКА ЗАДАЧ ОЦЕНКИ ПОКАЗАТЕЛЕЙ И ОПТИМИЗАЦИИ ЗАМКНУТЫХ НЕМАРКОВСКИХ СЕТЕЙ СМО. АЛГОРИТМ ДЕЙСТВИЙ ...................................................................................... 24

2.1. Постановка задач оценки показателей ........................................................... 24

2.1.1. Задача оценки показателей однородной одноканальной сети очередей .... 25

2.1.2. Задача оценки показателей однородной многоканальной сети очередей .. 26

2.1.3. Задача оценки показателей неоднородной одноканальной сети очередей 27

2.1.4. Задача оценки показателей неоднородной многоканальной сети очередей ................... . 28

2.2. Постановка задачи оптимизации сети ............................................................ 28

2.3. Алгоритм расчета показателей сети ............................................................... 30

2.4. Алгоритм оптимизации сети ........................................................................... 33

ГЛАВА 3. РАСЧЕТ ПОКАЗАТЕЛЕЙ И ОПТИМИЗАЦИЯ ЗАМКНУТЫХ НЕМАРКОВСКИХ СЕТЕЙ СМО........... 34

7

3.1. Однородная одноканальная сеть очередей .................................................... 35

3.1.1. Расчет сети ................................ ................................ ................................ .... 36

3.1.2 Оптимизация сети................................ ................................ .......................... 37

3.2. Однородная многоканальная сеть очередей .................................................. 39

3.2.1. Расчет сети ................................ ................................ ................................ .... 40

3.2.2. Оптимизация сети................................ ................................ ......................... 42

3.3. Неоднородная одноканальная сеть очередей ................................................. 43

3.3.1. Расчет сети ................................ ................................ ................................ .... 44

3.3.2. Оптимизация сети................................ ................................ ......................... 46

3.4. Неоднородная многоканальная сеть............................................................... 48

3.4.1. Расчет сети ................................ ................................ ................................ .... 49

3.4.2. Оптимизация сети................................ ................................ ......................... 51

ГЛАВА 4. АНАЛИЗ ПОГРЕШНОСТЕЙ .............................................................. 53

4.1. Анализ сети очередей с числом узлов равным 7 (М = 7) .............................. 53

4.1.1. Расчет сети очередей с числом узлов равным 7 (М = 7) ............................. 54

4.1.2. Оптимизация сети с числом узлов равным 7 (М = 7) ................................ . 55

4.2. Анализ погрешностей ..................................................................................... 58

4.3. Дополнительное исследование влияния входных параметров на время работы программы .. 59

ЗАКЛЮЧЕНИЕ ...................................................................................................... 61

СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ .............................................. 63

ПРИЛОЖЕНИЕ 1. ПРОГРАММНАЯ РЕАЛИЗАЦИЯ АЛГОРИТМА РАСЧЕТА И ОПТИМИЗАЦИИ ЗАМКНУТЫХ НЕМАРКОВСКИХ СЕТЕЙ СМО ............ 64

ПРИЛОЖЕНИЕ 2. ПРОГРАММА ИМИТАЦИОННОГО МОДЕЛИРОВАНИЯ ДЛЯ ОЦЕНКИ ПОКАЗАТЕЛЕЙ ЗАМКНУТЫХ НЕМАРКОВСКИХ СЕТЕЙ С ЧЕТЫРМЯ УЗЛАМИ И ДВУМЯ КЛАССАМИ ЗАЯВОК ............. 71

ПРИЛОЖЕНИЕ 3. ПРОГРАММА ИМИТАЦИОННОГО МОДЕЛИРОВАНИЯ ДЛЯ ОЦЕНКИ ПОКАЗАТЕЛЕЙ ЗАМКНУТЫХ ОДНОРОДНЫХ НЕМАРКОВСКИХ СЕТЕЙ С СЕМЬЮ УЗЛАМИ .............................................. 75

СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ

1. Рыжиков Ю. И. Вычислительные методы, СПб.: БХВ-Петербург, 2007.

2. Сиднев А. Г., Сабонис С. С., Цыган В. Н. Массовое обслуживание для исследования и оптимизации систем, СПб.: Изд-во СПбПУ, 2025.

3. Baskett F., Chandy K. M., Muntz R. R., Palacios-Gomez F. Open, closed and mixed networks of queues with different classes of customers, J. ACM, vol. 22, no. 2, pp. 248-260, 1975.

4. Bitran G., Morabito R. Open Queueing Networks: Optimization and Performance Evaluation Models for Discrete Manufacturing Systems, WP #3743 94, 1994.

5. Bose S. K. An Introduction to Queueing Systems, Springer Science+Business Media, New York, 2002.

6. Buitenhek R., Baynat B., Dallery Y. Production Capacity of Flexible Manufacturing Systems with Fixed Production Ratios, International Journal of Flexible Manufacturing, vol. 14, pp. 203-225, 2002.

7. Kleinrock L. Queueing Systems. Volume 1: Theory, John Wiley & Sons, 1975.

8. Sadre R., Haverkort B. R. Decomposition-Based Queueing Network Analysis with FiFiQueues, in Queueing Networks, Springer, 2011.

9. Satyam K., Krishnamurthy A., Kamath M. Solving general multi-class closed queuing networks using parametric decomposition, Computers & Operations Research, vol. 40, pp. 1777–1789, 2013.

10. Whitt W. Open and Closed Models for Networks of Queues, AT&T Bell Laboratories Technical Journal, vol. 63, no. 9, 1984.

11. Whitt W. The Queueing Network Analyzer, Bell Laboratories Technical Journal, vol. 62, no. 9, pp. 2779–2815, 1983. 12. Wu K. Three-Moment Approximation for the Mean Queue Time of a GI/G/1 Queue, IISE Transactions, July 2017.