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

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

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

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

Как показал анализ научных публикаций, посвященных системному анализу, моделированию и оптимизации процессов оперативного управления ТТО [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. Разработанные модели, алгоритмы и программные средства внедрены в ОАО «Азимут», а также в учебный процесс Волжской государственной академии водного транспорта и факультета Вычислительной математики и кибернетики ННГУ им. Н. И. Лобачевского.

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