автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.18, диссертация на тему:Характеристики многоканальных систем селективного массового обслуживания с поликомпонентным входным потоком заявок

На правах рукописи

ВАЛЕЕВ ИЛЬДАР НАИЛЕВИЧ

ХАРАКТЕРИСТИКИ МНОГОКАНАЛЬНЫХ СИСТЕМ СЕЛЕКТИВНОГО МАССОВОГО ОБСЛУЖИВАНИЯ С ПОЛИКОМПОНЕНТНЫМ ВХОДНЫМ ПОТОКОМ ЗАЯВОК

05.13.18 - Математическое моделирование, численные методы и комплексы программ

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

1 о ноя 2011

Казань-2011

4859204

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

Научный руководитель: доктор физико-математических наук, профессор

Кирпичников Александр Петрович

Официальные оппоненты: доктор технических наук, профессор

Емалетдинова Лилия Юнеровна

доктор технических наук, профессор Фафурин Виктор Андреевич

Ведущая организация: Марийский Государственный

технический университет, г. Йошкар-Ола

Защита состоится «2» декабря 2011 г. в 14 час. 00 мин. на заседании диссертационного совета Д 212.080.13 при ФГБОУ ВПО «КНИТУ» по адресу: 420015, г. Казань, ул. Карла Маркса, 68, в зале заседаний Ученого совета (А-ЗЗО).

Отзыв на автореферат в двух экземплярах, заверенный гербовой печатью, просим направлять по адресу: 420015, г. Казань, ул. К. Маркса, д. 68, ФГБОУ ВПО «КНИТУ», ученому секретарю диссертационного совета Д 212.080.13.

С диссертацией можно ознакомиться в фундаментальной библиотеке Казанского национального исследовательского технологического университета.

Автореферат разослан «215» октября 2011 г.

Ученый секретарь диссертационного совета доктор технических наук,

профессор

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы. Задачи, связанные с обслуживанием потоков требований случайного характера были актуальны всегда, однако в простейших случаях решались без применения каких-либо научных методов. С момента возникновения данных проблем в технических системах, в частности, в телефонии, к ним стал применяться научный подход, основанный на применении математического аппарата теории вероятностей. Обзор научных трудов последних лет показывает, что работы ученых в данной области направлены на решение задач в сфере телекоммуникационных систем. Однако, в последнее время, в связи с развитием рынка в России появляется большое количество различных товаров и услуг, и подобные проблемы все чаще возникают в сфере торговли и обслуживания населения.

Как научный, так и практический интерес имеют системы обслуживания, содержащие группы обслуживающих устройств одинаковой производительности, осуществляющие селекцию входного поликомпонентного потока по типу заявок. Также в подобных системах имеют место ожидания и потери заявок. В этой связи данная работа была посвящена изучению подобных систем массового обслуживания (СМО).

Несмотря на появление программных средств имитационного моделирования случайных процессов на ЭВМ, аналитическое исследование СМО остается актуальным, поскольку только аналитическое решение обладает общностью результата и позволяет предсказать характер поведения системы при любых изменениях параметров модели. Сложность аналитических методов не позволяет решать с их помощью любые задачи массового обслуживания, однако, круг задач, решаемых аналитически, весьма широк. Для решения практических задач достаточно рассмотреть системы весьма общей структуры в квазистационарном режиме функционирования.

Цель работы: разработка методов исследования открытых многоканальных систем селективного массового обслуживания с поликомпонентным входным потоком заявок.

Задачи:

■S математическое моделирование данного типа систем, вывод и анализ вероятностных, числовых и временных характеристика моделей;

S разработка численных алгоритмов и методов организации обслуживания предложенных СМО;

S создание комплекса программ имитационного моделирования для проведения вычислительного эксперимента.

Методом исследования является математическое моделирование с применением математического аппарата теории вероятностей, теории случайных процессов, включая аппарат непрерывных цепей Маркова. Имитационное моделирование СМО данного типа осуществлялось методом Монте-Карло с применением пакета прикладных программ GPSS World.

Достоверность научных результатов обеспечивается математической строгостью выполнения выкладок и корректностью постановок задач, а также хорошим совпадением полученных решений с результатами имитационного моделирования и с известными частными решениями других авторов. В работе примене-

ны строгие математические методы, в том числе методы теории вероятностей, теории случайных процессов и непрерывных цепей Маркова, методы имитационного моделирования, а также методы численного решения систем алгебраических уравнений.

Научная новизна. Предложена новая структура обслуживающих устройств. Особенность дайной структуры состоит в том, что имеются две группы обслуживающих устройств одинаковой производительности, а входной поток требований состоит из заявок разных типов: одни обслуживаются при любых обстоятельствах, независимо от наличия свободных мест и количества заявок, ожидающих обслуживания в очереди, другие - обслуживаются только при наличии свободного обслуживающего устройства и никогда не становятся в очередь; при этом заявки первого типа могут обслуживаться обеими группами обслуживающих устройств, а заявки второго типа - только одной. Вследствие этого, данные модели предложено называть системами селективного массового обслуживания, а поток заявок - поликомпонентным. Впервые изучены СМО, имеющие подобную структуру обслуживающих устройств и поликомпонентный входной поток заявок, как в стационарном, так и в нестационарном режимах работы. Сформулирована и решена задача определения количества обслуживающих устройств в каждой группе, необходимого для получения желаемой производительности.

Практическая значимость результатов диссертационной работы состоит в том, что приведенные результаты могут быть полезны при проектировании, объектов, работающих по принципу систем массового обслуживания, и применены в торговой отрасли, транспортных системах, на производстве, в телекоммуникациях и многих других областях. Подобные математические модели, во-первых, позволяют оценить производительность проектируемой системы при известной ее структуре, во-вторых, дают возможность разработать необходимую архитектуру СМО на этапе проектирования с целью получения требуемой производительности.

Апробация. Основные результаты диссертационной работы докладывались и обсуждались на: XX Международной научной конференции «Математические методы в технике и технологиях ММТТ-20» (г. Ярославль, 2007); VIII Всероссийском симпозиуме по прикладной и промышленной математике (г. Москва, 2007); XIX всероссийской научно-технической конференции «Современные проблемы математики и естествознания» (г. Нижний Новгород, 2007); VI Всероссийской научно-практической конференции студентов, аспирантов и молодых ученых «Молодежь и современные информационные технологии» (г. Томск, 2008); V Международной научно-практической конференции «Исследование, разработка и применение высоких технологий в промышленности» (г. Санкт-Петербург, 2008); XXII Международной научной конференции «Математические методы в технике и технологиях ММТТ-22» (г. Псков, 2009).

Публикации. По теме диссертации опубликовано 8 научных работ, включая 3 статьи в журналах, рекомендованных ВАК, и 5 тезисов докладов.

Структура и объем диссертационной работы. Диссертация состоит из введения, четырех глав, заключения и библиографического списка использован-

ной литературы. Работа изложена на 119 страницах, иллюстративный материал представлен в виде 40 рисунков, библиография включает 96 наименований.

ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫ

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

В главе 1 даны исторические сведения из теории массового обслуживания, составлена классификация систем и показаны три изученные модели массового обслуживания - Модель Эрланга, многоканальная модель и модель Коэна, представлены основные характеристики данных моделей.

В завершении данной главы перечислены преимущества и недостатки данных СМО, на основании которых были сделаны выводы о необходимости разработки и исследования селективных СМО с поликомпонентным потоком заявок.

В главе 2 приводится модель селективного обслуживания с двухкомпо-нентным потоком заявок.

Данная модель базируется на комбинированной модели, но в нее вносится усовершенствование: отличие данной модели от модели Коэна состоит в том, что в данной модели имеется два типа обслуживающих устройств - т\ и т2. При этом имеются два потока заявок:

- 1-й тип - заявки, которые обслуживаются при любых обстоятельствах, независимо от наличия свободных обслуживающих устройств и количества заявок, ожидающих обслуживания в очереди. При чем заявки первого типа могут обслуживаться как устройствами группы ту, так и т2\

- 2-й тип - заявки, которые обслуживаются только при наличии свободного обслуживающего устройства и никогда не становятся в очередь, при этом заявки данного типа обслуживаются только устройствами группы т\. В случае, если на момент поступления в систему очередной подобной заявки в системе не оказывается свободного обслуживающего устройства группы ти данная заявка покидает систему необслуженной.

Х,+Х2 и ^ м

(m,+l)

Рис. 1. Граф состояний модели селективного обслуживания с двухкомпонентным потоком заявок

Pi =

К

л,

Рг=~ Р = — = М V

Л л,+л2

= Р\ +Рг

(1)

И М п И X, - интенсивность входного потока ц - средняя интенсивность обслуживания заявок одним обслуживающим устройством, р, - приведённая интенсивность соответствующего потоков заявок.

Вероятностные характеристики модели

Общая формула для вероятностей состояний примет следующий вид:

i i i-mv

р'рГ"

/и,;-

т2 "'2 тг '■

Po,»i2 <í

/! ' " " Л

Вероятность простоя системы выражается следующей формулой:

(т2-\}.{т2 -р2)

Все графики данной главы приведены в сравнении с графиками комбинированной модели Коэна.

Ро'

(р)+рщ к (л;»,+!)- Р27'щ El (Р2; «2 + 1)]н

(3)

Рис. 2. Зависимость вероятности простоя от приведенной интенсивности входного потока р2: 1 - МК, р, = 0,5; 2 - М2, pi = 0,5; 3 - МК, р, = 2; 4 - М2, р, = 2 Вероятность простоя для модели селективного обслуживания с двухкомпо-нентным потоком заявок имеет характер, качественно схожий с комбинированной моделью и при приближении к точке с абсциссой рг = тг асимптотически стремится к нулю. Максимальное значение наблюдается при нулевой нагрузке со стороны входного потока, по мере увеличения нагрузки со стороны входного начальное значение р0 уменьшается.

•о

Е,(2,и)=У\—г-\ ~ функция Миттаг-Леффлера первого порядка (обобщение

;=о Г(ц + г)

показателей функции ехр г);

(я), = а{а + 1)(д + 2).. .(а + i -1) - символ Похгаммера; Г(пМп-1У,(а)гГ(а + 1)/Г(а)

Вероятность отказа и вероятность ожидания показаны на следующих формулах:

л Г , „'"2-ml „

(4)

=А Рт л

- Р0 +1)- РГ- ЕАкщ +1)]+

Рис. 3. Зависимость вероятности отказа от приведенной интенсивности входного потока р2: 1 - МК, р, = 0,5; 2 - М2, р, = 0,5; 3 - МК, р, = 2; 4 - М2, р, = 2 Вероятность отказа имеет возрастающий характер. С введением групп селективных устройств значение вероятности ртх увеличивается поскольку для «нетерпеливых» заявок группа устройств, обслуживающих эти заявки сужается. В точке с абсциссой р2 = т2 структура обслуживающих устройств не влияет на вероятность отказа.

2 Г.Щ „"г-Щ

_Л2__Р_Р2_ „ /С*

Л (»,-!)(»,-А)Л ()

Рис. 4. Зависимость вероятности ожидания от приведенной интенсивности входного потока р2: 1 - МК, р, = 0,5; 2 - М2, р! = 0,5; 3 - МК, р, = 2; 4 - М2, р) = 2

Вероятность ожидания имеет монотонно возрастающий характер. Структура обслуживающих устройств слабо влияет на характер поведения вероятности ожидания, а в точке с абсциссой р2=т2и вовсе перестает оказывать влияние.

Числовые характеристики модели

Среднее число требований, находящихся под обслуживанием (среднее число занятых каналов):

п = рр0е„, -г(р) + ~Гт2 Рожнд + Р°" Ро (РгР?~*1Е х{рг I тг)) (6)

2

Рис. 5. Зависимость числа занятых каналов от приведенной интенсивности входного потока р2: 1-МК, р, = 0,5;2-М2, р, =0,5; 3-МК, р, = 2; 4 - М2, р, = 2 Среднее число требований имеет возрастающий характер поведения, близкий к линейному. По мере увеличения нагрузки со стороны входного потока начальное значение п увеличивается, в точке с абсциссой р2=Щ п = т2. Среднее число требований в очереди (средняя длина очереди).

I — РьжаРт- (7)

К{т2-Рг)

Рис. 6. Зависимость средней длины очереди от приведенной интенсивности входного потока р2:1 - МК, р! = 0,5; 2 - М2, р, = 0,5; 3 - МК, р, = 2; 4 - М2, р, = 2 Средняя длина очереди имеет монотонно возрастающий характер, резкое возрастание наблюдается в окрестности точки р, = т. Такое бесконечное возрастание объясняется переполнением очереди при приближении приведенной интенсивности р, к значению т.

Проанализировав рисунки 5-6, видно, что в числовых характеристиках между двумя данными моделями различия практически не заметны.

Временные характеристики модели

Время ожидания имеет следующий вид:

Рохт

(В)

Ьжид

12 10

гп1=3 т2=5

Р2

Рис. 7. Зависимость времени ожидания от приведенной интенсивности входного потока р2: 1 -МК, р, = 0,5; 2 -М2, р, = 0,5; 3 - МК, р, = 2; 4 -М2, р, = 2

Время ожидания имеет монотонно возрастающий характер, резкое возрастание наблюдается в окрестности точки с абсциссой р2=т. Такое бесконечное возрастание объясняется переполнением очереди при приближении приведенной интенсивности р2 к значению т .

В главе 3 приводится модель селективного обслуживания с трехкомпо-нентным потоком заявок.

Отличие данной модели от предыдущей состоит в том, что в данной модели, так же, как и в предыдущей имеется две группы обслуживающих устройств - т\ и т2, но добавляется еще один поток заявок:

- 1-й тип - заявки, которые обслуживаются при любых обстоятельствах, независимо от наличия свободных обслуживающих устройств и количества заявок, ожидающих обслуживания в очереди. При чем заявки первого типа могут обслуживаться как устройствами группы т\, так и т2;

- 2-й тип - заявки, которые обслуживаются только при наличии свободного обслуживающего устройства и никогда не становятся в очередь, при этом заявки данного типа обслуживаются устройствами как группы ти так и группы тг. В случае, если на момент поступления в систему очередной подобной заявки в системе не оказывается свободного обслуживающего устройства любой группы, данная заявка покидает систему необслуженной;

- 3-й тип - заявки, которые обслуживаются только при наличии свободного обслуживающего устройства и никогда не становятся в очередь, при этом заявки данного типа обслуживаются только устройствами группы т\. В случае, если на момент поступления в систему очередной подобной заявки в системе не оказывается свободного обслуживающего устройства группы ти данная заявка покидает систему необслуженной;

Л =

Рис. 8. Граф состояний модели селективного обслуживания с трехкомпонентным потоком заявок А| _ _Аз___,

р2= — Рз = —. р = р, + р2 + р3

ц ц ц ц ц

Вероятностные характеристики модели

Общая формула для вероятностей состояний примет следующий вид:

—р0,т1<1^т2;- 3 рй,тг<х (10)

Д = р2+р,( 9)

«Г

Вероятность простоя системы выражается следующей формулой:

Ро =

[1 о"'1 К1"2'1"' +1)- П^ЕАЪ т2 +1)]+ ( _ ^

(И)

На графиках данной главы показаны характеристики моделей селективного обслуживания с двухкомпонентным и трехкомпонентным потоками заявок.

Рис. 9. Зависимость вероятности простоя от приведенной интенсивности входного потока р3: 1 - М2, Р! = 0,5; 2 - МЗ, р, = 0,5; 3 - М2, р, = 2; 4 - МЗ, р1 = 2 Вероятность простоя имеет характер, качественно схожий с моделью селективного обслуживания с двухкомпонентным потоком заявок, и при приближении к точке с абсциссой р3 = тг асимптотически стремится к нулю. При добавлении во входной поток дополнительной компоненты начальное значение ро существенно уменьшается.

Вероятность отказа и вероятность ожидания показаны на следующих формулах:

Рис. 10. Зависимость вероятности отказа от приведенной интенсивности входного потока р3: 1 - М2, р, = 0,5; 2 - МЗ, р( = 0,5; 3 -М2, Р! = 2; 4 - МЗ, Р1 = 2 С введением нового типа «нетерпеливых» заявок значение вероятности рот, увеличивается.

Р

Р оясид

Л (/;г2-1)!(м2-Рз)

Ро

(13)

Рис. 11. Зависимость вероятности ожидания от приведенной интенсивности входного потока р3: 1 - М2, Р1 = 0,5; 2 - МЗ, р, = 0,5; 3 - М2, р, = 2; 4 - МЗ, р, = 2 Анализ рисунков 9-11 показывает, что вероятностные характеристики данной модели имеют следующие закономерности: вероятность простоя системы уменьшается, также как и вероятность ожидания, а вероятность отказа увеличивается. Это можно объяснить тем фактором, что в данной модели уменьшилось количество общедоступных обслуживающих приборов.

-И-

Числовые характеристики модели

Среднее число требований, находящихся под обслуживанием (среднее число занятых каналов):

» = РР»ещЛр)+Тт1р— + (14)

Рис. 12. Зависимость числа занятых каналов от приведенной интенсивности входного потока р3: 1 - М2, р, = 0,5; 2 - МЗ, р! = 0,5; 3 - М2, р! = 2; 4 - МЗ, р, = 2 Среднее число требований в очереди (средняя длина очереди).

/=— р°***р\ (15)

Л, К-р3)

| ш1»3 гп2=5

Рис. 13. Зависимость средней длины очереди от приведенной интенсивности входного потока рз: 1 - М2, р! = 0,5; 2 - МЗ, = 0,5; 3 - М2, р1 = 2; 4 — МЗ, р1 = 2 Проанализировав рисунки 12-13, следует отметить, что принципиального отличия между двумя моделями селективного обслуживания по числовым характеристикам не наблюдается.

Временные характеристики модели Время ожидания имеет следующий вид:

- -Рожлд-

Ьжид т1=3 гч2=5

10 1

.А

4

I

Р'

2 3 А

Рис. 14. Зависимость времени ожидания от приведенной интенсивности входного потока р3:1 - М2, р, = 0,5; 2 - МЗ, р! = 0,5; 3 - М2, р, = 2; 4 -МЗ, р, = 2

В главе 4 представлена методика организации обслуживания в моделях селективного обслуживания и исследован нестационарный режим функционирования данных СМО.

В изученных моделях имеется различные группы устройств и поток требований, состоящий из заявок разных типов, в том числе и «нетерпеливых». Требуется организовать процесс обслуживания данных моделей таким образом, чтобы из всех поступающих в систему заявок доля обслуженных заявок «нетерпеливого» типа составила не менее определенного значения.

Для модели селективного обслуживания с трехкомпонентным потоком заявок данная задача и путь ее решения будет выглядеть следующим образом.

Суть данной методики заключается в том, чтобы по известным в качестве исходных данных интенсивностям входных потоков заявок всех типов и заданным требованиям к производительности СМО по каждому типу заявок рассчитать необходимое число обслуживающих устройств. Для этого относительная пропускная способность СМО представлена в виде нескольких слагаемых (в зависимости от конкретных моделей), каждое из которых представляет собой количество

обслуженных заявок определенного типа.

Поскольку заявки 1-го типа обслуживаются при любых обстоятельствах (д1 = 1), то задать требуемую производительность можно только для заявок 2-го и 3-го типов (в относительных единицах).

Чг

1 —

Ч\ =

{т2-\)\{т2-р3) _

^ л» +1) - ^ + О]+Г» -

рЪВЪ-Ъръ

,(17)

Так как правые части уравнений являются функциями от т} и т2, решение системы в той или иной форме относительно данных переменных даст значения числа обслуживающих устройств, удовлетворяющие заданным требованиям.

Следует отметить, что значения тп\ и тпг должны быть натуральными, поэтому возможно лишь приближенное решение данной системы уравнений. Ближайшим целочисленным решением, максимально удовлетворяющим поставленным требованиям, является то, при котором невязки между правой и левой частями уравнений будут минимальными. В зависимости от задаваемых пропускной способности и производительности искомое решение определяется либо как сумма абсолютных значений невязок, либо как сумма их квадратов. При этом, значения гп\ и «2 будут приемлемы если процент обслуженных заявок первого и второго типов будет более 50.

Методику решения данной задачи можно представить в виде блок-схемы,

Также в данной главе приводятся программы, по которым осуществляется имитационное моделирование моделей селективного обслуживания с отказами и очередью в системе GPSS World.

Результаты численных экспериментов, в рамках которых исследован нестационарный режим функционирования данных систем, показаны на рис. 16-17.

3,2 3 п, 1, to*

гь

24

2

1,6

1.2

0,8 г

0.* 1

О С 2SCCCO 50ССС0 75СОС0 10000»

Рис. 16. Зависимость п, /, (ож от времени для модели селективного обслуживания с двухкомпонентным потоком заявок: 1 - (ож; 2-1; 3 - п.

7' 3 п, (, 1ож

б Г'

5

4

3

2 2

1 1

0-1 20) 400 600 BOO 1000 *

Рис. 17. Зависимость п, I, tox от времени для модели селективного обслуживания с трехкомпонентным потоком заявок: 1 - t0JIC; 2-1; 3 - п.

Выявлено, что квазистационарный режим для моделей селективного обслуживания с двухкомпонентным и трехкомпонентным потоками заявок устанавливается приблизительно за 100000 и 1000 единиц модельного времени соответственно, равных среднему времени обслуживания заявки одним обслуживающим устройством. Данное различие связано с введением в поток нового типа заявок.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

1. Разработаны новые модели систем селективного массового обслуживания. Проведена математическая формализация моделей данных СМО, получены общие формулы для вероятностных, числовых и временных характеристик подобных систем.

2. Предложена новая структура обслуживающей системы в виде двух различных групп обслуживающих устройств.

3. Исследованы вероятностные, числовые и временные характеристики стационарного и нестационарного режимов в моделях селективного обслуживания с поликомпонентным потоком заявок, построены их графические зависимости с применением полученных математических моделей и численного эксперимента. Выявлено, что квазистационарный режим для моделей селективного обслуживания с двухкомпонентным и трехкомпонентным потоками заявок устанавливается приблизительно за 100000 и 1000 единиц модельного времени соответственно, равных среднему времени обслуживания заявки одним обслуживающим устройством.

4. Составлен комплекс программ имитационного моделирования моделей селективного обслуживания с поликомпонентным потоком заявок, проведен цикл вычислительных экспериментов.

5. Разработан численный алгоритм организации обслуживания в подобных СМО, позволяющий найти единственно приемлемое количество обслуживающих приборов в кавдой группе при заданных ограничениях.

Полученные результаты могут быть использованы для оценки производительности существующих систем подобной архитектуры, а также для расчета затрат на модернизацию или строительство объектов, работающих по принципу систем массового обслуживания, ещё на этапе проектирования.

]

ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ

Публикации в ведущих рецензируемых научных журналах, рекомендованных

ВАК:

1. Валеев И.Н. Многоканальная система массового обслуживания с отказами / И.Н. Валеев, А.П. Кирпичников // Казань: Вестник Казанского технологического университета. - 2006. - №4. - С. 66-70.

2. Кирпичников А.П. Комбинированная многоканальная система массового обслуживания с отказами / А.П. Кирпичников, И.Н. Валеев // Обозрение прикладной и промышленной математики. - Москва, 2007. - т. 14, вып .5, - С. 891-893.

3. Валеев И.Н. Характеристики многоканальной системы массового обслуживания / И.Н. Валеев // Казань: Вестник Казанского технологического университета. -2011. -№2,- С. 326-329.

Публикации в сборниках трудов всероссийских и международных научных конференций:

4. Валеев И.Н. Многоканальная система массового обслуживания с неоднородным потоком заявок и с отказами / И.Н. Валеев, А.П. Кирпичников // Ярославль. Сборник трудов XX Международной научной конференции «Математические методы в технике и технологиях ММТТ-20». -Т.4. - 2007. - С. 214-216.

5. Кирпичников А.П. Комбинированная модель систем массового обслуживания / А.П. Кирпичников, И.Н. Валеев И Материалы Всероссийской научно-технической конференции. - Нижний Новгород, 2007. - С. 17-19.

6. Валеев И.Н. Многоканальная система массового обслуживания с отказами и неограниченной очередью / И.Н. Валеев, А.П. Кирпичников // Молодежь и современные информационные технологии. Сборник трудов VI Всероссийской научно-практической конференции студентов, аспирантов и молодых ученых. - Томск, 2008.-С. 90-91.

7. Валеев И.Н. Исследования многоканальных систем массового обслуживания / И.Н. Валеев, А.П. Кирпичников // Сборник трудов Пятой международной научно-практической конференции «Исследование, разработка и применение высоких технологий в промышленности». Санкт-Петербург, 2008. - С. 53-56.

8. Валеев И.Н. Многоканальная система массового обслуживания с неоднородным потоком заявок и с отказами / И.Н. Валеев, А.П. Кирпичников // Псков. Сборник трудов XXII Международной научной конференции «Математические методы в технике и технологиях ММТТ-22». - Т.4, - 2009. - С. 214-216.

Отпечатано в ООО «Печатный двор», г. Казань, ул. Журналистов, 1/16, оф.207

Тел: 272-74-59, 541-76-41, 541-76-51. Лицензия ПД №7-0215 от 01.11.2001 г. Выдана Поволжским межрегиональным территориальным управлением МПТРРФ. Подписано в печать 28.10.2011 г. Печ.л.1,0 Заказ № К-7074. Тираж 100 экз. Формат 60х&4 1/16. Бумага офсетная. Печать - ризография.

Содержание.

Введение.

1. Литературный обзор и классические модели систем массового обслуживания

1.1. Обзор научных работ и классификация систем массового обслуживания.

1.2. Модель М/М/М/0 или модель Эрланга.

1.3. Модель М/М/ш или многоканальное устройство.

1.4. Комбинированная модель СМО.

2. Модель селективного обслуживания с двухкомпонентным потоком заявок

2.1. Вероятностные характеристики.

2.2. Числовые характеристики.

2.3. Временные характеристики.

3. Модель селективного обслуживания с трехкомпонентным потоком заявок.

3.1. Вероятностные характеристики.

3.2. Числовые характеристики.

3.3. Временные характеристики.

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

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

4.2. Имитационное моделирование в GPSS.

4.3. Исследование нестационарного режима в моделях селективного обслуживания.

Актуальность темы. Задачи, связанные с обслуживанием потоков требований случайного характера были актуальны всегда, однако в простейших случаях решались без применения каких-либо научных методов. С момента возникновения данных проблем в технических системах, в частности, в телефонии, к ним стал применяться научный подход, основанный на применении математического аппарата теории вероятностей. Обзор научных трудов последних лет показывает, что работы ученых в данной области направлены на решение задач в сфере телекоммуникационных систем. Однако, в последнее время, в связи с развитием рынка в России появляется большое количество различных товаров и услуг, и подобные проблемы все чаще возникают в сфере торговли и обслуживания населения.

Как научный, так и практический интерес имеют системы обслуживания, содержащие группы обслуживающих устройств одинаковой производительности, осуществляющие селекцию входного поликомпонентного потока по типу заявок. Также в подобных системах имеют место ожидания и потери заявок. В этой связи в данная работа была посвящена изучению подобных систем массового обслуживания (СМО).

Несмотря на появление программных средств имитационного моделирования случайных процессов на ЭВМ, аналитическое исследование СМО остается актуальным, поскольку только аналитическое решение обладает общностью результата и позволяет предсказать характер поведения системы при любых изменениях параметров модели. Сложность аналитических методов не позволяет решать с их помощью любые задачи массового обслуживания, однако, круг задач, решаемых аналитически, весьма широк. Для решения практических задач достаточно рассмотреть системы весьма общей структуры в квазистационарном режиме функционирования.

Цель работы: разработка методов исследования открытых многоканальных систем селективного массового обслуживания с поликомпонентным входным потоком заявок.

Задачи:

S математическое моделирование данного типа систем, вывод и анализ вероятностных, числовых и временных характеристика моделей;

•S разработка численных алгоритмов и методов организации обслуживания предложенных СМО;

•S создание комплекса программ имитационного моделирования для проведения вычислительного эксперимента.

Методом исследования является математическое моделирование с применением математического аппарата теории вероятностей, теории случайных процессов, включая аппарат непрерывных цепей Маркова. Имитационное моделирование СМО данного типа осуществлялось методом Монте-Карло с применением пакета прикладных программ GPSS World.

Достоверность научных результатов обеспечивается математической строгостью выполнения выкладок и корректностью постановок задач, а также хорошим совпадением полученных решений с результатами имитационного моделирования и с известными частными решениями других авторов. В работе применены строгие математические методы, в том числе методы теории вероятностей, теории случайных процессов и непрерывных цепей Маркова, методы имитационного моделирования, а также методы численного решения систем алгебраических уравнений.

Научная новизна. Предложена новая структура обслуживающих устройств. Особенность данной структуры состоит в том, что имеются две группы обслуживающих устройств одинаковой производительности, а входной поток требований состоит из заявок разных типов: одни обслуживаются при любых обстоятельствах, независимо от наличия свободных мест и количества заявок, ожидающих обслуживания в очереди, другие - обслуживаются только при налинии свободного обслуживающего устройства и никогда не становятся в очередь; при этом заявки первого типа могут обслуживаться обеими группами обслуживающих устройств, а заявки второго типа - только одной. Вследствие этого, данные модели предложено называть системами селективного массового обслуживания, а поток заявок — поликомпонентным. Впервые изучены СМО, имеющие подобную структуру обслуживающих устройств и поликомпонентный входной поток заявок, как в стационарном, так и в нестационарном режимах работы. Сформулирована и решена задача определения количества обслуживающих устройств в каждой группе, необходимого для получения желаемой производительности.

Практическая значимость результатов диссертационной работы состоит в том, что приведенные результаты могут быть полезны при проектировании, объектов, работающих по принципу систем массового обслуживания, и применены в торговой отрасли, транспортных системах, на производстве, в телекоммуникациях и многих других областях. Подобные математические модели, во-первых, позволяют оценить производительность проектируемой системы при известной ее структуре, во-вторых, дают возможность разработать необходимую архитектуру СМО на этапе проектирования с целью получения требуемой производительности.

Содержание работы

В данной работе на основе известных классических моделей систем массового обслуживания были разработаны две новые модели. За основу были взяты модель с отказами и многоканальная модель с ожиданием. При этом были добавлены некоторые изменения, касающиеся входного потока и дисциплины обслуживания.

В первой главе даны исторические сведения из теории массового обслуживания, составлена классификация систем и показаны три изученные модели массового обслуживания — Модель Эрланга, многоканальная модель и модель Коэна, представлены основные характеристики данных моделей.

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

В четвертой главе представлена разработанная методика организации обслуживания в СМО с ожиданием, отказами и неограниченной очередью, сформулированы постановка задачи организации обслуживания в подобных СМО и алгоритм её решения, а также приведены программы численного моделирования стационарного и нестационарного режимов данных СМО.

ЗАКЛЮЧЕНИЕ

В настоящей работе были получены следующие результаты:

1. Разработаны новые модели систем селективного массового обслуживания. Проведена математическая формализация моделей данных СМО, получены общие формулы для вероятностных, числовых и временных характеристик подобных систем.

2. Предложена новая структура обслуживающей системы в виде двух различных групп обслуживающих устройств.

3. Исследованы вероятностные, числовые и временные характеристики стационарного и нестационарного режимов в моделях селективного обслуживания с поликомпонентным потоком заявок, построены их графические зависимости с применением полученных математических моделей и численного эксперимента. Выявлено, что квазистационарный режим для моделей селективного обслуживания с двухкомпонентным и трехкомпонентным потоками заявок устанавливается приблизительно за 100000 и 1000 единиц модельного времени соответственно, равных среднему времени обслуживания заявки одним обслуживающим устройством.

4. Составлен комплекс программ имитационного моделирования моделей селективного обслуживания с поликомпонентным потоком заявок, проведен цикл вычислительных экспериментов.

5. Разработана методика организации обслуживания в подобных СМО, позволяющая найти единственно приемлемое количество обслуживающих приборов в каждой группе при заданных ограничениях.

Полученные результаты могут быть использованы для оценки производительности существующих систем подобной архитектуры, а также для расчета затрат на модернизацию или строительство объектов, работающих по принципу систем массового обслуживания, ещё на этапе проектирования.

1. Российский энциклопедический словарь. / Гл. ред. A.M. Прохоров. Кн. 1. М.: Большая Российская энциклопедия, 2001.

2. Математическая энциклопедия. / Гл. ред. И.М. Виноградов. Т. 3. М.: Советская энциклопедия, 1982.

3. Феллер В. Введение в теорию вероятностей и её приложения. Т. 1. М.: Мир, 1964.

4. Кофман А., Крюон Р. Массовое обслуживание. Теория и приложения. М.: Мир, 1965.

5. Риордан Дж. Вероятностные системы обслуживания. М.: Связь, 1966.

6. Вентцель Е.С. Теория вероятностей. М.: Наука, 1969.

7. Саати Т.Л. Элементы теории массового обслуживания и её приложения. М.: Советское радио, 1971.

8. Вентцель Е.С. Исследование операций. М.: Советское радио, 1972.

9. Клейнрок JI. Теория массового обслуживания. М.:. Машиностроение,1979.

10. Феррари Д. Оценка производительности вычислительных машин. М.: Мир, 1981.

11. Ивченко Г.И., Каштанов В.А., Коваленко И.Н. Теория массового обслуживания. М.: Высшая школа, 1982.

12. Альянах И.Н. Моделирование вычислительных систем. JL: Машиностроение, 1988.

13. Brockmeyer Е., Halstrom H.L., Jensen A., «The Life and Works of A.K. Erlang», Copenhagen Telephone Company, Copenhagen, 1948.

14. Fry T.C., The Theory of Probability as Applied to Problems of Congestion,1928.

15. Molina E.C., Application of the Theory of Probability to Telephone Trunk-ing Problems, Bell System Tech. J., vol. 6, pp. 461-494, 1927.

16. O'Dell C.F., Theoretical Principles of the Traffic Capacity of Automatic Switches, P.O. Elec. Engrs. J., vol. 13, pp. 209-223, 1920.

17. Syski R., The Theory of Congestion in Lost-call Systems, A.T.E. Journal, vol. 9, pp. 182-215, 1953.

18. Pollaczek F., «Problèmes stochastiques poses par le phenomene de formation d'uue queue d'attente a un guichet et par des phenomenes apparantes», Memorial des Sciences Mathématiques, Gauthier-Villars, Paris, 1957.

19. Saaty T.L. Resume of useful formulas in Queuing Theory, Operat. Res., v. 5, 1957, pp. 162-187.

20. Saaty T.L. Mathematical methods of operations research, McGraw-Hill, 1959, pp. 331-374.

21. Такач JI. Некоторые вероятностные задачи в телефонии, Математика (сб. переводов), 4:6, 1960, с. 93-144.

22. Bharucha Reid А.Т. Elements of Markov processes and the applications, McGraw-Hill, 1960.

23. Bodino G.A., Brombilla F. Teoria delle code, Milano Vares, 1959, pp. 1219.

24. Cox, Smith W.L. Queues, Methuen & Co, London, 1961.

25. Takacs L. Introduction to the theory of queues, Oxford University Press, 1962, pp. 1-268.

26. Syski R. Introduction to congestion theory in telephone systems, Oliver and Boyd, Edinburgh and London, 1960, pp. 1-742

27. Saaty T.L. Elements of Queuing theory with applications, McGraw-Hill, 1961, pp. 1-423.

28. Riordan J. Stochastic Service Systems, Wiley and Sons, 1962, pp. 1-139.

29. Feller W., An Introduction to Probability Theory and Its Applications. John Wiley, New York, 1957.

30. Kendall D.G., Some Problems in the Theory of Queues, J.Roy. Statist. Soc., Ser. B, vol 13, №2, pp. 151-185, 1951.

31. Kendall D.G., Stochastic Processes Occuring in the Theory of Queues and Their Analysis by the Method of the Imbedded Markov Chain, Ann. Math. Statist., vol. 24, pp. 338-354, 1953.

32. Clarke A.B., On the Solution of the «Telephone Problem», Univ. Michigan Rept. M720-1R39,1953.

33. Ledermann W., Reuter G.E., Spectral Theory for the Differential Equations of Simple Birth and Death Processes, Phil. Trans. Roy. Soc. London, Ser. A, vol. 246, pp. 321-369, 1954.

34. Bailey N.T.J., A Continuous Time Treatment of a Simple Queue, Using Generating Functions, J. Roy. Statist. Soc., Ser. B, vol. 16, pp. 288-291, 1954.

35. Morse P.M., Stochastic Properties of Waiting Lines, J. Operations Research Soc. Am., vol. 3, pp. 255-261, 1955.

36. Champernowne D.G., An Elementary Method of the Solution of the Queueing Problem with a Single Server and Constant Parameter, J. Roy. Statist. Soc., Ser. B, vol. 18, № 1, pp. 125-128, 1956.

37. Karlin S., Mcgregor J., Many Server Queueing Processes, with Poisson Input and Exponential Service Times, Pasific J. Math., vol. 8, №1, pp. 87-118, 1958.

38. Saaty T.L., Time Dependent Solution of the Many Server Poisson Queue, Operations Reaserch, 1960.

39. Clarke A.B., A Waiting Time Process of Markov Type, Ann. Math. Statist., vol. 27, pp. 452-459, 1956.

40. Lindley D.V., Mathematical Theory Marshalling & Queueing, Operational Research Quart., vol. 3, № 1, 1952.

41. Mellor S.D., Delayed Call Formulae When Calls Are Served in Random Order, P.O. Elec. Engrs. J., vol. 35, pt. 2, pp. 53-56, 1942.

42. Vaulot A.E., Délais d'attente des appels telephoniques, traits au hasard, Compt. rend., vol. 222, pp. 268-269, 1946.

43. Pollaszek F., La loi d'attente des appels telephoniques. Compt. rend., vol. 222, pp. 353-355,1946.

44. Palm С., Research on Telephone Traffic Carried by Full Availability Groups, Tele., № 1, 1957.

45. Wilkinson R.I., Working Curves for Delayed Exponential Calls Served in Random Order, Bell System Tech. J., vol. 32, pp. 360-383, 1953.

46. Burke P.J., Equilibrium Delay Distribution for One Channel with Constant Holding Time, Poisson Input and Random Service, Bell System Tech. J., pp. 10211031, 1959.

47. Morse P.M., «Queues, Inventories and Maintenance», John Wiley, New York, 1958.

48. Jackson J.R., Some Problems in Queueing with Dynamic Priorities, Univ. Calif., Management Sci. Research Project Paper 62,1959.

49. Miller R.G., Jr., Priority Queues, Ann. Math. Statist., vol. 31, № 1, 1960.

50. Finsh P.D., Balking in the Queueing System Gl/M/1, Acta math. Acad. Sci. Hung., vol. 10, № 1/2, pp. 241-247, 1959.

51. Barrer D.Y., Queueing with Impatient Customers and Indifferent Clerks, Operations Research, vol. 5, № 5, 1957.

52. Barrer D.Y., Queueing with Impatient Customers and Ordered Service, Operations Research, vol. 5, pp. 650-656, 1957.

53. Герасимов А.И. О нормализующих константах в открытых и смешанных сетях массового обслуживания с несколькими классами сообщений / А.И. Герасимов // Доклады Академии Наук. 2008. - №3. - с. 314-318.

54. Gerasimov A.I. Analytical Methods for the Investigation and Optimization of Computer Systems and Networks Based on Queueing Network Models. Moscow: Radio & Svjaz, 2003. 288 p.

55. Герасимов А.И. Аналитические методы исследования и оптимизации вычислительных систем и сетей на основе сетевых моделей массового обслуживания. М.: Радио и связь, 2001. 240 с.

56. Митрофанов Ю.И., Рогачко Е.С. Управление распределением нагрузки в сетях массового обслуживания. Автоматика и телемеханика. 2008. №9.

57. Tassiulas L., Ephremides A. Throughput properties of a queueing network with distributed dynamic routing and flow control // Adv. Appl. Prob. 1996. V. 28. № l.p. 285-307.

58. Митрофанов Ю.И., Юдаева H.B. Модели и анализ сетей массового обслуживания с управлением маршрутизацией // АиТ. 2000. №6. с. 104-113.

59. Down D.G., Lewis М.Е. Dynamic load balancing in parallel queueing systems: stability and optimal control // Eur. J. Oper. Res. 2006. V. 168. №2. p. 509-519.

60. Касконе H., Разумчик P.B. Экспоненциальная система массового обслуживания с отрицательными заявками и бункером для вытеснения заявок. Автоматика и телемеханика. 2008. №9.

61. Бочаров П.П., Печинкин А.В. Теория массового обслуживания. М.: Изд. РУДН, 1995.

62. Ким Ч.С., Клименок В.И., Орловский Д.С. Многолинейная система обслуживания с групповым марковским потоком и отрицательными заявками. Автоматика и телемеханика. 2006. №12.

63. Бочаров П.П., Вискова Е., Надаев Э. Марковская система массового обслуживания конечной емкости с отрицательными заявками в дискретном времени. Queues: Flows, Systems, Networks. 2005. № 18. P. 14-19.

64. Asmussen S. Applied Probability and Queues. N.Y. Springer-Verlag, 2003.

65. Бочаров П.П. Система МАР/Г/l/r в условиях большого коэффициента вариации времени обслуживания. Автоматика и телемеханика. 2005. №11.

66. Башарин Г.П., Бочаров П.П., Коган Я.А. Анализ очередей в вычислительных сетях. Теория и методы расчета. М.: Наука, 1989.

67. Bocharov P.P., D'Apice С., Pechinkin A.V., Salerno S. Queueing theory. Utrecht-Boston: VSP, 2004.

68. Д'Апиче Ч., Манзо P., Печинкин А.В. Система обслуживания МАРК/ Gk/1 конечной емкости с обобщенной дисциплиной преимущественного разделения прибора. Автоматика и телемеханика. 2004. №. 11.

69. Д'Апиче Ч., Кристофано M.JL, Печинкин A.B. Система обслуживания МАРК/ Gk/1/oc с обобщенной дисциплиной преимущественного разделения прибора. Автоматика и телемеханика. 2004. №. 12.

70. Микадзе И.С., Хочолава В.В., Хуродзе P.A. Виртуальное время ожидания в однолинейной СМО с ненадежным прибором. Автоматика и телемеханика. 2004. №. 12.

71. Хочолава В.В., Микадзе И.С. Об одной модели системы массового обслуживания. Georg, engin, news. 2002. № 4. с. 47-52.

72. Буриков М.Д., Малинковский Ю.В., Маталыцкий М.А. Теория массового обслуживания. Гродно: Изд. Гродненского университета, 1984. 108 с.

73. Матвеев В.Ф., Ушаков В.Г. Системы массового обслуживания. М.: Изд. МГУ. 1984. 240 с.

74. Тихоненко О.М. Модели массового обслуживания в системах обработки информации. Мн.: Университетское, 1990. 191 с.

75. Тихоненко О.М. Теория массового обслуживания. Мн.: ВУЗ-ЮНИТИ, 1999. 144 с.

76. Тихоненко О.М. Модели массового обслуживания в информационных системах. Мн.: УП «Технопринт», 2003. 327 с.

77. Таранцев A.A. Инженерные методы теории массового обслуживания. СПб.: Наука, 2007. 175 с.

78. Цициашвили Г. Ш., Осипова М. А. Модели массового обслуживания с различными схемами преобразования и типами заявок. Дальневост. матем. журн., 7:1-2 (2007), 101-107

79. Садовников A.A., Таций И.В. Решение управленческих производственных задач с применением теории массового обслуживания. Маркетинг. Теория и практика, 2008, №14. с.

80. Садовников A.A., Таций И.В. Применение теории массового обслуживания в решениях оптимизационных задач в производстве. Машиностроитель, 2008, №7. с. 2-5

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

82. Разумный А.И. Прикладные аспекты теории массового обслуживания в реализации складских. Автотранспортное предприятие. Сентябрь, 2009.

83. Хакимова Е.А. Методы теории массового обслуживания, используемые для оценки качества обслуживания в коммерческом банке. Маркетинг в России и за рубежом №1' 2010

84. Моисеев А.Н. Синяков М.В. Разработка объектно-ориентированной модели системы имитационного моделирования процессов массового обслуживания. Вестник Томского государственного университета, 2010, №1. с. 89-93.

85. Кирпичников А.П. Прикладная теория массового обслуживания. Казань: Изд-во Казанск. гос. ун-та, 2008. 118 с.

86. Кирпичников А.П., Титовцев A.C. Открытая одноканальная система массового обслуживания с отказами и неограниченной очередью.// Вестник Казанского технологического университета. 2006. - №4. - С. 78 — 85.

87. Кирпичников А.П., Титовцев A.C. Системы массового обслуживания с отказами и неограниченной очередью. // Обозрение прикладной и промышленной математики. 2007. - Т. 14 - Вып. 5. - С. 893 - 896.

88. Кирпичников А.П., Титовцев A.C. Методика оптимальной организации систем массового обслуживания с отказами и очередью. // Обозрение прикладной и промышленной математики. 2008. - Т. 15 - Вып. 6. - С. 1090 -1091.

89. Кирпичников А.П., Титовцев A.C. Многолинейные системы массового обслуживания с отказами и очередью. // XII Международная научная конференция им. академика М. Кравчука Киев, 2008. - С. 69.

90. Кирпичников А.П., Титовцев A.C. Системы обслуживания с неоднородным входным потоком требований, отказами и очередью.// Вестник Казанского технологического университета. 2011. — №5. - С. 154-161.

91. Титовцев A.C. Открытые многоканальные системы дифференцированного обслуживания поликомпонентных потоков, дис.канд. тех.наук. /

92. Титовцев A.C.-2011.- 143 с.