Оптимізація систем масового обслуговування: метод вибору оптимального часу обслуговування заявок
Комплекси систем вогневих засобів, радіолокаційного спостереження, зв’язку, обчислювальні центри, АСУ як системи масового обслуговування. Вибір оптимальних параметрів СМО для забезпечення заданого значення обраного показника оцінки ефективності СМО.
| Рубрика | Программирование, компьютеры и кибернетика |
| Вид | статья |
| Язык | украинский |
| Дата добавления | 26.10.2010 |
| Размер файла | 65,8 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Національна академія Державної прикордонної служби України імені Б. Хмельницького
Військовий інститут ракетних військ і артилерії СумДУ
Оптимізація систем масового обслуговування: метод вибору оптимального часу обслуговування заявок
І.С. Катеринчук, канд. техн. наук, доц.;
В.О. Мазуренко, канд. техн. наук, доц.;
М.М. Ляпа, канд. техн. наук
ВСТУП
Широке коло прикладних задач вирішуються методами теорії масового обслуговування. Як системи масового обслуговування (СМО) можуть використовуватися комплекси систем вогневих засобів, системи радіолокаційного спостереження, системи зв'язку, обчислювальні центри, автоматизовані системи управління тощо. У процесі функціонування СМО можуть виникати ситуації, коли канали обслуговування будуть задіяні на повну потужність та все одно не будуть справлятися з вхідним потоком заявок або, навпаки, будуть простоювати в очікуванні заявок на обслуговування. Тому постає питання вибору оптимальних (раціональних) параметрів СМО, які б забезпечили оптимальне значення (задане значення) обраного показника оцінки ефективності (цільової функції) системи обслуговування.
Для СМО, в яких буде стаціонарний режим роботи, виведено аналітичні формули для фінальних ймовірностей станів системи та розрахунку її параметрів [1-6]. Разом з тим теорію оптимізації систем обслуговування розвинуто недостатньо. Авторами [7] запропоновано методику вибору раціональної кількості каналів обслуговування, при якій забезпечується задана ймовірність обслуговування заявок у СМО з відмовою або мінімальна вартість обслуговування.
Основними показниками оптимізації СМО можуть бути: вартість системи, яку необхідно мінімізувати; ймовірність обслуговування заявок (відносна або абсолютна пропускна спроможність), яку необхідно максимізувати; коефіцієнт зайнятості системи, значення якого необхідно спрямувати до 1, або обернений до нього показник - коефіцієнт простою системи, який необхідно мінімізувати.
Необхідно зазначити, що у СМО можуть виникати протиріччя між джерелом заявок (заявками) та параметрами системи. Хоча у покращанні деяких характеристик можуть бути зацікавлені обидві сторони - як клієнти, так і обслуговуючий персонал СМО. Так, обидві сторони зацікавлені у зменшенні довжини черги та часу перебування у ній заявок (зростають витрати часу та ресурсів на утримання заявок у черзі). Протиріччя також виникають при виборі значень показників СМО. Збільшення кількості каналів обслуговування призводить до збільшення вартості СМО. З іншого боку, скорочення терміну обслуговування заявок збільшує пропускну спроможність системи, і разом з тим, це може негативно вплинути на якість обслуговування. Тому система повинна будуватися на основі компромісу.
На значення показників ефективності системи обслуговування впливають інтенсивність вхідного потоку, кількість каналів, тривалість обслуговування заявок, дисципліна обслуговування. Як правило, для СМО розімкнутого типу характеристики вхідних потоків не залежать від організації СМО. Тому покращити якість обслуговування заявок можна за рахунок зміни таких параметрів, як кількість каналів, тривалість обслуговування, дисципліна обслуговування. Конкретна методика вибору цих параметрів залежить від типу СМО та наявних ресурсів. Оскільки варіація кількістю каналів та дисципліною обслуговування заявок для діючих СМО обмежена, то вважається доцільним оптимізацію системи обслуговування здійснювати шляхом вибору оптимального часу обслуговування. Метою даної роботи є розроблення методу вибору оптимального часу обслуговування заявок
Вибір параметрів СМО відносять до обернених задач дослідження операцій, і він полягає у тому, що для відомої залежності показника ефективності W від параметра керування
xi (i=1, …, m):
(1)
шукаються такі значення параметрів, за яких цільова функція (1):
а) набуває заданого значення показника ефективності (раціональні параметри керування);
б) досягає оптимального значення показника ефективності (оптимальні параметри керування).
Оскільки при вирішенні оберненої задачі вибору параметрів СМО не завжди вдається знайти аналітичні залежності показника ефективності системи від параметрів керування, то цю задачу пропонується розв'язувати чисельними методами. Для чого один із параметрів керування змінюється у визначених для нього межах, решта параметрів набувають деяких фіксованих значень; для кожного значення обраного параметра керування шукається значення показника ефективності; аналогічним чином визначаються значення показника ефективності для решти параметрів керування; методом порівняння обираються параметри керування, при яких значення показника ефективності задовольняє вимоги.
У ході оптимізації СМО, головним чином, необхідно прагнути забезпечити високу пропускну спроможність системи - головного показника ефективності. Відносна пропускна спроможність багатоканальних СМО (ймовірність обслуговування чергової заявки) визначається як протилежна подія тому, що у момент приходу чергової заявки усі n каналів буде зайнято обслуговуванням і m заявок стоїть у черзі [8]:
(2)
де
- ймовірність того, що усі n каналів зайнято обслуговуванням;
- ймовірність того, що усі n каналів зайнято обслуговуванням і m заявок стоїть у черзі;
- ймовірність того, що усі n каналів вільні;
- коефіцієнт, що характеризує насиченість системи, якщо >1 (>), то у СМО буде утворюватися черга;
- інтенсивність вхідного потоку заявок;
- інтенсивність обслуговування заявок;
- тривалість обслуговування однієї заявки одним каналом.
Визначити абсолютну пропускну спроможність СМО можна за виразом
. (3)
Із аналізу (2) випливає, що ймовірність обслуговування заявки (пропускна здатність СМО) обернено пропорційна тривалості обслуговування однієї заявки одним каналом. Отже, при виборі параметрів каналів обслуговування необхідно забезпечити мінімальний час обслуговування. З іншого боку, зменшення тривалості обслуговування призводить до зниження якості обслуговування. Середнє значення часу обслуговування однієї заявки одним каналом визначається як середньостатистична величина або встановлюється нормативними документами. Тоді оцінити якість обслуговування заявки протягом часу t можна за формулою
,(4)
де - якість обслуговування заявки протягом часу .
Функція залежності ймовірності обслуговування чергової заявки q(t) із збільшенням часу обслуговування заявки зменшується і наближається до 0. Функція залежності ефективності обслуговування заявки роб(t), навпаки, із збільшенням часу обслуговування заявки збільшується і наближається до 1. Тоді задача пошуку оптимального значення пропускної здатності СМО являє собою задачу багатовимірної оптимізації. Разом з тим розв'язання цієї задачі відомими методами оптимізації функцій n змінних, наприклад [9-11], викликає певні труднощі. Останні пов'язані з тим що, по-перше, важко побудувати аналітичну залежність цільової функції від вихідних даних, по-друге, вихідні дані мають різний фізичний зміст з різною метрикою і можуть бути взаємозалежні тощо. Тому пошук екстремуму пропонується проводити чисельно. Для цього за цільову функцію оптимізації часу обслуговування можна обрати суму ймовірності обслуговування заявки q(t) та якості обслуговування роб(t), значення якої необхідно максимізувати:
.(5)
Проводився також аналіз цільової функції (5) як добутку або різниці її членів q(t) та роб(t). При цьому шукана точка для tопт зміщувалася вправо, що призводило до значного зменшення величини q(t) і незначного покращання значення роб(t).
Після нескладних перетворень остаточно формула (5) для цільової функції перепишеться у вигляді
.(6)
Цільова функція (6) має один максимум, а час, при якому цільова функція набуде максимального значення, необхідно вважати оптимальним часом обслуговування заявки. Для пошуку екстремуму функції скористаємося методом золотого перетину [12], який, порівняно з іншими методами, для розв'язуваної задачі задовольняє вимоги щодо точності та кількості обчислень.
Графіки залежностей ймовірності обслуговування заявки q(t) та ефективності контролю pоб(t) протягом часу t наведено на рис. 1.
Рисунок 1 - Графіки залежності показників ефективності СМО від тривалості обслуговування заявки
ПостаВЛЕННЯ завдання
Для заданих інтенсивності вхідного потоку - л, кількості каналів обслуговування - n, кількості місць у черзі m та середнього значення (нормативного) тривалості обслуговування - ф необхідно знайти час обслуговування одним каналом однієї заявки - tоб, при якому цільова функція набуде максимального значення:
.(7)
Обмеження: початкове значення часу t обслуговування заявки доцільно обрати з тих міркувань, що інтенсивність вхідного потоку заявок повинна перевищувати інтенсивність обслуговування, тобто . Оскільки при менших значення t система простоюватиме, то з метою забезпечення необхідної точності обчислень крок, з яким буде змінюватися значення часу обслуговування заявки, необхідно взяти не меншим Дt=0,001.
Обчислювальний алгоритм розв'язання задачі:
1. Встановлюються початкові умови: початкове значення часу обслуговування заявки , номер циклу оптимізації і=1, початкове значення цільової функції W0=0.
2. Визначається поточне значення часу обслуговування заявки
t=t+Дt
3. Визначається ймовірність того, що усі n каналів СМО вільні:
.
4. Визначається ймовірність того, зайняті усі n каналів зайняті обслуговування і m заявок стоять у черзі:
.
5. Визначається ймовірність того, що чергова заявка буде обслугованою у СМО:
.
6. Визначається ефективність контролю заявки:
.
7. Визначається поточне значення цільової функції:
.
8. Перевіряється умова, чи не вичерпано час, протягом якого моделюється СМО . Якщо умова виконується, то моделювання продовжується, починаючи з п. 2. В іншому випадку виконується п. 9.
9. Визначається коефіцієнт дроблення відрізка [t0, tk]:
.
10. Визначається абсциса
і визначається значення функції W(t1).
11. Визначається абсциса
і визначається значення функції W(t2).
12. Перевіряється виконання умови
,
де Е - задана похибка щодо визначення tопт. Якщо ця умова виконується, то визначаються абсциса
і оптимальне значення цільової функції W(tопт). Розрахунки припиняються. Якщо ця умова не виконується, то пошук екстремуму функції продовжується і виконується п. 13.
13. Перевіряється умова:
.
Якщо умова виконується, то це означає, що
t0=t1 і t1=t2, а W(t1)=W(t2).
Далі виконуються п. 11 та п. 12.
14. Якщо , то це означає, що tk=t2 і t2=t1 а W(t2)=W(t1). Далі виконуються п. 10 і п. 12.
Рисунок 2 - Графіки залежності значення оптимального часу обслуговування заявок tопт від інтенсивності л вхідного потоку та кількості каналів n обслуговування
Якщо у ході розв'язання задачі пошуку оптимального часу обслуговування необхідно надати перевагу одній із величин q(t) або роб(t), то вираз (5) можна подати у вигляді
,(8)
де а1 і а2 - вагові коефіцієнти при ймовірностях q(t) і роб(t) відповідно. Вони можуть бути визначені, наприклад, методом експертних оцінок [13]. Графіки залежності значення оптимального часу обслуговування заявок tопт від інтенсивності л вхідного потоку та кількості каналів n обслуговування наведено на рис. 2.
Таким чином, використання запропонованого методу дозволяє знайти оптимальний час обслуговування заявок при заданих інтенсивності вхідного потоку та кількості каналів обслуговування. Метод можна використовувати як для СМО з відмовою, так і для СМО з очікуванням та обмеженою кількістю місць у черзі, що розширює практичну сферу його застосування.
Наявність графіків (рис. 2) дозволяє розв'язати й обернену задачу: для заданого часу обслуговування заявки визначити оптимальну кількість каналів обслуговування.
SUMMARY
The article deals with the method of choosing the optimal time meaning of clime serving for providing the mass service system necessary ability its quality.
СПИСОК ЛІТЕРАТУРИ
Бусленко Н.П. Моделирование сложных систем. - М.: Наука, 1978. - 400 с.
Вентцель Е.С. Исследование операций. - М.: Воениздат, 1972. - 552 с.
Гнеденко Б.В., Коваленко И.Н. Введение в теорию массового обслуживания. - М.: Наука, 1966. - 431 с.
Иващенко А.В., Сыпченко Р.П. Основы моделирования сложных систем на ЭВМ. - Л.: ЛВВИУС, 1988. - 245 с.
Кузин Л.Т. Основы кибернетики: В 2 т. Т. 2. Основы кибернетических моделей. - М.: Энергия, 1979. - 584 с.
Саати Т.Д. Элементы теории массового обслуживания и ее приложения. - М.: Сов. радио, 1971. - 519 с.
Осинский Л.М. Элементы исследования операций и оценка эффективности сил и средств противовоздушной обороны. - К.: Изд-во КВИРТУ, 1968. - 444 с.
Абчук В.А. и др. Введение в теорию выработки решений. - М.: Воениздат, 1972. - 325 с.
Бакаев А.А., Ермольев Ю.М., Кузнецов Ю.Н., Кузубов В.И. Математические методы в планировании и экономических расчетах. - Киев: Наукова думка, 1968. - 368 с.
Банди Б. Методы оптимизации: Вводный курс. - М.: Радио и связь, 1988. - 128 с.
Сухарев А.Г., Тимохов А.В., Федоров В.В. Курс методов оптимизации. - М.: Наука, 1986. - 328 с.
Краскевич В.Е., Зеленский К.Х., Гречко В.И. Численные методы в инженерных исследованиях. - К.: Вища школа, 1979. - 263 с.
Основы научных исследований: Учебник для технических вузов / В.И. Крутов, И.М. Грушко, В.В. Попов и др.; Под ред. В.И. Крутова. - М.: Высшая школа, 1989. - 400 с.
Подобные документы
Формалізована схема системи масового обслуговування. Обгрунтування вибору UML-діаграм для ілюстрації функціонування системи масового обслуговування. Функційна модель, призначена для відображення основних зв’язків між елементами та компонентами системи.
курсовая работа [343,6 K], добавлен 15.10.2014Задачі масового обслуговування та моделі для імітації виробничої діяльності. Обслуговування та експлуатація матричних та струминних принтерів. Розрахунок надійності вбудованого контролера. Конфігурація офісного комп'ютера для зберігання інформації.
курсовая работа [224,6 K], добавлен 07.03.2011Створення системи експериментального дослідження математичних моделей оптимізації обслуговування складних систем. Визначення критеріїв оптимізації обслуговуваних систем та надання рекомендацій щодо часу проведення попереджувальної профілактики.
дипломная работа [3,0 M], добавлен 22.10.2012Поняття моделювання як процесу, що полягає у відтворенні властивостей тих чи інших предметів і явищ за допомогою абстрактних об’єктів та описів у вигляді зображень, планів, алгоритмів. Системи масового обслуговування. Модель роботи видавничого центру.
курсовая работа [255,8 K], добавлен 15.09.2014Проектування інформаційної підсистеми імітаційного моделювання для системи масового обслуговування відділення банку ПАТ комерційний "Приватбанк". Дослідження теорії черг для аналізу та забезпечення функціонування відділень банків за допомогою мови GPSS.
дипломная работа [5,2 M], добавлен 06.06.2014Вибір моделі задачі інформаційної підтримки сучасних автопаркінгів. Постановка задачі та вибір структур даних. Здійснення замовлень в системі. Перевірка замовлених місць на парковці. Специфікація системи інформаційного обслуговування автопаркінгу.
дипломная работа [2,5 M], добавлен 13.07.2014Моделювання в області системотехніки та системного аналізу. Імітація випадкових величин, використання систем масового обслуговування, дискретних і дискретно-безперервних марковських процесів, імовірнісних автоматів для моделювання складних систем.
методичка [753,5 K], добавлен 24.04.2011Виконання ОС в апаратній віртуальній машині під управлінням системної програми – монітора віртуальних машин, значення технології візуалізації в процесі. Прозоре обслуговування системних викликів, продуктивність. Точка обслуговування системного виклику.
контрольная работа [287,3 K], добавлен 20.05.2010Вплив інформаційних потреб користувачів на організацію інформаційного обслуговування. Бібліотечно-інформаційний сервіс: сучасний стан, можливості вдосконалення. Ресурси Інтернет і трансформація системи інформаційного обслуговування у Сарненській ЦСПШБ.
дипломная работа [57,0 K], добавлен 21.12.2010Принцип роботи СТО. Аналіз існуючих теоретико-практичних розробок по створенню інформаційних систем. Модель аналізу виконання робіт з ремонту й обслуговування на СТО. Розробка автоматизованої системи обробки інформації, опис програмного забезпечення.
дипломная работа [1,3 M], добавлен 11.10.2013
