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

На правах рукописи 1/0-

Цветков Александр Игоревич

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

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

- 8 ДЕК 2011

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

Нижний Новгород - 2011

005004047

Работа выполнена на кафедре Информатики, систем управления и телекоммуникаций Федерального бюджетного образовательного учреждения высшего профессионального образования «Волжская государственная академия водного транспорта».

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

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

Официальные оппоненты: доктор технических наук

доцент Хранилов Валерий Павлович

кандидат физико-математических наук доцент Гришагин Владимир Александрович

Ведущая организация: Учреждение Российской академии наук

Институт машиноведения им. А.А. Благонравова РАН (г. Москва)

Защита состоится «22.» декабря 2011 г. в /3 часов на заседании диссертационного совета Д 212.165.05 при Нижегородском государственном техническом университете им. Р.Е. Алексеева по адресу: 603950, г. Нижний Новгород, ул. Минина, 24, корпус 1, аудитория^®.

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

Автореферат разослан «£/ » ноября 2011 г.

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

А.С. Суркова

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

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

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

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

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

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

А.А. Лазарева, С.Е. Ловецкого, Т.П. Подчасовой, М.Х. Прилуцкого, И.Х. Сигала, М.В. Ульянова, Ю.Ю. Финкелыптейна, А.Ю.Шлюгаева и - других авторов.

В контексте тематики диссертационной работы отметим сравнительно недавно опубликованные исследования М.Б. Резникова, Н. БЬеп и Р. ТБЮй-аБ, посвященные решению задач синтеза оптимальных стратегий управления обслуживанием совокупностей объектов подвижными процессорами (тоЬПе-процессорами). В частности, в работах М.Б. Резникова рассматривается задача оптимального управления обслуживанием конечных детерминированных потоков объектов в рабочей зоне тоЫ1е-процессоров, а в статье Н. 8Ьеп и Р. Тбю^б решается задача синтезу оптимального управления для модели дозаправки орбитальной группировки спутников. Указанные задачи, также как и задачи оптимального управления снабжением дизельным топливом русловых добывающих комплексов, исследованные в работах А.Ю. Шлюгаева, покрывают значительную, но далеко не полную часть всего многообразия возможных эксплуатационных ситуаций, в которых осуществляется ТТО.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2 Позиции 159,350, 1016 Перечня российских рецензируемых научных журналов (http://vak.ed.gov.ru/common/img/uploaded/files/201 l/enumeration/per-22-07-2011 .doc).

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

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

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

В § 1.1 приводится обзор моделей управления обслуживанием множеств и потоков объектов. Рассмотрены: одно- и двухпроцессорная модель обслуживания множеств объектов с линейными функциями индивидуальных штрафов; каноническая модель однопроцессорного обслуживания потока объектов; модель обслуживания группы пространственно рассредоточенных стационарных объектов подвижным процессором; модели обслуживания бинарных потоков объектов.

В § 12 приведены постановки задач синтеза оптимальных стратегий управления обслуживанием объектов в рамках рассмотренных в § 1.1 математических моделей. Рассмотрены методы их решения, а именно: ветвей и границ, динамического программирования и эвристические приёмы.

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

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

В § 2.1 строится следующая бикритериальная математическая модель обслуживания детерминированного бинарного потока объектов в линейной рабочей зоне тоЫ1е-процессора.

Имеется w-элементный детерминированный поток независимых объектов 0(п) = {о( 1), о(2),..., о(п)}, проходящих транзитом линейную рабочую зону Е (отрезок АВ фиксированной длины) обслуживающего тоЬПе-процессора Р. Поток 0(п) обладает, свойством бинарности, т.е. состоит из двух подпотоков Ол и О в, таких, что OavjOb = 0{п\ 0Аг\Ов = 0: объекты подпотока Ол равномерно проходят рабочую зону в прямом направлении от граничной точки А, а объекты подпотока Ов аналогично проходят зону S от граничной точки В в противоположном (обратном) направлении. В дискретной идеализации зона Е рассматривается как упорядоченная последовательность элементарных участков с номерами 1,2, ..., s - 1, s (рис. 1).

Р

-—О—-

О О О_ О О О

А 1 2 3 • ^ ■ s-3 s-2 5-1 sв

Рис. 1. Зона Е однопроцессорного обслуживания бинарного потока объектов

Любой объект потока 0(п) при транзитном прохождении зоны Е может быть однократно обслужен или остаться необслуженным; процесс обслуживания является однофазным и осуществляется без прерываний; незанятый обслуживанием тоЬПе-процессор считается готовым к обслуживанию очередного объекта. Номера участков, соответствующих моменту завершения обслуживания «предыдущего» объекта и моменту начала обслуживания следующего назначенного на обслуживание объекта могут совпадать. При этом обслуживание должно начинаться и заканчиваться в пределах зоны 5.

Каждый объект о(/) (/= 1,«) характеризуется целочисленными параметрами: t(i) - момент поступления в зону a; d(i) - указатель принадлежности подпотоку О a (d(i) = 1) или О в (d(i) = 0); х(0 ~ норма длительности пребывания объекта о(г) на элементарном участке; т(/)-норма длительности обслуживания объекта о(г) процессором Р (т(/) > 0); w(i) -величина дохода за обслуживание тоЬПе-процессором Р объекта о(г') (w(0 > 0); с(г) - величина штрафа за отказ в обслуживании процессором Р объекта o(i) (c(i) > 0).

В пределах зоны Е тоЫ1е-процессор Р может находиться в одном из трех состояний: автономное движение с постоянной скоростью в прямом или в обратном направлении; обслуживание назначенного объ-

екта потока 0(п) при совместном с ним движении в направлении и со скоростью последнего; простой в ожидании подхода объекта, назначен--ного на обслуживание. Движение процессора Р в пределах рабочей зоны Е характеризуется целочисленными параметрами: г - номер участка, на котором тоЫ1е-процессор Р находится в начальный момент времени / = 0 (г е {1,2,...,.?}); ТА, Тв- нормы времени пребывания процессора Р на элементарном участке в процессе автономного движения в направлении граничных точек В и А соответственно.

Стратегия обслуживания р объектов потока 0(п) тоЬПе-процессором Р представляет собой т-элементный кортеж (т е [0, и]):

= |(«Р1»У1)»(ф2»Уг).-.(Ф», V») при т > 1, [0 при т = 0. (}

В соотношении (1) использованы следующие обозначения: ср,- идентификатор объекта о(<ру), обслуживаемою тоЫ1е-процессором Р в очередь

3 (фу е П>"]> 7= 1.'«); щ - номер участка начала обслуживания объекта °(ф/) в очередь/ (у, е [1, $]). Символом а далее будем обозначать совокупность всех допустимых (физически реализуемых) стратегий р.

Суммарный доход Щр) за обслуживание объектов потока <Э(п) при реализации стратегии р определяется соотношением

м

Суммарный штраф г(р) за отказы в обслуживании объектов потока вычисляется по формуле

¿(р) = 2>(/)-С(р).

/=1

Здесь определяемый равенством

ш(р) . .

с(р) = £с(ф/р))

м

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

Суммарное расстояние, которое проходит тоЬПе-процессор Р, двигаясь в автономном режиме при реализации стратегии р, определяется соотношением

5(р) = |2-Ч/1(р)|+ 2 (р),<х(ф7.(р),(р)))+ т(фу.(р))- (р)|.

о(г, /) - номер участка, на котором находится объект о(г) в момент времени а(/, х) - момент поступления объекта / на участок с номером х.

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

(тахИЧрХттгСр)}. (2)

реП реП

В работе задача (2) рассматривается в следующей эквивалентной форме:

{шах ^(р), тахС(р)}. (3)

реи реП

С учетом дополнительного ограничения, накладываемого на суммарное расстояние Б(р), формулируется также задача оптимизации вида {шах^(р), тахС(р)} при условии 5(р) < 5*, (4)

где «5* - пороговое значение критерия 5(р).

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

В § 2.3 дано описание технологии решения бикритериальной задачи (3) на основе идеологии динамического программирования. При этом поток объектов 0(п) и обслуживающий их процессор Р рассматриваются в совокупности как дискретная управляемая система3, переходящая на каждом этапе обслуживания из текущего состояния ^ в последующее состояние ¿^-н под действием управления {со, и}, где со - номер назначенного на обслуживание объекта, а и - номер участка начала его обслуживания. Состояние системы определяется совокупностью параметров г, Л}, где момент завершения обслуживания очередного объекта процессором Р; г- номер элементарного участка зоны Е, на котором находится процессор Р в момент г; Л - множество обслуженных на момент г объектов.

В пункте 2.3.1 выводятся рекуррентные соотношения динамического программирования для реализации алгоритма М)Р1 синтеза полной совокупности эффективных в задаче (3) оценок и построения соответствующих им Парето-оптимальных стратегий управления обслуживанием:

3 Коган Д.И. Динамическое программирование и дискретная многокритериальная оптимизация. - Нижний Новгород: Изд-во Нижегородского госуниверситета, 2005. - 260 с.

= и^)'^))®^,)], (5)

[{ш,о}бФйу) ]

Д(Ы = {(0,0)}. (6)

В записи выражений (5>-<6) использованы обозначения: Ф(^) -множество допустимых управлений в текущем состоянии определяемое из кинематических соотношений; £и - состояние, соответствующее последнему этапу обслуживания. Двуместная операция Ф и одноместная операция имеют следующий смысл.

Пусть х = (х,, х2) обозначает двумерный вектор, а У- множество векторов той же размерности. Тогда х@У обозначает совокупность всех векторов V = (у,, у2), представимых в виде V = х + у, где у = (у1,у2)еУ.

Пусть М- произвольное множество двумерных векторов-оценок, тогда е/^М) обозначает максимальное по включению подмножество недоминируемых в М векторов.

Що) — множество эффективных в задаче (3) оценок, а — множество эффективных оценок в соответствующей частной бикритери-альной задаче.

Пункт 2.3.2 посвящен описанию примера реализации алгоритма решения задачи (3).

В пункте 2.3.3 на конкретном примере обсуждается вопрос устойчивости структуры решения задачи (3).

В пункте 2.3.4. предлагается модификация АОР2 реализации решающей задачу (3) схемы динамического программирования, основанная на аналогичных численным процедурам ветвей и границ вычислениях верхних оценочных значений

Щр) = > Щр) и С(р) = } >С(р) _

,еГ ■/=' /е Г

Здесь Г - множество необслуженных по завершению текущего д-го этапа управления объектов потока 0(п), для которых возможно окончание обслуживания в пределах рабочей зоны; ( V/ е ГД = 1Д ) - решения двух задач о ранце вида £8>(г)-»тах, ]П5'2с(0->тах при

<бГ /еГ

Х8*Т(0 - ' 8* е .' е Г, Лг- интервал значений времени, за пределами которого не может начаться обслуживание любого объекта множества Г.

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

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

В § 2.5 вводится в рассмотрение показатель S(р) - расстояние, пройденное процессором в автономном режиме при реализации стратегии р, что позволило рассмотреть задачу (4) для эксплуатационных ситуаций, в которых ЛПР приходится учитывать ограничение на максимальное значение этого показателя.

Кроме этого, такой подход целесообразен для случаев, когда одной эффективной в задаче (3) оценке соответствует несколько стратегий (такие ситуации возникают достаточно часто). Выбор среди них единственной стратегии может осуществляться с позиций минимизации значения показателя S(р). Для селекции же множества эффективных оценок ЛПР может ориентироваться на значение £(р).

В третьей главе (Бикритериальная математическая модель и оптимизация стратегий двухпроцессорного обслуживания бинарного потока объектов в линейной рабочей зоне [3-6, 8,10, 11,15]) строится модель обслуживания при наличии двух тоЬПе-процессоров, действующих в пределах крупномасштабной линейной рабочей зоны S.

В §3.1 строится модель обслуживания, принципиальное отличие которой от рассмотренной в § 2.1 заключается в наличии двух независимых и невзаимозаменяемых тоЬПе-процессоров Р' и Р2, осуществляющих однофазное обслуживание без прерываний объектов потока 0(п). При этом одновременное обслуживание одного объекта обоими тоЬПе-процессорами и одновременное обслуживание mobile-процессором более одного объекта запрещены.

Каждый объект о(0 характеризуется следующими целочисленными параметрами: /(/) - момент поступления в зону Е; d(i) - указатель принадлежности подпотоку О А или О в (й?(0 = 1, если о( 0 е 0А и d(i) = 0, если о(0 е Ов); %(i) - норма времени пребывания объекта на элементарном участке; w'(/) (w (i))- доход за обслуживание процессором Р1

(f) объекта o(i) (w'(/) > 0, w2(/') > 0); Д/) (т2(/)) -норма длительности обслуживания объекта о(/') процессором Р1 (Р2) (т'(г) > 0, т2(г) > 0).

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

Движение процессоров характеризуется следующими целочисленными параметрами: z — номер элементарного участка, на котором расположен процессор Рк в начальный момент времени t- 0

(z е {1,2, ..., 5}, £ = 1,2); ТАк(Твк)- норма длительности пребывания процессора Р11 на элементарном участке при его автономном движении в направлении от участка с номером 1 к участку с номером s (от участка

с номером s к участку с номером 1), к-1,2.

Стратегия обслуживания р объектов потока процессорами Р1 и Р2 определяется в виде пары {р1, р2}, где р* (А: = 1,2) представляет собой /я(А:)-элементный (m(k) е [0, и]) кортеж

|(ф?. Vf ). (9Î. V2 ).-» (<PÎ,<*>. Vi(t) ), при т{к) â 1, [0, при т(к) = 0.

в записи которого использованы следующие обозначения: — идентификатор объекта о(ср/), обслуживаемого процессором Рк в оче-

редьj (фу* е [1, и],у = 1 ,т(к)); V)//- номер участка начала обслуживания объекта о(ср/) в очередь j (\j;/ е [1, î]).

При реализации стратегии р суммарный доход W*(p) за обслуживание объектов потока 0{п) mobile-процессором /^определяется выражением

т(к) , > _

м

В рамках рассматриваемой модели имеет место бикритериальная задача оптийизации вида

{max W] (р), max W2 (р)}, (7)

prii реП

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

В § 3.2 строится алгоритм АОРЗ синтеза полной совокупности Па-рето-оптимальных в задаче (7) стратегий и соответствующих эффективных оценок на базе идеологии динамического программирования для бикритериального случая. Здесь в качестве дискретной управляемой системы выступает бинарный поток объектов 0(п) и обслуживающие их процессоры Р1 и Р2. Как и в главе 2, на каждом этапе управления этой системой формируется двумерный вектор-управление {со, и}, переводящий систему из текущего состояния ^ в следующее состояние ^у+ь Состояние системы определяется совокупностью параметров {/, д,р, Ь, 0, ЛЛ2}, где Г-дискретное время; д - номер свободного процессора (д е. [1,2]); р - участок зоны 2, на котором распложен процессор Р1 (р е [1;«]); Ь - номер объекта, обслуживание которого производит процессор Р^; 6 - число тактов времени, оставшегося до завершения обслуживания процессором Р(3"1) объекта о(Ь); Л*-множество обслуженных на момент времени / объектов процессором Рк (к = 1,2). Состояние ^о системы на начальном этапе характеризуется набором (0,1, г1, г2, 0,0,0).

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

В&}) = ед\ и \{а),а])®В^А, (8)

[{<о,о}бФ(5у) ]

Щи) = {(0,0)}. (9)

В записи соотношений (8)-{9) использованы следующие обозначения.

Вектор-оценка (а1;, а2,) определяется соотношением

(а1;, а]) = ((2 - (д - 1)^))

и имеет смысл оценки, к которой приводит выбранное в состоянии ^ управление; Ф(^) - множество допустимых управлений в текущем состоянии определяемое исходя из кинематических соотношений; ^н-состояние, соответствующее последнему этапу обслуживания. Операции Ф и ^аналогичны описанным в главе 2; 0) ~ множество эффективных оценок в задаче (7); - множество эффективных оценок в соответствующей частной бикритериальной задаче.

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

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

В § 4.1 содержится описание построенной модели и постановка соответствующей бикритериальной проблемы.

Имеется «-элементный детерминированный тернарный поток объектов &{п) = {о(1), о(2),...,о(и)}, проходящих транзитом трехкомпо-нентную узловую рабочую зону 3 тоЬПе-процессора Р, реализующего однофазное обслуживание объектов без прерываний. Зона 3 представляется как набор трех упорядоченных последовательностей элементарных участков с номерами 1,2,... sq, каждая из которых соответствует

ветви зоны 3 (q = 1,3). Тернарный поток &(п) состоит из б подпотоков

подпотока поступают в зону 3 по некоторой ветви, проходят через точку А и покидают ее по другой ветви. В пределах любого компонента зоны 3 перемещение объектов осуществляется равномерно.

Обслуживающий объекты тернарного потока (?{п) процессор Р характеризуется следующими целочисленными параметрами: м-номер ветви рабочей зоны, на которой расположен процессор Р в начальный момент времени Г = 0; г - номер элементарного участка на ветви и, на котором расположен процессор Р в момент / = 0; (Т+ч) - норма длительности пребывания процессора Р на элементарном участке при его автономном движении по д-й ветви рабочей зоны по направлению к

О) (/' = 1,6 ) таких, что \JJ=xOj = Ofy) и f^O, = 0. Объекты каждого

Рис. 2. Трехкомпонентная узловая рабочая зона mobile-npoueccopa

точке А (от точки А), д = 1,3; w(z') - доход за обслуживание объекта o(i), i = l,n; c(í) — штраф за отказ в обслуживании объекта o(i), i = 1 ,п.

Каждый объект o(i) характеризуется следующими целочисленными параметрами: /(;') - момент поступления объекта в зону 3; %(i) (х+(0) ~ норма времени пребывания объекта на элементарном участке при движении по направлению к точке А (от точки A); d~(i) (ct(/')) - номер ветви, по которой объект начинает движение в зоне Е (покидает зону Е), ¿Г (О Ф it (i); т(/)- норма длительности обслуживания объекта o(i) процессором Р.

Стратегия р обслуживания объектов мультипотока &{п) mobile-процессором Р представляет собой /и-элементный кортеж (т е [0, и])

в записи которого использованы следующие обозначения:

9/ ~ идентификатор объекта 0(<рД обслуживаемого процессором Р в очередь у (ф; е [1, л]); у,- - номер участка начала обслуживания объекта о(фу) в очередь у (у, е [1,5?]); 0у - номер ветви зоны Е, на которой расположен участок начала обслуживания ^ (9У = [1, к])^ = \,т.

В условиях рассматриваемой модели формулируется бикритериаль-ная задача, аналогичная (3).

В §4.2 на основе идеологии динамического программирования строится алгоритм АБР4. Соотношения динамического программирования имеют вид (5}-(6). При их построении мультипоток объектов С?(п) и обслуживающий их процессор Р рассматриваются в совокупности как дискретная управляемая система, переходящая на каждом этапе обслуживания из текущего состояния ^ в последующее состояние £,+1 под действием управления {ш, о, г)}, где <о- номер назначенного на обслуживание объекта, а и - номер участка начала его обслуживания, 1 - номер ветви рабочей зоны, на которой начинается обслуживание объекта о. Состояние системы определяется совокупностью параметров {и г, гч, Л}, где ¿-моментзавершения обслуживания очередного объекта процессором Р; г и ^-соответственно участок зоны 3 и номер ветви расположения освободившегося процессора Р; А - множество обслуженных на момент / объектов. Множество допустимых управлений строится исходя из кинематических соотношений.

Р =

(ф1»У1,01),(ф2.^2.02Х-,(фш,^т,0и)прит>1, 0 при т- О,

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

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

В пятой главе (Программный комплекс поддержки оперативного управления обслуживанием потока объектов [9,16]) приводится описание разработанного программного комплекса, предназначенного для синтеза стратегий управления обслуживанием бинарного потока объектов одним или двумя тоЬПе-процессорами, действующими в линейной рабочей зоне, а также стратегий управления обслуживанием мультипо-тока объектов в рабочей зоне тоЬПе-процессора, имеющей разветвленную узловую структуру. В основу математического обеспечения комплекса легли соответствующие бикритериальные модели и решающие алгоритмы АОР2, Ав, АОРЗ, АОР4.

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

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

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

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

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

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

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

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

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

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

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

1. Федосенко, Ю.С. Синтез стратегий управления в бикритериальной модели однопроцессорного обслуживания бинарного потока объектов [Текст] / Ю.С. Федосенко, А.И. Цветков // Информационно-измерительные и управляющие системы - М.: Радиотехника, 2011. - Т.9. - № 3. - С. 28-32.

2. Федосенко, Ю.С. Управление обслуживанием мультипотока объектов в узловой рабочей зоне mobilе-процессора [Текст] / Ю.С. Федосенко, А.И. Цветков // Вестник АГТУ. Сер. «Управление, вычислительная техника и информатика». - 2011. - № 2. - С. 164-170.

3. Федосенко, Ю.С. Задача синтеза оптимально-компромиссных стратегий обслуживания бинарного потока объектов в линейной рабочей зоне двух mobile -процессоров [Текст] / Ю.С. Федосенко, А.И. Цветков // Вестник нижегородского университета им. Н.И. Лобачевского. - Нижний Новгород: Изд-во Нижегородского госуниверситета, 2011. -№ 4. - с. 160-165.

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

4. Цветков, А.И. Задача оптимизации обслуживания потока объектов в рабочей зоне двух шоЫ1е-процессоров [Текст] / А.И. Цветков II Технологии Microsoft в теории и практике программирования. Материалы конференции / под ред. проф. В.П. Гергеля. - Нижний Новгород: изд-во Нижегородского госуниверситета, 2009. - С. 487-491.

5. Федосенко, Ю.С. Бикритериальная оптимизация обслуживания потока объектов в линейной рабочей зоне двух тоЫ1е-процессоров [Текст] / Ю.С. Федосенко, А.И. Цветков // Информационные системы и технологии ИСТ-2009. Материалы XV Международной научно-технической конференции. - Нижний Новгород: НГТУ им. P.E. Алексеева, 2009. - С. 302-304.

6. Цветков, А.И. Бикритериальная модель оптимизации технологии обслуживания транзитного судопотока на линейном русловом полигоне [Текст] / А.И. Цветков //11-й Международный научно-промышленный форум «Великие реки' 2009». Труды конгресса - Нижний Новгород: ННГАСУ, 2010. - Т.2. -С. 113-115.

7. Федосенко, Ю.С. Задача синтеза оптимально-компромиссных стратегий однопроцессорного обслуживания бинарного потока в линейной рабочей зоне mobile-npoueccopa [Текст] / Ю.С. Федосенко, А.И. Цветков // Технологии Microsoft в теории и практике программирования. Материалы конференции / под ред. проф. В.П. Гергеля. - Нижний Новгород: Изд-во ННГУ, 2010 -С. 378-380.

8. Федосенко, Ю.С. Оптимизация обслуживания потока объектов в линейной рабочей зоне двух тоЬПе-процессоров [Текст] / Ю.С. Федосенко, А.И. Цветков // Информационные системы и технологии ИСТ-2010. Материалы XVI Международной научно-технической конференции. - Нижний Новгород: НГТУ им. P.E. Алексеева, 2010.- С. 332-333.

9. Резников, М.Б. Математические модели для компьютерной системы поддержки управления обслуживанием транзитного судопотока на линейном участке [Текст] / М.Б. Резников, А.И. Цветков II Материалы межвузовской научно-практической конференции студентов и аспирантов «Современные тенденции и перспективы развития водного транспорта России» 12-13 мая 2010 года. - СПб.: СПГУВК, 2010. - С. 213-216.

10. Резников, М.Б. Управление обслуживанием бинарного потока объектов в рабочей зоне двух шоЬНе-процессоров [Текст] / М.Б. Резников, Ю.С. Федосенко, А.И. Цветков // Будущее технической науки: тез. докл. IX Международной молодежной научно-технической конференции. - Нижний Новгород: НГТУ им. P.E. Алексеева, 2010. - С. 55-56.

11. Цветков, А.И. Задача оптимизации обслуживания судопотока в зоне ответственности сервисного предприятия [Текст] / А.И. Цветков // 12-й Международный научно-промышленный форум «Великие реки' 2010». Труды конгресса. В 2 т. - Нижний Новгород: ННГАСУ, 2011. -Т.2. - С. 145-146.

12. Цветков, А.И. Бикритериальная модель и алгоритм синтеза стратегий однопроцессорного обслуживания потока объектов в узловой рабочей зоне [Текст] / А.И. Цветков // Theoretical and Applied Aspects of Cybernetics. Proceedings of the International Scientific Conference of Students and Young Scientists. -Kyiv: Bukrek, 2011. - C. 336-338.

13. Цветков, А.И. Синтез стратегий обслуживания потока объектов в узловой рабочей зоне mobile-npoueccopa при наличии двух критериев оценки эффективности [Текст] / А.И. Цветков // Информационные системы и технологии ИСТ-2011. Материалы XVII Международной научно-технической конференции. - Нижний Новгород: НГТУ им. P.E. Алексеева, 2011. - С. 342-343.

14. Цветков, А.И. Модели технического обслуживания транзитного судопотока в крупномасштабной зоне ответственности сервисного предприятия [Текст] / А.И. Цветков // Материалы II Межвузовской научно-практической конференции студентов и аспирантов «Современные тенденции и перспективы развития водного транспорта России» 12-13 мая 2011 года.-СПб.: СПГУВК, 2011.-С. 294-299.

15. Резников, М.Б. Синтез стратегий выбора объектов в линейной зоне обслуживания двух тоЬйе-процессоров [Текст] / М.Б. Резников, А.И. Цветков // Проблемы теоретической кибернетики. Материалы XVI Международной конференции (Нижний Новгород, 20-25 июня 2011 г.) / под ред. Ю.И. Журавлева. -Нижний Новгород: Изд-во Нижегородского госуниверситета, 2011.- С. 388392.

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

16. Свидетельство о государственной регистрации программы для ЭВМ №2011618694. Программный комплекс поддержки оперативного управления обслуживанием транзитного судопотока [Текст] / А.И. Цветков. - за-явл. 16.09.11; зарег. 08.11.11. - Федеральная служба по интеллектуальной собственности, патентам и товарным знакам РФ, Реестр программ для ЭВМ.

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

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

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

4

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Заключение

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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