Системы массового обслуживания со специальными дисциплинами тема диссертации и автореферата по ВАК РФ 05.13.01, доктор физико-математических наук Таташев, Александр Геннадьевич

• Таташев, Александр Геннадьевич
• доктор физико-математических наук
• 2001

Оглавление диссертации доктор физико-математических наук Таташев, Александр Геннадьевич

1. Введение.

Глава 1. Системы с групповым поступлением требований и инверсионным обслуживанием с прерыванием.

1.1. Система с обслуживанием прерванного требования заново с новой длительностью.

1.2. Система с потерей прерванного требования.

1.3. Система с обслуживанием прерванного требования заново с прежней длительностью.

1.4. Система с возможным прерыванием требования.

1.5. Система с разделением процессора требованиями одной группы.

1.6. Система с обслуживанием первым кратчайшего требования внутри группы.

1.7. Система с разнотипными требованиями.

Глава 2. Системы с дисциплинами, учитывающими остаточные времена обслуживания требований.

2.1. Инвариантная инверсионная дисциплина обслуживания с вероятностным приоритетом и конечным числом мест ожидания.

2.2. Инвариантная инверсионная дисциплина с вероятностным приоритетом и бесконечным числом мест ожидания.

2.3. Одна инвариантная дисциплина обслуживания.

2.4. Многоканальная система с потерей требования наименьшей длины.

2.5. Система с потерей требования максимальной длины.

Глава 3. Некоторые системы массового обслуживания с разнотипными требованиями.

3.1. Система с одним местом ожидания и приоритетной дисциплиной с дообслуживанием прерванного требования.

3.2. Система с одним местом ожидания и приоритетной дисциплиной с обслуживанием прерванного требования заново.

3.3. Система с одним местом ожидания и приоритетной дисциплиной с потерей прерваннного требования.

3.4. Система с одной инверсионной дисциплиной и дообслуживанием прерванного требования.

3.5. Система с одной инверсионной дисциплиной и обслуживанием прерванного требования заново.

3.6. Система с требованиями двух типов и одной инверсионной дисциплиной с дообслуживанием прерванного требования.

3.7. Система с требованиями двух типов и одной инверсионной дисциплиной с обслуживанием прерванного требования заново.

3.8. Система с одной инверсионной дисциплиной обслуживания с прерыванием требований двух типов.

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

4.1. Система с инверсионной дисциплиной.

4.2. Система с обслуживаниям требований в порядке поступления.

Глава 5. Система с требованиями нескольких типов и обобщенной дисциплиной преимущественного разделения процессора.

5.1. Вычисление стационарного распределения времени пребывания требования в системе.

5.2. Вычисление нестационарных и стационарных вероятностей состояний системы.

Введение диссертации (часть автореферата) на тему «Системы массового обслуживания со специальными дисциплинами»

В настоящей диссертационной работе исследуются системы массового обслуживания со специальными дисциплинами.

Специальные дисциплины обслуживания используются в реальных информационно-вычислительных системах с целью повышения эффективности обслуживания или в силу удобства их применения.

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

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

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

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

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

Другой работой, посвященной оптимизационным вопросам теории массового обслуживания, является обзор [32].

Возможные применения результатов теории массового обслуживания при разработке и анализе вычислительных систем коллективного пользования, систем и сетей связи описываются в монографиях [7,11,12,15,58].

Как отмечается в [5], как информационно-вычислительные системы, так и автоматические системы управления, состоят из множества связанных между собой пунктов, оснащенных вычислительными машинами, где информация собирается, обрабатывается и передается далее. В таких сетевых структурах можно выделить по функциональному признаку последовательные уровни иерархии: от низшего уровня, на котором вычислительные машины непосредственно связаны с первичными источниками информации и объектами управления, до высшего, где на основе сводной информации вырабатываются наиболее общие решения. Но если даже рассмотреть отдельный пункт (узел) в такой сетевой структуре, то окажется, что на вычислительную машину в ней поступают разнородные потоки заявок на решение задач разной важности (срочности) и длительности (объема). Чтобы упорядочить работу вычислительной машины в такой ситуации, вводят систему приоритетов (динамическую или статическую) в обслуживании различных задач. Современные вычислительные средства в зависимости от характера поставленных задач могут решать их в различных режимах: запрос-ответ, пакетной обработки, разделения времени при коллективном пользовании, мультипрограммном. Этим режимам в той или иной степени соответствуют различные модели систем массового обслуживания, позволяющие рассчитывать такие показатели работы вычислительной машины, как загрузка памяти и процессора, задержки и потери информации, и оценивать эффективность и надежность принятых решений. В [5] при обосновании использования систем массового обслуживания с соответствующими дисциплинами в качестве моделей функционирования узла сети связи с коммутацией сообщений отмечается, в частности, следующее. Такая сеть представляет собой совокупность узлов коммутаций сообщений, некоторые из которых непосредственно соединены между собой ориентированными каналами связи. Узел сети вместе с набором сообщений, ожидающих в этом узле и претендующих на передачу по одному и тому же исходящему из узла каналу, может рассматриваться как одноканальная система массового обслуживания, а время, затрачиваемое сетью на перемещение от узла-источника в узел-адресат, называемое временем доставки сообщения, складывается из отрезков времени пребывания данного сообщения в системах массового обслуживания всех узлов, посещаемых им при перемещении по сети. Обеспечение требуемой гарантии доставки сообщений адресатам в заданные сроки зачастую зависит от дисциплины обслуживания, принятой в системах массового обслуживания на узлах. Необходимость в использовании приоритетных или других специальных дисциплин обслуживания сообщений на узлах сети возникает тогда, когда соотношение между пропускной способностью сети и интенсивностью потока движущейся по ней информации неблагоприятно в такой степени, что обслуживание в порядке поступления не может обеспечить для всех категорий срочности требуемую гарантию своевременной доставки.

В [15, 58] рассматриваются проблемы эффективного использования вычислтельных ресурсов в реальном масштабе времени. Приводятся основные характеристики различных методов организации вычислительного процесса. Даются рекомендации по применению различных методов и дисциплин организации вычислительного процесса и принципы оценки их эффективности.

В [58] отмечается, что в последнее время получило интенсивное развитие новое направление теории массового обслуживания, связанное с исследованием систем с дисциплинами обслуживания, отображающими существенные особенности алгоритмов диспетчеризации современных ЭВМ с разделением времени в узлах сетей передачи данных и вычислительных сетей. Важную роль среди таких систем обслуживания играют так называемые системы с разделением процессора, которым посвящен обзор [60]. Как отмечено в [15], практическое значение математической реализации, используемой в моделях разделения процессора, состоит в том, что она отражает существенную особенность вычислительной системы с разделением времени (если под требованием понимать отдельные задания пользователя) или мультиплексных узлов коммутации пакетов (если требованием является сообщение или сегмент) — замедление обслуживания каждого требования, пропорциональное их общему числу в текущий момент.

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

В [58] исследуются математические модели вычислительных систем с разделением времени, анализируемые в терминах теории массового обслуживания. Эти модели описывают функционирование алгоритмов диспетчеризации в современных ЭВМ, узлах сетей связи с пакетной коммутацией и других технических систем, оперативно разделяющих ресурсы процессора между заданиями многих пользователей. Как отмечается в [58], под режимом разделения времени понимается такая форма организации функционирования ЭВМ, при которой осуществляется оперативное предоставление ресурсов ЭВМ (времени процессора, памяти, каналов связи и др.) большому количеству одновременно работающих за терминалами пользователей, соединенных с системой каналами связи. К основным достоинствам системы с разделением времени можно отнести возможность коллективного пользования одной ЭВМ несколькими пользователями, быстрое получение ответа на короткие задания и значительное повышение эффективности взаимодействия с ЭВМ. Выполнение функций планирования порядка, в котором выполняются задания пользователей, возлагаются на составную часть операционной системы-алгоритм планирования (называемый также планировщиком или алгоритмом диспетчеризации), который устанавливает динамически изменяющуюся очередность заданий. Алгоритм планирования формирует очереди работ к процессору, выбирает задание для исполнения и согласно определенным правилам вычисляет для него квант времени процессора. При этом анализируются такие данные, как ранее использованное заданием время процессора, занимаемый им объем памяти, число активных заданий, приоритет, и т.д. В [58] анализируются методы организации вычислительного процесса в сетях ЭВМ, использующие следующие дисциплины обслуживания: инверсионные дисциплины; дисциплины равномерного и преимущественного разделения процессора; дисциплина обслуживания первым требования с наименьшей остаточной длиной и др.

Методам построения моделей массового обслуживания посвящена монография [9].

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

Системы массового обслуживания с инверсионными дисциплинами с прерыванием изучались, например, в [2,3,19,23,25,29,67]. При этом в [2,3,23,25] рассматривались системы с ординарным входящим потоком, а в [19,29,67] предполагалось, что обслуживание возобновляется с того места, где оно было прервано. В [29,67] считалось, что прерывание требования, находящегося на приборе, происходит при каждом поступлении новой группы требований, а в [19], что такое прерывание происходит с некоторой вероятностью, зависящей от числа требований в поступившей группе, остаточного времени находящегося на приборе требования и времени, необходимого для обслуживания каждого из поступивших требований.

Для повышения эффективности обслуживания в информационно-вычислительных системах могут использоваться дисциплины, которые уменьшают средние задержки путем предоставления приоритета "коротким" заданиям перед "длинными". При одной из таких дисциплин в текущий момент времени обслуживается требование с наименьшей остаточной длиной [65]. Другая дисциплина, предоставляющая преимущество требованиям с меньшими остаточными длинами, рассмотрена в работе [21]. Эта дисциплина является в определенном смысле промежуточной между инверсионной дисциплиной с прерыванием и инверсионной дисциплиной без прерывания. При дисциплине, рассмотренной в [21], вытеснение обслуживаемого требования вновь поступившим происходит лишь в случае, если длина поступившего требования меньше остаточной длины обслуживаемого. Изучение системы обслуживания с такой дисциплиной позволило получить оценку характеристик системы, в которой принята дисциплина обслуживания требования с наименьшей остаточной длиной. При дисциплине, рассматривавшейся в [21], в случае, если поступило требование, длина которого меньше остаточной длины требования, находящегося на обслуживании, поступившее требование занимает прибор, а обслуживаемое требование перемещается на первое место очереди. Если длина поступившего требования больше остаточной длины обслуживаемого, то, наоборот, поступившее требование становится первым в очередь, а требование, находящееся на приборе, продолжает обслуживаться. Доказано, что стационарное распределение числа требований в данной системе не зависит от распределения длины требования, если не изменяется среднее значение этого распределения.

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

Отметим, что результат, найденный в [21], является обобщением одного из результатов [26]. В [26] при рассмотрении системы массового обслуживания М\С\1\к с обслуживанием требования с наименьшей остаточной длиной было обнаружено, что в случае, когда место ожидания единственно, стационарные вероятности сотояний системы не зависят от распределения длины требования при фиксированном среднем (для системы М|(7|1|1 дисциплина обслуживания требования с наименьшей остаточной длиной и дисциплина, рассматривавшаяся в [21], как легко видеть, тождественны).

Система обслуживания, инвариантность которой установлена в [21], не принадлежит к описанному в [58] классу систем с инвариантными вероятностями состоянии относительно распределения длины требования при фиксированном среднем, сохраняющих на выходе пуассоновский поток. К этому классу, в частности, относятся следующие дисциплины: дисциплина "равномерного разделения процессора", т.е. дисциплина, при которой все находящиеся в системе требования обслуживаются одновременно с одинаковыми скоростями, составляющими в сумме 1; дисциплина обслуживания требований в обратном порядке с прерыванием и дообслуживанием. Инвариатными в смысле независимости распределения числа требований в системе относительно распределения длины требования при фиксированном среднем являются также системы массового обслуживания М|С7|оо и М\С\п\1. Некотрые другие системы массового обслуживания, инвариантные в рассматриваемом смысле, описаны в [6,10], где перечислен также ряд других работ, касающихся данного вопроса. Отметим, что до того, как в [21] был установлен факт инвариантности рассмотренной в этой работе системы, не были известны инвариантные системы массового обслуживания, не сохраняющие на выходе пуассоновский поток (для системы М|(7|п|0 пуассоновским является поток покидающих систему требований, образуемый обслуженными и потерянными требованиями). Кроме того, число требований в системе, рассматривавшейся в [21], распределено так, как для соответствующей системы М|1}|1 с обслуживанием в порядке поступления. В отличие от этого, для каждой из инвариантных систем, известных прежде, распределение числа требований совпадает с распределением числа требований в соответствующей системе с обслуживанием в порядке поступления и экспоненциальным распределением длины требования.

В упоминавшейся выше работе [67] рассматривалась система с неординарным пуассоновским потоком и инверсионной дисциплиной обслуживания, при которой требования одной группы обслуживаются в случайном порядке. Показано, что в этой системе распределение числа требований также не зависит от распределения времени обслуживания при фиксированном среднем. Инвариантность системы, рассмотренной в [67], следует также из результатов работы [19], где, в соответствии со сказанным выше, исследовалась система несколько более общего вида. Система обслуживания, рассматривавшаяся в [67], представляет собой обобщение инвариантной системы М\0\1 с инверсионной дисциплиной с прерыванием. Другие упомянутые выше инвариантные системы (в частности, системы М\С|оо и М|(7|п|0, система М|С|1 с системой разделения процессора) перестают быть инвариантными, если пуассоновский входящий поток заменить на неординарный пуассоновский.

Системы массового обслуживания с прямым или инверсионным порядком обслуживания, в которых интенсивность входящего потока зависит от суммарного объема требований, рассматривались, например, в [6,23-25,55-57,68].

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

Если величина кванта пренебрежимо мала, то можно считать, что задания обслуживаются процессором одновременно, но с уменьшенными скоростями. Дисциплина, при которой требования обслуживаются одновременно, но с уменьшенными скоростями, составляющими в сумме 1, называемая дисциплиной равномерного (справедливого) разделения процессора, была введена в рассмотрение в [62].

Если распределение длины требования является "молодеющим", т.е. требованию предстоит обслуживаться в вероятностном смысле тем дольше, чем больше времени оно уже обслуживалось, то целесообразно использовать введенную в рассмотрение в [66] дисциплину многоуровневого понижения приоритета. При этой дисциплине требованию предоставляется тем более высокий приоритет, тем меньше квантов обслуживания это требование уже получило. Предельным случаем такой дисциплины при бесконечно малой величине кванта времени является дисциплина "преимущественного (приоритетного) разделения процессора" требованиями с наименьшей обслуженной длиной. При этой дисциплине приоритет требования тем выше, чем меньше его обслуженная длина. Если в некоторый момент времени имеется сразу несколько требований, характеризующихся наименьшей обслуженной длиной, то никакое из этих требований не может использовать всю производительность системы, так как через сколь угодно малый промежуток времени значение обслуженной длины этого требования перестало бы быть минимальным. В связи с этим данная дисциплина обслуживания предусматривает одновременное обслуживание требований с наименьшей обслуженной длиной с одинаковыми скоростями, составляющими в сумме 1. В [61] получено выражение для преобразования Лапласа-Стилтьеса стационарного распределения времени пребывания требования в системе массового обслуживания М|(7|1 с дисциплиной преимущественного разделения процессора требованиями с наименьшей обслуженной длиной. В [22] найдено выражение для производящей функции числа требований в этой системе. В [59] получено аналогичное выражение для соответствующей системы с групповым поступлением. В [20,58] исследовалось нестационарное распределение числа требований в системе М|С|1 с дисциплиной преимущественного разделения процессора. Обзор литературы по системам массового обслуживания с "разделением процессора" содержится в [60].

В работе [21] введен метод, в соответствии с которым в множестве состояний процессора, описывающего функционирование системы обслуживания, выделяется некоторое подмножество и процесс рассматривается только на тех интервалах времени, когда он принимает значения из этого подмножества. При этом условное стационарное распределение исходного процесса при условии попадания его в выделенное подмножество состояний совпадает со стационарным распределением процесса, рассматриваемого на выделенных интервалах времени. Более подробно этот метод описан в [4]. Данный метод использовался в ряде других работ (в частности, в [17-19, 23-25, 28-31]). В соответствии с одной из модификаций этого метода рассматривается совокупность вспомогательных систем массового обслуживания, каждая из которых отличается от предыдущей тем, что допустимое число находящихся в системе требований увеличивается на единицу. Случайный процесс, описывающий функционирование рассматриваемой системы массового обслуживания, рассматривается лишь на тех интервалах времени, на которых число требований не превышает заданное значение.

Существует ряд естественно возникающих вопросов, которые в литературе по системам обслуживания со специальными дисциплинами не рассматривались или не были окончательно решены. Для одних типов систем не известны методы, которые позволяли бы получить более или менее пригодные для практических расчетов формулы. Для других классов систем со специальными дисциплинами методы исследования, учитывающие специфику этих систем, разработаны относительно недавно и остается не завершенной работа по совершенствованию этих методов и расширению области их применения (в частности, для исследования систем, представляющих прикладной интерес). Классом систем, для которых была разработана специальная методика, является класс систем массового обслуживания "типа" инверсионного. Для этого класса в [21] был предложен упоминавшийся выше специальный метод исследования, основанный на выделении интервалов времени, на которых рассматривается процесс, и "выкидывании" интервалов времени, которые на данном шаге исключаются из рассмотрения. С помощью этого метода (будем называть его методом Печинкина) первоначально были рассмотрены некоторые системы обслуживания, в каждой из которых поступившее требование в зависимости от его длины и остаточной длины обслуживаемого требования либо сразу занимает прибор, вытесняя обслуживаемое требование на первое место очереди, либо само становится в начало очереди. Данный метод применим к широкому классу систем обслуживания. Результаты диссертации позволили сделать класс систем, к которым применим этот метод, существенно более разнообразным и включить в этот класс ряд важных в прикладном отношении типов систем обслуживания.

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

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

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

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

При исследовании систем обслуживания, рассматриваемых в главе 1, применяется метод Печинкина. В соответствии с этим методом в множестве состояний процесса, описывающего функционирование системы, выделяется некоторое подмножество и процесс рассматривается только на тех интервалах времени, когда он попадает в это подмножество. При этом условное стационарное распределение исходного процесса при условии попадания его в выделенное множество состояний совпадает с распределением процесса, рассматриваемого на выделенных интервалах. В соответствии с первоначальной модификацией данного метода, использованной в [21], рассматривается совокупность вспомогательных систем обслуживания, каждая из которых отличается от предыдущей тем, что максимальное допустимое число находящихся в системе требований увеличивается на единицу. Случайный процесс, описывающий функционирование системы массового обслуживания, изучается лишь на тех интервалах времени, число требований не превышает допустимое значение. Для стационарных вероятностей состояний системы обслуживания составляется система уравнений равновесия. Последовательное рассмотрение вспомогательных систем обслуживания дает рекуррентную процедуру вычисления стационарных вероятностей состояний исходной системы.

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

В параграфах 1.1-1.3 исследуются системы с групповым поступлением, в которых прерванные требования либо впоследствии обслуживаются заново с новой длительностью (параграф 1.1), либо теряются (параграф 1.2), либо обслуживаются заново с прежней длительностью (параграф 1.3). Ранее из инверсионных систем обслуживания с групповым поступлением изучалась система с дообслуживанием прерванного требования с того места, где произошло прерывание. В параграфе 1.4 рассматривается система обслуживания, отличающаяся от исследуемой в параграфе 1.1 тем, что прерывание обслуживаемого требования поступившим происходит лишь с определенной вероятностью. В параграфах 1.1, 1.2 и 1.4 используется первоначальная модификация метода Печинкина, предусматривающая составление и решение уравнений равновесия. Для вычисления стационарных вероятностей состояний системы, рассматриваемой в параграфе 1.3, возникает необходимость использования другого подхода. Данная задача решена с помощью непосредственного вычисления среднего суммарного времени пребывания системы в каждом состоянии за период занятости.

В параграфе 1.5 рассмотрена система с групповым поступлением требований, в которой каждая группа требований имеет абсолютный приоритет над группами, поступившими раньше, а внутри группы требования обслуживаются так, как при дисциплине разделения процессора. В параграфе 1.6 изучается аналогичная система, в которой требования одной группы обслуживаются в порядке возрастания их длин. Как и для системы, рассматриваемой в параграфе 1.3, установлена целесообразность применения метода вычисления суммарного времени пребывания системы в каждом состоянии на периоде занятости. Кроме того, для этих систем предложена структура множества состоянии случайного процесса, описывающего функционирование системы, которая учитывает наряду с числом находящихся в системе требований их принадлежность к тем или иным поступавшим группам. Отметим, что с помощью введенной структуры состояний процесса могут исследоваться инверсионные системы с групповым поступлением и с другими правилами обслуживания требований внутри группы. Полученная в параграфе 1.5 процедура вычисления стационарного распределения числа требований в рассматриваемой системе обслуживания и найденная формула для среднего значения этого распределения позволяют иметь удобные для практических целей оценки характеристик системы с дисциплиной преимущественного разделения процессора требованиями с наименьшей обслуженной длиной (последняя дисциплина интересна в силу своих оптимизационных свойств). Аналогичным образом, полученные в параграфе 1.6 результаты, относящиеся к системе с инверсионной дисциплиной с групповым поступлением, в которой требования одной группы обслуживаются в порядке возрастания их длин, дают оценки для соответствующей системы с дисциплиной обслуживания требования с наименьшей остаточной длиной. Последняя дисциплина минимизирует задержки при наличии полной информации о временах, необходимых для обслуживания требований.

Модификация метода Печинкина, используемая в параграфах 1.5 и 1.6, применяется и при исследовании системы, рассматриваемой в параграфе 1.7, в которой группы требований различаются по типам, определяющим порядок обслуживания требований в системе. Найденные стационарные вероятности состояний системы оказываются не зависящими от распределений длительностей обслуживания требований всех типов при фиксированных средних.

В главе 2 рассматриваются системы массового обслуживания с дисциплинами, учитывающими длину поступившего требования и остаточную длину обслуживаемого требования.

Для систем массового обслуживания, рассматриваемых в параграфах 2.1-2.4 установлен факт инвариантности состояний при фиксированном среднем времени обслуживания. Ранее известные системы обслуживания, инвариантные в данном смысле, обладали следующими свойствами. При пуассо-новском входящем потоке требований поток требований, покидающих систему, также является пуассоновским. Стационарное распределение числа требований в системе является таким же, как в соответствующей системе с обслуживанием в порядке поступления и экспоненциальном распределении времени обслуживания. Инвариантностью другого типа обладает система, исследованная в [21], с дисциплиной обслуживания, при которой поступившее требование либо сразу занимает прибор, вытесняя обслуживавшееся на первое место (если его длина меньше остаточной длины обслуживаемого требования), либо само становится в начало очереди (если длина поступившего требования превышает остаточную длину обслуживаемого). Эта система не сохраняет на выходе пуассо-новский поток, а распределение находящихся в ней требований совпадает с распределением числа требований в соответствующей системе М|£)|1 с обслуживанием в порядке поступления. Как следует из результатов главы 2 диссертации, существует целый класс систем обслуживания с новым типом инвариантности. Принадлежащие к этому классу системы обслуживания, исследованные в параграфах 2.1-2.4, не сохраняют на выходе пуассоновский поток, а стационарное распределение числа требований в этих системах не совпадает со стационарным распределением числа требований в соответствующих системах в порядке поступления, вообще говоря, ни при экспоненциальном, ни при постоянном времени обслуживания. Установленный факт инвариантности вероятностей состояний соответствующих систем обслуживания можно использовать для получения удобных формул, полезных, в частности, для оценок характеристик неинвариантных систем обслуживания, которые могут рассматриваться как модели функционирования реальных систем. В частности, полученные в параграфе 2.3 формулы дают удобные оценки для стационарных вероятностей состояний системы с дисциплиной обслуживания требо-ваеия с наименьшей остаточной длиной и соответствующем числом мест ожидания, а формула для вероятности потери требования в системе, рассматриваемой в параграфе 2.4, дает верхнюю оценку для вероятности потери требования в многоканальной системе без мест ожидания с произвольным правилом выбора требования, подлежащего потере.

Метод Печинкина используется в параграфах 2.1-2.3. При этом новой является модификация этого метода, примененная к системе обслуживания, которая рассматривается в параграфе 2.3. В данной систем одновременно могут обслуживаться несколько требований, причем, в отличие, например, от системы, рассматриваемой в параграфе 1.5, моменты поступления одновременно обслуживаемых требований различны. В рассматриваемой в параграфе 2.3 системе одновременно обслуживаются с постоянной суммарной скоростью все находящиеся в системе требования за исключением ситуации, когда число требований в системе достигает максимального допустимого значения. В последнем случае обслуживается требование с наименьшей остаточной длиной. При используемом в параграфе 2.3 подходе функционирование рассматриваемой системы на определенных интервалах времени сравнивается с функционированием двух специально подобранных систем. В одной из этих систем при достижении числом требований заданного значения новые поступающие требования теряются, а во второй одновременно может обслуживаться неограниченное число требований, причем суммарная скорость обслуживания требований зависит от числа обслуживаемых требований. Аналогичным образом, метод, в соответствии с которым рассматриваемая система обслуживания сравнивается с соответствующей бесконечноканальной системой, использован при исследовании многоканальной системы с ожиданием, в которой теряются требования с наименьшими остаточными длинами. Идеи параграфов 2.3 и 2.4 могут использоваться и для вычисления характеристик других систем обслуживания. Например, можно исследовать систему, отличающуюся от рассматриваемой в параграфе 2.3 тем, что ее производительность зависит от числа находящихся в системе требований, или рассмотреть систему с дисциплиной равномерного разделения процессора с ограничением на число одновременно обслуживаемых требований, в которой при достижении числом требований максимального допустимого числа теряются требования с наименьшей остаточной длиной.

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

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

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

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

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

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

В параграфах 3.1-3.3 рассматриваются системы Мдг|(7лг|1|1 с приоритетными дисциплинами обслуживания с дообслужи-ванием (параграф 3.1), с обслуживанием заново (параграф 3.2) и с потерей (параграф 3.3) прерванного требования. В параграфе 3.4 исследуется инверсионная система обслуживания с прерыванием более приоритетного требования менее приоритетным и дообслуживанием прерванного требования. В параграфе 3.5 рассматривается аналогичная система с обслуживанием прерванного требования заново. В параграфах 3.6-3.8 изучаются инверсионные системы обслуживания с двумя типами требований. В системе, рассматриваемой в параграфе 3.6 прерывание требований одного типа не разрешено, прерванные требования другого типа впоследствии дообслужива-ются. В параграфе 3.7 расматривается аналогичная система, но предполагается, что прерванные требования обслуживаются заново. В параграфе 3.8 предполагается, что прерванные требования первого типа дообслуживаются, а прерванные требования второго типа обслуживаются заново.

В главе 4 исследуются системы массового обслуживания с входящим потоком, зависящим от состояния системы. Как и при исследовании систем, рассмотренных в главах 1 и 3, и большинства систем, рассмотренных в главе 2, используется метод, в соответствии с которым случайный процесс, описывающий функционирование системы рассматривается на интервалах времени, на которых данный процесс находится в выделенном множестве состояний. При этом показано, что для исследуемых в главе 4 этот метод удобно сочетать с методом, в соответствии с которым вычисляется суммарное время пребывания системы обслуживания в фиксированном множестве состояний за период занятости. Такой подход сходен с используемым в параграфах 1.3, 1.5-1.7, но структура случайного процесса, описывающего функционирование системы, усложняется за счет необходимости учитывать остаточные длины всех находящихся в системе требований.

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

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

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

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

Для рассматриваемой системы массового обслуживания найдено преобразование Лапласа-Стилтьеса стационарного распределения времени пребывания в системе требования заданного типа (параграф 5.1) и производящие функции нестационарного и стационарного распределений чисел требований различных типов, находящихся в системе (параграф 5.2).

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

Основное содержание диссертационной работы изложено в

27, 33-54]. количество печатных работ, содержащих результаты диссертационной работы - 23. Результаты диссертации докладывались на Всесоюзных совещаниях по распределенным системам массового обслуживания в 1990 и 1991 гг., на Всесоюзной научной сессии НТОРЭС им. А.С.Попова в 1988 г., на Белорусских зимних школах семинарах по теории массового обслуживания в 1986, 1990, 1991 и 1993 гг., на научно-методических и научно-исследовательских конференциях МАДИ (ТУ) в 1997 и 1999 гг.

Заключение диссертации по теме «Системный анализ, управление и обработка информации (по отраслям)», Таташев, Александр Геннадьевич

Заключение

1. Разработаны модификации метода исследования систем обслуживания, предложенного A.B. Печинкиным. Благодаря этим модификациям класс систем обслуживания, к которым применим данный метод, значительно расширен. С помощью этого метода стало возможным исследовать новые типы систем обслуживания со специальными дисциплинами, важные с теоретическом и прикладном отношении.

2. Для ряда систем массового обслуживания установлен факт инвариантности стационарных вероятностей состояний системы в смысле независимости этих вероятностей от распределения времени обслуживания при фиксированном среднем. Эти системы обслуживания составляют новый класс инвариантных систем.

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

- системы с неординарным пуассоновским потоком и различными инверсионными дисциплинами;

- системы с дисциплинами, учитывающими длину поступившего и остаточную длину обслуживаемого требования;

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

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

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

Список литературы диссертационного исследования доктор физико-математических наук Таташев, Александр Геннадьевич, 2001 год

1. Башарин Г.П., Бочаров П.П. Анализ очередей в вычислительных сетях. Теория и методы расчета. М.: Наука, 1987. -335 с.

2. Бочаров П.П., Павлова О.И. Анализ очереди с распределениями фазового типа и инверсионной дисциплиной обслуживания с прерываниями// Автоматика и телемеханика. 1992. -N 11. - С. 83 - 92.

3. Бочаров П.П., Павлова О.И., Печинкин A.B. Стационарные характеристики конечной очереди при инверсионном обслуживании/ / Вестник Российского университета дружбы народов. Сер. Прикл. мат. и информатика. - 1994. - N 1 - С. 62 -82.

4. Бочаров П.П., Печинкин A.B. Теория массового обслуживания// Изд-во РУДН, 1995. 528 с.

5. Бронштейн О.И., Духовный И.М. Модели приоритетного обслуживания в информационно-вычислительных системах// М.: Наука, 1976. 220 с.

6. Гнеденко Б.В., Коваленко И.Н. Введение в теорию массового обслуживания. М.: Наука, 1987, - 336 с.

7. Жожикашвили В.А., Вишневский В.М. Сети массового обслуживания. Теория и применение к сетям ЭВМ. М.: Радио и связь, 1988. - 192 с.

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

9. Калашников В.В., Рачев С.Т. Математические методы построения моделей обслуживания. М.: Высшая школа, 1988. -312 с.

10. Кениг Д., Штойян Д., Методы теории массового обслуживания. М.: Наука, 1987. - 128 с.

11. Клейнрок JI. Вычислительные системы с очередями. М.: Мир, 1979. 600 с.

12. Клейнрок JI. Коммуникационные сети. М.: Наука, 1970. 200 с.

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

14. Конвей Р.В., Максвелл В.Л., Миллер Л.В. Теория расписаний. Наука, 1975. - 360 с.

15. Липаев В.В., Яшков С.Ф. Эффективность методов организации вычислительного процесса в АСУ. М.: Статистика, 1975. - 255 с.

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

17. Нагоненко В.А. О характеристиках одной нестандартной системы массового обслуживания I// Изв. АН СССР. Техническая кибернетика. 1981. - N 1. - С. 187 - 195.

18. Нагоненко В.А. О характеристиках одной нестандартной системы массового обслуживания II// Изв. АН СССР. Техническая кибернетика. 1981. - N3.-C. 91-99.

19. Печинкин А.В. Инверсионный порядок обслуживания с вероятностным приоритетом в системе обслуживания с неординарным потоком// Математ. исследования. Сер. Вероятность и приложения (1989). - Т. 109. - С. 83 - 94.

20. Печинкин А.В. Нестационарные характеристики системы массового массового с дисциплиной преимущественного разделения процессора// Математ. исследования. Сер. Вероятность и приложения (1990). - Т. 110. - С. 84 - 87.

21. Печинкин А.В. Об одной инвариантной системе массового обслуживания// Matemat. Operatonsforsch. und Statist. -Ser. Optimisation. 1983. - N 3. - S. 433 - 444.

22. Печинкин А.В. О стационарных вероятностях в системе с дисциплиной преимущественного разделения процессора// Изв. АН СССР. Техническая кибернетика. 1980. - N 5. - С. 73 - 77.

23. Печинкин А.В. Система обслуживания с дисциплиной LIFO и ограничением на суммарный объем требований// Вестник Российского университета дружбы народов. 1996. - N 2. -С. 85 - 99.

24. Печинкин А.В. СистемаМAP\G\l\n с дисциплиной LIFOс прерыванием и ограничением на суммарный объем требований// Автоматика и телемеханика. 1999. - N 12. - С. 114 -120.

25. Печинкин A.B. Система MI/G/1/п с дисциплиной LIFO и ограничением на суммарный объем требований// Автоматика и телемеханика. 1998. - N 4. - С. 106 - 116.

26. Печинкин A.B., Соловьев А.Д., Яшков С.Ф. О системе обслуживания первым требования с минимальной остаточной длиной// Изв. АН СССР. Техническая кибернетика. 1979. -N5.-С. 51-58.

27. Печинкин A.B., Таташев А.Г. Обобщение дисциплины преимущественного разделения процессора// Изв. АН СССР. Техническая кибернетика. 1981. - N 4. - С. 120 - 125.

28. Печинкина O.A. Стационарное распределение времени пребывания в системе Mk/G/l с инверсионной вероятностной дисциплиной обслуживания// Вестник Российского университета дружбы народов. Сер. Прикл. мат. и информатика. -1996. -N 1. - С. 94-112.

29. Печинкина O.A. Стационарное распределение очереди в системе с дисциплиной LIFO и групповым поступением требований// Вестник Российского университета дружбы народов. Сер. прикл. мат. и информатика. - 1996. - N 2. -С. 100 - 109.

30. Печинкина O.A. Стационарное распределение очереди в системе Mk/G/l с инверсионной вероятностной дисциплиной обслуживания// Автоматика и телемеханика. 1996. - N -7. -С. 105 - 114.

31. Печинкина O.A. Стационарные вероятности состояний в системе MAP\G\1 с инверсионной вероятностной дисциплиной обслуживания// Автоматика и телемеханика. 2000. -N 1. - С. 98 - 104.

32. Рыков В.В. Управляемые СМО// Итоги науки и техники. Сер. Теория вероятностей. Математическая статистика. Теоретическая кибернетика. - 1974. - Т. 12.

33. Таташев А.Г. Инверсионная дисциплина обслуживанияв одноканальной системе с вероятностным приоритетом// В кн.: XLIII Всесоюзная научная сессия, посвященная Дню радио (НТОРЭС им. A.C. Попова). Тезисы докладов. Ч. 1. - М., 1988. - С. 55.

34. Таташев А.Г. Многоканальная система массового обслуживания с потерями кратчайших заявок// В кн.: Математические методы исследования сетей связи и сетей ЭВМ. Тезисы докладов. Витебск, январь февраль 1990. - С. 133 - 144.

35. Таташев А.Г. Многоканальная система массового обслуживания с потерями кратчайших требований// Автоматика и телемеханика. 1991. - N 7. - 187 - 189.

36. Таташев А.Г. Одна дисциплина обслуживания с разделением процессора// Автоматика и вычислительн. техника. -1993. N 6. - С. 27 - 32.

37. Таташев А.Г. Одна инвариантная система массового обслуживания// В кн.: III Всесоюзное совещание по распределенным автоматизированным системам массового обслуживания (4-7 сентября 1990 г.). Тезисы докладов. М., 1990. - С. 185 - 187.

38. Таташев А.Г. Одна инверсионная дисциплина обслуживания в одноканальной системе с разнотипными заявками// Автоматика и телемеханика. 1999. - N 7. - С. 171 - 181.

39. Таташев А.Г. Одна инверсионная дисциплина обслуживания с групповым поступлением// Автоматика и вычислительн. техника. 1995. - N 1. - С. 53 - 59.

40. Таташев А.Г. Одна система массового обслуживания с инвариантной дисциплиной// Автоматика и телемеханика. -1992. N 7. - С. 92 - 96.

41. Таташев А.Г. Одна система массового обслуживания с инвариантной дисциплиной// В. кн.: IV Всесоюзное совещание по распределенным системам массового обслуживания 22 -27 апреля 1991 г. Душанбе. Тезисы докладов. М., 1991. -С. 225 - 227.

42. Таташев А.Г. Одна система массового обслуживания с инвариантными вероятностями состояний// Кибернетика исистемный анализ. 1993. - N 5. - С. 183 - 186.

43. Таташев А.Г. Одноканальная система массового обслуживания с инвариантной дисциплиной// В кн: Применение математических методов и вычислительной техники при решении народнохозяйственных задач. Тезисы докладов. Гомель, 1986. - С. 67 - 68.

44. Таташев А.Г. Одноканальная система массового обслуживания с потерей заявки наибольшей длины// Кибернетика и системн. анализ. 1997. - N 3. -С. 187 - 188.

45. Таташев А.Г. Одноканальная система с инверсионной дисциплиной обслуживания// Техника средств связи. Сер. Системы связи. - 1986. - Вып. 2. - С. 11 - 15.

46. Таташев А.Г. Одноканальная система с инверсионной дисциплиной обслуживания с разнотипными заявками// Ки-бернет. и системн. анализ. 2000. - N 3. - С. 170 - 174.

47. Таташев А.Г. Приоритетная дисциплина в системе Mn\Gn\1\1// Кибернет. и системн. анализ. 1999. - N 5. -С. 181 - 184.

48. Таташев А.Г. Система инверсионного обслуживания с прерыванием группового поступления заявок// Автоматика и вычислительн. техника. 1996. - N 5. - С. 57 - 65.

49. Таташев А.Г. Система массового обслуживания с групповым поступлением заявок// Кибернетика и системн. анализ. 1995. - N 6. - С. 163 - 165.

50. Таташев А.Г. Система массового обслуживания с переменной интенсивностью входного потока// Автоматика и телемеханика. 1995. - N 12. - С. 78 - 84.

51. Таташев А.Г. Система массового обслуживания GI\Hr\1\0 с потерей заявки максимальной длины// В кн.: Тезисы докладов 9-й Белорусской зимней школы-семинара по теории массового обслуживания/ Минск, 1993. С. 95.

52. Таташев А.Г. Система массового обслуживания GI\Hr\1\0 с потерей заявки максимальной длины// Кибернетика и системн. анализ. 1994. - N 2. - С. 188 - 182.

53. Таташев А.Г. Система обслуживания GI\M\1\0 с потерей заявки максимальной длины// В кн. Белорусское научно-техническое совещание "Сети связи и сети ЭВМ как модели массового обслуживания" (Гродно, январь 1991). С. 119.

54. Таташев А.Г. СМО с инвариантной дисциплиной// Техника средств связи. Сер. Системы связи. - 1991. - Вып. 6. -С. 29 - 33.

55. Тихоненко О.М. Определение характеристик суммарного объема требований в однолинейных системах обслуживания с абсолютным приоритетом// Автомат, и телемех. -1999. N 8. - С. 181-188.

56. Тихоненко О.М. Распределение суммарного объема в однолинейной системе с экспоненциальным обслуживанием и рекуррентным входным потоком// Автомат, и телемех. 1999. -N 7. - С. 80-84.

57. Тихоненко О.М. Системы обслуживания требования случайной длины с ограничениями / / Автоматика и телемеханика. 1989. - N 9. - С. 159 - 162.

58. Яшков С.Ф. Анализ очередей в ЭВМ. М.: Радио и связь, 1989. - 216 с.

59. Яшков С.Ф. Анализ системы с приоритетным разделением процессора// Автоматика и вычислительная техника. -1984. N 3. - С. 29 - 38.

60. Яшков С.Ф. Математические вопросы теории систем обслуживания с разделением процессора// Итоги науки и техники. Сер. Теория вероятностей. Математическая статистика. Теор. кибернетика. - ВИНИТИ. - Т. 29. - 1990. - С. 3-82.

61. Яшков С.Ф. О дисциплине преимущественного разделения процессора требованиями с наименьшей обслуженной длиной/ / Техника средств связи. Сер. АСУ. - 1978. - Вып. 2. -С. 51-61.

62. Kleinrock L. Time-sharing systems: a theoretical treatment// Assos. Comput. Mash. 1967. - V. 14. - N 2. - P. 242 - 251.

63. Kooper R., Nico Shun-Chen. Benes formula for M\G\1 —

64. FIFO explained by preemptive-resume LIFO// J. of Applied Probability. 1986. - V. 23. - N 2. - P. 550 -554.

65. Olivier G. Kostenminimale Prioritäten in Wartesystemen vom Typ M\G\1// Elektronische Rechenanlagen 1972. - B. 14. -N 6. - S. 262 - 271.

66. Schräge L. A proof of optimality of the shortest remaining time discipline// Operations Research, 1968. N 3. - P. 687 -690.

67. Schräge L. The queue M\G\1 with feedback to lower priority queues// Management Science. 1967. - V. 13. - N 7. - P. 466 -474.

68. Van Dijk N.M. A LCFS finite model with batch input and non-exponential service// Stochast. Prosseses and their Ap-plicat. 1989. - V. 33. - N 1. -P. 123 - 129.

69. Van Dijk N.M. Queueing systems with restricted workload. An explicit solution// J. of Applied Probability. 1990. - V. 27. -N 2. - P. 393 - 400.