Московский государственный университет

имени М. В. Ломоносова

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

ЗАХАРОВА ТАТЬЯНА ВАЛЕРЬЕВНА

ОПТИМИЗАЦИЯ

РАСПОЛОЖЕНИЯ В ПРОСТРАНСТВЕ

СИСТЕМ МАССОВОГО ОБСЛУЖИВАНИЯ

01.01.05 теория вероятностей и математическая статистика

Автореферат диссертации на соискание ученой степени кандидата физико-математических наук

МОСКВА 2008 г.

Работа выполнена на кафедре математической статистики факультета вычислительной математики и кибернетики Московского государственного университета имени М.В. Ломоносова.

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

Официальные оппоненты: доктор технических наук, профессор А. И. Костогрызов;

кандидат физико-математических наук, профессор С. Н. Смирнов.

Ведущая организация: Институт проблем информатики РАН.

Защита диссертации состоится 14 марта 2008 г. в 11 часов на заседании диссертационного совета Д 501.001.44 в Московском государственном университете имени М.В. Ломоносова по адресу: 119991, Российская Федерация, Москва, ГСП-1, Ленинские горы, МГУ, 2-й учебный корпус, факультет ВМиК, аудитория 685.

С диссертацией можно ознакомиться в библиотеке факультета ВМиК МГУ. С текстом автореферата можно ознакомиться на официальном сайте ВМиК МГУ имени М.В. Ломоносова http://www.cmc.msu.ru в разделе „Наука“-“Работа диссертационных советов“-“Д.501.001.44“.

Автореферат разослан " " 2008 г.

Ученый секретарь диссертационного совета профессор Н. П. Трифонов

1.

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

Актуальность темы. Очень многие задачи из разных областей техники и народного хозяйства удается сформулировать и решить с помощью теории массового обслуживания. Среди них можно выделить класс задач, к которому приводят такие реальные системы, где обслуживание производится территориально распределенными объектами [5,7,9]. В качестве примеров подобных систем можно привести работу такси [39,40], функционирование сборочной линии [28,41], движение автомобиля скорой помощи в соответствии с адресами поступающих вызовов, перемещение ремонтных бригад, устраняющих отказы в какой-либо территориально распределенной структуре типа сети связи [9,36,37], пожарных частей и т.п.

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

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

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

Первоначально задача по оптимизации расположения станций решалась для обслуживания конечного числа потребителей, адреса которых были известны, и сами станции могли располагаться в конечном числе точек заданного множества. В такой постановке задача была проанализирована Альфредом Вебером в 1909 году в работе "О штандорте индустрии". Им были введены такие понятия, как склад и штандортная фигура – многоугольник, вершинами которого являются n складов и потребитель. Решалась задача нахождения штандорта (размещения), минимизирующего транспортные издержки.

В сходной постановке, но в предположении, что станции могут располагаться в произвольных точках, задача оптимизации решалась И.В.Гирсановым, Б.Т.Поляком (1963 - 1965 г.г.).

К задачам оптимального размещения приводит и исследование знаменитой задачи коммивояжера, впервые поставленной в 1934 году. В каком порядке следует обойти n городов, чтобы замкнутый путь коммивояжера был кратчайшим? Эта задача является так называемой NPтрудной задачей, т.е. точное ее решение может быть получено только за экспоненциальное время. Переборный алгоритм для решения задачи является неэффективным при большом числе n, поэтому на практике пользуются эвристическими методами, такими, как метод ветвей и границ (1960 г.), метод генетических алгоритмов (1975 г.).

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

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

Исследованию описанных проблем посвящена данная диссертационная работа.

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

Научная новизна. Все основные результаты диссертации являются новыми и состоят в следующем:

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

- найдена предельная оптимальная плотность размещений;

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

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

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

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

Теоретическая и практическая значимость. Результаты диссертации носят как теоретический, так и практический характер. Полученные результаты могут быть применены при изучении реальных систем, перечисленных выше. Алгоритмы построения асимптотически оптимальных размещений могут быть реализованы на ЭВМ, в то время, как отыскание оптимальных размещений представляет собой достаточно сложную задачу численного анализа[42,43].

Апробация работы и публикации. По теме диссертации опубликовано 5 печатных работ. Результаты работы докладывались и обсуждались на научно-исследовательском семинаре по теории массового обслуживания кафедры математической статистики факультета Вычислительной математики и кибернетики МГУ (2007), на конференции "Распределенные автоматизированные системы массового обслуживания" (Кишинев, 1987), на научно-исследовательском семинаре Механико-математического факультета МГУ "Вероятностные методы в технике"(1988), на научно-исследовательском семинаре ИППИ АН СССР (1989), на XXVI Международном семинаре по проблемам устойчивости стохастических моделей (2007).

Структура диссертации. Диссертация состоит из введения, двух глав, разбитых на параграфы, списка литературы, содержащего 44 наименования, приложения. Общий объем работы - 106 страниц.

2. КРАТКОЕ СОДЕРЖАНИЕ ДИССЕРТАЦИИ

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

Определение 1. Размещением n станций в пространстве RN назовём множество {x1,..., xn } точек пространства R, в которых эти станции расположены.

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

Расстояние между точками u и v будем также обозначать (u, v).

Определение 2. Зоной влияния станции xi назовём множество Ci тех точек пространства R, для которых эта станция является ближайшей, т.е.

Точка пространства R, из которой поступает вызов, является случайной величиной с плотностью распределения p. Станции обслуживают вызовы только из своих зон влияния. Для оценивания оптимальности расположения этих станций задан критерий :

Определение 3. Размещение x = {x,..., x } называется оптиn мальным по критерию среди размещений x = {x1,..., xn }, если Задача заключается в нахождении оптимального размещения станций обслуживания.

Корректность определения 3 следует из теоремы 1 приводимой ниже.

оптимальное размещение x = {x,..., x }.

В рассматриваемом критерии параметр s можно выбирать из следующих соображений. Если s=1, то (x) = E min (, xi ) и задача своin дится к минимизации среднего расстояния от вызова до ближайшей к нему станции. Если s > 1, тогда оптимальным будет размещение, при котором не появляются слишком удаленные вызовы. При s < 1, наоборот, выгоднее размещать станции в точках с большой плотностью (в областях скопления вызовов).

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

Когда оптимальные размещения ищутся на плоскости (N=2), то расстояние определяется по евклидовой норме и норме 1 :

для u = (u1, u2 ), v = (v1, v2 ).

В N -мерном пространстве (N = 1, 2,...) расстояние будет определяться следующей нормой:

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

Определение 4. Диаметром множества A в метрическом пространстве называется число где – расстояние в данном пространстве.

Лемма 1. Если E||s <, то lim (x ) = 0.

Обозначим Dn (x) = max diam Ai, Ai = {u Ai : p(u) > 0}, где Ai – зона влияния станции xi на произвольном компакте G.

Лемма 2. Если lim (x) = 0, то lim Dn (x) = 0.

Лемма 3. Пусть x = {x1,..., xn } – размещение на выпуклом kугольнике S и зоны влияния Ci каждой точки xi этого размещения являются выпуклыми mi -угольниками. Тогда среднее арифметическое числа сторон многоугольников Ci оценивается следующим образом Введем функцию Лемма 4. Пусть в выпуклый k-угольник S помещается n точек x1,..., xn. Ci – зона влияния xi на S. Справедливо следующее неравенство где – правильный шестиугольник площади S/n с центром в нуле, R – положительное число, определяемое соотношением Замечание. Эта оценка является обобщением результата Л.Фейеша Тота [25].

Чтобы подчеркнуть с каким именно нормированным пространством мы работаем, будем обозначать пространства символами R0, R1, R, соответственно введенным нормам, 1,.

Рассмотрим случаи метрических пространств R1 и R.

Лемма 5. Если Q – измеримое по Лебегу подмножество метрического пространства, S – шар с центром в точке v из того же пространства и меры Лебега множеств Q и S равны, тогда для любой неубывающей на [0, ) действительной функции a(u).

следующее неравенство для любой неубывающей на [0, ) действительной функции a(u).

Введем следующие обозначения:

для пространства R где M6 – правильный шестиугольник единичной меры Лебега с центром в нуле;

для пространств R1 и R где E – шар единичной меры Лебега с центром в нуле.

Следующая теорема описывает предельное поведение критерия на последовательности оптимальных размещений.

Теорема 2. Если Es (0, ) <, функция p2/(2+s) интегрируема по Лебегу, то для всякой последовательности оптимальных размещений {x } где Для пространства R1 справедливо аналогичное утверждение. Основное отличие при доказательстве заключается в следующем: оптимальные размещения зависят от выбранной системы координат, при этом константа C определяется по формуле Предельное поведение критерия будет аналогичным и в пространстве R, с константой C определяемой по формуле Следующая теорема описывает еще одно асимптотическое свойство оптимальных размещений.

Теорема 3. Если E||s <, функция pN/(N +s) интегрируема по Лебегу, A – измеримое по Лебегу множество из RN, тогда для всякой последовательности оптимальных размещений {x } в R0, R1 или R где x = x A, |x | – число элементов в x.

Определение 5. Пусть F – некоторый критерий для размещений.

Размещение x = {x1,..., xn } называется асимптотически оптимальным первого порядка или просто асимптотически оптимальным, если где x = {x,..., x } – оптимальное размещение по критерию F.

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

Отрезок и его длину будем обозначать одной и той же буквой.

В следующей лемме сформулированы необходимые условия оптимальности размещения.

Лемма 7. Пусть [d1, dn+1 ] – носитель плотности распределения p и p – дифференцируема. Тогда для всякого оптимального размещения x = {x,..., x } выполняются соотношения где i = [di, di+1 ] – зона влияния станции x на носителе плотности, pi = p(di ), pi = p (di ).

Следствие. Длины зон влияния станций на носителе плотности при оптимальном размещении x = {x,..., x } имеют порядок O( n ).

Определение 6. Размещение x = {x1,..., xn } будем называть асимптотически оптимальным второго порядка по критерию, если где x = {x,..., x } – оптимальное размещение по критерию.

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

Теорема 4. Если плотность p имеет непрерывную вторую производную, то для всякой последовательности оптимальных размещений {x } Построим последовательность {x} – асимптотически оптимальных размещений второго порядка. Такие размещения не являются единственными. Укажем один из возможных алгоритмов построения асимптотически оптимальных размещений второго порядка x = {x1,..., xn }.

Исходный отрезок G разобьем на непересекающиеся множества Gi, i = 1, 2,..., k так, чтобы выполнялись следующие условия:

числа ni, определяемые соотношениями должны быть натуральными.

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

В параграфе 1.4 первой главы рассматривается специальный класс нормированных пространств.

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

Если в пространстве с нормой x – оптимальное размещение, то в пространстве с нормой размещение, полученное отображением h размещения x, будет обладать тем же свойством оптимальности.

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

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

Рассмотрим, например, задачу, возникающую при работе больниц.

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

Вначале рассматривается проблема оптимизации расположения станций обслуживания по критерию стационарного среднего времени ожидания начала обслуживания для систем с дисциплиной обслуживания FIFO.

Размещения x = {x1,..., xn } оцениваются по критерию оптимальности при условии, что max i i1 < 1, где i – интенсивность потока вызовов, поступающих на станцию xi, i1, i2 – соответственно первый и второй моменты времени обслуживания на xi.

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

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

В этом случае исследованы асимптотические свойства оптимальных размещений по критерию при условии, что max i i1 < 1, где i – интенсивность потока вызоin вов, поступающих на станцию xi, Bi – функция распределения времени обслуживания на xi, i1, i2 – соответственно первый и второй моменты времени обслуживания на xi.

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

Предполагается, что станции функционируют как независимые системы массового обслуживания типа M |G|1, тогда их средняя суммарная длина очереди L(x) при размещении x при условии, что загрузка каждой станции меньше единицы, т.е. max i i1 < 1, определяется по формуле Для этой модели получены следующие результаты.

Теоpема 5. Если плотность p ограниченная, интегрируемая по Лебегу функция, E||2 < и интенсивность входящего потока (n) изменяется так, что тогда для всякой последовательности оптимальных размещений {x } справедливы равенства где A – произвольное измеримое по Лебегу множество.

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

Теоpема 6. Если плотность p ограничена, интегрируема по Лебегу, E||2 < и интенсивность входящего потока требований изменяется так, что тогда для всякой последовательности оптимальных размещений {x } для любого измеримого по Лебегу множества A.

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

3. СПИСОК ПУБЛИКАЦИЙ АВТОРА ПО ТЕМЕ ДИССЕРТАЦИИ

1. Новикова Т.В. Оптимальные размещения в пространстве // Вопр.

вычисл. мат. и програм. обесп. ЭВМ.- М., 1984, с.95-100. Деп. в ВИНИТИ, 23.11.84, № 7484-84.

2. Захарова Т.В. Оптимальные размещения для систем с оптимальной дисциплиной обслуживания.- Вест. Моск. ун-та, сер.15. Вычисл. матем. и киберн., 1987, № 4, с.67-69.

3. Захарова Т.В. Оптимизация расположения станций обслуживания на плоскости// Изв. АН СССР. Техн.киберн. 1987. №6. с.83-91.

4. Захарова Т.В. Оптимальные размещения для систем с оптимальной дисциплиной обслуживания.- Случайный анализ: Сб. научных статей.- М.: Изд-во Моск. ун-та, 1987, с.43-50.

5. Захарова Т.В. Оптимальные размещения систем массового обслуживания с дисциплиной обслуживания FIFO.- Вест. Моск. ун-та, сер.15. Вычисл. матем. и киберн., 2007, № 4, с.32-37.