Бикритериальные модели и алгоритмы оптимизации управления обслуживанием детерминированных потоков объектов в системах транспортного типа тема диссертации и автореферата по ВАК РФ 05.13.01, кандидат технических наук Цветков, Александр Игоревич

• Цветков, Александр Игоревич
• кандидат технических наук
• 2011

Оглавление диссертации кандидат технических наук Цветков, Александр Игоревич

4

ГЛАВА 1. ДИСКРЕТНЫЕ МАТЕМАТИЧЕСКИЕ МОДЕЛИ И МЕТОДЫ РЕШЕНИЯ ЗАДАЧ СИНТЕЗАТЕГИЙ УПРАВЛЕНИЯ

ОБСЛУЖИВАНИЕМ В СИСТЕМАХ ТРАНСПОРТНОГО ТИПА.

§1.1. Модели обслуживания.

1.1.1. Модели обслуживания множества объектов с линейными функциями индивидуальных штрафов.

1.1.2. Каноническая модель управления однопроцессорным обслуживанием потока объектов.

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

1.1.4. Модели управления обслуживанием бинарного потока объектов.

§ 1.2. Постановки задач синтеза оптимальных стратегий управления и методы их решения.

1.2.1. Метод динамического программирования.

1.2.2. Метод ветвей и границ.

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

§ 1.3. Подходы к решению многокритериальных задач управления обслуживанием.

1.3.1. Схемы компромисса.

1.3.2. Метод динамического программирования для решения многокритериальных задач дискретной оптимизации.

1.3.3. Метод ветвей и границ для решения многокритериальных задач дискретной оптимизации.

ВЫВОДЫ ПО ГЛАВЕ 1.

ГЛАВА 2. БИКРИТЕРИАЛЬНАЯ МАТЕМАТИЧЕСКАЯ МОДЕЛЬ И АЛГОРИТМЫ ОПТИМИЗАЦИИ СТРАТЕГИЙ ОДНОПРОЦЕССОРНОГО ОБСЛУЖИВАНИЯ БИНАРНОГО

ПОТОКА ОБЪЕКТОВ В ЛИНЕЙНОЙ РАБОЧЕЙ ЗОНЕ.

§ 2.1. Построение математической модели обслуживания и постановка экстремальных задач.

2.1.1. Содержательное описание технологии однопроцессорного обслуживания бинарного потока объектов.

2.1.2. Математическая модель однопроцессорного обслуживания.

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

§ 2.2. Использование схем компромисса для решения бикритериальной проблемы управления обслуживанием.

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

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

2.2.3. Применение метода линейной свертки критериев.

2.2.4. Применение метода идеальной точки.

§ 2.3. Синтез полной совокупности Парето-оптимальных стратегий управления обслуживанием на основе идеологии динамического программирования. 55 2.3.1. Построение рекуррентных соотношений динамического программирования.

2.3.2. Пример реализации алгоритма динамического программирования.

2.3.3. Устойчивость структуры стратегий управления обслуживанием.

2.3.4. Модификация метода динамического программирования.

§ 2.4. Синтез стратегий управления обслуживанием на основе эволюционногенетического подхода.

2.4.1. Построение эволюционно-генетического алгоритма.

2.3.1. Результаты численных экспериментов.

§ 2.5. Результаты тестирования разработанных алгоритмов.

§ 2.6. Учет расстояния, пройденного процессором при автономном движении.

ВЫВОДЫ ПО ГЛАВЕ 2.

ГЛАВА 3. БИКРИТЕРИАЛЬНАЯ МАТЕМАТИЧЕСКАЯ МОДЕЛЬ

И ОПТИМИЗАЦИЯ СТРАТЕГИЙ ДВУХПРОЦЕССОРНОГО ОБСЛУЖИВАНИЯ БИНАРНОГО ПОТОКА ОБЪЕКТОВ

В ЛИНЕЙНОЙ РАБОЧЕЙ ЗОНЕ.

§ 3.1. Построение математической модели обслуживания и постановка экстремальной задачи.

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

3.1.2. Построение математической модели.

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

§ 3.2. Синтез полной совокупности Парето-оптимальных стратегий управления обслуживанием на основе идеологии динамического программирования.

3.2.1. Построение рекуррентных соотношений динамического программирования.

3.2.2. Иллюстрация работы алгоритма.

3.2.3. Результаты вычислительных экспериментов.

ВЫВОДЫ ПО ГЛАВЕ 3.

ГЛАВА 4. БИКРИТЕРИАЛЬНАЯ ОПТИМИЗАЦИЯ СТРАТЕГИЙ

УПРАВЛЕНИЯ ОДНОПРОЦЕССОРНЫМ ОБСЛУЖИВАНИЕМ ТЕРНАРНОГО ПОТОКА ОБЪЕКТОВ В ТРЕХКОМПОНЕНТНОЙ

УЗЛОВОЙ ЗОНЕ.

§ 4.1. Построение модели однопроцессорного обслуживания тернарного потока объектов и постановка экстремальной задачи.

4.1.1. Содержательное описание технологии обслуживания в трехкомпонентной рабочей зоне.

4.1.2. Построение математической модели.

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

§ 4.2. Синтез полной совокупности Парето-оптимальных стратегий управления обслуживанием на основе идеологии динамического программирования.

4.2.1. Построение рекуррентных соотношений динамического программирования.

4.2.2. Результаты вычислительных экспериментов.

§ 4.3. Обобщение модели обслуживания на случай произвольного количества ветвей узловой зоны и тоЬПе-процессоров.

4.3.1. Построение модели обслуживания.

4.3.2. Постановка многокритериальной задачи.

ВЫВОДЫ ПО ГЛАВЕ 4.

ГЛАВА 5. ПРОГРАММНЫЙ КОМПЛЕКС ПОДДЕРЖКИ ОПЕРАТИВНОГО

УПРАВЛЕНИЯ ОБСЛУЖИВАНИЕМ ПОТОКА ОБЪЕКТОВ.

§5.1. Назначение и функциональные возможности программного комплекса.

§ 5.2. Интерфейс пользователя программного комплекса.

§5.3. Архитектура программного комплекса.

ВЫВОДЫ ПО ГЛАВЕ 5.

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

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

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

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

Как показал анализ научных публикаций, посвященных системному анализу, моделированию и оптимизации процессов оперативного управления ТТО [14, 17,25], их адекватное математическое описание для достаточно обширного класса эксплуатационных ситуаций может быть выполнено в рамках детерминированных моделей - на традиционном для теории расписаний языке обслуживания объектов процессорами [36, 37]. Точность такого моделирования определяется выбором шага дискретности пространственных и временных параметров, а синтез оптимальных стратегий управления обслуживанием (расписаний, оперативных планов) принципиально осуществим вычислительными алгоритмами, реализующими комбинаторные методы математического программирования.

Научные исследования по данному направлению базируются на фундаментальных работах по теории расписаний [32], в числе авторов которых - M. Garey, D. Johnson [22], E.G. Coffman [85, 86], R.L. Graham [91], W.L. Maxwell [32], B.C. Гордон [18 - 20], M .Я. Ковалев, B.C. Танаев, Я.M. Шафранский, B.B. Шкурба [61, 62, 63]. Применительно к различным задачам управления дискретными ресурсами, и в частности оптимизации ТТО, математические модели и решающие алгоритмы исследовались в работах Д.И. Батищева [3] A.C. Беленького [7, 8],

B.Н. Буркова [11], Э.Х. Гимади [15], Р.В. Игудина [24], Д.И.Когана и Ю.С. Федосенко [27, 29 - 31], A.A. Корбута [33, 35], A.A. Лазарева [38, 39],

C.Е. Ловецкого [50], Т.П. Подчасовой [48], М.Х. Прилуцкого [49], И.Х. Сигала [59], М.В. Ульянова [64, 65], H.H. Моисеева [43], Ю.Ю. Финкельштейна [75], А.Ю. Шлюгаева [73, 74, 102] и других авторов.

В контексте тематики диссертационной работы отметим сравнительно недавно опубликованные исследования М.Б. Резникова [53, 54], H. Shen и P. Tsiotras [100, 101], посвященные решению задач синтеза оптимальных стратегий управления обслуживанием совокупностей объектов подвижными процессорами (mobile-процессорами). В частности, в работах М.Б. Резникова рассматривается задача оптимального управления обслуживанием конечных детерминированных потоков объектов в рабочей зоне mobile-процессоров, а в работах H. Shen и P. Tsiotras решается задача синтеза оптимального управления для модели дозаправки орбитальной группировки спутников. Указанные задачи, также как и задачи оптимального управления снабжением дизельным топливом русловых добывающих комплексов [12], исследованные в работах

А.Ю. Шлюгаева, покрывают значительную, но далеко не полную часть всего многообразия возможных эксплуатационных ситуаций, в которых осуществляется ТТО.

В отличие от работ вышеперечисленных авторов основное внимание в диссертации уделено моделированию и оптимизации управления ТТО тоЬПе-процессорами потоков объектов в производственных комплексах, системный анализ которых выявил необходимость учета значений двух, а в отдельных случаях и трех независимых критериев оценки эффективности управления их функционированием. Такого рода ТТО характерно, в частности, при реализации сравнительно новой технологии обслуживания потоков транспортных судов на ходу при транзитном прохождении ими крупномасштабной зоны ответственности сервисного предприятия. Обслуживание при этом осуществляется специализированными судами технического флота (одним или несколькими), предназначенными для выполнения одного определенного вида или некоторого фиксированного набора работ, в том числе материально-технического и продовольственного снабжения, утилизации отходов, ремонта оборудования и т.п. В районах интенсивного судоходства, а также в короткие периоды северного завоза через зону ответственности сервисного предприятия (протяженностью от нескольких десятков до нескольких сотен километров в зависимости от специфики географического региона) на горизонте оперативного планирования может проходить до 20 и более транспортных судов. Любое такое судно может запросить у сервисного предприятия обслуживание, получить на это согласие или отказ в зависимости от складывающейся оперативной обстановки. Весьма значительная стоимость содержания специализированных судов, экономические критерии их эффективной эксплуатации диктуют необходимость высокой адаптивности диспетчерского регулирования использования специализированного флота в темпе изменения параметров внешней среды, а это, в свою очередь, накладывает весьма жесткие ограничения на допустимую длительность штатного регламента формирования управляющих воздействий. Соответственно в диссертационной работе построение и исследование алгоритмов синтеза стратегий управления ТТО выполнено с учетом вышеотмеченных особенностей.

Целью работы является построение и исследование математических моделей и алгоритмов решения бикритериальных задач оптимизации управления обслуживанием потоков объектов в рабочих зонах тоЫ1е-процессоров. При этом рассмотрены следующие типовые схемы обслуживания и конфигурации рабочей зоны.

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

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

3. Обслуживание потока объектов тоЫ1е-процессором в узловой рабочей зоне. В качестве критериев оценки эффективности управления выступают значения суммарного дохода и суммарного штрафа за обслуживание и отказы в обслуживании объектов потока.

Достижение поставленной цели диссертационной работы требует исследования следующих вопросов:

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

- разработки адекватных бикритериальных математических моделей обслуживания потоков объектов тоЬПе-процессорами;

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

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

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

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

3. Исследованы особенности применения различных схем компромисса для решения поставленных задач и обосновано использование парадигмы Парето.

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

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

-Научные конференции «Технологии Microsoft в теории и практике программирования» (Нижний Новгород, 2009, 2010);

- 11-й и 12-й Международные научно-промышленные форумы «Великие реки» (Нижний Новгород, 2009, 2010);

-Международные научно-технические конференции «Информационные системы и технологии - ИСТ» (Нижний Новгород, 2009, 2010, 2011);

- IX Международная молодежная научно-техническая конференция «Будущее технической науки» (Нижний Новгород, 2010);

- Межвузовские научно-практические конференции студентов и аспирантов «Современные тенденции и перспективы развития водного транспорта России» (Санкт-Петербург, 2010, 2011);

- XVI Международная конференция «Проблемы теоретической кибернетики» (Нижний Новгород, 2011);

- Международная научная конференция студентов, аспирантов и молодых ученых «Теоретические и прикладные аспекты кибернетики» (Киев, 2011).

Структура и объем работы. Диссертация состоит из введения, пяти глав, заключения и 3-х приложений; содержит 119 страниц текста; библиографический список включает 105 источников.

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

ВЫВОДЫ ПО ГЛАВЕ 5

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

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

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

Заключение

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

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

Получены следующие научно-технические результаты.

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

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

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

4. Разработанные модели, алгоритмы и программные средства внедрены в ОАО «Азимут», а также в учебный процесс Волжской государственной академии водного транспорта и факультета Вычислительной математики и кибернетики ННГУ им. Н.И. Лобачевского.

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

Список литературы диссертационного исследования кандидат технических наук Цветков, Александр Игоревич, 2011 год

1. Алексеев, О.Г. Комплексное применение методов дискретной оптимизации Текст]/ О.Г. Алексеев. -М. : Наука, 1987. 248 с.

2. Батищев, Д.И. Генетические алгоритмы решения экстремальных задач Текст] / Д.И. Батищев ; под ред. Я.Е. Львовича. Воронеж : ВГТУ 1995.-64 с.

3. Батищев, Д.И. Задачи и методы векторной оптимизации : учеб. пособие. Текст] / Д.И. Батищев. Горький : Изд-во ГГУ, 1979. -92 с.

4. Батищев, Д.И. Применение генетических алгоритмов к решению задач дискретной оптимизации Текст] : учеб. пособие / Д.И. Батищев, Е.А. Неймарк, Н.В. Старостин. Н. Новгород : Изд-во ННГУ им. Н.И. Лобачевского, 2006. - 123 с.

5. Батищев, Д.И. Решение многокритериальных задач методом идеальной точки Текст] / Д.И. Батищев, Д.Е. Шапошников // Модели и алгоритмы оптимизации в автоматизированных системах. Воронеж : ВПИ, 1989. - С. 48-53.

6. Батищев, Д.И. Решение дискретных задач с помощью генетических алгоритмов Текст] : учеб. пособие / Д.И. Батищев, В.Е. Костюков, Е.А. Неймарк [и др.]. Н. Новгород : Изд-во ННГУ им. Н.И. Лобачевского, 2011. - 199 с.

7. Беленький, A.C. Исследование операций в транспортных системах: идеи и схемы методов оптимизации планирования Текст] / A.C. Беленький, Е.В. Левнер. М. : Мир, 1992. - 582 с.

8. Беленький, A.C. Применение моделей и методов теории расписаний в задачах оптимального планирования на грузовом транспорте Текст] / A.C. Беленький, Е.В. Левнер // Автоматика и телемеханика. 1989. - №2. - С. 3-77.

9. Беллман, Р. Динамическое программирование Текст] / Р. Беллман. М. : Изд-во иностр. лит., 1960. - 400 с.

10. Беллман, Р. Прикладные задачи динамического программирования Текст] / Р. Беллман, С. Дрейфус. М. : Наука, 1965. - 460 с.

11. Бурков, В.Н. Эвристический подход к решению динамических задач распределения ресурсов Текст] / В.Н. Бурков, С.Е. Ловецкий // Автоматика и телемеханика. 1966. - № 5. - С. 8990.

12. Бутов, A.C. Планирование работы флота и портов Текст] / A.C. Бутов, В.А Легкостаев. -М. : Транспорт, 1988. 175 с.

13. Вентцель, Е.С. Элементы динамического программирования Текст] / Е.С. Вентцель. М. : Наука, 1964. - 176 с.

14. Войчинский, A.M. Гибкие автоматизированные производства Текст. / A.M. Войчинский, Н.И. Диденко, В.П. Лузин.-М. : Радио и связь, 1987.-272 с.

15. Гимади, Э.Х. Новая версия асимптотически точного алгоритма решения евклидовой задачи коммивояжера Текст. / Э.Х. Гимади // Труды XII Байкальской международной конференции. Методы оптимизации и их приложения. Иркутск, 2001. - Т. 1.- С. 117124.

16. Гладков, JI.A. Генетические алгоритмы Текст. : учебное пособие / JI.A. Гладков, В.В. Курейчик, В.М. Курейчик. М. : Физматлит, 2006. - 320 с.

17. Гордон, B.C. Минимизация стоимости, связанной с переменными директивными сроками, в задаче теории расписаний с одним прибором Текст. / B.C. Гордон // Автоматика и телемеханика. -1992,-№2.-С. 105-112.

18. Гордон, B.C. К вопросу минимизации функций на множестве перестановок частично упорядоченных элементов Текст. / B.C. Гордон, Я.М. Шафранский // Изв. АН БССР. Сер. физ.-мат. наук. 1979. - № 2. - С. 122-124.

19. Гордон, B.C. О минимаксных задачах теории расписаний с одним прибором / B.C. Гордон, B.C. Танаев // Изв. АН БССР. Сер. физ.-мат. наук. 1982. - № 3.

20. Грэхем, Р. Конкретная математика. Основание информатики Текст. /

21. Р. Грэхем, Д. Кнут, О. Паташник. М. : Мир, 1998. - 703 с.

22. Гэри, М. Вычислительные машины и труднорешаемые задачи

23. Текст. / М. Гэри, Д. Джонсон. М. : Мир, 1982. - 416 с.

24. Джонс, М.Т. Программирование искусственного интеллекта в