Алгоритм імітаційного моделювання СМО

На основі приведених вище теоретичних положень магістром Національного транспортного університету М.А. Маляренко під науковим керівництвом д.т.н., проф. Б.М. Четверухіна була розроблена програма IMMODELING для визначення ймовірностей можливих станів СМО та показників ефективності роботи СМО в умовах впливу на неї вхідного потоку заявок, що мають довільний характер розподілу ймовірностей їх надходження в СМО, а також при довільному законі розподілу вихідного потоку обслуговувань в СМО із застосуванням внутрішньої мови системи Microsoft Office 97 VBA на базі програми Excel 97.

Програма Excel 97 як основа моделювання була обрана з тієї причини, що за допомогою її робочих сторінок легко організувати накопичення та обробку однорідної статистичної інформації, якою являються дані про потік вимог, і також в цій системі добре розвинута графічна система: легко будувати різноманітні графіки.

Програма побудована так, що на відповідних робочих аркушах Excel зберігаються вхідні данні, результати обчислень, графіки і форми для введення умов розрахунку і вхідних даних. Програма дозволяє моделювати процес формування інтервалів вхідного потоку випадкових подій, на основі псевдо випадкових величин, які формуються функцією РВП BASIC, роботу СМО по відпрацюванню зовнішніх впливів у вигляді вимог і в результаті отримувати вихідний потік інтервалів між сусідніми обслуженими вимогами. При цьому була передбачена можливість розглядати вимоги як рівноправні, так і пріоритетні. Нижче наведений алгоритм програми IMMODELING.

Основна програма:

1. Початок програми.

2. Об'ява та ініціалізація змінних:

n - кількість каналів

m - кількість місць в черзі

tm - час моделювання

j - поточна позиція на аркуші

kl - кількість зайнятих каналів

k2 - кількість зайнятих місць в черзі

z - кількість відкинутих заявок

ul - інтервал вхідного потоку

u2 - інтервал вихідного потоку

u3 - інтервал пріоритетного потоку

npriority - відношення між пріоритетними заявками і загальною кількістю заявок, %

ti - поточний час

t3 - час пріоритетної заявки

ty - сумарний час обслуговування

kу - кількість прийнятих заявок

chanals(10,2) - масив для обчислення роботи кантів

turn(100,3) - масив для обчислення роботи черги

vTime - масив для реєстрування зайнятості каналів

vTimel - масив індикатор останнього зайнятого каналу

vTt - масив для реєстрування зайнятості черги

vTtl - масив індикатор останнього зайнятого місця в черзі

змінні для формування потоків Гауса:

fGaussl, fGauss2

vGaussinl, vGaussin2 - вхідний потік

vGaussoutl, vGaussout2 - вихідний потік

3. Підготовка робочого аркуша.

3.1Очищення робочого аркуша

3.2Заповнення текстової інформації (шапка таблиці результатів).

3.3Зчитування вихідних даних з аркуша "Вихідні дані"

4. Ініціалізація масивів для організації роботи каналів

5. Ініціалізація масивів для організації роботи черги

6. Отримання першої заявки

7. Занесення часу виконання заявки в перший канал

8. Реєстрація зайнятого каналу

9. Виклик процедури сортування каналу по часу виконання (нагорі в масиві знаходиться інтервал часу, який має найменше значення виконання або дорівнює нулю)

10.Занесення в поточний лічильник часу надходження заявки

11.Цикл по часу моделювання. Якщо цикл закінчився то п.25.

12.Отримання наступної заявки. (виклик підпрограми "Моделювання вхідного потоку")

12.1 Реєстрація на робочому аркуші в колонці 1 і 2

13.Перевірка: заявка пріоритетна чи ні.

14.Якщо заявка пріоритетна то п. 15, якщо ні п. 19

15.Перевірка стану системи

16.Канал вільний

16.1Заявка надходить в канал (виклик підпрограми "Моделювання вихідного потоку").

16.2Реєстрація зайнятості каналу

16.3 Сортування каналу по часу виконання

16.4 Перехід на п.11

17. Канали зайняті. Вільна черга.

17.1 Поставити в чергу з зсувом на перше місце

17.2 Зареєструвати час зайнятості черги

17.3 Перехід на п.11

18. Черга зайнята

18.1 Звільнити перше місце в черзі

18.2Перехід на п. 11

19.Перевірка зайнятості каналів (якщо час обслуговування скінчився, то канал звільняється) (Виклик підпрограми "Перевірка зайнятості каналів")

20.Якщо в черзі є заявка, то вона переноситься в канал (Виклик підпрограми " Перенесення заявки з черги в канал")

21.Перевірка стану системи

22.Є вільні канали

22.1 Наступна заявка з вхідного потоку надходить в канал 22.2Реєстрація зайнятості каналу.

22.3 Сортування каналів (виклик підпрограми "Сортування каналів")

22.4Перехід на п.11

23. Є місце в черзі

23.1 Поставити заявку в чергу з поточним часом

23.2 Сортування черги (виклик підпрограми "Сортування черги ")

23.3 Реєстрація зайнятості черги

23.4 Перехід на п. 11

24. В черзі немає місця. Відкинути заявку. Перехід на п. 11

25. Розрахунок параметрів вхідного потоку (обробка 1 і 2 колонок робочого аркуша)

25.1 Розрахунок середнього інтервалу (математичне очікування)

вхідного потоку

25.2 Розрахунок середньоквадратичного відхилення

26. Розрахунок теоретичних значень параметрів вхідного потоку в залежності від типів вхідного потоку

27. Розрахунок середнього часу перебування в черзі

28.Розрахунок середньоквадратичного відхилення часу очікування в черзі

29. Розрахунок середньої довжини черги.

30. Вивід результатів моделювання на аркуш "Результати":

- Час моделювання

- Прийняті до обслуговування заявки

- Середній час обслуговування заявок

- Середній час знаходження заявки в системі

- Дисперсія часу знаходження заявки в системі

- Середній час очікування на обслуговування

- Дисперсія часу очікування на обслуговування

- Середня довжина черги

- Імовірність відмови

- Середня кількість зайнятих каналів Показники стану системи:

- Час зайнятості 0 каналів (всі канали вільні)

- Час зайнятості 1 каналу

- Час зайнятості 2-х каналів

- Час зайнятості п каналів

- Імовірність зайнятості 0 каналів

- Імовірність зайнятості 1 каналу

- Імовірність зайнятості 2-х каналів

- Імовірність зайнятості п каналів

- Час зайнятості 0 місць в черзі (черга вільна)

- Час зайнятості 1 місця в черзі

- Час зайнятості 2-х місць в черзі

- Час зайнятості m місць в черзі

- Імовірність зайнятості 0 місць в черзі (черга вільна)

- Імовірність зайнятості 1 місця в черзі

- Імовірність зайнятості 2-х місць в черзі

- Імовірність зайнятості m місць в черзі Таблиця даних по вхідному потоку:

- інтервали часу появи заявок

- частота потраплянь інтервалів часу появи заявок в ці інтервали часу

Таблиця даних по вихідному потоку:

- інтервали часу появи заявок

- частота попадань інтервалів часу появи заявок в ці інтервали часу

31. Розрахунок діаграм вхідного потоку (Діаграма № 1)

31.1 Пошук максимуму та мінімуму серед інтервалів

31.2 Розбиття інтервалів між максимумом та мінімумом на 10 частин

31.3 Цикл по вхідному потоку доки не закінчаться заявки. Якщо кінець то п. 31.7

31.4 Перевірка інтервалів заявки на номер інтервалу

31.5 Додавання одиниці до відповідного стовпчика діаграми

31.6 Перехід на п. 31.3

31.7 Занесення на аркуш "Результати" таблиці з розмірами інтервалу і кількістю потраплянь в ці інтервали.

31.8 Побудова діаграми (виклик підпрограми "Побудова діаграми №1")

32. Розрахунок діаграм вихідного потоку (діаграма №2)

32.1 Пошук максимуму та мінімуму серед інтервалів

32.2 Розбиття інтервалів між максимумом та мінімумом на 10 частин

32.3 Цикл по вхідному потоку доки не закінчаться заявки. Якщо кінець то п. 32.7

32.4 Перевірка інтервалів заявки на номер інтервалу

32.5 Додавання одиниці до відповідного стовпчика діаграми

32.6 Перехід на п. 32.3

32.7 3анесення на аркуш "Результати" таблиці з розмірами інтервалу і кількістю потраплянь в ці інтервали.

32.8 Побудова гістограми (виклик підпрограми "Побудова діаграми №2")

33. Кінець

Підпрограма "Моделювання вхідного потоку"

1. Початок

2. Вибір типу вхідного потоку:

(1) Гаус

(2) Експоненціальний (Пуассон)

(3) Ерланг

(4) Рівномірний

3. Якщо(1), то формуємо вхідний потік:

3.1 формуємо оператором RND 2 випадкові величини (ksil, ksi2).

3.2 отримуємо 2 випадкові величини(Vgaussin1, Vgaussin2) за формулою

3.3 Перевірка: яке звернення до функції (п.3.2). Якщо непарне, то йде запит двох випадкових величин п.3.2 - Vgaussinl, Vgaussin2 і видати на виході 1-е (Vgaussinl). Якщо парне, то видати 2-ге - Vgaussin2 і встановити ознаку, що наступне значення буде непарне.

4. Якщо (2), то формуємо вхідний потік випадкових чисел за розподілом Пуассона за формулою:

Vexp=-(1/lambda)*Log(l- RND())

5. Якщо (3), то формуємо вхідний потік випадкових чисел за розподілом Ерланга:

(Програма дозволяє обирати варіант формули - за проф. Соболем А. М. або за проф. Четверухіним Б.М.)

Формування потоку за методикою проф. Соболя A.M.:

5.1 Цикл від 1 до nsito (nsito- параметр Ерланга). Якщо кінець циклу, то п.5.5

5.2 Формування випадкових величин (vrand) за допомогою оператора RND

5.3Розрахунок добутку випадкових величин, які були сформовані в п.5.2

5.4Повернення до п.5.1

5.5 Формування інтервалів випадкових подій за формулою:

vErlang=-(1 /(Lambda*nsito))*Log(vrand)

Формування потоку за методикою проф. Четверухіна Б.М.:

5.6 Цикл від 1 до nsito (nsito- параметр Ерланга). Якщо кінець циклу, то п.5.9

5.7 Формування випадкових величин (vrand) за допомогою
оператора RND за формулою:

vrand=Log(l-RND())

5.8Повернення до п.5.6

5.9Формування інтервалів випадкових подій за формулою:

vv=-((l/(Lambda*nsito)))*vrand)/SQR(nsito) vErlang=(vv+l/(2*Lambda*nsito))*nsito)

5.Якщо (4), то формуємо вхідний потік випадкових чисел за рівномірним розподілом за формулою:

uniform=RND()*(B-A)+A

7. Кінець

Підпрограма "Моделювання вихідного потоку"

1. Початок

2. Вибір типу вихідного потоку:

(1)Гаус

(2) Експоненціальний (Пуассон)

(3)Ерланг

(4) Рівномірний

3. Якщо (1), то формуємо вихідний потік:

3.1 формуємо оператором RND 2 випадкові величини (ksi1, ksi2).

3.2 отримуємо 2 випадкові величини(Vgaussin1, Vgaussin2) за формулою

3.3 Перевірка: яке звернення до функції (п.3.2). Якщо непарне, то йде запит двох випадкових величин п.3.2 - Vgaussinl, Vgaussin2 і видати на виході 1-е (Vgaussinl). Якщо парне, то видати 2-ге - Vgaussin2 і встановити ознаку, що наступне значення буде непарне.

4. Якщо (2), то формуємо вихідний потік випадкових чисел за розподілом Пуассона за формулою:

Vexp=-(1/lambda)*Log(l- RND())

5. Якщо (3), то формуємо вихідний потік випадкових чисел за розподілом Ерланга за формулою:

(Програма дозволяє обирати варіант формули - за проф. Соболем А. М. та за проф. Четверухіним Б.М.)

за проф. Соболем A.M.:

5.1 Цикл від 1 до nsito (nsito- параметр Ерланга). Якщо кінець циклу, то п.5.5

5.2 Формування випадкових величин (vrand) за допомогою оператора RND

5.3 Розрахунок добутку випадкових величин які були сформовані в п.5.2

5.4Повернення до п.5.1

5.5Формування інтервалів випадкових подій за формулою:

vErlang=-(l/(Lambda*nsito))*Log(vrand)

за проф. Четверухіним Б.М.

5.6 Цикл від 1 до nsito (nsito- параметр Ерланга). Якщо кінець циклу, то п.5.9

5.7 Формування випадкових величин (vrand) за допомогою оператора RND за формулою:

vrand=Log(l-RND())

5.8Повернення до п.5.6

5.9Формування інтервалів випадкових подій за формулою:

vv=-((l/(Lambda*nsito)))*vrand)/SQR(nsito) vErlang=(vv+l/(2*Lambda*nsito))*nsito)

6. Якщо (4), то формуємо вихідний потік випадкових чисел за рівномірним розподілом за формулою:

uniform=RND()*(B-A)+A

7. Кінець

Підпрограма "Сортування каналів"

1. Початок

2. Цикл з кінця масиву мінус 1.(і - змінна циклу). Якщо кінець циклу - перехід на п.7

3. цикл від 1 до і. Якщо кінець циклу перехід на п.6

4. якщо поточний час більше наступного часу то міняємо місцями ' в обох стовпчиках масиву.

5. перехід на п.3

6. перехід на п.2

7. кінець.

Підпрограма " Сортування черги"

1. Початок

2. цикл з кінця масиву мінус 1. (і1 - змінна масиву). Якщо кінець то перехід на п.7

3. цикл від 1 до і 1. Якщо кінець, то перехід на п.6

4. Якщо поточний час більше наступного часу то змінюємо місцями в обох місцях масиву

5. перехід на п.3

6. перехід на п.2

7. Кінець.

Підпрограма "Перевірка зайнятості каналів"

1. Початок

2. Цикл від 1 до п (п - кількість каналів). Якщо кінець, то перехід на п.6

3. якщо канал зайнятий і час звільнення каналу дорівнює поточному, то його потрібно звільнити і звернутися до функції реєстрації, що канал звільнився

4. зареєструвати час звільнення каналу.

5. перехід на п.2

6. кінець

Підпрограма "Перенесення заявки з черги в канал"

1. Початок

2. цикл по черзі від 1 до m (m - кількість місць в черзі). Якщо кінець циклу то п.6

3. якщо час постановки в чергу не дорівнює 0 то п.4, якщо дорівнює 0 то нічого

4. визначити скільки часу буде обслужуватись заявка і переноситься в канал

5. перехід на п.2

6. кінець.

Підпрограма " Побудова діаграми №1 розподілу часових інтервалів вхідного потоку"

1. початок

2. перевірка наявності аркуша "Діаграма №1". Якщо є, то знищуємо.

3. Створюємо діаграму №1. Розміщення на новому аркуші. (Будується по значенням аркушу "Результати" по таблиці вхідного потоку)

4. Задаємо властивості діаграми:

4.1 Без легенди

4.2Має заголовок, який має назву "Вхідний потік"

4.3Розмір шрифту 12

4.4Шрифт "Sans serif'"

4.5Діаграма має вісь значень(Ох) і вісь результатів(Оу)

4.6Має допоміжні лінії сітки

4.7Вісь Ох має назву "Інтервали часу"

4.8Розмір шрифту 12

4.9Шрифт "Sans serif

4.10 Вісь Оу має назву "Частота потраплянь"

4.11 Розмір шрифту 12

4.12Шрифт "Sans serif

5. Кінець.

Підпрограма " Побудова діаграми №2 розподілу часових інтервалів вихідного потоку"

1. початок

2. перевірка наявності аркуша "Діаграма №2". Якщо є, то знищуємо.

3. Створюємо діаграму №2. Розміщення на новому аркуші. (Будується по значенням аркушу "Результати" по таблиці вихідного потоку)

4. Задаємо властивості діаграми:

a. Без легенди

b. Має заголовок, який має назву "Вхідний потік"

c. Розмір шрифту 12

d. Шрифт "Sans serif

є. Діаграма має вісь значень(Ох) і вісь результатів(Оу)

f. Має допоміжні лінії сітки

g. Вісь Ох має назву "Інтервали часу"

h. Розмір шрифту 12

і. Шрифт "Sans serif

j. Вісь Оу має назву "Частота потраплянь"

к. Розмір шрифту 12

1. Шрифт "Sans serif

5. Кінець

Лістинг програми, що реалізує вище зазначений алгоритм імітаційного моделювання систем масового обслуговування з урахуванням пріоритетності обслуговування певних заявок, наведено у додатку 1. Ця програма розроблена магістром Маляренко М.А. під науковим керівництвом проф. Б.М.Четверухіна.

Дата добавления: 2014-12-29