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

• Дуничкина, Надежда Александровна
• кандидат физико-математических наук
• 2012

Оглавление диссертации кандидат физико-математических наук Дуничкина, Надежда Александровна

ВВЕДЕНИЕ.

ГЛАВА 1. МЕТОДЫ РЕШЕНИЯ И ВЫЧИСЛИТЕЛЬНАЯ СЛОЖНОСТЬ

МНОГОКРИТЕРИАЛЬНЫХ ЗАДАЧ ТЕОРИИ РАСПИСАНИЙ.

§ 1.1. Теория расписаний.

§ 1.2. Методы решения многокритериальных задач.

1.2.1. Схемы компромисса между критериями.

1.2.2. Концепция Парето.

§ 1.3. Вычислительная сложность задач и алгоритмов.

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

Выводы по главе 1.

ГЛАВА 2. МОДЕЛИ, ЗАДАЧИ И АЛГОРИТМЫ СИНТЕЗА СТРАТЕГИЙ

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

ОБЪЕКТОВ В ОДНОМЕРНОЙ РАБОЧЕЙ ЗОНЕ.

§ 2.1. Однопроцессорное обслуживание объектов в одномерной зоне.

2.1.1. Математическая модель Line

2.1.2. Постановка оптимизационных задач.

2.1.3. Исследование вычислительной сложности задач Line l^(£,max),

Line l!^(E,E), Line (max, max).

§ 2.2. Синтез совокупности эффективных оценок на основе идеологии динамического программирования.

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

2.2.2. Примеры реализации синтеза стратегий обслуживания.

§ 2.3. Синтез совокупности эффективных оценок на основе метода ветвей и границ

2.3.1. Описание метода.

Выводы по главе 2.

ГЛАВА 3. МОДЕЛИ, ЗАДАЧИ И АЛГОРИТМЫ СИНТЕЗА СТРАТЕГИЙ ОБСЛУЖИВАНИЯ СТАЦИОНАРНЫХ ОБЪЕКТОВ В ОДНОМЕРНОЙ РАБОЧЕЙ ЗОНЕ ДВУХ ОБСЛУЖИВАЮЩИХ

ПРОЦЕССОРОВ.

§ 3.1. Обслуживание объектов в рабочей зоне двух попутных процессоров.

3.1.1. Математическая модель Line2^.

3.1.2. Постановка оптимизационных задач.

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

3.1.4. Примеры реализации синтеза стратегий обслуживания.

§ 3.2. Обслуживание объектов в рабочей зоне двух встречных процессоров.

3.2.1. Математическая модель Line2^ и постановка оптимизационных задач

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

3.2.3 Примеры реализации синтеза стратегий обслуживания.

Выводы по главе 3.

ГЛАВА 4. МОДЕЛИ, ЗАДАЧИ И АЛГОРИТМЫ СИНТЕЗА СТРАТЕГИЙ

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

ОБЪЕКТОВ В РАБОЧЕЙ ЗОНЕ ГРАФОВОЙ СТРУКТУРЫ.

§ 4.1. Обслуживание объектов в рабочей зоне графовой структуры.

4.1.1. Математическая модель Graphl.

4.1.2. Постановка оптимизационных задач.

4.1.3. Исследование вычислительной сложности задач Graphl(E, max),

Graphl(E, Е) и Graphl(E,r).

§ 4.2. Синтез совокупности эффективных оценок на основе идеологии динамического программирования.

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

§ 4.3. Обобщение модели обслуживания на случай наличия ограничений на порядок обслуживания объектов.

4.3.1. Концепция ¿-расписаний и постановка оптимизационных задач.

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

Выводы по главе 4.

ГЛАВА 5. АЛГОРИТМЫ СИНТЕЗА СУБ ОПТИМАЛЬНЫХ СТРАТЕГИЙ

ОБСЛУЖИВАНИЯ.

§ 5.1. О сравнении двух множеств оценок.

§ 5.2. Алгоритмы мягких вычислений для задач Linel^(E, max), Linel^(E, Е), Linel^ (max, max).

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

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

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

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

§ 5.3. Алгоритмы мягких вычислений для задач Line2^(E,max), Line2l^(E,E), Line2^(max,max), Line2^(E,max), Line2^(E,E), Line2^(max,max).

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

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

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

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

§ 5.4. Алгоритмы мягких вычислений для задач Graphl(E, max), Graphl(E, Е), Graphl(max, max), Graphl(E,T).

5.4.1. Синтез субоптимальных стратегий обслуживания на основе концепции ¿/-расписаний.

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

5.4.3. Синтез совокупности субоптимальных стратегий на основе эволюционно-генетического подхода.

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

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

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

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

Выводы по главе 5.

ГЛАВА 6. ПРОГРАММНЫЙ КОМПЛЕКС ПОДДЕРЖКИ УПРАВЛЕНИЯ СНАБЖЕНИЕМ ПЛАВУЧИХ ДОБЫВАЮЩИХ КОМПЛЕКСОВ

ДИЗЕЛЬНЫМ ТОПЛИВОМ.

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

§ 6.2. Программный комплекс поддержки оперативного управления обслуживанием группировки плавучих добывающих комплексов.

6.2.1. Назначение и функциональные возможности.

6.2.2. Интерфейс пользователя.

6.2.3. Описание типового сценария работы с комплексом.

6.2.4. Описание архитектуры программного комплекса.

Выводы по главе 6.

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

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

Фундаментальные исследования по теории расписаний представлены в трудах B.C. Танаева (а также его учеников и коллег - B.C. Гордона, М.Я. Ковалева, A.A. Лазарева, Ю.Н. Сотскова, В.А. Струсевича, Я.М. Шафранского), В.В. Шкурбы, M. Garey, D. Johnson, E.G. Coffman, R.L. Graham, R.W. Conway, W.L. Maxwell, L.W. Miller, R.M. Karp. Применительно к различным проблемам управления дискретными ресурсами, в частности для моделей технологического обслуживания, задачи синтеза оптимальных решений - стратегий (расписаний) обслуживания исследовались в работах Д.И. Батищева, A.C. Беленького, В.Н. Буркова, Э.Х. Гимади, Д.И. Когана и Ю.С. Федосенко, A.A. Корбута, Е.В. Левнера, Д.А. Новикова, Т.П. Подчасовой, М.Х. Прилуцкого, И.Х. Сигала, М.В. Ульянова, Ю.Ю. Финкелыптейна и ряда других авторов.

В классических постановках задач теории расписаний процессоры стационарны, а качество управления обслуживанием оценивается по значению скалярного критерия. Вместе с тем, в условиях рыночных отношений между субъектами хозяйственной деятельности и в связи с появлением инновационных производственных и транспортных технологий, реализуемых на крупномасштабных полигонах, объективно зрела необходимость введения в исследовательский оборот новых, более сложных математических моделей, в том числе с перемещающимся процессором (тоЬПе-процессором), с двумя и более критериями оценки качества стратегий управления. Переход к таким моделям связан, с одной стороны, с естественным требованием обеспечения адекватности математического описания реальным приложениям, а с другой — с дополнительными трудностями, обусловленными необходимостью использования специальных принципов оптимальности, разработкой новых, обобщенных схем решения и нетривиальным анализом вычислительной сложности [21] как самих оптимизационных задач, так и алгоритмов их решения. Именно эти обстоятельства обусловливают актуальность темы диссертационной работы, в которой очерченный выше круг вопросов рассматривается применительно к задачам управления реализацией транспортных технологий, адекватно моделируемых детерминированными системами обслуживания стационарных объектов в рабочей зоне тоЫ1е-процессоров. Соответственно целью работы является построение алгоритмов и вычислительных процедур с характеристиками, приемлемыми для использования в компьютерных системах поддержки оперативного управления процессами рассматриваемого класса.

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

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

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

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

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

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

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

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

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

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

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

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

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

7. Предложена методика определения отклонений квазипаретовских множеств оценок (полученных при реализации процедур п. 6) от паретовских множеств, позволяющая оценивать эффективность основанных на метаэвристиках вычислительных схем.

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

Доказанные результаты об -трудности подтверждают невозможность построения для соответствующих задач полиномиальных решающих алгоритмов в силу общепринятой гипотезы Р Ф №\

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

Практическая ценность полученных результатов заключается в том, что разработанные математические модели, решающие алгоритмы и программный комплекс могут применяться в компьютерных системах, предназначенных для поддержки управления обслуживанием пространственно рассредоточенной группировки стационарных объектов. В частности, в рамках такого рода математических моделей и оптимизационных постановок описываются перспективные проектные решения управления дозаправкой орбитальной группировки спутников [114] и магистральных гражданских самолетов [93]. Отдельно отметим важную прикладную задачу диспетчерского управления снабжением дизельным топливом группировки плавучих добывающих комплексов, подробно рассмотренную в главе 6 диссертации.

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

- Международная конференция по исследованию операций "Operations Research OR'2011" (Zurich, Switzerland, 2011)1;

- Третья международная IT-конференция "Information Technology in modem everyday life" (Bonn-Rhein-Sieg, Germany, 2008);

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

- VI Московская международная конференция по исследованию операций ORM'2010 (Москва, 2010);

- Нижегородские сессии молодых ученых (Нижний Новгород, 2007, 2008,2010, 20112);

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

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

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

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

- Восьмой международный симпозиум «Интеллектуальные системы» (Нижний Новгород, 2008);

- III Всероссийская студенческая научно-техническая конференция «Прикладная информатика и математическое моделирование» (Москва, 2009)5; Участие поддержано грантом РФФИ, проект №11-01 -093 30-мобз Доклад удостоен диплома 1 степени

3 В 2009 и 2010 г доклады удостоены дипломов 111 степени

4 Доклад удостоен диплома I степени

5 Доклад удостоен диплома за содержательные научные результаты

- Международные конференции «Идентификация систем и задачи управления - SICPRO» (Москва, 2008, 2012);

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

- Всероссийская научно-техническая конференция «Новые информационные технологии» (Москва, 2010, 2011).

Личный вклад автора. Результаты, выносимые на защиту, получены соискателем лично или при его непосредственном участии. Им же лично подготовлены публикации [24, 45,46], представленные в изданиях Перечня рецензируемых научных журналов.

В первой главе (Методы решения и вычислительная сложность многокритериальных задач теории расписаний) проводится обзор: а) основных вопросов синтеза стратегий обслуживания (§ 1.1); б) подходов к решению многокритериальных оптимизационных задач, в том числе на основе концепции Парето (§ 1.2); в) методов оценки вычислительной сложности задач и алгоритмов (§ 1.3). Описывается отличие классических задач теории расписаний от рассматриваемых в диссертационном исследовании (§ 1.4).

Во второй главе (Модели, задачи и алгоритмы синтеза стратегий однопроцессорного обслуживания стационарных объектов в одномерной рабочей зоне [55, 36, 38, 56, 42, 58-60]) выполняется построение математической модели, формулируются оптимизационные задачи, исследуются вопросы их вычислительной сложности, разрабатываются алгоритмы синтеза совокупности парето-оптимальных стратегий обслуживания и приводятся примеры их численной реализации.

§ 2.1 посвящен описанию математической модели Line обслуживания совокупности стационарных объектов в одномерной рабочей зоне mobile-процессора. Ставятся оптимизационные задачи Line l^(S,max), Line 1^(2,И), Line l^(max,max). Доказываются теоремы об NP-трудности и о числе возможных эффективных оценок.

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

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

В третьей главе (Модели, задачи и алгоритмы синтеза стратегий обслуживания стационарных объектов в одномерной рабочей зоне двух обслуживающих тоЬПе-процессоров [24, 40, 45, 61]) рассматривается расширение модели, описанной в главе 2, на случай двух обслуживающих процессоров. При этом § 3.1 посвящен модели Line2^ с двумя процессорами, осуществляющими движение в одном направлении (попутные процессоры), а § 3.2 -модели Line 2^ с двумя процессорами, осуществляющими встречное движение. В рамках каждой модели ставятся оптимизационные задачи, строятся решающие алгоритмы, основанные на многокритериальном динамическом программировании, доказывается их псевдополиномиальность, приводятся примеры численного счета по рекуррентным соотношениям динамического программирования.

В четвертой главе (Модели, задачи и алгоритмы синтеза стратегий однопроцессорного обслуживания стационарных объектов в рабочей зоне графовой структуры [27, 28, 30, 37, 90, 100]) рассматривается общая модель однопроцессорного обслуживания Graphl, в которой объекты совокупности находятся в вершинах неориентированного односвязного графа.

§4.1 посвящен описанию математической модели, постановке оптимизационных задач Graphl(£, max), Graphl(Z, Z), Graphl (max, max) и Graphl(X,r). Доказываются теоремы об NP-трудности в сильном смысле задач, в которых хотя бы один критерий аддитивный.

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

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

Пятая глава (Алгоритмы синтеза субоптимальных стратегий обслуживания [23, 25, 26, 29, 31-34, 46, 91, 99]) посвящена разработке решающих алгоритмов на основе концепции мягких вычислений, реализованной с использованием следующих метаэвристик: муравьиная колония, поиск с запретами, имитация отжига, эволюционно-генетическая парадигма. Построен также итеративный алгоритм синтеза субоптимальных стратегий обслуживания на основе концепции ё-расписаний [54].

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

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

§ 5.4 посвящен описанию и анализу алгоритмов синтеза субоптимальных стратегий для задач, поставленных в главе 4. В дополнение к рассмотренным в § 5.2 и § 5.3 для указанных задач были разработаны алгоритмы, основанные на идеологии муравьиной колонии и итерационном подходе, использующем концепцию ё-расписания.

В шестой главе (Программный комплекс поддержки управления снабжением плавучих добывающих комплексов дизельным топливом [35, 39, 41, 43, 44]) рассматриваются прикладные задачи для построенных в главах 2-4 моделей обслуживания стационарных объектов тоЫ1е-процессорами. Описывается разработанный программный комплекс, предназначенный для синтеза оптимальных и субоптимальных стратегий управления обслуживанием.

В заключении изложены основные научные и практические результаты диссертационной работы.

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

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

ЗАКЛЮЧЕНИЕ

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