Geum.ru
   Авторефераты по всем темам  >>  Авторефераты по техническим специальностям

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

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

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

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

е и промышленности) по физико-математическим наукам

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

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

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

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

профессор Федосенко Юрий Семенович доктор технических наук, Научный консультант:

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

Официальные оппоненты: Алексеев Владимир Евгеньевич, доктор физико-математических наук, профессор, Нижегородский государственный исследовательский университет им. Н.И. Лобачевского, профессор кафедры Математической логики и высшей алгебры Орлов Юрий Федорович, доктор физико-математических наук, профессор, Нижегородский государственный технический университет им. Н.И. Алексеева, профессор кафедры Прикладной математики Федеральное бюджетное учреждение науки

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Shen, H. Optimal Scheduling for Satellite Refueling in Circular Orbits // PhD thesis, School of Aerospace Engineering, Georgia Institute of Technology, Atlanta, Georgia, March 2003.

Дозаправка в полете гражданских самолетов: перспективы и проблемы / ЦАГИ. URL:

(дата обращения:

16.02.2012).

Участие поддержано грантом РФФИ, проект №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 источников.

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

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

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

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

Позиции 98, 350, 1016 Перечня российских рецензируемых научных журналов (

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

В первой главе (Методы решения и вычислительная сложность многокритериальных задач теории расписаний) проводится обзор:

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

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

Основным элементом дискретных моделей процессов обслуживания, рассматриваемых в диссертационной работе, является совокупность On = {о1, о2, Е, оn} стационарных объектов, расположенных в рабочей зоне обслуживающего mobile-процессора P. Считается, что рабочая зона L одномерна и конечна, её начальная точка А является базовой для процессора; объекты считаем пронумерованными в порядке возрастания их расстояний от точки А; конечная точка В зоны L является местом расположения объекта оn. Из точки А, начиная от момента времени t = 0, процессор поступательно перемещается к конечной точке В (прямой рейс +), а затем, достигнув её, также поступательно возвращается в точку А (обратный рейс Ц).

При реализации цикла + - процессор P выполняет одностадийное без прерываний обслуживание объектов группы On: часть объектов обслуживается в рейсе +, все остальные - в рейсе Ц. С каждым объектом оj ассоциируются две монотонно возрастающие (в нестрогом смысле) функции индивидуального штрафа j(t) и j(t), выражающие зависящие от момента завершения его обслуживания величины потерь по первому и второму показателям соответственно.

Примем обозначения: 1, 2, Е, n точки отрезка L, в которых расположены объекты о1, о2, Е, оn соответственно (точки n и В совпадают);

j - продолжительность обслуживания процессором P объекта оj; j-1,j и j,j-1 - затраты времени на перемещения процессора между точками (j - 1) и j в рейсах + и - соответственно (j = 1,n ); при этом 0,1 и 1,0 - затраты времени на перемещение процессора между точкой А и точкой 1 в прямом и обратном рейсах. Все числа j, j-1,j, j,j-1 считаем целыми положительными.

Стратегией обслуживания будем называть произвольное подмножество элементов из совокупности индексов N = {1, 2, Е, n}; объекты оj, где j, в реализации стратегии обслуживаются mobileпроцессором в рейсе +, все остальные объекты группы On - в рейсе Ц.

Для определенности полагаем, что объект оn обслуживается при завершении процессором рейса +. Таким образом, n; число различных стратегий обслуживания равно 2n-1.

Обслуживание любого объекта оj, jN, начинается от момента прибытия mobile-процессора в точку j при реализации определяемого стратегией рейса; по завершению обслуживания процессор продолжает своё движение. Не связанные с обслуживанием объектов промежуточные простои mobile-процессора запрещены. Любая стратегия однозначно определяет моменты начала и завершения обслуживания каждого из объектов. Через C () обозначим момент завершения обслуживания j объекта оj при реализации стратегии (j = 1, n ), а через T* - величину n k k,k1).

(k1,k k Если объект оj обслуживается в рейсе +, т.е. j , то j C () = , где (j) - совокупность не превосходящих j j k1,k k k 1 k( j ) элементов из . Если jN\, то обслуживание объекта оj реализуется j позже. Для величины введем обозначение j, а через k1,k k k1 k( j) М(j) обозначим задержку по объекту оj при переносе его обслуживания с прямого рейса на обратный; М(j) - это сумма трех слагаемых:

n (затраты времени на перемещение процессора от точки j к k1,k k jn точке n); (затраты времени на перемещение процессора от k,kk jn точки n к точке j); (суммарная продолжительность обслуживания k k jобъектов оj+1, оj+2,Е, оn). В итоге имеем общую формулу j , если j C () j j j M ( j), если j .

С позиций повышения эффективности управления обслуживанием совокупности объектов о1, о2, Е, оn ставятся следующие три задачи.

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

n min( (C ())), min(max (C ())).

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

n n min( (C ())), min( (C ())).

j j j j (2) j1 jЗ а д а ч а Line1 (max, max). Найти полную совокупность Е эф фективных по Парето оценок в бикритериальной проблеме минимизации величин максимального из индивидуальных штрафов j и максимального из индивидуальных штрафов j по всем объектам совокупности On:

min(max (C ())), min(max (C ())).

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

Теорема 1. Задача Line1(, max) NP-трудна.

Теорема 2. Задача Line1 (, ) NP-трудна.

Теорема 3. Для задачи Line1(, max) с линейными функциями ин дивидуального штрафа j (t), (t) (t), j = 1,n, проблема опредеj j ления по произвольным натуральным константам С1 и С2, существует ли стратегия обслуживания *, одновременно удовлетворяющая условиям n (C ()) С1 и max (C ()) С2, NP-трудна.

j j j j j jТеорема 4. Для задачи Line1 (, ) с линейными функциями инди видуального штрафа j (t), (t), j = 1, n, проблема определения по j произвольным натуральным константам С1 и С2, существует ли стратегия обслуживания *, одновременно удовлетворяющая условиям n n (C (*)) С1 и (C (*)) С2, NP-трудна.

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

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

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

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

Теорема 7. Пусть функции штрафа имеют вид i(t) = ait + bi, i(t) = cit + di, i = 1, n ; при этом для i = 1, n выполняются ограничения i , i-1,i,i,i-1 и хотя бы одно из ограничений a ai a или c ci c. Тогда для любого натурального n число эффективных оценок задачи Line1 (, ) ограничено сверху полиномом от n второй степени.

Теорема 8. Пусть функции штрафа имеют вид i(t) = ait + bi, i(t) = cit + di, i = 1, n ; при этом для i = 1, n выполняются ограничения i , i-1,i,i,i-1 и хотя бы одна из пар ограничений a ai a, b bi b или c ci c, d di d. Тогда для любого натурального n число эффективных оценок задачи Line1(max, max) ограничено свер ху линейной функцией от n.

Теорема 9. Пусть функции штрафа имеют вид i(t) = ait + bi, i(t) = cit + di (i = 1,n) и выполняются ограничения вида: i , i, i,i-1 (i = 1,n). Тогда справедливы два следующих утверждения:

1,i 1) если выполняется ограничение a ai a (i = 1,n), то для любого натурального n число эффективных оценок задачи Line1(, max) огра ничено сверху полиномом от n второй степени; 2) если выполняются ограничения c ci c и d di d (i = 1,n), то для любого натурального n число эффективных оценок задачи Line1(, max) ограничено сверху линейной функцией от n.

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

Вводится в рассмотрение ряд частных задач Z(i, D), отличающихся от исходной задачи Line1(, max) только следующим: функции инди видуального штрафа по объектам оi+1, оi+2, Е, оn тождественно нулевые, а общее время, затрачиваемое на обслуживание в рейсе + объектов о1, о2, Е, оi, равно D. Через E(i, D) обозначим полную совокупность эффективных оценок в задаче Z(i, D). Тогда рекуррентные соотношения записываются в виде E(1, 0) = {1(0,1 + М(1) + 1), 1(0,1 + М(1) + 1)}, E(1, 1) = {1(0,1 + 1), 1(0,1 + 1)}, E(1, D) = {(+, +)} при D{0, 1}, E(i + 1, D) = eff(K1, K2), где i{1, 2, Е, n - 2}, E(n, D) = eff(E(n - 1, D - n) {n(0,1 + 1,2 + Е + nЦ1,n + D), n(0,1 + 1,2 + Е + nЦ1,n + D)}).

Здесь K1 = E(i, D - i+1) {i+1(0,1 + 1,2 + Е + i,i+1 + D), i+1(0,1 + 1,2 + Е + i,i+1 + D)}, K2 = E(i, D) {i+1(0,1 + 1,2 + Е + i,i+1 + D + i+1 + М(i + 1)), i+1(0,1 + 1,2 + Е + i,i+1 + D + i+1 + М(i + 1))}; двуместная операция и одноместная операция eff имеют следующий смысл.

Пусть x = (x1, x2) обозначает двумерный вектор, а Y - множество векторов той же размерности, M - произвольное множество двумерных векторов-оценок. Выражением вида Y x обозначаем совокупность v = (v1, v2) всех векторов, у которых первый компонент представим в виде v1 y1 x1, а второй - определяется по правилу v2 max( y2, x2 ), где y = (y1, y2)Y. eff(M) обозначает максимальное по включению подмножество недоминируемых в M векторов.

С целью построения рекуррентных соотношений для решения задач Line1 (, ) и Line1(max, max) в работе переопределяются введен ные операции Y x с учетом специфики рассматриваемых критериев.

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

Утверждение 1. Алгоритм решения задачи Line1(, max) имеет псевдополиномиальную оценку трудоемкости: О(n T max (T *)).

j j Утверждение 2. Алгоритм решения задачи Line1(, ) имеет псев дополиномиальную оценку трудоемкости: О(n2 T max (T *)).

j j Утверждение 3. Алгоритм решения задачи Line1(max, max) имеет псевдополиномиальную оценку трудоемкости: О(n T max (T *)).

j j Из теорем 1 и 2 и утверждений 1 и 2 следует, что задачи Line1(, max) и Line1(, ) являются NP-трудными в слабом смыс ле.

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

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

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

В модели з 3.1 начальная точка A рабочей зоны L является базовой для mobile-процессоров P1 и P2. Начиная от момента времени t 0, процессор P1 поступательно перемещается от исходной точки A к конечной точке B и, последовательно останавливаясь у части объектов совокупности On, выполняет их однофазное обслуживание. Процессор P2 начинает прямолинейное движение из точки A в точку B в момент времени t 0 (0 0) и выполняет однофазное обслуживание остальных объектов группы.

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

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

В четвертой главе (Модели, задачи и алгоритмы синтеза стратегий однопроцессорного обслуживания стационарных объектов в рабочей зоне графовой структуры [5, 8, 9, 11, 21, 32]) рассматривается общая модель однопроцессорного обслуживания, в которой объекты совокупности On находятся в вершинах неориентированного односвязного графа G, содержащего также некоторую базовую вершину A. Считается известной матрица {i, j} размерности (n 1) (n 1), где i, j продолжительность перемещения процессора P из вершины i в вершину j непосредственно; если такое перемещение недопустимо, то i, j . По матрице с помощью алгоритма Флойда может быть получена матрица {i, j} продолжительностей перемещения из вершины i в вершину j по кратчайшему пути. Стратегию обслуживания процессором P объектов совокупности On определяем как перестановку = (i1, i2, Е, in) элементов множества {1, 2, Е, n}; объект совокупности On с номером ik согласно стратегии обслуживается k-м по очереди (k 1,n).

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

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

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

n n min( (C ())), min( i, iq ).

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

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

E(0,0,0) {(0,0)}, E(t,i,S) eff ({E(t i ,i, S \{oj}) (i (t);i (t))), j,i o j E eff ( \ {oi})).

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

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

Теорема 10. Задача Graph1(, max) NP-трудна в сильном смысле.

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

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

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

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

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

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

В качестве первого способа оценки E, E' качества аппроксимации паретовского множества E синтезируемым метаэвристическим алгоритмом квазипаретовским множеством E' предлагается формула avg ( ((W,Q); (W ',Q'))) min (W ',Q ')E ' (W,Q)E E, E' 100% (5) avg ((W,Q); (0,0)) (W,Q )E где ((W,Q); (W ',Q' )) max(| W W '|, | Q Q'|) - расстояние между двумя оценками, avg - операция вычисления среднего значения.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2. Дуничкина, Н.А. Бикритериальные задачи оптимизации обслуживания линейно рассредоточенной группировки стационарных объектов [Текст] / Н.А. Дуничкина // Вестник Нижегородского университета им.

Н.И. Лобачевского. - Нижний Новгород: Изд-во Нижегородского госуниверситета, 2011. - №6. - С. 232Ц237.

3. Дуничкина, Н.А. Бикритериальные модели и алгоритмы синтеза Паретооптимальных стратегий обслуживания линейно рассредоточенной группировки объектов [Текст] / Н.А. Дуничкина // Бизнес-информатика, 2012. - №1. - С. 17Ц23.

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

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

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

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

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

9. Дуничкина, Н.А. Алгоритмы синтеза расписаний для бикритериальных моделей обслуживания транспортного типа [Текст] / Н.А. Дуничкина // Интеллектуальные системы: Труды Восьмого Международного симпозиума / под ред.

К.А. Пупкова. - М.: Русаки, 2008. - С. 178Ц182.

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

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

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

Математические науки: Материалы докладов. - Нижний Новгород, 2008. - С. 37Ц38.

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

14. Дуничкина, Н.А. Применение муравьиного алгоритма для решения бикритериальной задачи обслуживания группы стационарных объектов [Текст] / Н.А. Дуничкина, Ю.С. Федосенко // Проблемы теоретической кибернетики.

Тезисы докладов 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 Conference 2008 УInformation Technology in modern everyday lifeФ. Abstracts of presentations. 24.04.08 - 25.04.08. - Bonn-Rhein-Sieg University of Applied Sciences. - P. 4.

16. Дуничкина, Н.А. Об оценке приближенных решений бикритериальных задач дискретного программирования [Текст] / Н.А. Дуничкина, Ю.С. Федосенко // Информационные системы и технологии ИСТЦ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-процессора при наличии двух оценочных критериев [Текст] / Н.А. Дуничкина, Ю.С. Федосенко // Технологии Microsoft в теории и практике программирования. Материалы конференции. - Нижний Новгород: Изд-во Нижегородского госуниверситета, 2010.

- С. 131Ц133.

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

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

25. Дуничкина, Н.А. Алгоритмы бикритериального синтеза план-графиков снабжения топливом плавучих добывающих комплексов с учетом специфики зоны дислокации [Текст] / Н.А. Дуничкина, А.Ю. Шлюгаев // Материалы международной научно-практической конференции Водный транспорт России:

инновационный путь развития 6 - 7 октября 2010 года. Том 3. - СПб.:

СПГУВК, 2011. - С. 96Ц101.

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

Труды. - М.: МАКС Пресс, 2010. - С. 298Ц299.

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

28. Коган, Д.И. Бикритериальные задачи обслуживания объектов перемещающимся в одномерной рабочей зоне процессором [Текст] / Д.И. Коган, Ю.С. Федосенко, Н.А. Дуничкина // Новые информационные технологии:

Сборник трудов XIV Всероссийской научно-технической конференции (Москва, 18Ц20 апреля 2011 г.) / Под ред. В. В. Никонова, А. Г. Шмелевой. - М.:МГУПИ, 2011. - С. 93Ц99.

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

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

31. Коган, Д.И. Бикритериальная задача построения стратегий обслуживания линейно рассредоточенных объектов [Текст] / Д.И. Коган, Ю.С. Федосенко, Н.А. Дуничкина // Фундаментальные и прикладные проблемы приборостроения и информатики. Научные труды XIV Международной научно-практической конференции, посвященной 75-летию МГУПИ. - Москва, 2011. - C. 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. Коган, Д.И. Бикритериальные модели и парето-оптимальные стратегии обслуживания группировки стационарных объектов [Текст] / Д.И. Коган, Ю.С. Федосенко, Н.А. Дуничкина // Труды IX Международной конференции Идентификация систем и задачи управления - SICPROТ 12. Москва 30 января - 2 февраля 2012 г. Институт проблем управления им. В.А. Трапезникова РАН.

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

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

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

Формат 6084 1/16. Гарнитура Таймс.

Ризография. Усл. печ. л. 1,0. Уч.-изд. л. 1,0.

Тираж 100 экз. Заказ 195.

Издательско-полиграфический комплекс ФБОУ ВПО ВГАВТ 603950, Нижний Новгород, ул. Нестерова, 5а    Авторефераты по всем темам  >>  Авторефераты по техническим специальностям