Методика оптимизации структуры и параметров библиотечной автоматизированной системы обеспечения информационными услугами (стр. 6 из 12)

Вершины начального симплекса:

Оптимизируемой функцией является (2.2), где

взяты из табл. 2.3.

Критерий останова:

Результат:

2.4 Структура ИМ

Исходные данные:

1. Система планирования. Моделируется п - канальная система массового обслуживания. Каналы системы равноэффективны. Известна плотность распределения случайного времени обслуживания заявок -j(t).

2. Входящий поток заявок. На вход системы поступает случайный поток заявок с плотностью распределения случайного временного интервала между заявками y(t).

3. Ожидание в системе. Заявки, поступившие в буфер, ожидают свое обслуживание в порядке очереди некоторое время. Известна плотность распределения случайного времени ожидания заявок - ς (t).

4. Дисциплина обслуживания. Если в момент поступления заявки хотя бы один из каналов системы свободен, поступившая заявка начинает обслуживаться этим каналом. Если в момент поступления заявки свободных каналов нет, то заявка поступает в буфер, емкость которого - М заявок. Заявка, поступившая в момент, когда все п каналов заняты и буфер занят, теряется.

5. Экономические характеристики системы. За каждую поступившую заявку система получает прибыль – С0, за каждую потерянную заявку – платит штраф – С1. Стоимость эксплуатации одного канала в единицу времени Сэ зависит от производительности канала, определяемой средним временем обслуживания одной заявки Тобс по формуле

Сэ(Тэ) = а0 + а1

. (2.3)

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

Сб = bМ2/3. (2.4)

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

Таблица 2.4 - Календарь событий

№	Тип события	Наименование события	Момент наступлениясобытия,	Признак
0	0	Поступление очередной заявки	0	0
1	1	Освобождение 1-го канала	0	1
2	1	Освобождение 2-го канала	0	1
…	…	…	…	…
	1	Освобождение -го канала	0	1
n+1	2	Уход из очереди 1-й заявки	0	1
…	…	…	…	…
n+m	2	Уход из очереди m-й заявки	0	1

В соответствии с логикой работы имитационной модели её алгоритм состоит из трех модулей: модуля 0, реализующего действия, инициируемые поступлением в систему очередной заявки (событие типа 0), модуля 1, реализующего действия, которые необходимо осуществить в связи с освобождением канала (событие типа 1), модуля 2, реализующего действия, которые необходимо осуществить в связи с уходом из очереди m-й заявки (событие типа 2).

Очередность работы модулей определяется координирующим элементом модели, которым является календарь событий. Совокупность операторов, обеспечивающих ввод необходимых для работы модели исходных данных, просмотр календаря и инициирующих действия модулей 0, 1, 2 образует внешний контур модели.

Структурная схема внешнего контура модели представлена на рис. 2.1.

Рис. 2.1 - Блок-схема внешнего контура модели

Работа внешнего контура начинается с ввода исходных данных и настройки.

Исходные данные:

n – число каналов системы;

M – емкость буфера;

N0 – заданное заранее число заявок, которые должны поступить в систему за время её работы;

Е0 = {1, 2,…, n} – массив номеров свободных каналов системы;

Е1 = {0,0,…,0} – массив номеров занятых обслуживанием каналов системы.

2.5 Описание алгоритма функционирования

Перед началом работы модели все каналы системы свободны, поэтому массив Е0 содержит номера всех каналов, а массив Е1 – пуст.

Начальный оператор модели сравнивает число заявок N, прошедших через систему, с предельным значением N0. Если N=N0, то выполняется статистическая обработка результатов моделирования и печать. Если же N<N0, то осуществляется просмотр календаря. При этом просматриваются в порядке возрастания номеров строки календаря, отмеченные признаком c=0, и выбирается та, для которой время выполнения соответствующего события является минимальным. Назначение и смысл признаков cj будут разъяснены позднее. Фиксируется номер найденного события (номер строки). Если он равен 0, то далее работает модуль 0, в противном случае проверяется тип события. Если тип является 1, то выполняется модуль 1, иначе модуль 2.

Перейдем к рассмотрению операций, реализуемых в модуле 0. Блок-схема модуля 0 приведена на рис. 2.2.

Рис. 2.2 - Блок-схема модуля 0

Оператор 1 увеличивает содержимое счетчика заявок, прошедших через систему, на единицу.

Оператор 2 проверяет, есть ли хотя бы один свободный канал. В этом случае переходим к оператору 3, в противном случае (если свободных каналов нет) – к оператору 11.

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

Оператор 4 реализует формирование случайной продолжительности обслуживания заявки в соответствии с заданной плотностью распределения j(t).

Оператор 5. Сформированная оператором 4 случайная величина h используется для расчета момента времени освобождения канала k0. Этот момент времени вычисляется по формуле

:= t0 + h,

t0 – момент поступления заявки (содержится в строке 0).

Полученное значение

запоминается в строке k0. Переход к оператору 6.

Оператор 6 присваивает признаку

, соответствующему номеру занятого канала, значение 0, символизирующее занятость канала. Переход к оператору 7.

Оператор 7 исключает из массива Е0 номеров свободных каналов номер k0 занятого канала. Переход к оператору 8.

Оператор 8 добавляет номер k0 занятого канала к массиву Е1. Переход к оператору 9.

Оператор 9 формирует случайную величину продолжительности интервала между заявками в соответствии с плотностью распределения y(t). Переход к оператору 10.

Оператор 10. Сформированная датчиком случайных чисел с плотностью распределения y(t) случайная величина x добавляется к значению t0 и, таким образом, определяется момент поступления следующей заявки: t0:= t0+x. Возврат к блоку 2 внешнего контура, контролирующему общее число заявок, прошедших через систему.

Оператор 11 выполняет действия в случае, когда в момент поступления заявок все каналы системы заняты. При этом проверяется, заполнен ли буфер. Если не заполнен (число т содержащихся в буфере заявок меньше емкости буфера М), то переход к оператору 12, в противном случае – к оператору 13.

Оператор 12 увеличивает число заявок в буфере на единицу.

Оператор 13 реализует формирование случайной продолжительности ожидания заявки в соответствии с заданной плотностью распределения N(t).

Оператор 5. Сформированная оператором 12 случайная величина H используется для расчета момента времени освобождения места в очереди. Этот момент времени вычисляется по формуле

tn+m:= t0 +H, (2.7)

t0 – момент поступления заявки (содержится в строке 0).

Полученное значение tn+m запоминается в строке n+m. Переход к оператору 9.

Оператор 15 увеличивает число заявок, получивших отказ (все каналы и буфер заняты), на единицу. Переход к оператору 9.

Рассмотрим теперь операции, реализуемые в модуле 1. Блок-схема модуля 1 приведена на рис. 2.4.

Рис. 2.3 - Блок-схема модуля 1

Модуль 1 начинает работать в случае, когда самое ранее из событий, отображаемых календарем, соответствует освобождению канала с номером r0.

Оператор 1 проверяет, есть ли хотя бы одна заявка, ждущая обслуживания в буфере. Если буфер не пуст (m¹0), то переход к оператору 2, в противном случае – к оператору 5.

Оператор 2 обеспечивает формирование случайной продолжительности h занятости канала r0 при обслуживании заявки, хранившейся в буфере. Переход к оператору 3.

Оператор 3 определяет момент окончания обслуживания каналом r0 заявки, взятой из буфера. Момент освобождения канала рассчитывается по формуле

:= + h. (2.8)

Переход к оператору 4.

Оператор 4 уменьшает число заявок, хранящихся в буфере и ожидающих освобождения какого-либо канала, на единицу. Возврат к оператору 2 внешнего контура.

Оператор 5 сдвигает массив заявок, ожидающих в очереди, на 1 позицию вверх.

Оператор 6 присваивает признаку

-го значение 1. В результате этой операции строка r0, соответствующая освободившемуся, но не занятому каналу (буфер пуст), при очередном просмотре календаря не будет выделена (просматриваются только те строки, для которых cj=0). Если описанную операцию присваивания :=1 не выполнить, то при просмотре календаря та же строка r0 будет выбрана вновь (этой строке соответствует минимальное время наступления события) и процедура реализации модели зациклится. Переход к оператору 6.