Введение к работе
К середине XX века в научном мире сформировался устойчивый интерес к системному анализу и исследованиям проблем оперативного управления различными производственными процессами с целью повышения их эффективности. Та часть отмеченных проблем, которая математически адекватно описывалась в рамках дискретного формализма, со временем сформировалась в самостоятельную научную дисциплину, получившую название теория расписаний. В рамках этой теории изучаются вопросы, связанные с распределением и упорядочением конечного множества объектов (требований, заявок) в системах, включающих один или несколько обслуживающих эти объекты процессоров (приборов, машин).
Фундаментальные исследования по теории расписаний представлены в трудах B.C. Танаева (а также его учеников и коллег -B.C. Гордона, М.Я. Ковалева, А.А. Лазарева, Ю.Н. Сотскова, В.А. Стусевича, Я.М. Шафранского), В.В. Шкурбы, М. Garey, D. Johnson, E.G. Coffman, R.L. Graham, R.W. Conway, W.L. Maxwell, L.W. Miller, R.M. Karp. Применительно к различным проблемам управления дискретными ресурсами, в частности для моделей технологического обслуживания, задачи синтеза оптимальных решений - стратегий (расписаний) обслуживания исследовались в работах Д.И. Батищева, А.С. Беленького, В.Н. Буркова, Э.Х. Гимади, Д.И. Когана и Ю.С. Федосенко, А.А. Корбута, Е.В. Левнера, Д.А. Новикова, Т.П. Подчасовой, М.Х. Прилуцкого, И.Х. Сигала, М.В. Ульянова, Ю.Ю. Финкелыптейна и ряда других авторов.
В классических постановках задач отмеченного выше класса процессоры стационарны, а качество управления обслуживанием оценивается по значению скалярного критерия. Вместе с тем, в условиях рыночных отношений между субъектами хозяйственной деятельности и в связи с появлением инновационных производственных и транспортных технологий, реализуемых на крупномасштабных полигонах, объективно зрела необходимость введения в исследовательский оборот новых, более сложных математических моделей, в том числе с перемещающимся процессором (mobile-процессором), с двумя и более критериями оценки качества стратегий управления. Переход к таким моделям связан, с одной стороны, с естественным требованием обеспечения адекватности математического описания реальным приложениям, а с другой - с дополнительными трудностями, обусловленными необходимостью использования специальных принципов оптимальности, разработкой новых, обобщенных схем решения и нетривиальным анализом вы-
числительной сложности как самих оптимизационных задач, таки алгоритмов их решения. Именно эти обстоятельства обусловливают актуальность темы диссертационной работы, в которой очерченный выше круг вопросов рассматривается применительно к задачам управления реализацией транспортных технологий, адекватно моделируемых детерминированными системами обслуживания стационарных объектов в рабочей зоне mobile-процессоров. Соответственно целью работы является построение алгоритмов и вычислительных процедур с характеристиками, приемлемыми для использования в компьютерных системах поддержки оперативного управления процессами рассматриваемого класса.
Для достижения поставленной цели потребовалось выполнить анализ научных публикаций по теме исследования и рассмотреть следующие вопросы:
построение математических моделей обслуживания совокупности стационарных объектов в крупномасштабной рабочей зоне mobile-процессоров;
постановка бикритериальных задач оптимизации управления обслуживанием;
исследование вычислительной сложности задач оптимизации управления обслуживанием;
разработка алгоритмов синтеза оптимальных стратегий управления обслуживанием и оценка их трудоемкости;
разработка алгоритмов синтеза субоптимальных стратегий управления обслуживанием с приемлемыми для решения практических задач временными характеристиками.
Методы исследования. При выполнении работы использовались методы теории вычислительной сложности задач и алгоритмов, концепции многокритериальной оптимизации, динамического программирования, ветвей и границ, а также мягких вычислений.
Научная новизна работы состоит в следующих выносимых на защиту основных результатах.
Построены новые модели обслуживания mobile-процессорами совокупности стационарных объектов при наличии двух независимых критериев оценки качества стратегий обслуживания.
Для всех моделей п. 1 поставлены бикритериальные задачи оптимизации управления обслуживанием.
Гэри, М., Джонсон, Д. Вычислительные машины и труднорешаемые задачи. - М.: Мир, 1982.
Доказана серия теорем об Ж'-трудности задач п. 2 и о числе возможных стратегий обслуживания, оптимальных по Парето.
Разработаны решающие алгоритмы, реализующие в рамках концепции Парето многокритериальные схемы динамического программирования, а также ветвей и границ; получены оценки их трудоемкости.
Разработаны ускоренные вычислительные процедуры, учитывающие естественные для ряда транспортных технологий дополнительные ограничения на классы допустимых стратегий обслуживания.
Для синтеза субоптимальных решений поставленных в работе оптимизационных задач повышенной размерности сконструировано семейство вычислительных процедур, основанных на метаэвристических концепциях мягких вычислений.
Предложена методика определения отклонений квазипаретовских множеств оценок (полученных при реализации процедур п. 6) от паретовских множеств, позволяющая оценивать эффективность основанных на метаэвристиках вычислительных схем.
Теоретическая значимость результатов работы. Для бикритери-альных задач синтеза стратегий обслуживания стационарных объектов mobile-процессорами разработана методика построения рекуррентных соотношений динамического программирования. Указанные соотношения обеспечивают для всех видов решаемых задач синтез совокупностей эффективных оценок и возможность построения по любой из них соответствующей парето-оптимальной стратегии обслуживания.
Доказанные результаты об TVP-трудности подтверждают невозможность построения для соответствующих задач полиномиальных решающих алгоритмов в силу общепринятой гипотезы Р Ф NP.
Соответственно дальнейшие исследования для многокритериальных задач обслуживания стационарных объектов mobile-процессорами следует концентрировать на выделении полиномиально разрешимых подклассов, совершенствовании метаэвристических решающих алгоритмов, реализации концепций решения, предусматривающих синтез не всего паретовского множества, а его достаточно представительных совокупностей.
Практическая ценность полученных результатов заключается в том, что разработанные математические модели, решающие алгоритмы и программный комплекс могут применяться в компьютерных системах, предназначенных для поддержки управления обслуживанием пространственно рассредоточенной группировки стационарных
объектов. В частности, в рамках такого рода математических моделей и оптимизационных постановок описываются перспективные проектные решения управления дозаправкой орбитальной группировки спутников и магистральных гражданских самолетов . Отдельно отметим важную прикладную задачу диспетчерского управления снабжением дизельным топливом группировки плавучих добывающих комплексов, подробно рассмотренную в главе 6 диссертации.
Обоснованность и достоверность результатов работы
обеспечивается корректной реализацией использованного
математического аппарата и выполненными вычислительными экспериментами.
Реализация результатов работы^ Разработанные при выполнении диссертационных исследований модели и алгоритмы использовались при создании компьютерных систем поддержки оперативного управления и планирования в ОАО «Азимут» (Казань). Они также используются в учебном процессе с аспирантами, проходящими подготовку по научной специальности 05.13.01, со студентами специализации «Информационные и телекоммуникационные системы на транспорте» в Волжской государственной академии водного транспорта, а также на факультете Вычислительной математики и кибернетики Нижегородского государственного университета им. Н.И. Лобачевского. Разработанный программный комплекс зарегистрирован в Реестре программ для ЭВМ Федеральной службы по интеллектуальной собственности, патентам и товарным знакам РФ.
Апробация работы. Основные результаты диссертации докладывались и обсуждались на следующих научных форумах:
Международная конференция по исследованию операций "Operations Research OR'2011" (Zurich, Switzerland, 2011)4;
Третья международная ІТ-конференция "Information Technology in modern everyday life" (Bonn-Rhein-Sieg, Germany, 2008);
Международные конференции «Проблемы теоретической кибернетики» (Казань, 2008 и Нижний Новгород, 2011);
VI Московская международная конференция по исследованию операций ORM'2010 (Москва, 2010);
Shen, Н. Optimal Scheduling for Satellite Refueling in Circular Orbits II 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) ;
-Международные научно-технические конференции «Информационные системы и технологии» (Нижний Новгород, 2008-2011);
IX Международная молодежная научно-техническая конференция «Будущее технической науки» (Нижний Новгород, 2010) ;
Межвузовские научно-практические конференции студентов и аспирантов «Современные тенденции и перспективы развития водного транспорта России» (Санкт-Петербург, 2010, 2011);
Восьмой международный симпозиум «Интеллектуальные системы» (Нижний Новгород, 2008);
III Всероссийская студенческая научно-техническая конференция «Прикладная информатика и математическое моделирование» (Москва, 2009)8;
Международные конференции «Идентификация систем и задачи управления - SICPRO» (Москва, 2008, 2012);
Международная конференция «Водный транспорт России: инновационный путь развития» (Санкт-Петербург, 2010);
Всероссийская научно-техническая конференция «Новые информационные технологии» (Москва, 2010, 2011).
Публикации. Основные результаты диссертационных исследований отражены в 34 работах [1-34], в том числе в четырех статьях [1—4], представленных в Перечне рецензируемых научных журналов .
Личный вклад автора. Результаты, выносимые на защиту, получены соискателем лично или при его непосредственном участии. Им же лично подготовлены публикации [2^1], представленные в изданиях вышеупомянутого Перечня.
Структура и объем работы. Диссертация состоит из введения, шести глав, заключения и 3-х приложений; содержит 163 страницы текста; библиографический список включает 119 источников.
