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

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

Куимова Анастасия Сергеевна

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

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

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

1 я ДПР 2013

Нижний Новгород — 2013

005057560

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

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

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

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

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

Официальные оппоненты: Хранилов Валерий Павлович,

доктор технических наук, доцент, Нижегородский государственный технический университет им. P.E. Алексеева, кафедра «Компьютерных технологий в проектировании и производстве», профессор Таланов Владимир Александрович, кандидат физико-математических наук, доцент, Национальный исследовательский университет «Высшая школа экономики» в Нижнем Новгороде, кафедра «Прикладной математики и информатики», доцент

Ведущая организация: Федеральное бюджетное учреждение науки

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

Защита диссертации состоится «<gi~»алр^лл 2013 г. в /У часов в аудитории на заседании диссертационного ¿овета Д 212.165.05 при Нижегородском государственном техническом университете им. P.E. Алексеева по адресу: 603950, г. Нижний Новгород, ул. Минина, 24.

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

Автореферат разослан «¿6~» ucy>nna~'lQ 13 г.

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

Суркова Анна Сергеевна

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

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

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

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

Фундаментальным научным исследованиям по теории расписаний посвящены труды B.C. Танаева, В.В.Шкурбы, B.C. Гордона, Я.М. Шафранского, Ю.Н. Сотскова, В.А. Струсевича, М.Я.Ковалева,

A.A. Лазарева, M. Garey, D. Johnson, E.G. Coffman, R.L. Graham, R.W. Conway, W.L. Maxwell, L.W. Miller, R.M. Karp, P. Brucker, M.L. Pinedo.

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

B.Н.Буркова, Э.Х.Гимади, Д.И.Когана и Ю.С.Федосенко, А.А.Корбута, Д.А. Новикова, Т.П. Подчасовой, Ю.Ю. Финкелыльейна, М.Х. Прилуцкого, И.Х. Сигала, М.В. Ульянова, A.B. Шеянова и ряда других авторов.

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

ния ресурсов многоядерных вычислительных систем, выполнение в работах В.А. Костенко, М.Г. Курносова, A.B. Калашникова.

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

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

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

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

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

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

— анализ научных публикаций по теме исследования и существующих методов решения дискретных оптимизационных задач;

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Реализация результатов работы. Диссертационная работа выполнялась в соответствии с Федеральной целевой программой «Электронная Россия». Материалы диссертации послужили основой для проектирования систем поддержки организационного управления в ОАО «Салехардский речной порт». Результаты диссертации используются в учебном процессе студентами специализации «Информационные и телекоммуникационные системы на транспорте» в Волжской государственной академии водного транспорта и на факультете Вычислительной математики и кибернетики Национального исследовательского университета «ННГУ им. Н.И. Лобачевского». Разработанная программная реализация алгоритмов зарегистрирована в Реестре программ для ЭВМ Федеральной службы по интеллектуальной собственности, патентам и товарным знакам РФ [27].

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

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

— 25th European Conference on Operational Research, EURO'2012 (Vilnius, Lithuania, 2012).

— Нижегородские сессии молодых ученых (Нижний Новгород, 2011, 20121).

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

— Конкурс «Молодые ученые транспортной отрасли» в рамках V Международного форума «Транспорт России» (Москва, 20112).

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

— Международная конференция «XI Белорусская математическая конференция» (Минск, Республика Беларусь, 2012).

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

"Работа заняла второе призовое место.

— Научно-практическая конференция в рамках международного научно-промышленного форума «Великие реки» (Нижний Новгород, 2010, 20123).

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

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

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

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

— Всероссийская конференция «Высокопроизводительные параллельные вычисления на кластерных системах» (Нижний Новгород, 2011).

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

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

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

Краткое содержание работы

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

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

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

4Позиции 169, 35?, 1051 Перечня российских рецензируемых научных журналов (http://vak.ed.gov.ru/comraon/img/uploaded/fiIes/2013/enumeratioii/per-25-05-2012-6.doc).

Во второй главе (Модели, однокритериальиые задачи и алгоритмы синтеза стратегий обслуживания объектов в однопроцессорнохг системе с накопительно-расходным компонентом [1, 2, 5, 8, 11-14, 17, 18, 23, 25, 26]) выполняется построение базовых математических моделей обслуживания, для которых: а) формулируются однокритериальиые оптимизационные задачи синтеза стратегий обслуживания; б) конструируются решающие алгоритмы и выводятся оценки их трудоемкости; в) приводятся примеры реализации алгоритмов и обобщенные результаты массовых вычислительных экспериментов.

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

П. 2.1.1 в §2.1 посвящен рассмотрению математической модели обслуживания множества объектов Оп на стационарном процессоре. Для каждого объекта ¿»¿, г = 1. тг определены целочисленные параметры: т, - норма длительности обслуживания, ¿1 - мягкий директивный срок завершения обслуживания, V,; - объемная характеристика объекта. С каждым объектом о; ассоциируется монотонно возрастающая функция индивидуального штрафа (¿¿(г), выражающая зависящую от момента Ъ завершения обслуживания объекта величину потерь.

Множество Оп обладает свойством бинарности, т.е. состоит из двух подмножеств: «входящего» 0+ и «исходящего» 0~ таких, что 0+ и 0~ = Оп и О+(10~ — 0. Принадлежность объекта г = 1, п к тому или иному подмножеству определяется значением параметра «и; (ш; = +1, если о, € 0+\ и>1 = —1, если Ог € <Э~).

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

Накопительно-расходный компонент процессора представляет собой резервуар ограниченной емкости V*. В момент времени I объемная величина его заполнения характеризуется значением переменной (Ро - величина заполнения в начальный момент времени). В результате обслуживания объекта о; из подмножества 0+ (0~) заполнение резервуара увеличивается (уменьшается) на величину г^. Следовательно, обслуживание объекта 0{ из входящего подмножества 0+ возможно при наличии необходимого свободного объема в резервуаре, т.е. при выполнении условия \\ + < V*; обслуживание любого объекта ог из исходящего подмножества 0~ возможно при

наличии достаточного количества продукта в резервуаре, т.е. при выполнении УСЛОВИЯ 0 < 14 — Ь'г5.

Стратегия обслуживания множества Оп представляет собой перестановку 5 = {¿1 } совокупности шадексов объектов. Необходимым условием существования допустимых стратегий обслуживания является выполнение следующих объемных ограничений:

п

+ (1)

к=1

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

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

2 ■ Уг < V*,г = Т~п. (2)

В предположении (2) выполнение неравенств (1) необходимо и достаточно для непустоты множества П.

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

Задача 5е11К(]Р). Построить стратегию обслуживания Б, минимизирующую значение суммы индивидуальных штрафов (£) по всем объектам множества Оп:

п

п™(1><* №*.$)))■ (3)

Здесь и везде ниже через обозначен момент завершения обслу-

живания объекта с индексом при реализации стратегии 5.

Задача 8е:1Я(тах). Построить стратегию обслуживания 5, минимизирующую значение максимального из индивидуальных штрафов <¿>,(4) по всем объектам множества Оп:

ЗУЯ^Й0? (V«* №:,.?)))). (4)

Задачи (3) и (4) являются А'Р-трудными. В п. 2.1.3 приведен вывод решающих соотношений динамического программирования, соответственно

Е(гп + в, {а}, Цп+а) = ¥>„(«„ + е + га), (5)

'Близкая модель была рассмотрена в работе GafarovE.R., LazarevA.A., WernerF. Single machine scheduling problems with financial resource constraints: Some complexity results and properties //Mathematical Social Sciences, July, 2011. Elsevier. 2011. vol.62(1), P.7-13.

E{t, Q, Vt) = min [^(t + та) + E(t + Ta,Q\ {a}, Vt + wa • uQ))j (6)

об Q*

для задачи SetlR(J^) и

E(tn + в, {a}, Vtn+e) — 4>a(t n ~r v ~ 'a ), (7)

E{t., Q, Vt) = min [max{va(i + ra), E(t +ra,Q\ {a}, Vt + wa • г>а))}] (8)

ocÇQ*

для задачи SetlR(max).

В записи выражений (5)-(8) использованы обозначения: Q — множество индексов объектов, еще необслуженных в момент времени i; Q* — множество индексов объектов, допустимых к обслуживанию в текущем состоянии (Q* Q Q)> а — индекс допустимого к обслуживанию объекта; E(t, Q, Vt) — минимальная величина суммарного штрафа за период времени от момента t и до окончания процесса обслуживания всех объектов множества Оп.

Трудоемкость алгоритмов, реализующих рекуррентные соотношения (5), (6) и (7), (8), оценивается величиной 0(Н2пп2), где H = Х]"=0 п.

В п. 2.1.4 приводится пример решения задачи SetlR(^) при V* = 19, Vo = 10, ipi(i) = ai - tu наборе значений параметров из таблицы 1.

Таблица 1.

i и п Cli di Щ Wi

1 0 3 2 5 5 1

2 2 4 3 7 6 1

3 4 2 5 9 2 -1

4 5 4 6 9 7 -1

Решением примера является оптимальная стратегия обслуживания вида 5" = {3,4,2,1}. Ей соответствует величина суммарного штрафа для множества объектов 04, равная 50.

В п. 2.1.5 приводятся результаты вычислительных экспериментов, демонстрирующие зависимость продолжительностей решения задач БеИК^) и 8е1Ш(тах) от размерности множества Оп.

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

Для такой, обобщенной модели в п. 2.2.2 сформулированы задачи минимизации: Р1о\у1К(]Г) — суммы индивидуальных штрафов и Р1о\у1К(тах) — максимального из индивидуальных штрафов.

Соответственно, решающие рекуррентные соотношения динамического программирования имеют вид (п. 2.2.3)

Е(Ьп + в, {а}, У^+е) = 1ра&п + в + та), (9)

Е(1,0,14) = тт>а(* + та)+

а€<Э* (10)

Е(ь + та, (<2 \ {а}) и £>(4, га), Ц + гиа- уа))\

для задачи FlowlR(Y]) и

E(tn + в, {а}, Vt„+o) = <pa(tn + в + га), (И)

E{t, Q, Vt) = min [max{</3a(i + ra), E(t + ra,(Q\{a})uD(t,ra),Vt + wa-va))}} V

для задачи FlowlR(max).

В соотношениях (10), (12) через D(t, S) обозначена совокупность индексов объектов потока Оп, поступающих в систему обслуживания на интервале времени [i, t + <5], 5 > 1.

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

В § 2.3 описываются основанные на схеме ветвей и границ алгоритмы решения задач SetlR(^), SetlR(max), FlowlR^) и FlowlR(max) и приводятся результаты сравнительных вычислительных экспериментов. В частности, на рис. 1 представлены зависимости длительностей отработки 9 алгоритмов динамического программирования (DP) и ветвей и границ (ВпВ) на примере решения задачи FlowlR(^).

Рис, 1. Зависимости длительностей © отработки алгоритмов решения задачи Р1о\у1К(£) от размерности потока объектов Оп,

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

§2.4 посвящен алгоритмам синтеза субоптимальных решений задач 8еШ1(]Г), 8еиИ(тах), РкдаШ^) и Р1о\у1К(тах) повышенной размерности с использованием следующих метаэвристик мягких вычислений: эволюционно-генетическая парадигма (йА, п. 2.4.1), имитация отжига (БА, п. 2.4.2), поиск с запретами (ТЭ, п. 2.4.3). В п. 2.4.4 приведены результаты вычислительных экспериментов. Качество субоптимальных решений оценивалось по количеству х (в процентном выражении) точных совпадений с

оптимальными и в обобщенном виде проиллюстировано на рис. 2.

%

98 96 94 92 90 ВБ 86 84 82 80

8 9 10 11 12 13 14 15 11

Рис. 2. Зависимость качества субоптимальных решений от размерности

потока объектов.

В третьей главе (Модели, бикритериальные задачи и алгоритмы синтеза стратегий обслуживания объектов в однопроцессорной системе с накопительно-расходным компонентом [1-7, 10, 11, 13, 15, 16, 19-25]) рассмотрено расширение введенных в главе 2 базовых математических моделей на случай двух критериев оценки качества стратегий управления обслуживанием. Для этих моделей в рамках концепции Парето сформулированы бикритериальные задачи синтеза оптимальных стратегий обслуживания, сконструированы алгоритмы их точного и приближенного решения, приведены примеры реализации алгоритмов и результаты массовых вычислительных экспериментов.

В п. 3.1.1 вводится модель обслуживания множества объектов, принципиальное отличие которой от рассмотренной (п. 2.1.1) заключается в наличии не одной, а двух монотонно возрастающих (в нестрогом смысле) функций индивидуального штрафа <¿>¿(0 и Совокупно функции

г = 1, п выражают величины потерь по первому показателю эффективности, а -ф^ (Ь), г — 1, п — по второму.

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

Задача SetlR(£3, max). Найти полную совокупность парето-оптимальных оценок в проблеме минимизации суммы индивидуальных штрафов <Pi(t) по всем объектам под.множества 0+ и величины максимального из индивидуальных штрафов i!>i(t) по всем объектам подмножества 0~:

€ k:oikeO+ '°i,€

Задача SetlR(^, Найти полную совокупность парето-

оппишальных оценок в проблеме минимизации суммы индивидуальных штрафов <fii{t) по всем объектам подмножества 0+ и суммы индивидуальных штрафов 1pi(t) по всем объектам подмножества 0~:

{min( Yj ^(i(t*.£))),mjn( Е ^,№,5)))}. (14)

fc:oi(c60+ ьчео-

Задача SetlR(max,шах). Найти полную совокупность парето-оптимальных оценок в проблеме минимизации величины максимального из индивидуальных штрафов >Pi(t) по всем объектам подмножества и величины максимального из индивидуальных штрафов ipi(t) по всем объектам подмножества 0~:

{min( max ipik {t(ik, S))), min( max ^¡(¿(¿i, 5)))}. (15)

В п. 3.1.3 конструируются алгоритмы решения задач (13)-(15) на основе идеологии динамического программирования в его бикритериальном расширении.

Решающие рекуррентные соотношения для задачи SetlR(^) max) имеют вид

E(tn + в, {a}, Vtn+e) = {VaUn + в + ra), i>a(t.n + в + та)}, (16)

E(t,Q,Vt) = eff{ U [(v(i + Ta),^(i + ra))®

a&Q' (17)

E(t + ra,Q\ {a},Vt + tua • «„)]}.

В соотношениях (16), (17) запись E(t,Q,Vt) обозначает совокупность эффективных по Парето двумерных оценок, сгенерированную за период времени от момента t и до окончания процесса обслуживания всех объектов множества Оп. Двуместная операция & и одноместная операция eff имеют следующий смысл.

Пусть х = (х\, х2) — двумерный вектор, а Y — множество векторов той же размерности, М — произвольное множество двумерных векторов-оценок.

Выражением вида х®У обозначаем совокупность векторов вида z = (zi, z2), в которых Z\ = ух + жь а г2 = тах(у2,х2), где у = (у!,у2) е Y. eff(M) обозначает максимальное по включению подмножество недоминируемых в М векторов.

Для решения задач SetlR(£), и SetlR(max, max) используются соотношения (16) и (17), в которых операция ® объединения вектора и множества векторов определяется следующим образом.

Выражение х @ Y означает совокупность векторов z = (21,22), в которых при решении задачи SetlR(]T, ]Г) компоненты представимы в виде z\ = У\ + Л'1 и г2 = У2 + х2, а при решении задачи SetlR(max, max) — zi = max{yi,xi), z2 ~ max(y2,a:2).

Трудоемкость алгоритмов, реализация которых обеспечивает решение задач SetlR(^, max) и SetlR(max,max), оценивается величиной maxДля задачи SetlR(]T. этот показатель характеризуется величиной 0(Н2пп2 max il>i(H)), где Я = V" т,.

i:OiQO~ ¿-«»—и

В п. 3.1.4 для задачи SetlR(]T, max) приводится численный пример, демонстрирующий на наборе данных из таблицы 1 процесс построения полной совокупности эффективных оценок {(71,4); (67,5); (59,8)}; соответствующие стратегии обслуживания имеют вид {2,1,3,4}, {2,3,1,4}, {4, 3,2,1}.

В п. 3.1.5 приводятся результаты массовых вычислительных экспериментов.

В § 3.2 формулируется математическая модель обслуживания бинарного потока объектов, отличие которой от рассмотренной в §3.1 заключается в учете моментов поступления tj, i = 1,тг объектов в очередь на обслуживание.

В рамках введенной модели в п. 3.2.2 сформулированы бикритериальные задачи типа (13), (14), (15), соответственно FlowlR(£, max), FlowlR(]T, V) и FlowlR(max, max). Для их решения в п. 3.2.3 и п. 3.2.4 построены решающие рекуррентные соотношения динамического программирования и приведены результаты массовых вычислительных экспериментов.

§ 3.3 посвящен конструированию и оценке быстродействия алгоритмов ветвей и границ для решения бикритериальных задач FlowlRf^, max), FlowlR(£, J2), FlowlR(max, max).

На рис. 3 представлены зависимости от размерности потока Оп длительностей 9 отработки алгоритмов динамического программирования (DP) и ветвей и границ (ВпВ) при решении задачи FIowlR(£, max).

В § 3.4 рассмотрены модификации модели обслуживания, учитывающие ограничения на допустимые величины опережений в очереди на обслуживание. Данный подход основан на введенных понятиях <1- и g-стратегий об-

Рис. 3. Зависимость длительностей отработки 0 алгоритмов решения задачи FlowlRi^, max) от размерности потока Оп.

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

§3.5 посвящен описанию сконструированных в диссертации алгоритмов решения задач Flow IR(£, max), FlowlR(£.£) и FlowlR(max, max) повышенной размерности на основе метаэвристических концепций мягких вычислений GA, SA, TS. На рис. 4 представлены результаты оценки качества аппроксимации парето-множества синтезируемым метаэвристикой квазипарето-множеством, которое оценивалась по значению среднего нормированного отклонения А(М, М*).

Рис, 4. Отклонение полученных решений от точного решения.

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

В четвертой главе (Модели, бикритериальные задачи и алгоритмы синтеза стратегий обслуживания потока объектов в однопроцессорной системе с двумя накопительно-расходными компонентами [1-3, 23, 25]) построена модель обслуживания бинарного потока объектов, которая отличается от рассмотренной в § 3.2 наличием двух накопительно-расходных компонентов.

Каждый накопительно-расходный компонент процессора представляет собой резервуар ограниченной емкости V*, предназначенный для промежуточного хранения продукта вида /¿, // = {1,2}. В момент времени Ь объемная величина заполнения компонента Ям характеризуется переменной с начальным значением 1^.(0).

Каждый объект потока Оп может быть одного из двух типов Аь А* = {1,2} и однозначно определяется видом продукта /(, для транспортировки которого он предназначен.

Обозначим через с\'(р. а) функцию изменения объемной характеристики компонента определяемую по формуле

( 0, если Аа ф /х, с*) = < (18)

[ гиа ■ уа, если Аа = ц,

где а — произвольный индекс объекта оа потока Оп.

Объект оа допустим к обслуживанию, если выполняются объемные ограничения вида 0 < + а) < V*. Обозначим через И множество всех допустимых стратегий. В общем случае проверка непустоты множества является АУ-полной задачей. Как очевидно, выполнение неравенств

п

0<^(0) + ^Су(^,г)<1/; (19)

г=1

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

2 • и, < тт(У[*, У2*), г = Т7п. (20)

В предположении (20) выполнение неравенств (19) является необходимым и достаточным условием непустоты множества О.

В § 4.2 в рамках модели с двумя накопительно-расходными компонентами сформулированы бикритериальные задачи вида (13), (14), (15), соответственно Р1о\\'211(^, тах), Р1о\у211(£3, О и Р1о\у2Я(тах, тах).

В § 4.3 построены решающие алгоритмы динамического программирования вида

Е(±п + в, {а}, Цп+в) = {<ра(Ьп +в + та), У'а(«п + 0 + Та)}, (21)

аед- (22)

Е(Ь + та, (О \ {а}) и £>(«, га), УМ) + ст(1, а), У2(1) + су(2, а))]}.

Оценка трудоемкости алгоритма, реализующего соотношения (21), (22) для решения задач Flow2R(]P, max) и Flovv2R(max, max), представляет собой величину 0(L2nn max ф^Ь)), где L = tn + rt-

i.Oi&O-

Трудоемкость решения задачи Flow2R(J^,X3) оценивается величиной 0{Ь1пп2 max &•(£,)).

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

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

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

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

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

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

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

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

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

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

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

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

5. Сконструированы основанные на метаэвристических концепциях мягких вычислений алгоритмы построения субоптимальных множеств оценок.

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

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

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

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

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

1. Кушюва, A.C. Управление однопроцессорным обслуживанием бинарного потока объектов в системе с накопительным компонентом [Текст] / А.С.Куимова, Д.В.Минаев, Ю.С.Федосенко // Журнал Информационно-измерительные и управляющие системы. — Москва : Издательство «Радиотехника», 2011. - т. 9, №3. - С. 33-37.

2. Куимова, А. С. Синтез стратегий обслуживания бинарного потока объектов стационарным процессором с накопительным элементом [Текст] / A.C. Куимова, Д.В. Минаев, Ю.С. Федосенко И Вестник АГТУ. Серия: Управление, вычислительная техника и информатика. — Астрахань : Издательство АГТУ, 2011. - №2. - С. 150-157.

3. Куимова, A.C. Реализация концепции параметризованной сложности в бикритериальной модели управления обслуживанием потока объектов [Текст] / A.C. Куимова // Вестник Нижегородского университета

им. Н.И. Лобачевского. — Н.Новгород : Издательство Нижегородского госуниверситета, 2012. -№5(2) — С. 131-135.

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

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

- С. 329-330.

5. Кугшова, A.C. Развитие математической модели для компьютерной системы поддержки управления очередностью обработки речных судов [Текст] / A.C.Куимова, Д.В.Минаев // Материалы I межвузовской научно-практической конференции студентов и аспирантов «Современные тенденции и перспективы развития водного транспорта России» 12-13 мая 2010 года. - СПб. : СПГУВК, 2010. - С. 195-197.

в. Куимова, А С. Модель и алгоритм синтеза стратегий обслуживания потока объектов в системе с накопительным элементом при наличии двух оценочных критериев [Текст] / A.C.Куимова, Д.В.Минаев // Технолог™ Microsoft в теории и практике программирования. Материалы всероссийской конференции молодых ученых / под редакцией проф. В.П. Гергеля.

— Н.Новгород : Издательство Нижегородского госуниверситета, 2010. — С. 241-243.

7. Кугшова, A.C. Особенности распараллеливания алгоритма оптимизации в задаче однопроцессорного обслуживания потока объектов [Текст] / A.C. Куимова // Сборник трудов научного конгресса 12-го международного научно-промышленного форума «Великие реки'2010». — Н.Новгород : ННГАСУ, 2010. - Т. 2. - С. 149-151.

8. Куимова, A.C. Диспетчеризация однопроцессорного обслуживания по-' тока объектов [Текст] / A.C.Куимова, Д.В.Минаев, Ю.С.Федосенко // Будущее технической науки: тезисы докладов IX Международной молодежной научно-технической конференции. — Н.Новгород : НГТУ, 2010. — С. 104-109.

9. Куимова, A.C. Параллельные алгоритмы решения задачи диспетчеризации грузовой обработки бинарного судопотока в условиях Салехардского речного порта [Текст] / A.C. Куимова, Д.В. Минаев // Материалы международной научно-практической конференции «Водный транспорт России: инновационный путь развития». 6-7 октября 2010 года. — СПб. : СПГУВК, 2011.-С. 104-109.

\0. Куимова, A.C. О канонической задаче диспетчеризации с двумя критериями оценки [Текст] / A.C. Куимова // Материалы международной научно-практической конференции «Водный транспорт России: инноваци-

онный путь развития». 6-7 октября 2010 года. — СПб. : СПГУВК, 2011. — С. 109-114.

11. Кушюва, A.C. Синтез оптимально-компромиссных стратегий в однопроцессорной модели с ограниченной дисциплиной обслуживания потока объектов [Текст] / A.C. Куимова // Theoretical and Applied Aspects of Cybernetics. Proceedings of the International Scientific Conference of Students and Young Scientists. - Kyiv : Bukrek, 2011. - C. 333-335.

12. Кушюва, A.C. Опыт реализации технологии CUDA в вычислительных задачах диспетчеризации [Текст] / A.C.Куимова, Д.В.Минаев, Ю.С. Федосенко // Информационные системы и технологии ИСТ-2011. Материалы XVII международной научно-технической конференции. — Н.Новгород : НГТУ, 2011. - С. 339.

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

14. Кушюва, A.C. Параллельная реализация алгоритма синтеза оптимальной стратегии однопроцессорного обслуживания потока объектов в стандарте Open MP [Текст] / A.C. Куимова // 16-я Нижегородская сессия молодых ученых (математические науки), «Красный плес», 18-21 апреля 2010 г.

— Н.Новгород : изд. Гладкова О. В., 2010.

15. Кушюва, A.C. Синтез ограниченных по структуре оптимально-компромиссных стратегий обслуживания потока объектов [Текст] / A.C. Куимова, Ю.С. Федосенко // Вестник Национального технического университета «ХПИ». Сборник научных трудов. Тематический выпуск: Информатика и моделирование. — Харьков : НТУ «ХПИ», 2011. — №17. — С. 70-75.

16. Кушюва, A.C. Задача синтеза стратегий обслуживания потока объектов в системе с накопительным компонентом [Текст] / A.C. Куимова, Д.В. Минаев, Ю.С. Федосенко // Проблемы теоретической кибернетики. Тезисы докладов XVI Международной конференции, г. Нижний Новгород, 20-25 июня 2011г. — Н.Новгород : Издательство Нижегородского госуниверситета, 2011. - С. 495^199.

17. Куимова, A.C. Опыт распараллеливания алгоритма динамического программирования для задачи синтеза стратегий обслуживания потока объектов [Текст] / A.C. Куимова // Высокопроизводительные параллельные вычисления на кластерных системах. Материалы XI Всероссийской конференции (Н.Новгород, 2-3 ноября 2011 г.) / под редакцией проф. В.П.Гергеля.

— Н.Новгород : Издательство Нижегородского госуниверситета, 2011. — С. 181-185.

18. Куимова, A.C. Модели и алгоритмы для компьютерной системы поддержки управления обработкой танкерного флота в условиях водных путей приполярного региона [Текст] / A.C. Куимова, Д.В. Минаев // Научно-техническая международная молодежная конференция «Системы, методы, техника и технологии обработки медиаконтента»: Сборник тезисов. — М. : МГУП им. Ивана Федорова, 2011. - С. 63.

19. Куимова, A.C. Об алгоритмах синтеза стратегий управления однопроцессорным обслуживанием потока объектов в системе с накопительным элементом [Текст] / A.C. Куимова // 17-ая Нижегородская сессия молодых ученых (технические науки), «Морозовский», 19-22 марта 2012 года. — Н.Новгород : НИУ РАНХиГС, 2012. - С. 93-96.

20. Куимова, A.C. О параметризации вычислительной сложности бикри-териальной задачи управления обслуживанием потока объектов в системе с накопительным элементом [Текст] / A.C. Куимова, Ю.С. Федосенко // Информационные системы и технологии ИСТ-2012. Материалы XVIII международной научно-технической конференции. — Н.Новгород : НГТУ, 2012. — С. 319.

21. Куимова, A.C. Модификация концепции d-расписаний для бикри-териальной задачи обслуживания бинарного потока объектов в стационарной однопроцессорной системе с накопительным элементом [Текст] / A.C. Куимова, Ю.С. Федосенко // Труды 14-го международного научно-промышленного форума «Великие реки - 2012». Материалы научно-методической конференции профессорско-преподавательского состава, аспирантов, специалистов и студентов «Проблемы использования и инновационного развития внутренних водных путей в бассейнах великих рек». — Н.Новгород : Издательство ФБОУ ВПО «ВГАВТ», 2012. - Т. 1. - С. 74-77.

22. Куимова, A.C. Модели сравнения двух множеств оценок для бикри-териапьных задач синтеза оптимизированных по Парето решений [Текст]' / A.C. Куимова, Н.А. Дуничкина // Труды 14-го международного научно-промышленного форума «Великие реки - 2012». Материалы научно-методической конференции профессорско-преподавательского состава, аспирантов, специалистов и студентов «Проблемы использования и инновационного развития внутренних водных путей в бассейнах великих рек». — Н.Новгород : Издательство ФБОУ ВПО «ВГАВТ», 2012. - Т. 1. - С. 71-74.

23. Куимова, A.C. Модель и алгоритмы синтеза стратегий обслуживания бинарного потока объектов при наличии двух критериев оценки [Текст] / A.C. Куимова // XI Белорусская математическая конференция: Тезисы докладов Международной научной конференции. Минск, 5-9 ноября 2012. — Минск : Институт математики HAH Беларуси, 2012. — Ч. 4. — С. 91-92.

24. Куимова, A.C. Bi-criteria optimization problem of binary objects flow servicing by stationary service processor with storage container [Текст] /

A.S. Kuimova // 25th European Conf. on Operational Research, EURO 2012 : Conference Programme, Vilnius, Lithuania, 8-11 July, 2012. — Sei. Comm. : M. Christiansen [et.al.]. The Association of European Operational Research Societies, 2012.-P. 193.

25. Куимова, A.C. Оптимизация оперативных планов обработки танкерного флота в условиях салехардского порта: модели и алгоритмы синтеза [Текст] / A.C. Куимова, Ю.С. Федосенко // «1НФОРМАЦЕЙН1 УПРАВЛЯЮЧ1 СИСТЕМИ ТА ТЕХНОЛОГИ» (1УСТ-ОДЕСА-2012). Тези доповщей. Ма-тер1али Всеукрашськн науково! — практично! конференцп, 17-18 жовтня 2012 р., Одеса / видп. ред. В.В. Вичужанш. — Суми : TOB «Друкарсышй д1м «Ilapipyc», 2012. — С. 124-126.

26. Куимова, A.C. Алгоритмы решения задачи диспетчеризации грузовой обработки судопотока в условиях Салехардского речного порта [Текст] / A.C. Куимова // Сборник докладов 60-й Международной молодежной научно-технической конференции «МОЛОДЕЖЬ.НАУКА.ИННОВАЦИИ», 17-18 сентября 2012г. — Владивосток : Мор. гос. ун-т, 2012. — Т. 1. — С. 133— 138.

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

27. Куимова, A.C. Программа синтеза оптимально-компромиссных стратегий обслуживания потока объектов в задаче диспетчеризации [Текст] / A.C. Куимова /У Свидетельство об официальной регистрации программ для ЭВМ № 2012661024. Зарегистрировано в реестре программ для ЭВМ Федеральной службы по интеллектуальной собственности, патентам и товарным знакам РФ от 5 декабря 2012.

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

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