Модели обслуживания территориально распределенных объектов тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

ВВЕДЕНИЕ

ГЛАВА I. ОБСЛУЖИВАНИЕ ДВУХ УДАЛЕННЫХ ЭЛЕМЕНТОВ.

СИСТЕМА

Введение

§ I. Постановка задачи. Схемы маршрутных дисциплин

§ 2. Производительность ремонтной бригады, производительность ремонтной бригады во время функционирования

§ 3. Производительность ремонтной бригады во время движения

§ 4. Среднее время ожидания ремонта

§ 5. Абсолютный приоритет первого элемента. Третья маршрутная схема

§ 6. Примеры

§ 7. Вспомогательная задача

ГЛАВА П. ОБСЛУЖИВАНИЕ ПУАССОНОВСКИХ ПОТОКОВ ЗАЯВОК, ПОСТУПАЮЩИХ НА ДВА УДАЛЕННЫХ ПУНКТА. СИСТЕМА-2, СИСТЕМА

Введение

§ 8. Постановка задачи. Описание систем-2,

§ 9. Предварительные результаты

§ 10.Производительность ремонтной бригады во время движения и во время функционирования

§ II.Вспомогательные величины для определения стационарного времени ожидания обслуживания в системе

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

ВОЗВРАЩЕНИЯМИ РЕМОНТНОЙ БРИГАДО НА БАЗУ

Введение

§ 12. Постановка задачи. Общие результаты

§ 13. Расположение пунктов поступления заявок на прямой

§ 14. Расположение пунктов поступления заявок на плоскости

§ 15. Расположение пунктов поступления заявок в вершинах неориентированного графа

ГЛАВА 1У. ОДНА МОДЕЛЬ ТЕХНИЧЕСКОГО ОБСЛУЖИВАНИЯ

ГОРОДСКОГО ПАРКА ВЫЧИСЛИТЕЛЬНЫХ МАШИН

§ 16. Описание модели. Постановка задачи

§ 17. Средний суммарный штраф. Эвристический алгоритм

В задачах, решаемых теорией надежности и теорией массового обслуживания, в основном предполагается, что прибор после обслуживания (или прерывания обслуживания) одного требования сразу приступает к обслуживанию очередного, хотя на практике встречается немало систем, в которых это предположение не выполняется. Например, ЭВМ, работающая в режиме разделения времени. В таком случае после прерывания одной программы происходит запись ее данных и чтение данных очередной программы. Подобные системы в литературе получили название систем массового обслуживания (СМО) с "разогревом" [2-4] ,[25] или ориентацией [5-12, 18, 25], В этих работах (кроме [18]) считается, что обслуживающий прибор и поступающие заявки совмещены, и периоду "разогрева", ориентации (переключения, переналадки) придается физический смысл и математическая формализация, которые не соответствуют времени передвижения обслуживающего прибора от одной заявки к другой по некоторому пути.

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

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

Это и определяет актуальность и практическую значимость темы диссертации.

При изучении систем территориально распределенных объектов можно рассматривать разные модели обслуживания и управления движением обслуживающей системы - одной или нескольких ремонтных бригад (РБ). Например, можно предполагать или не предполагать существование центров базирования РБ и их обязательное периодиче ское возвращение в центры; можно рассматривать случаи одной или нескольких РБ, по-разному конкретизировать стохастическую структуру процесса появления вызовов на обслуживание, выбщ>аТ|Ь разные критерии качества управления и т.д. В работах [13, 14] рассматривается система П объектов, которая обслуживается (инспектируется) одним обслуживающим комплексом (ОК). В [13] после проведения инспекции ¿-го объекта с вероятностью Щ инспектируется ^ -к. функционирование системы определяется выбором чисел Ду для каждой пары I , у . При этом стационарная частота инспекций каждого объекта должна быть равна заданной, а средняя длина пути между двумя инспекциями - минимальной. В [14] рассматриваются только простые циклические стратегии, при которых ОК за один цикл посещает каждый объект по разу. Минимизируется средний суммарный ущерб, который с заданными интенсивностями накапливается в отсутствие ОК на каждом объекте. В [15, 16] изучается модель управления в дискретные моменты времени подвижным обслуживающим объектом, перемещающимся в системе, в которой возникают заявки, имеющие случайные координаты, распределенные в некоторой области. Несколько моделей размещения станций обслуживания в городе изучается в [17]. Учитывается возможность перемещения станций при изменении интенсивности движения по городским коммуникациям (часы "пик" и др.). Наиболее интересные результаты получены в ¿18, 19], где исследуется обслуживание вызовов, распределенных в пространстве, одним подвижным обслуживающим прибором. В [19] также решается задача оптимального размещения станций обслуживания возникающих вызовов.

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

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

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

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

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

Рассмотрена одна модель технического обслуживания городского парка вычислительных машин. Оптимизация маршрута РБ может быть проведена методом ветвей и границ. Предложен также простой эвристический алгоритм. Модель использована в СНПО "Алгоритм".

Основные результаты диссертации были доложены и обсуждены на семинарах лаборатории "Исследование операций" ВЦ АН СССР, на заседаниях кафедры "Большие системы" ЖГИ, на научно-технической конференции МФТИ (1981г.).

По своей структуре диссертация делится на введение, четыре главы, список литературы и приложение.

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

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

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

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

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

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

- 8

П.6), (П.п.1.3), (П.пп.1.3,1.4).

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

- 1 -е-Ъх ^

Р/ %с '¿¡¿С*)

Е - - математическое ожидание с.в. к. ; С

Ь2 г. - второй момент с.в. ^г. ; г-£ б (- преобразование Лапласа-Стилтьеса

Ф.р.

А ~ + Д а - жаэс{а,€}? алё■= уши/а^ запись

Р, ) Ю означает, что

J р,>0,р^>0

Диссертационная работа выполнена в рамках ГЬсбюджетной темы ВЦ АН СССР "Разработка комплексной модели и принципов проектирования систем связи с большим периодом создания"("Такт-1") с номером государственной регистрации: 0182.7 043938.

- 9

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

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

2. В системе, состоящей из двух удаленных друг от друга пунктов, на которые поступают пуассоновские потоки заявок, рассмотрено два типа обслуживания: а) заявки обслуживаются РБ на пунктах поступления, б) поступившие на пункты заявки впоследствии перевозятся РБ к обслуживающим центрам системы. Показатели эффективности маршрутных схем найдены в замкнутой форме.

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

4. Исследована одна модель технического обслуживания городского парка вычислительных машин. Оптимизация маршрута РБ может быть проведена методом ветвей и границ. Предложен простой эвристический алгоритм. Модель использована в СНПО "Алгоритм" .

1. Климов Г.П. Стохастические системы обслуживания., М.: Наука, 1966, 244 с.

2. Даниелян Э.А. Однолинейные стохастические системы обслуживания с приоритетами. Ротапринт ВЦ МГУ, статистика и стохаст. сист., вып.7, 1969.

3. Даниелян Э.А., Димитров Б.Н. Обслуживание с изменяющимися приоритетами и "разогревом". "Уч.зап.ЕрГУ", 1971, № I, с.3-10.

4. Гнеденко Б.В., Даниелян Э.А., Димитров Б.Н., Климов Г.П., Матвеев В.Ф. Приоритетные системы обслуживания. М.:Изд. МГУ, 1973, 448 с.

5. Климов Г.П., Мишкой Г.К. Приоритетные системы обслуживания с ориентацией. М.: Изд.МГУ, 1979, 223 с.

6. Толмачев А.Л. Обслуживание нескольких потоков со случайным переключением. Изв. АН СССР. Техн.кибернет., 1979, № 5, с.107-114.

7. Волковинский М.И., Кабалевский A.M. Анализ приоритетных очередей с учетом времени переключения. М.: Энергоиздат,1981, 168 с.

8. Драгалин В.П., Мишкой Г.К. Обслуживание со смешанным приоритетом и ориентацией. Изв. АН СССР. Техн.кибернет., 1984,3, с.166-172.

9. Gaver D.P. Competitive queuing: idleness probabilities under

10. Priority disciplines» J.Roy Stat .Soc., 1963» B.25, N2 489-499).,

11. Gaver D.P. A comparison of queue disciplines when service orientation times occur, Nav. Res. Logistics Quart.,1963, V.10 (219-235).

12. Mevert P.A, Priority system with setup times, Oper, Res,, 1968, v.16, N3.

13. Sykes I.S. Simplified analysis of an alternating priority queuing model with setup times,-Oper,Res.,1970,V,18, U 6,

14. Deaman C, and Klein M, Surveillance of Multi-Component Systems s A Stochastic Travelling Salesman's Problem, Naval Research Logistics Quarterly,V.13, N2, 1966 (103-111).

15. Рубальский Г.Б. Модель обслуживания удаленных объектов. -Изв.АН СССР. Техн.кибернет., 1980, с.86-92.

16. Гордиенко Е.й. Модель управления обслуживающим объектом в территориально распределенной системе. I. Изв. АН СССР, Техн.кибернет., 1980, № 6, с.77-85.

17. Гордиенко Е.И. Модель управления обслуживающим объектом в территориально распределенной системе. П. Изв. АН СССР. Техн.кибернет., 1981, № I, с.I03-II0.

18. Веппап О,, Larson R,, Odoni A, Developments in network location with mobile and congested facilities, European Journal of Operation Research, V,6, N2, 1981 (104-116).

19. Назаров Л.В. Система обслуживания с ориентацией. Изв.АН СССР. Техн.кибернет., 1981, № 4, с.131-135.

20. Назаров Л.В., Смирнов С.Н. Обслуживание вызовов, распределенных в цространстве. Изв. АН СССР. Техн.кибернет.,1982, & I, с.95-99.

21. Ashcroft Н. The productivity of several machines under the care of one operator.-J.Roy.Stat.Soc,»Series B,12,1950(145-1. OT 151);

22. Blom G. Some contribution to the theory of machine interference, Biometrica, 50, 1963 (135-143).

23. Ушаков И.А., Климов А.Ф. Одна задача выбора оптимальной дисциплины обслуживания. Изв. АН СССР. Техн.кибернет., 1966, & 2, с.40-44.

24. Правоторова H.A. К определению оптимальной дисциплины обслуживания в системе с разнотипными конечными источниками. -В сб. "Теория и средства автоматики". М.:Наука, 1968, с. 199-204.

25. Абрамов А.Х., Агаларов Ч.С., Бронштейн О.И., Правоторова H.A. Об оптимальной последовательности обработки информации в системах централизованного управления. В сб. "Адаптивные системы. Большие системы", М.: Наука, 1971, с.416-423.

26. Джейсуол Н. Очереди с приоритетами. М.: Мир, 1973, 279 с.

27. Перлов Ю.М. Применение метода пробных функций в задаче выбора оптимальной дисциплины обслуживания. Изв. АН СССР. Техн.кибернет., 1981, №2, с.224-229.

28. Перлов Ю.М. Задача оптимизации дисциплины обслуживания элементов подвижным ремонтным устройством. Надежность и контроль качества, 1984, № 4, с.28-33.

29. Сильвестров Д.С. Полумарковские процессы с дискретным множеством состояний. М.: Сов.радио, 1980, 272 с.

30. Гаджиев А.Г. Случайное движение частиц по кольцу. Доклады АН Аз.ССР, 1974, В 10, с.8-11.

31. Гаджиев А.Г. Модель движения частиц по замкнутому контуру без обгона. Изв. АН СССР. Техн.кибернет., 1976, № 5, с. 79-84.

32. Беляев Ю.К., Гаджиев А.Г., Громак Ю.И., Дутина Т.Н. Сравнительный анализ простейших систем вертикального транспорта.-Изв.АН СССР. Техн.кибернет., 1977, № 3, с.97-103.

33. Моисеев Н,Н., Иванилов Ю.П., Столярова Е.М. Методы оптимизации. М., Наука, 1978, 352 с.

34. Колмогоров А.Н., Фомин С.В. Элементы теории функций и функционального анализа. М.: Наука, 1976, 544 с.

35. Гусейнов Б.А., Перлов Ю.М. Одна задача технического обслуживания территориально распределенных объектов. Изв. АН СССР, Техн.кибернет., 1983, $ 6, с. 98-102.

36. Hakimi S.L. Optimum Distribution of Switching Centers in a Communication network and Some Related Graph Theoretic Problems, Operations Research, V.13» N3, 1965 (462-475)»

37. Кристофидес H. Теория графов. M.: Мир, 1978, 432 с.

38. Майника Э. Алгоритмы оптимизации на сетях и графах. М.: Мир, 1981, 323 с.

39. Little I.D» et al. An Algorithm for the Travelling Salesman Problem. Operations Research, V.11, 1963 (972-989).