|
Оглавление
Предисловие к третьему изданию
Скромный труд по подготовке сего издания с благоговением
посвящаю светлой памяти дорогих мне людей Бориса Владимировича
и Натальи Константиновны Гнеденко
И.Н.Коваленко Книга "Введение в теорию массового обслуживания" впервые была издана физико-математической редакцией издательства "Наука" в 1966 году. В 1987 году вышло 2Не издание, переработанное и дополненное. Книга вызвала большой интерес математиков и инженеров, четыре раза переиздавалась за рубежом (в последний раз в 1989 году издательством "Биркхойзер" в Бостоне). Мне представляется, что несмотря на появление многих новых книг, наша с Б.В.Гнеденко книга сохранила свое значение и поныне, благодаря мастерски написанным Борисом Владимировичем главам 1 и 2, которые могут служить начальному (но строгому) изучению теории, а также единообразному изложению более общих методов и принципов статистического моделирования систем. В настоящее издание включены: обзор новых работ, очерк о деятельности Б.В.Гнеденко в области теории массового обслуживания и теории надежности и список публикаций ученого в этой области. Для подготовки этого списка я воспользовался любезно предоставленным Дмитрием Борисовичем Гнеденко полным списком публикаций Бориса Владимировича. Другие отличия настоящего издания от предыдущего состоят в следующем. Весь текст книги внимательно прочитан. Устранены замеченные недочеты, в основном опечатки. Устранены неточности в доказательстве теоремы Кифера–Вольфовица, замеченные С.Асмуссеном и С.Г.Фоссом. Добавлены параграфы: § 1.9 "Сети массового обслуживания", § 2.12 "Специальные потоки однородных событий", § 4.10 "Системы с повторными вызовами", § 6.6 "Краткий обзор дальнейших работ" (связанных со статистическим моделированием систем массового обслуживания), пункт 8 § 5.5 "Кусочно-линейные сети массового обслуживания". § 5.7 дополнен пунктами 4 "Краткий обзор" и 5 "Асимптотическая инвариантность". Целью написания этого дополнительного материала было ознакомление читателя с новыми направлениями в теории массового обслуживания. Правда, охватить или даже перечислить все напрвления было невозможно – такая задача и не ставилась. На выбор материала оказали влияние мои научные интересы. Как и в предыдущем издании, список литературы к книге основывается на поалфавитном списке авторов на русском языке и самостоятельной нумерации работ каждого автора. Благодаря такому расположению цитированных работ было удобно включить новые работы в общий список. Пользуясь случаем, благодарю А.А.Левитскую за упорядочение литературы, О.А.Король за подготовку файлов нового текста. И.Н.Коваленко
Предисловие ко второму изданию
За два десятилетия, прошедшие со времени, когда было осуществлено первое издание нашей книги, теория массового обслуживания получила существенное развитие. Изучено большое число новых систем обслуживания традиционными методами марковских процессов и вложенных цепей Маркова. Интенсивно исследовались приоритетные системы (главным образом в связи с задачами современной вычислительной техники), системы телетрафика, управления запасами, транспорта, исследования операций. Наряду с марковскими методами развиты мощные эргодические методы, разработана теория устойчивости систем обслуживания. Метод статистического моделирования стал самым распространенным вычислительным методом решения задач теории массового обслуживания. Все это сделало необходимой значительную переработку книги. В ней появилась новая глава (гл.6) о статистическом моделировании. Добавлен материал о новых качественных методах, например, методе моментов обновления А.А.Боровкова, методе маркированных точечных процессов, методе укрупнения состояний случайных процессов и многих других. Однако основные математические модели, принятые в книге, остаются на уровне цепей и процессов Маркова. Таким образом, сохраняется доступность материала книги инженеру с хорошей математической подготовкой. В рамках марковских моделей доказательства теорем даются на достаточном уровне математической строгости. На отбор материала и ссылок определенное влияние оказали научные интересы как наши собственные, так и наших коллег. Исследования авторов по теории массового обслуживания и смежным областям всегда велись в тесном сотрудничестве со специалистами в различных областях приложений. Их живой интерес к теории массового обслуживания наряду с вниманием наших коллег – математиков и кибернетиков придавал нам решимость в выполнении настоящего издания. Существенные замечания, способствовавшие улучшению книги, были высказаны в разное время Г.П.Башариным, Ю.К.Беляевым, А.Д.Соловьевым, В.В.Рыковым, В.А.Ивницким, II. Ю.Кузнецовым. Авторы считают своим приятным долгом выразить всем им искреннюю благодарность. Б.В.Гнеденко,
И.Н.Коваленко
Из введения
Практические требования телефонного дела, физики и рациональной организации массового обслуживания (билетные кассы, магазины, автоматы и пр.) выдвинули в начале XX столетия ряд интересных математических задач нового типа. Первоначально эти задачи касались преимущественно вопросов обслуживания абонентов телефонной станции, расчета запасов магазинов для бесперебойного снабжения покупателей, а также установления наиболее рационального числа продавцов и касс в торговых предприятиях. На первичное развитие этой теории особое влияние оказали работы известного датского ученого А.К.Эрланга (1878–1929) – многолетнего сотрудника Копенгагенской телефонной компании. Основные его исследования в этой области относятся к 1908–1922 гг. С того времени интерес к проблемам, выдвинутым Эрлангом, необычайно возрос. В результате значительно увеличилось число математиков и инженеров, а также экономистов, интересующихся и разрабатывающих подобные проблемы. Оказалось, что задачи типа телефонных возникают в самых разнообразных направлениях исследований: в естествознании, в технике, экономике, транспорте, военном деле, организации производства. Требования практики выдвигают перед теорией массового обслуживания большое число новых постановок задач. Рассмотрение их необходимо для приложений, для постепенного приближения условий, в которых они решаются, к истинной картине изучаемых явлений; с другой стороны, это поучительно для выработки методов исследования и для создания стройной теории, которая даст возможность решать все эти частные задачи почти автоматически. В теории массового обслуживания особую роль играют случайные процессы, в особенности процессы Маркова и различные их обобщения. Прежде чем переходить к систематическому изложению материала книги, рассмотрим несколько областей применения, не вдаваясь при этом в подробности. Предположим, что на телефонную станцию в случайном порядке поступают вызовы. Если в момент поступления вызова на станции имеются свободные линии, то происходит подключение абонента к свободной линии и начинается разговор в течение того времени, которое необходимо для его завершения. Если же на станции все линии заняты, то возможны различные системы обслуживания абонентов. В настоящее время особенно хорошо разработаны две системы обслуживания: система с ожиданием и система с потерями. При первой системе обслуживания вызов, поступивший на станцию и нашедший все линии занятыми, становится в очередь и ожидает, когда все поступившие ранее требования будут обслужены. При второй организации работы каждый вызов, поступивший в момент, когда все линии заняты, получает отказ (происходит потеря требования) и все дальнейшее течение обслуживания происходит так, как будто бы этот вызов вообще не поступал. Заметим, что только что описанные системы обслуживания отличаются не только техническими особенностями, но и характером возникающих при их изучении задач. Действительно, для оценки качества обслуживания системой с ожиданием наиболее существенным является определение среднего времени ожидания начала обслуживания. Для систем с потерями время ожидания не представляет ни технического, ни математического интереса. Здесь важна другая характеристика – вероятность отказа (потери требования). Но если во второй постановке задачи вероятность отказа дает достаточно полное представление о том, на что можно рассчитывать при данной организации и технике обслуживания, то в первой задаче положение оказывается более сложным. Средняя длительность ожидания является важной, но не исчерпывающей характеристикой работы систем. Весьма существенно выяснить также возможный разброс фактических длительностей ожидания около их среднего значения. Далее, представляет интерес средняя длина очереди и распределение длины очереди. Важно также выяснить, насколько загружены обслуживающие приборы. Нет нужды говорить, что ситуация, которая создается около театральной кассы (как, впрочем, и около иной кассы), когда в нее обращаются за билетами, весьма напоминает описание системы обслуживания абонентов на телефонной станции. Если только в первоначальной постановке задачи шла речь о телефонных линиях, то теперь вопрос касается занятости кассира. Стремление рационально обслуживать потребителей приводит к необходимости изучения закономерностей образования очередей. Знание этих закономерностей должно, в частности, помочь решению вопроса о числе касс, которые рационально установить для продажи билетов на железнодорожной станции или в магазине. Содержание каждой кассы вызывает некоторые расходы, но и потеря требований также наносит определенный ущерб. Возникает вопрос о разыскании некоторого оптимума. Быть может, в экономическом отношении еще важнее вопрос организации на крупных предприятиях пунктов выдачи инструмента. Если такой пункт один, то квалифицированные рабочие теряют много времени на получение необходимого им инструмента и, кроме того, простаивают станки, которые могли бы в это время работать. Если же таких пунктов много, то их работники будут слабо загружены. Само собой разумеется, что только что затронутые вопросы имеют общий интерес и возникают при расчете пропускной способности аэропортов, подъездных путей, шлюзов, портовых причалов, больниц и пр. В тридцатые годы XX века в связи с автоматизацией станков в промышленности наметился переход на обслуживание одним рабочим нескольких станков. Станки в случайные моменты времени в силу тех или иных причин выходят из строя и требуют к себе внимания рабочего. Длительность операции по приведению станка в порядок, вообще говоря, не постоянна и является случайной величиной. Спрашивается, как велика вероятность того, что в определенный момент времени (при заданном режиме работы станка и рабочего) будет ожидать обслуживания то или иное число станков. Дальнейшие естественные и важные для практики вопросы таковы: как велико среднее время простоя станков при том или ином числе станков, порученных рабочему? Сколько станков при заданной организации труда экономически оправдано поручить одному рабочему? Как рациональнее организовать обслуживание: поручить ли n станков одному рабочему или ns станков s рабочим? Мы не станем сейчас продолжать перечисление дальнейших вопросов, которые возникают при глубоком анализе проблемы обслуживания нескольких станков. Известно, что в ряде отделов современного естествознания, в частности в ядерной физике, широко используются так называемые счетчики Гейгера–Мюллера. Одна из особенностей работы этого прибора состоит в том, что частица, попавшая в счетчик, вызывает в нем разряд. В первом приближении можно считать, что такой разряд продолжается некоторое определенное время т, в течение которого вновь попадающие в счетчик частицы уже не регистрируются счетчиком. По этой причине счетчик показывает, как правило, не истинную картину, а несколько искаженный ход явлений, в связи с чем возникает задача построения поправок к показаниям счетчиков. На первое место при этом выдвигается подсчет вероятности потерь того или иного числа частиц при регистрации их счетчиком за определенный промежуток времени t. Другая важная задача для многих конкретных вопросов состоит в том, чтобы по показаниям счетчика восстановить истинный поток частиц, поступающий в счетчик. Для многих реальных задач научного, производственного и экономического характера естественны не только задачи, в которых рассматривается обслуживание с потерями и ожидание без ограничения времени. В самом деле, зачастую мы отказываемся от обслуживания только из-за возможной длительной задержки с началом обслуживания. Так, если в очереди к продавцу имеется более пяти покупателей, то порой мы уходим из магазина и откладываем предполагаемую покупку. Точно так же, сделав заказ на междугородный телефонный разговор, мы нередко ограничены временем и предупреждаем, что если разговор не будет дан до определенного момента, то наше требование должно быть снято. Несколько иная ситуация может создаваться, когда ограничено не время ожидания, а время пребывания в системе обслуживания. С такой постановкой задачи приходится встречаться при продаже скоропортящихся продуктов: от момента изготовления до употребления должно пройти не более чем т единиц времени, так как иначе эти продукты теряют свои ценные качества и могут представлять угрозу для здоровья потребителя. Другой реальной иллюстрацией такой постановки вопроса является обслуживание лиц, попавших в уличную катастрофу. Для них время пребывания в системе обслуживания ограничено и притом ограничено случайной величиной т, поскольку способность лица дождаться конца обслуживания зависит от полученной травмы и от его физических качеств. Под временем нахождения в системе обслуживания мы должны понимать все время от момента аварии до момента излечения (т.е. ожидание кареты скорой помощи, транспортировку, осмотр врачом, операцию и излечение). Хорошо известно, что не каждое потерпевшее лицо способно дождаться конца обслуживания, а иногда даже его начала. Таким образом, вполне естественна постановка следующей группы близких по характеру задач. Требования, поступающие для обслуживания, остаются в очереди, если число ранее прибывших и ожидающих обслуживания требований не превосходит заданного числа k, в противном случае требование теряется. Каждое требование остается в обслуживающей системе не более чем время т, даже если началось его обслуживание. Возможна также и третья постановка вопроса: ограничено время ожидания величиной т, но если до истечения этого срока обслуживание началось, то оно доводится до конца. Во всех трех случаях особый интерес представляет вычисление среднего числа потерь за определенный промежуток времени, среднего времени ожидания начала обслуживания или потерянного времени на ожидание. Во второй постановке задачи естественно различать среднее число потерь не совсем обслуженных требований, обслуживание которых все-таки было начато. В только что обрисованных, но еще недостаточно строго математически поставленных задачах мы исходили из предположения, что обслуживающие приборы обладают абсолютной надежностью и сами никогда не выходят из рабочего состояния. Известно, что такое положение несколько идеализирует реальные системы. В результате возникает естественная и важная задача учета влияния на эффективность системы обслуживания порчи обслуживающих приборов. Возможное разнообразие практически интересных вопросов здесь совершенно не ограничено. Для примера укажем на такую задачу: самолеты после каждого вылета проходят профилактический осмотр, а затем с некоторой вероятностью а направляются в ремонт или с вероятностью 1 – alpha возвращаются в строй действующих. Учет выхода обслуживающих приборов из рабочего состояния для некоторых постановок задач можно включить в иную задачу, которая получила название обслуживания с преимуществом. Эта задача состоит в следующем: в систему обслуживания поступает не один, а несколько потоков требований. Требования потоков с меньшими номерами пользуются преимущественным правом обслуживания и становятся при появлении в очередь впереди всех ранее поступивших требований с более высокими номерами породивших их потоков. Здесь приходится рассматривать две постановки вопроса: требование высокого ранга не прерывает обслуживания требований менее высоких рангов; требование высокого ранга прерывает уже проводящееся обслуживание более низкого ранга. Во втором случае приходится различать две возможности: при возвращении вытесненного требования в обслуживающий прибор предыдущая работа забывается и обслуживание начинается сначала; ранее произведенная работа не забывается. С обеими последними постановками вопроса приходится встречаться, например, в работе вычислительных машин. Назовем поломку или сбой машины преимущественным требованием, тогда могут представиться оба случая: предыдущая работа была проделана хорошо и вычисления после восстановления машины могут начинаться с того места, на котором они были прерваны; сбой машины ввел ошибку в предшествующие вычисления, их нужно проделать заново. Этим примером мы одновременно пояснили, как в систему обслуживания с преимуществом можно включить задачу учета поломки обслуживающих устройств. Задачи, в которых следует принимать в расчет преимущественные требования, встречаются постоянно: ремонтная бригада в первую очередь устраняет аварийную ситуацию, а потом выполняет текущий ремонт; к зубному врачу вне очереди принимаются больные с острой зубной болью и т.д. Можно указать множество других постановок задач реального содержания, которые в своей математической части сводятся к вопросам теории массового обслуживания. Но в столь подробном перечислении нет никакой необходимости, так как математическая теория не может претендовать на перечисление всех частных и даже только важнейших прикладных проблем, к которым она может применяться. Задача математической теории состоит в первую очередь в выработке общих методов, применимых не только к решению тех частных задач, на базе которых была начата ее разработка, но и множества других, быть может, даже очень далеких по своей формулировке от первоначальных. Об авторах
Выдающийся ученый в области теории вероятностей и ее приложений. Мировую известность ему
принесли исследования по теории суммирования независимых случайных величин. Одним из первых
среди отечественных ученых в середине 1930-х гг. начал развивать теорию массового обслуживания,
притом в ее прикладном аспекте. Создал на Украине всемирно известную школу теории вероятностей
и математической статистики, московскую школу теории массового обслуживания. С 1966 г. до конца
своих дней бессменно руководил кафедрой теории вероятностей механико-математического факультета
МГУ им. М.В.Ломоносова. Академик АН Украины (1948). Лауреат Государственной премии СССР (1979).
Известный ученый в области прикладной теории вероятностей, в особенности теории массового обслуживания, теории надежности, а также вероятностной комбинаторики. Ученик Б.В.Гнеденко. С середины 1950-х гг. активно работает в области теории массового обслуживания, особенно в таких ее аспектах, как метод дополнительных переменных и системы с малой нагрузкой. В 1960-х гг. работал в Москве; к этому периоду относится функционирование семинара по теории массового обслуживания и теории надежности при мехмате МГУ, руководимого Б.В.Гнеденко, А.Д.Соловьевым, Ю.К.Беляевым и И.Н.Коваленко. С 1971 г. работает в Киеве, бессменно руководя отделом математических методов теории надежности в Институте кибернетики им. В.М.Глушкова НАН Украины, действительным членом которой избран в 1978 г. Лауреат Государственной премии СССР (1979). |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||