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

Введение

ГЖАБ1А1 ЗАДАЧИ ОБСЛУЖИВА]ШВД С ОГРАНИЧЕНИМЖЙ НА НЕВРЕМЕННОЙ РЕСУРС

§1. " Примеры задачи обслу>живания с ограничениями на невременной ресурс

§2. Формализация задач обслуживания с невременным ограничением на ресурс

§3. Теорема о разрешимости задачи обслу>хиванмя с ограничен&мми на невременной ресурс

§4. ТеореЕл1 а о разрешимости задачи обслуживания с ограничениями на невременной ресурс в матричном виде

ГЛАВА 11 ЖОГОТИШВЫЕ ЗАДАЧИ ОБСЛУЖИВАНИЯ С ОГРАНИЧЕБПЙШМй НА НЕВРЕМЕННОЙ РЕСУРС

§1. JLlpMMepibi многотишиых задач обслуживания с ограничениями на ресзфс

§2. МЬщность многотипных задач обслуживания с незременным ограничением на ресурс

§3. Формализация и постановка многотипных задач обслуживания с временным ограничением на ресурс

§4. Свойства многотипной задачи обслуживания с невременными ограничениями на ресурс

§5. Теорема о разрешимости многотинной задачи обслуживания с ограничениями на невременной ресурс

ГЛАВА III Б0РИМЕНЕК1ИЕ МНОГОТИПНЫХ ЗАДАЧ 05СЛУ}?К:ИВА1Л[йЯ К МОДЕЛИРОВАНИЮ ДЕЯТЕЛЬНОСТИ ОПТОВОЙ ФЕРМЫ SS

§1. Онйсание работы онтозой фирмы.

§2. Мощность оптовой фирмы и выполнимость работ.

§3. Алгоритм решения 30 оптовой фирмы.

§4. Ефимеры расчета и анализа деятельности оптовой фирмы. 104 ЗАЖЛЮЧЕНЕПЕ

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

Методам решения и анализа задач обслуживания и их математическим моделированием занимались многие отечественные специалисты: Е.С.Вентцель, В.С.Танаев, В.С.Гордон,

Т.К.Сиразетдинов, Р.Т.Сиразетдинов, Ш.Д. Амирханов,

И.С.Иваненко, В.В.Родионов, и другие. Среди зарубежных авторов можно назвать след}тощих: Р.В. Конвей, В.Л. Максвелт, Л.В. Миллер и других.

Исследование и развитие методов математического моделирования задач и систем обсл}'ЖИвания, к которым относится и тема данной диссертационной работы, является актуальной проб.темой современной науки и техники.

Как известно, в ряде работ достаточно подробно и-зз-т-хались вопросы использования рес}рсов при наложенных ограничениях.

В работе [26] ставятся две задачи: зАета потребности в отдельных видах рес}фсов и оптимального распределения рес}фса. Первая задача сводится к построению графиков потребления ресзфсов. Эти графики, показывая распределение потребности ресурсов во времени, позволяют сравнивать эту потребность с возможностями своевременного обеспечения этими ресурсами и могут слЛЛжить для оценки качества того или иного варианта расписания. Задачи распределения рес}фсов состоит в построении графиков потребления ресурсов всеми работами, оптимальных по принятоА'у критерию. Требуется найти такие продолжительности выполнения работы, при которых минимизирз-ется потребление ресзфса или такие интенсивности потребления реслфсов, при которых минимизируется суммарное превышение времени выполнения работ над директивными сроками их окончания.

В работе [41] встречается аналогичная постановка: при обслЗ''живании требований в каждый момент времени известно количество складируемого ресурса. Количество имеющегося ресурса задано в виде функции от времени. Эта функция является разностью функций прихода и расхода. Для обслзЛживания требования в каждый момент времени необходимо определенное количество складируемого рес}фса. Если количество имеющегося складируемого ресзфса превосходит потребность в этом ресЛфсе в каждый момент времени, то расписание называется допустимым по ресЛфсам, т.е. происходит сравнение межд}.' имеющимся и необходиь'гым количеством ресурса в каждый момент времени.

Часто возникающим на практике вопросам разрешимости задач обслз'живания, которые представляют собой требования выполнить некоторый обьем работ за определенный интервал времени, начиная с некоторого момента времени, посвящена работа [3".

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

Задача обслз'живания, с ограничениями на мощность типа равенства, с временным ограничением было введено в работе [2'.

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

Данная диссертационная работа посвящена моделированию и анализу обсл\'ЖИвающих систем, возможности или мощности которых на произвольных интервалах времени характериз}тотся всеми возможными объемами работ, которые может выполнить система. Эти возможности ог1заниченны имеющимися временными и невременными ресурсами.

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

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

1. Формализована и дана математическая постановка, пол}Аены необходиьАые и достаточные условия разрешимости задач обслуживания с невременным ресурсом, то есть когда ресурс или мощность системы при неполном использовании в данном интервале переносится на последующие интервалы времени. Рассмотрены однотипные и многотипные задачи обслуживания.

2. Выполнимость или невыполнимость однотипных работ сведена к решению системы некоторых линейных неравенств, а многотипных работ с ограничениями мощности - к решению систе]\1Ы нелинейных неравенств.

3. На основе доказанных теорем о необходимых и достаточных условиях выполнимости работ построен алгоритм анализа ра.зрешимости задач обслААживания, как процедлфы формирования матриц инцидентности графа, построенного в соответствии с определенными правилами ф)ормирования матриц заданной стрЛ'''ктзфы, неизменной для различных вариантов задач обслуживания.

Практическая ценность пол>А1енных наз-Ашых ре.зультатов в диссертации состоит в том, что они позволяют разработать инженерные методы и алгоритмы решения задач обслуживания.

Приведем краткое содержание глав:

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

ЗАКЛЮЧЕНИЕ.

В диссертационной работе получены следующие научные результаты:

1. Даны формализованные определения невременного ресурса, 1, т-мощности, последовательности 1, г-мощностей, элементарной задачи обслуживания (ЭЗО), последовательности ЭЗО, задачи обслз'живания (30), разрешимости ЭЗО обслз'живающей системой, выполнимости последовательности ЭЗО для однотипных и многотипных обслуживае]угых и обслуживающих систем.

2. Получены условия разрешимости однотипных задач обслуживания в спз'чае, если необходимьпй для .этого ресурс обсл}''живающей систеь/ы не является временем и может быть перемещен из одного временного интервала в цругой в случае его не использования.

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

4. Сформ}ширована и доказана теорема о необходиьмх и достаточных итовиях разрешимости многотипных задач обслуживания в случае гевременных ограничений на ресурс. Задача сведена к решению системы шнейных равенств и неравенств.

117

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

6. Построены модель функционирования оптовой фир№1 и алгоритм решения, позвогиющий определить выполнимость заданных обьемов работ при имеюш;ихся ресурсах.

1. Амирханов Ш.Д., Сиразетдинов Р. Т. Моделирование многорежимных систем обслуживания. Изв. вузов. Авиационная техника. 1995. N4. С.52-58.

2. Амирханов Ш.Д., Лагодюк А.Н. Матричный алгоритм анализа разрешимости задач обслуживания. Известия ВУЗов. Авиационная техника, 1998, №4, с. 76-79

3. Амирханов Ш.Д., Лагодюк А.Н. Выбор равномерного режима выполнения требований в задаче обслуживания. Статьи и тезисы докладов республиканской научной конференции молодых уАюных и студентов "Молодежь и .экономическая наука". Казань, 1998, с. 169-170

4. Амирханов Ш.Д., Лагодюк А.Н. Многотипнью задачи с невременными ограничениями на ресурс и их применение при анализе технологршеских процессов. Международная научно-практриеская конференция "Технология. Инновация. Качество." КазанъЛ999

5. Амирханов Ш.Д., Лагодюк А.Н. Условия разрешимости дискретных задач обслуживания КХТИ

6. Амирханов Ш.Д., Лагодюк А.Н. Анализ разрешимости однотипных задач обслуживания при невременных ограничениях мощности на примере служб ГСМ. Известия ВУЗов. Авиационная техника, 1999, №3, с. 69-71

7. Ашфорд П., Стентон Х.П.Р1., Р.1 }ф К.А. Функционирование аэропорта. Пер. с англ.- М.: Транспорт, 1991, 372с.

8. Воронов A.A., Петрушин Е.П. Решение задачи оптимального распределения ресурсов методом квадратичного программирования. Автоматика и телемеханика. 1965. Хо7. с.46-52

9. Вентцель Е.С. Исследование операций. М.: Сов.радио, 1972, 552с.

10. Голиков А.И., Деменчук В.И. Об оптимальном распределении ресурсов в планировании комплексов операций. Автоматика и телемеханика. 1969. №2. с.60-70.

11. Зуховицкий СИ., Радчик И.А. Математические методы сетевого планирования. М.:Наука, 1965, 317с.

12. Иваненко И.О., Сиразетдинов Р.Т. Р1атематическое описание задач пользователей авиационной транспортной системьг Изв. вузов. Авиационная техника. 1996. N2. с.94-99.

13. Изыскания и проектирование а.эродромов: Справочник. Г.И.Гпушков, В.Е.Тригони, И.А.Медников и др.; Под. ред. Г.И.Гл}'шкова.- М;.: Транспорт, 1990, 296с.

14. Канторович Л.В. Экономический расчет наилз'чшего использования ресурсов. М.: АН СССР, 1960

15. Козлов РРК., Шафранский В.В. Календарное планирование выполнения комплексов работ при заданной динамике поступления складируек'гых ресурсов. Известия АН СССР. Техническая кибернетика. 197Р №4, с.75-81; №5, с.38-43

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

17. Кустарева Е.В. Об одной задаче распределения ресурса. Рруды 29 научной конференции «Процессы управления и устойчивость». С-Петербург, 1998, с.343-345

18. Ловас Л., Шаммер Р1 Прикладные задачи теории гзафов. Реория паросочетаний в математике, физике, химии: Пер. с англ. -М.:Мир, 1998.- 653 с.

19. Максименков A.B. Формирование расписания с учетом ограничения на интенсивность потребления ресурса. Кибернетика, 1979, №6, с. 91-95

20. Михалевич B.C., Кукса А.И. Методы последовательной оптимизации. М.:Наука, 1983, 217с.

21. Неьгчинов B.C. Экономико-математические методы и модели.- М.: А&юль, 1965.

22. Основные положения по разработке и применению систем сетевого планирования и управления. М. :Статистика, 1974, 21 бс.

23. Разумихин Б.С. Задача об оптимальном распределении ресурсов. Автоматика и телемеханика. 1966. №12. с. 115-125.

24. Саати Т. Л. Элементы теории массового обслуживания и ее приложения. Пер. с англ. Е.Г.Коваленко. Под ред. И.Н.Коваленко. С предисл. акад. Б.В.Гнеденко. Изд. 2-е. ML: Сов.радио, 1971, 520с.

25. Сиразетдинов Р.Т. Математическое моделирование развития систе№1 однотипных объектов с учетом интенсивности их .эксплуатации (На примере самолетно-вертолетного парка). Изв. ВУЗов. Сер. "Авиационная техника". Казань, 1994, N 1, с.63-68.

26. Сиразетдинов Т.К. Основная задача управления и проектирования многорежимных технических объектов. Вестник КГТУ им. А.Н.Туполева, 1995, N1. с.7б-84.

27. Сиразетдинов Т.К. Динамическое моделирование экономических объектов Казань, "Фэн", 1996, 224с.

28. Сиразетдинов Т.К., Амирханов Ш.Д., Лагодюк А.Н. Анализ платежеспособности предприятия как задача обслуживания с невременным ограничением на ресурс. Вестник КГТУ им.А.Н.Туполева, 1998, №2, с. 50-53

29. Сиразетдинов Т.К., Шургин Ю.П. К задаче построения динамической модели экономического объекта с уАютом временной структуры фондов. Изв.вузов.Авиационная техника, 1981. N4. с.51-55.

30. Сиразетдинов Т.К. Функционирутощие системы и их моделирование. Изв.вузов. Авиационная техника, 1986. N 1. с.52-56.

31. Сиразетдинов Т.К. Методы решения многокритериальных задач синтеза сложных технических систем. М.: Машиностроение, 1988, - 1бОс.

32. Сиразетдинов Т.К. Основная задача управления и проектирования многорежимных технических объектов. Вестник КГТУ им. А.Н.Туполева, 1995, N1. с.76-84.

33. Сиразетдинов Т.К. Динамическая модель прогнозирования и оптимальное управление экономическим объектом. Изв.вузов. Авиационная техника, 1972. N4.

34. ТанаевВ.С. Теория расписаний М.; «Знание», 1988, 132с.

35. Танаев B.C., ШкАфба В.В. Введение в теорию расписаний. М.; «Наука», 1984, 382с,

36. Танаев В,С, Ковалев М,Я,, Шафранский Я.Ml. Теория расписаний. Групповые технологии, А1инск, 1998. - 290 с,

37. Уздемир А, П. Динамические целочисленные задачи оптимизации в экономике, М,: Изд. фирма "Физ. - мат. лит.", 1995. - 285с.

38. Хейт Ф. Математическая теория транспортных потоков. Пер. с англ.- М.: Мир, 1966, 286.

39. Blazewicz J., Benstra J. Scheduling subject to resource constraints: classificaton and complexity.- Discrete Appl.Math., 1983,5,№l,p.ll-24

40. Garey MLR., Johnson D.S. Complexit}' result for multiprocessor schedulmg under resource constraints.-SIAM J.Comput., 1975,4,№4, p. 397-411