Введение 3
Постановка задачи 5
Обзор литературы 6
Глава 1. Аналитическая модель НСО 8
1.1. Модель НСО 8
1.2. Модель НСО с абсолютными приоритетами 12
Глава 2. Описание алгоритма 16
2.1. Формирование списка возможных состояний 16
2.2. Заполнение матрицы коэффициентов 20
2.3. Реализация решения 21
2.4. Реализация имитационного моделирования 23
Глава 3. Практический пример 25
Заключение 33
Список литературы
Теория массового обслуживания (ТМО) является относительно новым разделом теории вероятности. Целью изучения ТМО является выбор структуры системы обслуживания и процесса обслуживания на основе изучения потоков требований на обслуживание, поступающих в систему и выходящие из неё, длительности ожидания и длины очередей.
Большинство авторов используют модели ТМО в предположении, что очередь заявок бесконечна, существует стационарный режим. Это позволяет оценить эффективность системы обслуживания на длительном интервале времени, получить характеристики «в среднем». Какой в среднем процент заявок будет теряться, какая средняя длительность ожидания обслуживания, какая в среднем нагрузка на один канал и т.д.
В то же время большой практический и теоретический интерес представляют модели нестационарных систем обслуживания (НСО). Изучению таких систем посвящено сравнительно мало работ.
Под моделью НСО понимается модель системы обслуживания с переменными во времени вероятностями состояний, каждое из которых определяет вероятность числа находящихся в НСО заявок и числа получивших обслуживание заявок. Число заявок, поступающих на обслуживание в рассматриваемых моделях, конечно. Стационарный режим не выделяется и основным предметом исследования является переходный процесс. Соответственно и важными характеристиками системы являются совсем другие: например среднее время обработки всех или некоторого числа заявок или вероятность не уложиться в требуемые сроки, вероятность превышения критической длины очереди, вероятность отказа в обслуживании критического числа заявок и т.д. Для иллюстрации важности моделирования НСО можно рассмотреть работу приемной комиссии университета. Заявления на поступление, приходят концентрированно в течение небольшого промежутка времени. Кроме того нас не интересует сколько из них мы можем потерять ведь важно обработать их все. Поэтому одной из важных характеристик будет являться количество людей (каналов обслуживания) необходимых для обработки заявлений в срок.
Имеется большое число реальных ситуаций, когда в потоке требований могут содержаться требования нескольких типов, причем требования первого типа обслуживаются вне всякой очереди, если только в очереди нет требований того же типа. По отношению к требованиям третьего и следующих типов правом преимущества пользуются требования второго типа и т.д. В качестве хорошего примера можно привести обслуживание на телеграфе, где срочные телеграммы передаются раньше обычных, даже когда простые телеграммы сданы ранее срочных.
Далее будут рассматриваться системы с так называемыми абсолютными приоритетами, в которых обслуживание заявки меньшего приоритета в случае прихода более «важной» заявки прерывается, и возобновляется лишь после обработки всех более приоритетных заявок.
Вероятности нахождения системы в том или ином состоянии есть функции от времени, которые являются решением обратного уравнения Чепмена - Колмогорова. Однако его составление даже для одноканальной НСО с абсолютными приоритетами представляется проблематичным.
В данной работе представлен алгоритм формирования нижнетреугольной матрицы коэффициентов линейной стационарной системы обыкновенных дифференциальных уравнений (ОДУ) для вышеуказанных систем без вывода общего уравнения системы. Для проверки корректности составления матрицы, проводится сравнение решения системы ОДУ с указанной матрицей коэффициентов, и результатами имитационного моделирования. Так же приведены графики, отображающие наиболее интересные характеристики исследуемой системы.
Постановка задачи
Рассматривается одноканальная нестационарная система массового обслуживания с абсолютными приоритетами. На вход системы поступают N заявок K типов (приоритетов) (K < N). Известно сколько заявок каждого типа может прийти. Распределения временных интервалов между моментами поступления заявок описывается экспоненциальными законами с интенсивностями, зависящими от номера типа заявок. Закон распределения времён обслуживания - экспоненциальный с интенсивностями, так же зависящими от номера типа заявок. Вычислительную систему представим в виде одноканальной нестационарной системы обслуживания без потерь.
Необходимо сформулировать правила формирования списка состояний, а так же способ генерации нижнетреугольной матрицы коэффициентов системы однородных дифференциальных уравнений, описывающих вышеуказанную систему.
Обзор литературы
Изучение нестационарных систем обслуживания на практике, как впрочем и всей теории массового обслуживания, невозможно без должного освоения теоретической литературы.
В книге Дж. Кемени и Дж. Снелла [6] изложены основы теории цепей Маркова. Основные теоремы даны в простой и понятной форме, не требующей глубоких математических познаний.
В последнем разделе учебника Е. С. Венцель [4], даются основные определения и теоремы ТМО. Автор учебника ставил задачу изложить предмет наиболее просто и наглядно. Книга снабжена большим количеством примеров, в ряде случаев расчетного характера, в которых применение излагаемых методов иллюстрируется на конкретном практическом материале и доводится до численного результата.
Для более подробного и целостного изучения ТМО следует обратиться к труду А. Я. Хинчина [10], а так же к работе Л. Клейнрока [7].
В книге Б. В. Гнеденко, И. Н. Коваленко [5] помимо рассмотрения задач теории массового обслуживания в целом и методов их решений, уделено внимание интересующим нас нестационарным системам обслуживания.
В учебнике В. Ф. Матвеева и В. Г. Ушакова [8] рассматриваются приоритетные НСО, в частности системы с абсолютными приоритетами.
Методическое издание В. П. Бубнова и В. И. Сафонова [2] содержит рассмотрение основных моделей НСО с различными типами поступления и обработки заявок. Приводятся диаграммы переходов, а так же характеристики этих моделей.
Колмогорова. Показано преимущество данного метода над “классическим” методом Рунге-Кутты четвертого порядка с постоянным шагом, а так же методом ode4 5 п а к е т аMatlab, использующимися при решении вышеуказанных уравнений.
В данной работе описан алгоритм формирования списка состояний для НСО с абсолютными приоритетами таким образом, чтобы матрица A коэффициентов уравнения Чепмена - Колмогорова, описывающего данную систему, имела нижнетреугольный вид.
Правильность выполнения поставленной задачи показана, путем сравнения решения уравнения с результатами имитационного моделирования.
Для решения уравнения Чепмена - Колмогорова был реализован метод матричной экспоненты, имеющий очевидные недостатки. Одним из них является накапливающаяся величина погрешности округления, растущая вместе с увеличением рассматриваемого отрезка времени. Так же, в связи с разреженностью матрицы A, выбранный метод выполняет множество ненужных операций, что значительно увеличивает время работы программы. Чтобы максимально избежать описанных проблем, планируется использовать численно-аналитический метод, описанный в статье [1].
В дальнейшем планируется так же рассмотрение НСО с абсолютными приоритетами с несколькими каналами обслуживания, а так же с распределениями временных интервалов между моментами поступления и обработки заявок подчиняющимися гиперэкспоненциальному распределению, а так же распределениям Эрланга и Кокса.
Рост количества входных заявок увеличивает рассматриваемую систему на порядки, делая её крайне неудобной для исследования. В связи с этим возникает потребность в объединении состояний в группы по некоторому принципу, тем самым аппроксимируя исходную громоздкую систему. Выбор таких принципов так же входит в планы дальнейшего рассмотрения НСО с приоритетами.
Помощь студентам и аспирантам в выполнении работ от наших партнеров
