Здесь необходимо пояснить следующее. В контексте решаемой оптимизационной задачи под интенсивностью обслуживания в узле понимается интенсивность обслуживания в одном (любом) его канале. Иными словами, интенсивность μi обслуживания в узле – это величина, обратная среднему времени обслуживания в узле.
Ваши варианты СеМО совпадают с теми, которые вы исследовали в лабораторных работах 3 и 4. Таким образом, расчет системных характеристик экспоненциальной версии СеМО, включая время E, уже выполнен и проверен. Но это был не оптимизированный вариант СеМО. Теперь, выполняя данную лабораторную работу 5, вы должны получить оптимизированный вариант, в котором суммарный ресурс M* вашей сети перераспределен так, чтобы время E было минимальным. По-видимому, полученное при оптимизации значение E = E(μopt ) будет заметно меньше рассчитанного в работе 4. Для проверки по-
лученного значения E = E(μopt ) используйте имитационную модель вашей
СеМО, написанную на языке GPSS в лабораторной работе 3. В модель нужно внести следующие изменения: а) все распределения времени обслуживания следует определить как экспоненциальные; б) все интенсивности обслуживания в узлах должны быть оптимальными, полученными способом, описанным выше на примере СеМО рис. 3.18. Для наглядности приведем листинг GPSS-модели этой СеМО и фрагмент листинга отчета, полученного в результате выполнения GPSS-модели по команде START 1.
1. Листинг GPSS-модели СеМО:
* Суммарный ресурс M* = 30
TTB TABLE |
M1,0,2,60 |
1 |
CHAN1 |
STORAGE |
|
CHAN2 |
STORAGE |
2 |
CHAN3 |
STORAGE |
1 |
CHAN4 |
STORAGE |
1 |
CHAN5 |
STORAGE |
1 |
CHAN6 |
STORAGE |
1 |
CHAN7 |
STORAGE |
1 |
CHAN8 |
STORAGE |
3 |
CHAN9 |
STORAGE |
1 |
|
GENERATE |
(Exponential(1,0,1)) |
|
TRANSFER |
.5,,SMO3 |
SMO1 |
TRANSFER |
.6,SMO1,SMO2 |
QUEUE |
1 |
|
|
ENTER |
CHAN1 |
|
DEPART |
1 |
|
ADVANCE |
(Exponential(1,0,1/0.83244)) |
|
LEAVE |
CHAN1 |
SMO2 |
TRANSFER |
,SMO4 |
QUEUE |
2 |
|
|
ENTER |
CHAN2 |
126
|
DEPART |
2 |
|
ADVANCE |
(Exponential(1,0,1/0.60184)) |
|
LEAVE |
CHAN2 |
SMO3 |
TRANSFER |
.3,SMO4,SMO5 |
QUEUE |
3 |
|
|
ENTER |
CHAN3 |
|
DEPART |
3 |
|
ADVANCE |
(Exponential(1,0,1/1.49997)) |
|
LEAVE |
CHAN3 |
SMO4 |
TRANSFER |
,SMO5 |
QUEUE |
4 |
|
|
ENTER |
CHAN4 |
|
DEPART |
4 |
|
ADVANCE |
(Exponential(1,0,(1/3.01989))) |
|
LEAVE |
CHAN4 |
|
TRANSFER |
.3,,CMO9 |
SMO5 |
TRANSFER |
.571429,SMO6,SMO7 |
QUEUE |
5 |
|
|
ENTER |
CHAN5 |
|
DEPART |
5 |
|
ADVANCE |
(Exponential(1,0,1/9.33498)) |
|
LEAVE |
CHAN5 |
SMO6 |
TRANSFER |
.1,SMO8,CMO9 |
QUEUE |
6 |
|
|
ENTER |
CHAN6 |
|
DEPART |
6 |
|
ADVANCE |
(Exponential(1,0,1/1.31551)) |
|
LEAVE |
CHAN6 |
SMO7 |
TRANSFER |
,SMO4 |
QUEUE |
7 |
|
|
ENTER |
CHAN7 |
|
DEPART |
7 |
|
ADVANCE |
(Exponential(1,0,1/1.59226)) |
|
LEAVE |
CHAN7 |
SMO8 QUEUE |
TRANSFER |
,SMO4 |
8 |
CHAN8 |
|
|
ENTER |
|
|
DEPART |
8 |
|
ADVANCE |
(Exponential(1,0,1/2.92903)) |
|
LEAVE |
CHAN8 |
CMO9 |
TRANSFER |
,SMO5 |
QUEUE |
9 |
|
|
ENTER |
CHAN9 |
|
DEPART |
9 |
|
ADVANCE |
(Exponential(1,0,1/2.41417)) |
|
LEAVE |
CHAN9 |
|
TABULATE |
TTB |
|
TERMINATE |
|
|
GENERATE |
1000000 |
|
TERMINATE |
1 |
127
1. Фрагмент листинга отчета:
|
GPSS World Simulation Report |
- SeMO-9.1.1 |
|
|
|
|
||||||
|
Thursday, September 29, |
2012 04:24:20 |
|
STORAGES |
|
|||||||
START TIME |
|
|
END TIME |
|
BLOCKS |
FACILITIES |
|
|||||
|
0.000 |
|
1000000.000 |
|
61 |
0 |
|
9 |
|
|
||
QUEUE |
|
|
MAX CONT. ENTRY ENTRY(0) AVE.CONT. AVE.TIME |
|
||||||||
AVE.(-0) RETRY |
0 |
199729 |
151882 |
|
0.076 |
0.382 |
1.594 |
0 |
||||
1 |
9 |
|
||||||||||
2 |
7 |
0 |
299099 |
269727 |
|
0.032 |
0.108 |
1.099 |
0 |
|||
3 |
11 |
0 |
499428 |
332116 |
|
0.167 |
0.334 |
0.998 |
0 |
|||
4 |
15 |
0 |
1361370 |
|
747392 |
|
0.369 |
0.271 |
0.601 |
0 |
||
5 |
28 |
0 |
5894283 |
|
2168623 |
|
1.082 |
0.184 |
0.290 |
0 |
||
6 |
9 |
0 |
408346 |
281399 |
|
0.140 |
0.343 |
1.102 |
0 |
|||
7 |
13 |
0 |
543744 |
358092 |
|
0.175 |
0.321 |
0.941 |
0 |
|||
8 |
23 |
0 |
5305311 |
|
3394742 |
|
0.545 |
0.103 |
0.285 |
0 |
||
9 |
15 |
1 |
998252 |
586012 |
|
0.291 |
0.291 |
0.705 |
0 |
|||
STORAGE CAP. REM. |
MIN. MAX. ENTRIES AVL. AVE.C. |
UTIL. RETRY DELAY |
||||||||||
CHAN1 |
1 |
1 |
0 |
1 |
199729 |
1 |
0.240 |
0.240 |
0 |
0 |
||
CHAN2 |
2 |
1 |
0 |
2 |
299099 |
1 |
0.497 |
0.248 |
0 |
0 |
||
CHAN3 |
1 |
0 |
0 |
1 |
499428 |
1 |
0.333 |
0.333 |
0 |
0 |
||
CHAN4 |
1 |
1 |
0 |
1 |
1361370 |
1 |
0.451 |
0.451 |
0 |
0 |
||
CHAN5 |
1 |
1 |
0 |
1 |
5894283 |
1 |
0.631 |
0.631 |
0 |
0 |
||
CHAN6 |
1 |
1 |
0 |
1 |
408346 |
1 |
0.310 |
0.310 |
0 |
0 |
||
CHAN7 |
1 |
1 |
0 |
1 |
543744 |
1 |
0.341 |
0.341 |
0 |
0 |
||
CHAN8 |
3 |
1 |
0 |
3 |
5305311 |
1 |
1.812 |
0.604 |
0 |
0 |
||
CHAN9 |
1 |
0 |
0 |
1 |
998251 |
1 |
0.413 |
0.413 |
0 |
1 |
||
TABLE |
|
|
MEAN |
|
STD.DEV. |
|
|
RANGE |
|
RETRY |
|
|
FREQUENCY CUM.% |
7.918 |
|
7.123 |
|
|
|
|
0 |
|
|
||
TTB |
|
|
|
- |
|
2.000 |
|
11.54 |
||||
|
|
|
|
|
0.000 |
|
|
115155 |
||||
|
|
|
|
|
2.000 |
- |
|
4.000 |
|
216396 |
33.21 |
|
|
|
|
|
|
4.000 |
- |
|
6.000 |
|
182184 |
51.46 |
|
|
|
|
|
|
6.000 |
- |
|
8.000 |
|
132456 |
64.73 |
|
|
|
|
|
|
8.000 |
- |
|
10.000 |
|
94162 |
74.17 |
|
|
|
|
|
|
10.000 |
- |
|
12.000 |
|
67308 |
80.91 |
|
|
|
|
|
|
12.000 |
- |
|
14.000 |
|
48398 |
85.76 |
|
|
|
|
|
|
14.000 |
- |
|
16.000 |
|
35421 |
89.30 |
|
|
|
|
|
|
16.000 |
- |
|
18.000 |
|
25679 |
91.88 |
|
Как видим из результатов моделирования, таблица TTB, вычисляющая статистические характеристики времени ответа E, выдала его среднее значение 7,918, которое (с точностью до статистических погрешностей эксперимента) согласуется с рассчитанным значением E(μopt ) = 7,938.
128
Варианты заданий
Выполните приведенную в примерах оптимизацию СеМО, изображенной на рис. 3.18, и проверьте ее результаты путем ИМ этой СеМО. Затем выполните индивидуальные варианты заданий.
Индивидуальные варианты заданий (моделируемые СеМО и их параметры) указаны в лабораторной работе 3. В них изменяется только то, что интервалы обслуживания теперь нужно считать распределенными экспоненциально. Это позволит применить подход, описанный выше в примере оптимизации, поскольку он корректен только для экспоненциальных СеМО (теорема Джексона).
Примечание 1. При наличии в выбранном варианте двух и более входных потоков их рекомендуется «собрать» в один входной поток. Его интенсивность Λ должна быть равна сумме интенсивностей исходных потоков. И он должен разветвляться на входы соответствующих СМО (как, напр., на рис. 3.18). Переходные вероятности на его ветвях определяются как p01 = Λ1/Λ, p02 = Λ2/Λ и т. д. Это не изменит рассчитанных ранее локальных характеристик и времени E, но значительно облегчит составление и решение уравнений баланса.
Примечание 2 . Суммарный ресурс M * для вашего варианта СеМО нужно взять таким же, каким он был в лабораторной работе 3.
Примечание 3 . Корректное решение задач анализа и оптимизации немарковских (неэкспоненциальных) СеМО должно существенно опираться на их имитационное или численное моделирование [2–6, 10–20]. При ИМ СМО и СеМО возникают задачи планирования имитационных экспериментов, связанные с анализом переходных процессов, которые выше в учебном пособии подробно не рассматривались. Хорошее математическое введение в методы планирования имитационных экспериментов дается в книге [13], в методы оптимизации – в книге [1]. Один из наиболее эффективных методов оптимизации немарковских СеМО – двухуровневый двухэтапный аналитико-имитационный метод – описан в статьях [10, 11].
Форма отчёта
Отчет по лабораторной работе должен содержать описание всех основных этапов работы и формальные части, определенные в установленном порядке (титульный лист, реферат, оглавление и т. п.). Допускается представление отчета в электронном формате.
Контрольные вопросы
1.Выведите формулу μi min = λi / Ki для минимально допустимой интенсивности обслуживания узла из неравенства ρi max = 1.
2.Выведите формулу для расчета суммарного ресурса M * вашего варианта
СеМО.
3.Выведите формулы (3.32) для расчета среднего времени ожидания в узлах СеМО, рассматриваемой в примере оптимизации.
4.Докажите, что в центре ОДР, определяемом формулой (3.33), коэффициенты загрузки всех узлов СеМО одинаковы.
5.Объясните смысл всех числовых показателей на листе Excel на рис. 3.17.
129
Библиографический список к части 3
1.Базара, М. Нелинейное программирование. Теория и алгоритмы : [пер.
сангл.] / М. Базара, К. Шетти. – М. : Мир, 1982. – 583 с.
2.Боев, В. Д. Моделирование систем. Инструментальные средства GPSS World : учеб. пособие / В. Д. Боев. – СПб. : БХВ-Петербург, 2004. – 368 с.
3.Вишневский, В. М. Моделирование ведомственных систем электронной почты / В. М. Вишневский, С. М. Пороцкий // Автоматика и телемеханика. – 1996. – № 12. – С. 48–57.
4.Вишневский, В. М. Теоретические основы проектирования компьютерных сетей / В. М. Вишневский. – М. : Техносфера. – 2003. – 512 с.
5.Герасимов, А. И. Oптимизация замкнутых сетей массового обслуживания
снесколькими классами сообщений / А. И. Герасимов // Пробл. передачи ин-
форм., 30:1 (1994). – С. 85–96. http://www.mathnet.ru/php/archive.phtml? wshow=paper&jrnid=ppi&paperid=222&option_lang=rus (дата обращения: 13.02.2013).
6.Жожикашвили, В. А. Сети массового обслуживания. Теория и применение к сетям ЭВМ / В. А. Жожикашвили, В. М. Вишневский. – М. : Радио и связь, 1988. – 192 с.
7.Задорожный, В. Н. Моделирование систем : конспект лекций /В. Н. Задорожный. – Омск : Изд-во ОмГТУ, 2006. – 56 с.
8. Задорожный, В. Н. Имитационное моделирование : учеб. пособие / В. Н. Задорожный. – Омск : Изд-во ОмГТУ, 1999. – 151 с.
9.Статистическое моделирование : метод. указания к лаб. работам / сост. В. Н. Задорожный. – Омск : Изд-во ОмГТУ, 2006. – 32 с.
10.Задорожный, В. Н. Методы двухуровневого моделирования систем с
очередями / В. Н. Задорожный // Труды VII Междунар. конф. «Идентификация систем и задачи управления» SICPRO ’08 (28–31 янв. 2008 г.). – М., 2008. – С. 1484–1563.
11.Задорожный, В. Н. Оптимизация однородных немарковских сетей массового обслуживания / В. Н. Задорожный // Проблемы управления. – 2009. –
№6 – С. 68–75.
12.Иглхарт, Д. Л. Регенеративное моделирование сетей массового обслуживания / Д. Л. Иглхарт, Д. С. Шедлер. – М. : Радио и связь, 1984. – 135 с.
13.Клейнен, Дж. Статистические методы в имитационном моделировании : [пер с англ.] / Дж. Клейнен ; под ред. Ю. П. Адлера и В. Н. Варыгина. – М. :
Статистика, 1978. – Вып. 1. – 221 с.
14.Клейнрок, Л. Вычислительные системы с очередями : [пер. с англ.] / Л. Клейнрок / под ред. Б. С. Цыбакова. – М. : Мир, 1979. – 600 с.
15.Рыжиков, Ю. И. Имитационное моделирование. Теория и технологии / Ю. И. Рыжиков. – СПб. : КОРОНА принт; М. : Альтекс-А, 2004. – 384 с.
16. Феррари, Д. Оценка производительности вычислительных систем / Д. Феррари ; пер. c англ. А. И. Горлина, Ю. Б. Котова и Л. В. Ухова ; под ред.
В. В. Мартынюка. – М. : Мир, 1981. – 576 с.
17. Gabriel R. Bitran, Reinaldo Morabito. Open Queueing Networks: Optimization and Performance Evaluation Models for Discrete Manufacturing Systems // Сайт
130