автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.01, диссертация на тему:Анализ и алгоритмы решения бикритериальных задач управления обслуживанием стационарных объектов mobile-процессорами

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

Дуничкина Надежда Александровна

АНАЛИЗ И АЛГОРИТМЫ РЕШЕНИЯ БИКРИТЕРИАЛЬНЫХ ЗАДАЧ УПРАВЛЕНИЯ ОБСЛУЖИВАНИЕМ СТАЦИОНАРНЫХ ОБЪЕКТОВ МОВШЕ-ПРОЦЕССОРАМИ

Специальность 05.13.01 - «Системный анализ, управление и обработка информации (в науке и промышленности) по физико-математическим наукам»

1 5 МА? 2012

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

Нижний Новгород-2012 г.

005014091

005014091

Работа выполнена на кафедре Информатики, систем управления и телекоммуникаций ФБОУ ВПО «Волжская государственная академия водного транспорта».

Научный руководитель:

Научный консультант:

Официальные оппоненты:

Ведущая организация:

доктор технических наук,

профессор Федосенко Юрий Семенович

доктор технических наук,

профессор Коган Дмитрий Израилевич

Алексеев Владимир Евгеньевич,

доктор физико-математических наук, профессор, Нижегородский государственный исследовательский университет им. Н.И. Лобачевекого, профессор кафедры Математической логики и высшей алгебры

Орлов Юрий Федорович,

доктор физико-математических наук, профессор, Нижегородский государственный технический университет им. Н.И. Алексеева, профессор кафедры Прикладной математики

Федеральное бюджетное учреждение науки

Институт проблем управления

им. В.А. Трапезникова РАН, г. Москва

Защита состоится « 5» апреля 2012 г. в Д часов в аудитории 1258 на заседании диссертационного совета Д 212.165.05 при Нижегородском государственном техническом университете им. Р.Е.Алексеева по адресу: 603950, г. Нижний Новгород, ул. Минина, 24.

С диссертацией можно ознакомиться в библиотеке Нижегородского государственного технического университета им. P.E. Алексеева.

Автореферат разослан » марта 2012 г.

Ученый секретарь диссертационного совета A.C. Суркова

Общая характеристика работы

К середине 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. Корбута, Е.В.Левнера, Д.А. Новикова, Т.П. Подчасовой, М.Х. Прилуцкого, И.Х. Сигала, М.В. Ульянова, Ю.Ю. Финкельштейна и ряда других авторов.

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

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

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

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

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

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

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

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

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

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

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

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

1 Гэри, М., Джонсон, Д. Вычислительные машины и труднорешаемые задачи. - М.: Мир 1982.

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

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

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

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

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

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

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

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

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

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

Обоснованность и достоверность результатов работы

обеспечивается корректной реализацией использованного математического аппарата и выполненными вычислительными экспериментами.

Реализация результатов работы. Разработанные при выполнении диссертационных исследований модели и алгоритмы использовались при создании компьютерных систем поддержки оперативного управления и планирования в ОАО «Азимут» (Казань). Они также используются в учебном процессе с аспирантами, проходящими подготовку по научной специальности 05.13.01, со студентами специализации «Информационные и телекоммуникационные системы на транспорте» в Волжской государственной академии водного транспорта, а также на факультете Вычислительной математики и кибернетики Нижегородского государственного университета им. Н.И. Лобачевского. Разработанный программный комплекс зарегистрирован в Реестре программ для ЭВМ Федеральной службы по интеллектуальной собственности, патентам и товарным знакам РФ.

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

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

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

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

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

1 Shen, Н. Optimal Scheduling for Satellite Refueling in Circular Orbits // PhD thesis, School of

Aerospace Engineering, Georgia Institute of Technology, Atlanta, Georgia, March 2003.

Дозаправка в полете гражданских самолетов: перспективы и проблемы / ЦАГИ. URL: http://wvw.tsagi.ru/cgi-bin/jet/viewnews.cgi?id=201012300807776]8957 (дата обращения-16.02.2012). "

4 Участие поддержано грантом РФФИ, проект№11-01-09330-моб_з.

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

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

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

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

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

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

- III Всероссийская студенческая научно-техническая конференция «Прикладная информатика и математическое моделирование» (Москва, 2009)8;

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

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

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

Публикации. Основные результаты диссертационных исследований отражены в 34 работах [1-34], в том числе в четырех статьях [1-4], представленных в Перечне рецензируемых научных журналов9.

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

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

Во введении дается общая характеристика диссертационной работы, обосновывается актуальность выполненных исследований, об-

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

6 В 2009 и 2010 г. доклады удостоены дипломов III степени.

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

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

9 Позиции 98,350,1016 Перечня российских рецензируемых научных журналов (http://vak.ed.gov.ru/comrnon/img/uploadcd/files/2011/епитега(юп/рег-22-07-201Ыос).

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

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

Во второй главе (Модели, задачи и алгоритмы синтеза стратегий однопроцессорного обслуживания стационарных объектов в одномерной рабочей зоне [19,20,22,26-28,30,31]) выполняется построение математической модели, формулируются оптимизационные задачи, исследуются вопросы их вычислительной сложности, разрабатываются алгоритмы синтеза совокупности парето-оптимальных стратегий обслуживания и приводятся примеры их численной реализации.

Основным элементом дискретных моделей процессов обслуживания, рассматриваемых в диссертационной работе, является совокупность Оп= {ои о2,..., о„} стационарных объектов, расположенных в рабочей зоне обслуживающего тоЫ1е-процессора Р. Считается, что рабочая зона X одномерна и конечна, её начальная точка А является базовой для процессора; объекты считаем пронумерованными в порядке возрастания их расстояний от точки А; конечная точка В зоны £ является местом расположения объекта о„. Из точки А, начиная от момента времени / = 0, процессор поступательно перемещается к конечной точке В (прямой рейс Х+), а затем, достигнув её, также поступательно возвращается в точку А (обратный рейс /1_).

При реализации цикла процессор Р выполняет одностадийное без прерываний обслуживание объектов группы 0„: часть объектов обслуживается в рейсе все остальные - в рейсе С каждым объектом Оу ассоциируются две монотонно возрастающие (в нестрогом смысле) функции индивидуального штрафа <ру{/) и у//), выражающие зависящие от момента завершения его обслуживания величины потерь по первому и второму показателям соответственно.

Примем обозначения: 1,2,..., и - точки отрезка Ь, в которых расположены объекты Ои 02»..., о„ соответственно (точки п и В совпадают); Ту - продолжительность обслуживания процессором Р объекта о/, уу.у и у^.1 - затраты времени на перемещения процессора между точками

(/ - 1) и } в рейсах ¡Ц и соответственно (/ = 1, п); при этом у0,1 и у^о -затраты времени на перемещение процессора между точкой А и точкой 1 в прямом и обратном рейсах. Все числа у, у,.^, у^., считаем целыми положительными.

Стратегией обслуживания будем называть произвольное подмножество элементов р из совокупности индексов Ы= {1,2,...,«}; объекты ор где ]ер, в реализации стратегии р . обслуживаются тоЬПе-процессором в рейсе Х+, все остальные объекты, группы Оп-ъ рейсе Для определенности полагаем, что объект о„ обслуживается при завершении процессором рейса Я+. Таким образом, «ер; число различных стратегий обслуживания равно 2"'1.

Обслуживание любого объекта о7, начинается от момента прибытия тоЬПе-процессора в точку} при реализации определяемого стратегией р рейса; по завершению обслуживании процессор продолжает своё движение. Не связанные с обслуживанием объектов промежуточные простои тоЪПе-процессора запрещены. Любая стратегия однозначно определяет моменты начала и завершения обслуживания каждого из объектов. Через СДр) обозначим момент завершения обслуживания

объекта о, при реализации стратегии р (/' = 1, п), а через Т* - величину

п

Если объект о, обслуживается

в рейсе А^-, т.е. у'е р, то

)

С7(р) = + где Р^) _ совокупность не превосходящих )

4=1 ЫрО)

элементов из р. Если jeN\p, то обслуживание объекта о] реализуется

]

позже. Для величины ^Уыл + XIх* введем обозначение 5;, а через

М{]) обозначим задержку по объекту о, при переносе его обслуживания с прямого рейса на обратный; М(/) - это сумма трех слагаемых:

я

(затраты времени на перемещение процессора от точки j к

УЦ/+1

п

точке и); (затраты времени на перемещение процессора от

к=у+1

точки п к точке/); (суммарная продолжительность обслуживания

¿=7+1

объектов 0,+ь 0/+2,..., о„). В итоге имеем общую формулу

(5„ если /ер

5, ++ М( Д если у е р.

С позиций повышения эффективности управления обслуживанием совокупности объектов оь ог> ••••> о„ ставятся следующие три задачи.

Задача 1лпе1^(Е,тах). Найти полную совокупность Е эффективных по Парето оценок в бикритериальной проблеме минимизации суммы индивидуальных штрафов ф; и величины максимального из индивидуальных штрафов у,- по всем объектам совокупности Оп:

и

тт^ф/СДр))), тт(тахч/ДСДр))). (1)

р м Р 1

Задача Ьше1^(2,Е). Найти полную совокупность Е эффективных по Парето оценок в бикритериальной проблеме минимизации сумм индивидуальных штрафов ср, и по всем объектам совокупности Оп\

п и

тш(£ф,(СДр))), ma{^J{CJ (р))). (2)

Задача ЬтеЦДтах, тах). Найти полную совокупность Е эффективных по Парето оценок в бикритериальной проблеме минимизации величин максимального из индивидуальных штрафов <ру и максимального из индивидуальных штрафов щ по всем объектам совокупности 0„:

тт(тахф/Су(р))), тт(таху/Су(р))). (3)

Доказаны нижеследующие теоремы 1 и 2 о вычислительной сложности оптимизационных задач (1) и (2), а также соответствующих им задач распознавания - теоремы 3 и 4.

Теорема 1. Задача 1лпе1^(1, шах) Ш-трудна.

Теорема 2. Задача 1лпе1^(2,Е) ЛУ-трудна.

Теорема 3. Для задачи 1лпе1^(£,тах) с линейными функциями индивидуального штрафа фу(0, = = 1 ,п, проблема определения по произвольным натуральным константам С1 и С2, существует ли

стратегия обслуживания р*, одновременно удовлетворяющая условиям

п

£ф/С/р)) <С\ и тах ф,(СДр)) < С2, М>-трудна.

^=1 1

Теорема 4. Для задачи 1лпе1^(£, Е) с линейными функциями индивидуального штрафа проблема определения по

произвольным натуральным константам С\ и Сг, существует ли стратегия обслуживания р*, одновременно удовлетворяющая условиям

п ' ¡1

£ф,.(С/р*))< С, и ^уДСДр*)) ^ Сг, М'-трудна. М у=1

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

Теорема 5. Для любого натурального п существует задача 1лпе1^(Е, шах), множество эффективных оценок которой имеет в своем составе 2я"1 различных элементов.

Теорема 6. Для любого натурального п существует задача 1лпе1^(2, £), множество эффективных оценок которой имеет в своем составе 2й"1 различных элементов.

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

Теорема 7. Пусть функции штрафа имеют вид ф,(0 = а,г + \(/,(() = с,1 + с?/, /= \,п ; при этом для / = 1 ,п выполняются ограничения г'<т,<г", у'<у,-и,у,>1<у" и хотя бы одно из ограничений а'<а,<а" или с'<с,< с". Тогда для любого натурального п число эффективных оценок

задачи 1лпе1^(£, 2) ограничено сверху полиномом от п второй степени.

Теорема 8. Пусть функции штрафа имеют вид ф,(/) = а,/ + \|/,(/) = с,/ + с/„ г = 1 ,п; при этом для г'= 1 ,п выполняются ограничения г'<г,<г", у'<ум,/,у(,,--1<у" и хотя бы одна из пар ограничений а'<а/<а", Ь'<Ь,<Ь" или с'<с,<с", с1'<¿,<с1". Тогда для любого натурального и число эффективных оценок задачи Ьте1^(шах, тах) ограничено сверху линейной функцией от п.

Теорема 9. Пусть функции штрафа имеют вид cp,(r) = a,t + b„ \|(,{t) = c,r + dj (i= 1 ,ri) и вьшолняются ограничения вида: т'<т,<т", у'<у,. 1.» Y/./-1 S У" 0'= 1,и)- Тогда справедливы два следующих утверждения: 1) если выполняется ограничение а'< а,< а" (i - 1,и), то для любого натурального п число эффективных оценок задачи Linel^(E,max) ограничено сверху полиномом от и второй степени; 2) если вьшолняются ограничения с' < с, < с" и d'<d,<d" (i = l,п), то для любого натурального п число эффективных оценок задачи Linel^(£, max) ограничено сверху линейной функцией от п.

§ 2.2 посвящен решению задач (1) - (3) на основе идеологии динамического программирования. В п. 2.2.1 выводятся соответствующие рекуррентные соотношения. Поясним технологию их построения на примере задачи Linel^(2, max).

Вводится в рассмотрение ряд частных задач Z(i, D), отличающихся от исходной задачи Linel^(£,max) только следующим: функции индивидуального штрафа по объектам oI+(, o,+2, ■■■ ,о„ тождественно нулевые, а общее время, затрачиваемое на обслуживание в рейсе Х+ объектов оьо2,...,о„ равно D. Через E{i,D) обозначим полную совокупность эффективных оценок в задаче Z(i, D). Тогда рекуррентные соотношения записываются в виде

Е(1,0) = {«рДуод + М( 1) + х, ), yKYo.i + М( 1) + -л)},

Е( 1, т0 = {<pi(y0,i + Tj ), Vi(y0,i + т,)},

£(1, D) = {(+оо, +оо)} при£>g {0, т,},

E(i + 1,D) = еМКиКт), где/е{1,2,... ,п-2),

Е(п, D) = effl,E{n-\,D-t„)@ {ф„(у0.1 + у,,2 + ... + Ъ-и + D), +

Yl,2+ ...+У„-1,п + jD)}).

Здесь Ki = E(i,D-xi+l) Ф {cp(+i(Yo,i + Y1.2 + ... + Y»,m + D\ V/+i(7o,i + ÏU + • • • + Yu+i + Щ, K2=E(i, D) ® {9î+i(yo,i + Yu +•■•+ Y;,i+i + D ++ M(i + 1», \|/,+i(y0,i + Y1.2 + ... + y,,/>1 + D + t,+i + Щ + 1))}; двуместная операция Ф и одноместная операция eff имеют следующий смысл.

Пусть х -(хьх2) обозначает двумерный вектор, a Y - множество векторов той же размерности, М- произвольное множество двумерных векторов-оценок. Выражением ввда У® х обозначаем совокупность V = (vi, V2) всех векторов, у которых первый компонент представим в виде V, = ух + а второй - определяется по правилу v2 = max(_y2,x2),

где >> = (уиу2)^У. е${М) обозначает максимальное по включению подмножество недоминируемых в М векторов.

С целью построения рекуррентных соотношений для решения задач

1лпе1!;(Е, £) и 1лпе1!;(тах,тах) в работе переопределяются введенные операции УФхс учетом специфики рассматриваемых критериев.

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

Утверждение 1. Алгоритм решения задачи Ьте1^(Е, шах) имеет псевдополиномиальную оценку трудоемкости: 0{п Т шах ц/ДГ*)).

Утверждение 2. Алгоритм решения задачи 1лпе1^(Е, 2) имеет псевдополиномиальную оценку трудоемкости: 0(п Т шах ц/ДГ*)).

Утверждение 3. Алгоритм решения задачи Ьте1^(тах, тах) имеет псевдополиномиальную оценку трудоемкости: 0(п Т тахц/ДГ*)).

Из теорем 1 и 2 и утверждений 1 и 2 следует, что задачи 1лпе1Х(2,тах) и Ьте1^(2, Е) являются ///"-трудными в слабом смысле.

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

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

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

В модели § 3.1 начальная точка А рабочей зоны I является базовой для тоЫ1е-процессоров Р1 и Рг- Начиная от момента времени г = О, процессор Р1 поступательно перемещается от исходной точки А к конечной точке В и, последовательно останавливаясь у части объектов совокупности От выполняет их однофазное обслуживание. Процессор Р2 начинает прямолинейное движение из точки А в точку В в момент

времени t = т0 (т0 > 0) и выполняет однофазное обслуживание остальных объектов группы.

Модель, описанная в § 3.2, отличается тем, что процессор Р2 начинает свое движение из точки В и перемещается к точке А . Стратегией обслуживания называем произвольное подмножество элементов р из совокупности индексов N= {1,2, ..., п}. Объекты, индексы которых входят в подмножество р, обслуживаются процессором Рь остальные объекты - процессором Р2.

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

В четвертой главе (Модели, задачи и алгоритмы синтеза стратегий однопроцессорного обслуживания стационарных объектов в рабочей зоне графовой структуры [5, 8, 9,11,21,32]) рассматривается общая модель однопроцессорного обслуживания, в которой объекты совокупности Оп находятся в вершинах неориентированного односвязного графа G, содержащего также некоторую базовую вершину А. Считается известной матрица О = {со,у} размерности (« + 1) •(« + ]), где

со ¡J - продолжительность перемещения процессора Р из вершины i в вершину j непосредственно; если такое перемещение недопустимо, то со¡j = со. По матрице Q, с помощью алгоритма Флойда может быть получена матрица Г = {уtJ} продолжительностей перемещения из вершины i в вершину j по кратчайшему пути. Стратегию обслуживания процессором Р объектов совокупности Оп определяем как перестановку Р = Oh h, •••, Q элементов множества {1,2,..., п}; объект совокупности 0„ с номером in согласно стратегии р обслуживается к-м по очереди {к = й).

Для введенной графовой модели однопроцессорного обслуживания поставлены бикритериальные задачи Graph 1(1, шах), Graph 1(2,2), Graph l(max, max), формульная запись которых идентична соответственно выражениям (1) — (3), и рекуррентные решающие соотношения построены на основании рассуждений, аналогичных изложенным в §2.2.

Дополнительно поставлена и рассмотрена следующая бикритери-альная задача, учитывающая суммарные расходы на перемещение тоЫ1е-процессора.

Задача Graph 1(2,Г). Найти полную совокупность Е эффективных по Парето оценок в бикритериальной проблеме:

min(jî>,(C,(p))), min(j> у lg ). (4)

9 ;=l P 4=1

Здесь a - некоторая положительная константа, определяющая затраты за единицу времени перемещения процессора.

Решающие соотношения для задачи (4) записываются в следующем виде:

£(0,0,0) = {(0,0)},

E = eff{[j[jE{t,i,On\{o,})).

I /=1л

Здесь кортеж (t, i, S) описывает состояние системы в момент времени / завершения обслуживания объекта о„ при этом S - совокупность объектов из От которые были обслужены раньше, чем о,.

Следующие три теоремы свидетельствуют об АгР-трудности в сильном смысле задач, в которых хотя бы один из критериев является аддитивным.

Теорема 10. Задача Graph 1(Е, шах) JVP-трудна в сильном смысле.

Теорема 11. Задача Graph 1(S, S) MP-трудна в сильном смысле.

Теорема 12. Задача Graph 1(2, Г) NP-трудна в сильном смысле.

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

Пятая глава (Алгоритмы синтеза субоптимальных стратегий обслуживания [1,4,6,7,10,12 - 17]) посвящена разработке решающих алгоритмов на основе концепции мягких вычислений, реализованной с использованием следующих метаэвристик: муравьиная колония, поиск с запретами, имитация отжига, эволюционно-генетическая парадигма. Построен также итеративный алгоритм синтеза субоптимальных стратегий обслуживания на основе концепции d-расписаний .

10 Коган Д.И., Федосенко Ю.С. Задача диспетчершации: анализ вычислительной сложности и полиномиально разрешимые подклассы // Дискретная математика. 1996. Т. 8, вып. 3. С. 135-147.

В качестве первого способа оценки А(Е, Е') качества аппроксимации паретовского множества Е синтезируемым метаэвристическим алгоритмом квазипаретовским множеством Е' предлагается формула avg ( min РW,Q);(W\g)))

avg p((W,Q); (0,0)) ^

(Ir,Q)eE

где p((W,Q); (W',Q')) = maxfl W -W'\,\Q-Q'\) - расстояние между двумя оценками, avg - операция вычисления среднего значения.

В качестве второго, дополнительного, способа оценки качества аппроксимации предлагается в формуле (5) учитывать только те оценки (W,Q) множества Е, для которых min p((W,Q);(W',£)'))< г, где s-

наперед заданное число, а также рассматривать число оценок Le, для которых min p(OF,ß);(0",ß'))>s.

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

Предложенные способы оценки качества аппроксимации использовались при анализе результатов вычислительных экспериментов наряду с оценкой времени отработки алгоритмов. По результатам анализа были сформулированы рекомендации по использованию алгоритмов для решения задач, рассмотренных в главах 2-4. Например, исходя из данных о зависимости длительностей отработки 9 решающих алгоритмов от числа объектов совокупности п, для задачи Linel^(£, 2) рекомендуется применять алгоритм ветвей и границ. На сводном иллюстрирующем графике (рис. 1, а) используются следующие обозначения:

Exact- алгоритм, основанный на идеологии динамического программировании; ВгВ - алгоритм ветвей и границ; GA - эволюционно-генетический алгоритм (Genetic Algorithm); SA - алгоритм имитации отжига (Simulated Annealing); TS - алгоритм поиска с запретами (Taboo Search).

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

Рис. 1. Зависимость времени отработки 9 решающих алгоритмов от числа объектов группировки п в задаче 1лпе1^(1,2).

В шестой главе (Программный комплекс поддержки управления снабжением плавучих добывающих комплексов дизельным топливом [18,23,25,29, 34]) рассматриваются прикладные задачи для построенных в главах 2-4 моделей обслуживания стационарных объектов тоЬПе-процессорами. Описывается разработанный программный комплекс [35], предназначенный для синтеза оптимальных и субоптимальных стратегий управления обслуживанием.

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

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

Основные результаты и. выводы

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

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

1.2. Обслуживание двумя попутными тоЬИе-процессорами совокупности объектов, рассредоточенных в одномерной рабочей зоне.

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

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

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

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

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

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

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

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

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

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

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

Публикации в рецензируемых журналах

1. Дуннчкнна, H.A. Бикритериальная модель и алгоритмы синтеза управлений обслуживанием группировки стационарных объектов [Текст] / H.A. Дуничкина, Ю.С. Федосенко // Информационно-измерительные и управляющие системы. - 2010. - №2. - С. 20-23.

2. Дуннчкнна, H.A. Бикритериальные задачи оптимизации обслуживания линейно рассредоточенной группировки стационарных объектов [Текст] / H.A. Дуничкина // Вестник Нижегородского университета им, Н.И. Лобачевского. - Нижний Новгород: Изд-во Нижегородского госуниверситета, 2011,- №6. - С. 232-237.

3. Дуннчкнна, H.A. Бикритериальные модели и алгоритмы синтеза Парето-оптимальных стратегий обслуживания линейно рассредоточенной группировки объектов [Текст] / H.A. Дуничкина II Бизнес-информатика, 2012. - N°l. -С. 17-23.

4. Дуничкина, H.A. Бикритериальная модель и алгоритмы синтеза оптимально-компромиссных стратегий однопроцессорного обслуживания линейной группировки стационарных объектов [Текст] / H.A. Дуничкина // Вестник Нижегородского университета им. Н.И. Лобачевского. - Нижний Новгород: Изд-во Нижегородского госуниверситета, 2012. -№1. - С. 175-181.

Статьи в журналах и трудах научных конференций

5. Шлюгаев, А.Ю. О реализации концепции d-расписаний в бикритериаль-ной задаче одностадийного обслуживания группы пространственно рассредоточенных объектов [Текст] / А.Ю. Шлюгаев, H.A. Дуничкина // XII нижегородская сессия молодых ученых. Математические науки. Нижний Новгород, 23-26 мая 2007 г. - Нижний Новгород: Изд-во Гладкова О.В., 2007. - С. 38-39.

6. Дуничкнна, H.A. Использование муравьиного алгоритма для решения однокритериальной задачи обслуживания группы стационарных объектов [Текст] / H.A. Дуничкина, Ю.С. Федосенко // Материалы научно-методической конференции профессорско-преподавательского состава, аспирантов и специалистов «ТРАНСПОРТ - XXI ВЕК». - Нижний Новгород: Изд-во ФГОУ ВПО «ВГАВТ», 2007. - С. 73-75.

7. Дуннчкнна, H.A. Реализация муравьиного алгоритма для решения бик-ритериальной задачи обслуживания группы стационарных объектов [Текст] / H.A. Дуничкина // Труды итоговой научной конференции учебно-инновационного комплекса «Модели, методы и программные средства» (Нижний Новгород, 27-30 ноября 2007 г.). - Нижний Новгород: Изд-во Нижегородского госуниверситета, 2007. - С. 134-137.

8. Дуничкина, H.A. Бикритериальная модель и алгоритмы синтеза расписаний однопроцессорного обслуживания тоЫ1е-процессором группировки стационарных объектов [Текст] / H.A. Дуничкина, Ю.С. Федосенко // Информационные системы и технологии ИСТ-2008. Материалы международной научно-технической конференции. - Нижний Новгород: НГТУ, 2008. - С. 225-226.

9. Дуничкина, H.A. Алгоритмы синтеза расписаний для бикритериальных моделей обслуживания транспортного типа [Текст] / H.A. Дуничкина // Интеллектуальные системы: Труды Восьмого Международного симпозиума / под ред. К.А. Пупкова. - М.: Русаки, 2008. - С. 178-182.

10. Дуничкина, H.A. Синтез решений в бикритериальной задаче однопроцессорного обслуживания группировки стационарных объектов [Текст] / H.A. Дуничкина, Ю.С. Федосенко // Технологии Microsoft в теории и практике программирования. Материалы конференции. Н.Новгород, 19-20 марта 2008 г. / под ред. проф. Р.Г. Стронгина. - Нижний Новгород: Изд-во Нижегородского госуниверситета, 2008. - С. 134—137.

11. Дуничкина, H.A. Бикритериальные модели и алгоритмы синтеза оптимально-компромиссных стратегий однопроцессорного обслуживания пространственно рассредоточенной группы стационарных объектов [Текст] / H.A. Дуничкина, Ю.С. Федосенко, А.Ю. Шлюгаев // Труды VII Международной конференции «Идентификация систем и задачи управления - SICPRO' 08» Москва 28-31 января 2008 г. Институт проблем управления им. В.А. Трапезникова РАН. -М.: Институт проблем управления им. В.А. Трапезникова РАН, 2008. -С. 1350-1365.

12. Шлюгаев, А.Ю. Об эффективности комплексного применения метаэв-ристических алгоритмов в бикритериальной задаче однопроцессорного обслуживания пространственно рассредоточенной группировки объектов [Текст] / А.Ю. Шлюгаев, H.A. Дуничкина И XIII нижегородская сессия молодых ученых. Математические науки: Материалы докладов. - Нижний Новгород, 2008. -С. 37-38.

13. Дуничкина, H.A. Муравьиный алгоритм синтеза стратегий обслуживания mobile-процессором группировки стационарных объектов [Текст] / H.A. Дуничкина // Сб. трудов аспирантов и магистрантов. Технические науки. -Нижний Новгород: Изд-во ННГАСУ, 2008. - С. 162-166.

14. Дуничкина, H.A. Применение муравьиного алгоритма для решения бикритериальной задачи обслуживания группы стационарных объектов [Текст] / H.A. Дуничкина, Ю.С. Федосенко // Проблемы теоретической кибернетики. Тезисы докладов XV международной конференции 2008. (Казань, 2-7 июня 2008 г.) - Казань: Отечество, 2008. - С. 30.

15. Dunichkina, N. Algorithms for bi-criteria single-machine scheduling problem of a spaced group of objects [Text] / N. Dunichkina // 3rd International IT Conférence 2008 "Information Technology in modem everyday life". Abstracts of présentations. 24.04.08 - 25.04.08. - Bonn-Rhein-Sieg University of Applied Sciences. -P. 4.

16. Дуничкина, H.A. Об оценке приближенных решений бикритериальных задач дискретного программирования [Текст] / Н.А. Дуничкина, Ю.С. Федосен-ко // Информационные системы и технологии ИСТ-2009. Материалы XV международной научно-технической конференции. - Нижний Новгород: НГТУ, 2009.-С. 300-302.

17. Дуничкина, Н.А. Опыт использования комбинированных алгоритмов для синтеза решений бикритериалыюй задачи обслуживания группировки объектов [Текст] / Н.А. Дуничкина, Ю.С. Федосенко // Технологии Microsoft в теории и практике программирования. Материалы конференции. Н.Новгород, 11-12 марта 2009 г. / под ред. проф. В.П. Гергеля. - Нижний Новгород: Изд-во Нижегородского госуниверситета, 2009. - С. 129-135.

18. Дуничкина, Н.А. Модель и алгоритмы синтеза оперативных планов снабжения дизельным топливом группировки плавучих добывающих комплексов [Текст] / Н.А. Дуничкина // Прикладная информатика и математическое моделирование: Межвузовский сборник научных трудов. -М.: МГУП, 2009. -С. 96-104.

19. Коган, Д.И. О синтезе стратегий обслуживания группы стационарных объектов в одномерной рабочей зоне процессора при наличии двух оценочных критериев [Текст] / Д.И. Коган, Ю.С. Федосенко, Н.А. Дуничкина // Новые информационные технологии. Сборник трудов XIII Всероссийской научно-технической конференции (Москва, 19-21 апреля 2010 г.). -М., МГУПИ, 2010. -С. 77-81.

20. Дуиичкина, Н.А. Синтез стратегий обслуживания стационарных объектов в бикритериальной модели с директивными сроками [Текст] / Н.А. Дуничкина // Информационные системы и технологии ИСТ-2010. Материалы XVI международной научно-технической конференции. - Нижний Новгород: НГТУ, 2010. - С. 327-328.

21. Дуничкина, Н.А. Оптимизация управления обслуживанием группировки пространственно рассредоточенной группировки стационарных объектов [Текст] / Н.А. Дуничкина, Ю.С. Федосенко, АЛО. Шлюгаев // Будущее технической науки: тез.докл. IX Междунар. молодеж. научно-техн. конф. - Нижний Новгород: НГТУ, 2010. - С. 51-52.

22. Дуничкнна, Н.А. Оптимизационные задачи обслуживания группировки стационарных объектов в линейной рабочей зоне mobile-npoueccopa при наличии двух оценочных критериев [Текст] / Н.А. Дуничкина, Ю.С. Федосенко // Технологии Microsoft в теории и практике программирования. Материалы конференции. - Нижний Новгород: Изд-во Нижегородского госуниверситета, 2010. -С. 131-133.

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

плексов [Текст] / H.A. Дуничкина, А.Ю. Шлюгаев // Материалы межвузовской научно-практической конференции студентов и аспирантов. «Современные тенденции и перспективы развития водного транспорта России» 12-13 мая 2010 года. - СПб.: СПГУВК, 2010. - С. 184-189.

24. Дуничкина, H.A. Синтез Парето-оптимальных стратегий в бикритери-альной задаче обслуживания группировки стационарных объектов в одномерной рабочей зоне двух идентичных тоЬПе-процессоров [Текст] / H.A. Дуничкина // Нижегородская сессия молодых ученых. Математические науки. Материалы докладов (15; 2010). -НижнийНовгород: ГладковаО.В., 2010.-С. 13-14.

25. Дуничкина, H.A. Алгоритмы бикритериального синтеза план-графиков снабжения топливом плавучих добывающих комплексов с учетом специфики зоны дислокации [Текст] / H.A. Дуничкина, А.Ю. Шлюгаев // Материалы международной научно-практической конференции «Водный транспорт России: инновационный путь развития» 6-7 октября 2010 года. Том 3 - СПб ■ СПГУВК, 2011. - С. 96-101.

26. Коган, Д.И. Задачи обслуживания линейно рассредоточенных стационарных объектов перемещающимися процессорами II [Текст] /Д.И.Коган, Ю.С. Федосенко, H.A. Дуничкина // VI Московская международная конференция по исследованию операций (ORM2010), Москва, 19-23 октября 2010 г.: Труды. - М.: МАКС Пресс, 2010. - С. 298-299.

27. Дуничкина, H.A. О вычислительной сложности бикритериальной задачи обслуживания группировки стационарных объектов в линейной рабочей зоне тоЫ1е-процессора [Текст] / H.A. Дуничкина // Информационные системы и технологии ИСТ-2011. Материалы XVII международной научно-технической конференции. - Нижний Новгород: НГТУ, 2011. - С. 340-341.

28. Коган, Д.И. Бикритериальные задачи обслуживания объектов перемещающимся в одномерной рабочей зоне процессором [Текст] /Д.И.Коган, Ю.С. Федосенко, H.A. Дуничкина // Новые информационные технологии: Сборник трудов XIV Всероссийской научно-технической конференции (Москва, 18-20 апреля 2011 г.) / Под ред. В. В. Никонова, А.Г.Шмелевой. -М.:МГУПИ, 2011. - С. 93-99.

29. Дуничкина, H.A. К созданию компьютерной системы поддержки управления снабжением топливом плавучих добывающих комплексов [Текст] / H.A. Дуничкина // Материалы II межвузовской научно-практической конференции студентов и аспирантов. «Современные тенденции и перспективы развития водного транспорта России» 12-13 мая 2011 года. - СПб.: СПГУВК 2011 -С. 256-262.

30. Коган, Д.И. Бикритериальные задачи обслуживания mobile-процессором рассредоточенных в одномерной рабочей зоне объектов [Текст] / Д.И. Коган, Ю.С. Федосенко, H.A. Дуничкина // Проблемы теоретической кибернетики. Материалы XVI Международной конференции. (Н.Новгород, 2025 июня 2011 г.). - Нижний Новгород: Изд-во Нижегородского госуниверситета, 2011. - С. 202-205.

31. Коган, Д.И. Бикритериальная задача построения стратегий обслуживания линейно рассредоточенных объектов [Текст] / Д.И. Коган, Ю.С. Федосенко, H.A. Дуничкина И Фундаментальные и прикладные проблемы приборостроения и информатики. Научные труды XIV Международной научно-практической конференции, посвященной 75-летию МГУПИ. - Москва, 2011. - С. 60-67.

32. Dunichkina, N. Bi-criteria optimization model and algorithms of servicing scheduling for a distributed objects group [Text] / N. Dunichkina // International conference on Operations Research. August 30 to September 2, 2011. OR 2011 Zurich. Book of abstracts. - Zurich, IFOR, Institute for Operations Research, ETH Zurich, 2011.-P. 20.

33. Коган, Д.И. Бикритериальные модели и парето-оптимальные стратегии обслуживания группировки стационарных объектов [Текст] / Д.И. Коган, Ю.С. Федосенко, H.A. Дуничкина // Труды IX Международной конференции «Идентификация систем и задачи управления - SICPRO' 12». Москва 30 января

- 2 февраля 2012 г. Институт проблем управления им. В.А. Трапезникова РАН.

- М.: Институт проблем управления им. В.А. Трапезникова РАН, 2012. -С. 287-300.

34. Дуничкина, H.A. Оптимизационные модели управления снабжением топливом плавучих добывающих комплексов [Текст] / H.A. Дуничкина // Научно-техническая международная молодежная конференция «Системы, методы, техника и технологии обработки медиаконтента»: Сб. тезисов. - М.: МГУП имени Ивана Федорова, 2011. - С. 3 5-3 6.

Свидетельство о регистрации программы для ЭВМ

35. Свидетельство о государственной регистрации программы для ЭВМ №2012611833. Программный комплекс поддержки оперативного управления снабжением топливом группировки плавучих добывающих комплексов [Текст] / H.A. Дуничкина. - заявл. 22.12.11; зарег. 17.02.12. - Федеральная служба по интеллектуальной собственности, патентам и товарным знакам РФ, Реестр программ для ЭВМ.

Формат 60x84 '/16. Гарнитура «Тайме». Ризография. Усл. печ. л. 1,0. Уч.-изд. л. 1,0. Тираж 100 экз. Заказ 063.

Издательско-полиграфический комплекс ФБОУ ВПО «ВГАВТ»

603950, Нижний Новгород, ул. Нестерова, 5а

ВВЕДЕНИЕ.

ГЛАВА 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.

К середине 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е-процессорами. Описывается разработанный программный комплекс, предназначенный для синтеза оптимальных и субоптимальных стратегий управления обслуживанием.

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

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

ЗАКЛЮЧЕНИЕ

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