WWW.KONF.X-PDF.RU
БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА - Авторефераты, диссертации, конференции
 

Pages:   || 2 | 3 | 4 |

«МНОГОКРИТЕРИАЛЬНЫЕ МОДЕЛИ ОДНОПРОЦЕССОРНОГО ОБСЛУЖИВАНИЯ СТАЦИОНАРНЫХ ОБЪЕКТОВ: ИССЛЕДОВАНИЕ ОПТИМИЗАЦИОННЫХ ЗАДАЧ, ПОСТРОЕНИЕ РЕШАЮЩИХ АЛГОРИТМОВ ...»

-- [ Страница 1 ] --

МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

ИНФОРМАЦИОННЫХ ТЕХНОЛОГИЙ, РАДИОТЕХНИКИ И

ЭЛЕКТРОНИКИ

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

Пушкин Антон Михайлович

МНОГОКРИТЕРИАЛЬНЫЕ МОДЕЛИ

ОДНОПРОЦЕССОРНОГО ОБСЛУЖИВАНИЯ

СТАЦИОНАРНЫХ ОБЪЕКТОВ: ИССЛЕДОВАНИЕ



ОПТИМИЗАЦИОННЫХ ЗАДАЧ, ПОСТРОЕНИЕ

РЕШАЮЩИХ АЛГОРИТМОВ

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

е и промышленности) по техническим наукам Диссертация на соискание ученой степени кандидата технических наук

Научный руководитель: д.т.н., профессор Д.И. Коган

Научный консультант: д.т.н., профессор Ю.С. Федосенко Москва – 2015

СОДЕРЖАНИЕ

ВВЕДЕНИЕ

ГЛАВА 1. СОВРЕМЕННОЕ СОСТОЯНИЕ ТЕОРИИ РАСПИСАНИЙ. 17

§ 1.1. Актуальность задач теории расписаний

§ 1.2. Проблемы вычислительной сложности задач теории расписаний........ 19 § 1.3. Регулярные методы решения задач теории расписаний

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

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

1.3.3. Эвристические алгоритмы

§ 1.4. Технология решения многокритериальных задач оптимизации............ 32 § 1.5. Типовые задачи обслуживания стационарных объектов перемещающимся процессором

Выводы по главе 1

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

СТАЦИОНАРНЫХ ОБЪЕКТОВ ПЕРЕМЕЩАЮЩИМСЯ

ПРОЦЕССОРОМ

§ 2.1. Двурейсовые задачи обслуживания

2.1.1. Математическая модель 1DZ1

2.1.2. Постановки однокритериальных оптимизационных задач........

2.1.3. Вычислительная сложность задач 1DZ1(sP) и 1DZ1(mP)............ 40 § 2.2. Однорейсовые задачи обслуживания

2.2.1. Математическая модель 1DZ2

2.2.2. Постановки однокритериальных оптимизационных задач........ 45 2.2.3. Алгоритмы решения задач 1DZ2(sP) и 1DZ2(mP)

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

§ 2.3. Обобщенные задачи обслуживания

2.3.1. Математическая модель 1DZ3

2.3.2. Постановки однокритериальных оптимизационных задач........ 53 2.3.3. Алгоритмы решения задач 1DZ3(sP) и 1DZ3(mP)

2.3.4. Иллюстрирующий пример и результаты вычислительных экспериментов

§ 2.4. Задачи обслуживания в двумерной рабочей зоне

2.4.1. Математическая модель 2DZ3

2.4.2. Постановки однокритериальных оптимизационных задач........ 59 2.4.3. Алгоритмы решения задач 2DZ3(sP) и 2DZ3(mP)

2.4.4. Иллюстрирующий пример

Выводы по главе 2

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

СТАЦИОНАРНЫХ ОБЪЕКТОВ ПЕРЕМЕЩАЮЩИМСЯ

ПРОЦЕССОРОМ

§ 3.1. Двурейсовые задачи обслуживания

3.1.1. Постановки многокритериальных задач для модели 1DZ1........ 64 3.1.2. Алгоритмы решения задач 1DZ1(T,sP), 1DZ1(T,mP), 1DZ1(sP) и 1DZ1(mP)

3.1.3. Алгоритм решения задачи 1DZ1(Tc,T)

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

§ 3.2. Однорейсовые задачи обслуживания

3.2.1. Постановки многокритериальных задач для модели 1DZ2........ 80 3.2.2. Алгоритмы решения задач 1DZ2(L,T,sP), 1DZ2(L,T,mP), 1DZ2(T,sP) и 1DZ2(T,mP)

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

§ 3.3. Обобщенные задачи обслуживания

3.3.1. Постановки многокритериальных задач для модели 1DZ3........ 92 3.3.2. Алгоритмы решения задач 1DZ3(L,T,sP), 1DZ3(L,T,mP), 1DZ3(T,sP) и 1DZ3(T,mP)

3.3.3. Вычислительная сложность задач 1DZ3(T,sP), 1DZ3(T,mP), 1DZ3(L,T,sP) и 1DZ3(L,T,mP)

3.3.4. Иллюстрирующий пример и результаты вычислительных экспериментов

§ 3.4. Задачи обслуживания в двумерной рабочей зоне

3.4.1. Постановки многокритериальных задач для модели 2DZ3...... 104 3.4.2. Алгоритмы решения задач 2DZ3(L,T,sP), 2DZ3(L,T,mP), 2DZ3(T,sP) и 2DZ3(T,mP)

3.4.3. Иллюстрирующий пример





Выводы по главе 3

ГЛАВА 4. АЛГОРИТМЫ СИНТЕЗА СУБОПТИМАЛЬНЫХ

СТРАТЕГИЙ ОБСЛУЖИВАНИЯ

§ 4.1. Проблемы сравнения двух множеств оценок

§ 4.2. Идеология эволюционно-генетических вычислений

4.2.1. Обобщенная структура генетического алгоритма

4.2.2. Оператор скрещивания в задачах синтеза стратегий обслуживания

§ 4.3. Эволюционно-генетический алгоритм синтеза совокупности субэффективных оценок для решения задач, сформулированных в рамках моделей 1DZ3 и 2DZ3

4.3.1. Алгоритм решения однокритериальных задач

4.3.2. Алгоритм для решения многокритериальных задач................. 123 § 4.4. Результаты вычислительных экспериментов

Выводы по главе 4

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

ДИСПЕТЧЕРСКОГО УПРАВЛЕНИЯ ОБСЛУЖИВАНИЕМ

РАССРЕДОТОЧЕННЫХ ОБЪЕКТОВ

ПЕРЕМЕЩАЮЩИМСЯ ПРОЦЕССОРОМ

§ 5.1. Обоснование выбора языка программирования Python

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

5.2.1. Назначение и функциональные возможности

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

5.2.3. Схема работы с программным комплексом

Выводы по главе 5

ЗАКЛЮЧЕНИЕ

ЛИТЕРАТУРА

ПРИЛОЖЕНИЯ

Приложение А. Условия проведения вычислительных экспериментов....... 152 Приложение Б. Свидетельство о государственной регистрации программы для ЭВМ

Приложение В. Акт внедрения результатов диссертационной работы в ОАО «Судоходная компания «ТАТФЛОТ»

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

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

ВВЕДЕНИЕ

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

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

Вышеуказанное обусловливает актуальность темы данной диссертации, направленной на:

1) создание и исследование новых, обобщенных теоретических моделей процессов обслуживания;

2) постановку и исследование семейства оптимизационных задач обслуживания, покрывающих массовые типы эксплуатационных ситуаций;

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

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

Соответствующее направление в науке берет начало с известной работы Gantt H.L. (1903 г.). Термин «теория расписаний» в 50-х годах ввел Bellman R.;

одними из первых были работы Smith W.E., Johnson S.M., Jackson J.R. Отдельным направлением в области исследования операций данная проблематика стала благодаря работам Bellman R., Brucker P., Coffman E.G., Conway R.W., Garey M., Graham R.L., Johnson D., Karp R.M., Lawler E.L., Lenstra J.K., Maxwell W.L., Miller L.W., Pinedo M.L., Танаева В.С., Шкурбы В.В.

Различные проблемы управления обслуживанием в моделях транспортно-технологических систем и соответствующие им задачи синтеза расписаний обслуживания исследовались в работах Blazewicz J., Gendreau M., Nossack J., Pesch E., Sterna M., Werner F., Батищева Д.И., Беленького А.С., Буркова В.Н., Гимади Э.Х., Гордона В.С., Зака Ю.А., Ковалева М.Я., Корбута А.А., Лазарева А.А., Левнера Е.В., Новикова Д.И., Подчасовой Т.П., Прилуцкого М.Х., Серваха В.В., Сигала И.Х., Сотскова Ю.Н., Струсевича В.А., Ульянова М.В., Фазылова В.Р., Финкельштейна Ю.Ю., Шафранского Я.М. и др.

В работах указанных авторов, как правило, полагается, что обслуживающие процессоры стационарны, а требующие обслуживания объекты поступают к ним в заданные моменты времени; оптимизируется один критерий. В данной работе объекты считаются стационарными, расположенными в рабочей зоне мобильного процессора. Соответствующее направление активно изучается в работах Дуничкиной Н.А., Когана Д.И., Федосенко Ю.С., Шлюгаева А.Ю. Настоящее исследование развивает работы перечисленных авторов.

При этом принципиальными являются следующие обстоятельства:

– учет ранних сроков готовности объектов к обслуживанию;

– системные ограничения на возможные траектории перемещения обслуживающего процессора;

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

В наиболее общей ситуации рабочая зона процессора определяется конечным взвешенным ориентированным графом G, вершины которого соответствуют точкам расположения объектов; веса ребер в соответствии с моделью могут задавать как длины непосредственных переходов между парами смежных точек, так и времена переходов между такими вершинами. В ряде моделей ребру между вершинами i и j рабочей зоны соответствует вектор характеристик: длина перехода si, j, si, j s j,i ; время перехода при движении процессора в одну сторону i, j и время перехода при движении процессора в другую сторону j,i ; в общем случае i, j j,i (если в графе отсутствует какоелибо ребро, то непосредственный переход между соответствующими вершинами невозможен). При перемещениях процессора не ограничивается число транзитных проходов точек расположения объектов. Такие модели и порождаемые ими оптимизационные задачи имеют ряд содержательных интерпретаций на уровне транспортно-технологических систем, связанных с обходом рассредоточенных стационарных объектов для выполнения их обслуживания.

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

Моделирование изучаемых процессов выполняется с помощью их формализации как систем обслуживания перемещающимся процессором P совокупности объектов On o1, o2,, on, расположенных в вершинах вышеописанного графа G. Обслуживание процессором объекта o j, j 1, n, требует времени j и начинается либо от предписанного раннего срока rj, либо от момента прибытия процессора в точку (если на момент прибытия объект уже готов к обслуживанию). В случае прибытия процессора в точку j в момент вре

–  –  –

Объекты подлежат однократному обслуживанию, при этом накладывается ряд ограничений:

– обслуживание осуществляется без прерываний;

– простои процессора, не связанные с обслуживанием объектов и с ожиданием наступления ранних сроков, запрещены.

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

Граф G представим в виде цепи из n вершин и n 1 ребра, где ребрами связаны только вершины j и j 1, j 0, n 1. Обозначим такой граф G1.

Рабочая зона перемещающегося процессора, представляемая в виде графа G1, одномерна, она соответствует рассмотренному в главе 2 семейству моделей 1DZ. Здесь возможны варианты:

1.1) обслуживание всех объектов группы On осуществляется в процессе реализации двух рейсов между крайними точками рабочей зоны – прямого и обратного (модель 1DZ1);

1.2) обслуживание объектов группы On осуществляется в процессе реализации одного рейса между базовой и конечной точками рабочей зоны, реализуется только прямой рейс, при этом существует возможность отложить обслуживание конкретных объектов на более поздний срок (модель 1DZ2);

1.3) на последовательность обслуживания объектов множества On не налагается каких-либо ограничений (модель 1DZ3).

2) Граф G имеет произвольную структуру (рабочая зона процессора двумерна). Аналогично п. 1.3. на перемещения процессора при обслуживании объектов совокупности On не накладывается никаких ограничений (модель 2DZ3).

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

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

Достижение поставленной цели потребовало реализации следующих этапов.

1. Обзор литературы по теме исследования.

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

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

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

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

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

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

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

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

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

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

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

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

Реализация результатов работы. Исследования по теме диссертационной работы выполнялись в соответствии с государственной программой РФ «Информационное общество (2011-2020 годы)», частично поддержаны грантом Российского фонда фундаментальных исследований (проект № 15-07-03141). Результаты диссертации внедрены в процесс проектирования систем поддержки организационного управления в ОАО «ТАТФЛОТ», а также используются в учебном процессе в Волжском государственном университете водного транспорта и Московском государственном университете информационных технологий, радиотехники и электроники. Разработанная программная реализация алгоритмов зарегистрирована в Реестре программ для ЭВМ Федеральной службы по интеллектуальной собственности, патентам и товарным знакам РФ. Сведения о практическом использовании приведены в приложениях.

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

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

– XVI Всероссийская научно-техническая конференция «Новые информационные технологии» МГУПИ (г. Москва, 2013 г.);

– Международная научно-практическая конференция «Информационные управляющие системы и технологии», ИУСТ-ОДЕССА-2013 (г. Одесса, 2013 г.);

Загрузка...

– XII Всероссийское совещание по проблемам управления, ВСПУ-2014 (г. Москва, 2014 г.);

– Научно-практическая конференция «Актуальные проблемы приборостроения, информатики и социально-экономических наук» (г. Москва, 2014 г.);

27th Conference of the European Chapter on Combinational Optimization, ECCO XXVII – CO 2014 Joint Conference (г. Мюнхен, 2014);

– Шестая международная научная конференция: Танаевские чтения.

(г. Минск, 2014 г.);

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

– Международная научно-техническая конференция «Информатика и технологии. Инновационные технологии в промышленности и информатике» (г. Москва, 2015 г.);

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

– 17-й Международный научно-промышленный форум «Великие реки – 2015» (г. Нижний Новгород, 2015).

Личный вклад автора. Результаты, выносимые на защиту

, получены соискателем лично или при его непосредственном участии. Им же подготовлены статьи [68, 72, 73], представленные в Перечне рецензируемых научных журналов.

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

Работа содержит 156 страниц текста, библиографический список включает 126 позиций.

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

В первой главе (Современное состояние теории расписаний): а) обоснована актуальность исследования новых задач теории расписаний (§ 1.1);

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

Во второй главе (Однокритериальные задачи обслуживания стационарных объектов перемещающимся процессором [28, 29, 40, 42, 66, 67, 99, 107]) выполняется построение ряда моделей обслуживания стационарных объектов перемещающимся процессором, формулируются однокритериальные оптимизационные задачи, излагаются разработанные на основе идеологии динамического программирования алгоритмы синтеза оптимальных стратегий обслуживания, приводятся примеры вычислений по составленным рекуррентным соотношениям и результаты вычислительных экспериментов.

В § 2.1 выполнено построение математической модели 1DZ1 обслуживания стационарных объектов перемещающимся процессором в одномерной рабочей зоне, где процессор выполняет два рейса – прямой и обратный. Поставлены однокритериальные оптимизационные задачи 1DZ1(sP), 1DZ1(mP), для которых доказаны теоремы об NP-трудности.

В § 2.2 построена модель 1DZ2, где процессор выполняет обслуживание объектов одномерной рабочей зоны посредством одного рейса из базовой точки в конечную. Сформулированы однокритериальные задачи 1DZ2(sP), 1DZ2(mP), описан решающий алгоритм, рассмотрен иллюстрирующий пример и приведены результаты вычислительных экспериментов.

В § 2.3 сконструирована обобщенная модель 1DZ3, в которой процессор выполняет обслуживание объектов без каких-либо ограничений на возможные перемещения между пунктами одномерной рабочей зоны. В рамках модели сформулированы две однокритериальные задачи 1DZ3(sP), 1DZ3(mP), разработаны алгоритмы их решения на основе метода динамического программирования. Рассмотрен иллюстрирующий пример и приведены результаты вычислительных экспериментов.

В § 2.4 описана математическая модель 2DZ3 обслуживания группы стационарных объектов в двумерной рабочей зоне. Какие-либо ограничения на перемещения процессора не накладываются. Поставлены однокритериальные задачи 2DZ3(sP) и 2DZ3(mP), выведены решающие соотношения динамического программирования, решен иллюстрирующий пример.

В третьей главе (Многокритериальные задачи обслуживания стационарных объектов перемещающимся процессором [28, 29, 30, 41, 42, 43, 68, 69, 70, 71, 72, 73, 99]) для введенных в главе 2 моделей сформулированы многокритериальные оптимизационные задачи. На основе идеологии динамического программирования в его многокритериальном обобщении разработаны алгоритмы синтеза полных совокупностей эффективных оценок; по любой из таких оценок может быть построена порождающая ее Парето-оптимальная стратегия. Приведены примеры вычислений по составленным рекуррентным соотношениям и результаты вычислительных экспериментов.

В § 3.1 для модели 1DZ1 поставлен ряд многокритериальных задач 1DZ1(T,sP), 1DZ1(T,mP), 1DZ1(Tc,T), для решения которых выведены рекуррентные соотношения динамического программирования; представлены результаты массовых вычислительных экспериментов. Реализация алгоритма продемонстрирована на иллюстрирующем примере.

В § 3.2 в рамках модели 1DZ2 поставлены многокритериальные задачи 1DZ2(L,T,sP), 1DZ2(L,T,mP), 1DZ2(T,sP) и 1DZ2(T,mP). Для их решения построены алгоритмы на основе динамического программирования. Рассмотрен иллюстрирующий пример и приведены результаты массовых вычислительных экспериментов.

В § 3.3 для модели 1DZ3 выполнена постановка и решение многокритериальных задач 1DZ3(L,T,sP), 1DZ3(L,T,mP), 1DZ3(T,sP), 1DZ3(T,mP). Для этих задач доказаны результаты об NP-трудности, рассмотрен иллюстрирующий пример и приведены результаты вычислительных экспериментов.

В § 3.4 для модели 2DZ3 также поставлен набор многокритериальных задач 2DZ3(L,T,sP), 2DZ3(L,T,mP), 2DZ3(T,sP) и 2DZ3(T,mP). Выведены рекуррентные соотношения динамического программирования, а также представлен иллюстрирующий пример.

В четвертой главе (Алгоритмы синтеза субоптимальных стратегий обслуживания [70, 72, 73]) рассмотрены построенные на основе идеологии эволюционно-генетических вычислений процедуры решения задач, сформулированных в рамках моделей 1DZ3 и 2DZ3.

§ 4.1 посвящен вопросу оценивания отклонения квазипаретовского множества оценок, полученного путем использования генетического алгоритма, от паретовского множества оценок, полученного в результате использования концепции динамического программирования. Рассмотрено несколько вариантов оценивания.

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

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

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

В пятой главе (Программный комплекс поддержки диспетчерского управления обслуживанием рассредоточенных объектов перемещающимся процессором [74]) приводится обоснование выбора языка программирования Python (§ 5.1), описывается программный комплекс синтеза оптимальных и субоптимальных стратегий обслуживания пространственно рассредоточенных стационарных объектов перемещающимся процессором – излагаются его назначение, функциональные возможности, программная архитектура и типовая схема использования лицом, принимающим решения (ЛПР) (§ 5.2).

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

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

ГЛАВА 1. СОВРЕМЕННОЕ СОСТОЯНИЕ ТЕОРИИ РАСПИСАНИЙ

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

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

§ 1.1. Актуальность задач теории расписаний Теория расписаний – раздел исследования операций, в котором строятся и анализируются математические модели календарного планирования (т.е.

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

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

1) графическое представление – диаграмма Гантта [102] и др.;

2) табличное представление – в таблицах указываются промежутки времени, в которые выполняются задания, а также их исполнители (номер станка, процессор и т.п.);

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

Первой в теории расписаний была известная работа Gantt H.L.

(1903 г.) [102]. Термин «теория расписаний» в 50-х годах ввел Bellman R. [88].

К числу первых в этой теории следует отнести работы Smith W.E. [121], Johnson S.M. [106], Jackson J.R. [105]. Отдельным направлением в области исследования операций данная проблематика стала благодаря работам Bellman R. [13], Brucker P. [93, 94], Coffman E.G. [95, 96], Conway R.W. [98], Garey M. [26], Graham R.L. [104], Johnson D. [26], Karp R.M. [35], Lawler E.L.

[109], Lenstra J.K. [110], Maxwell W.L. [98], Miller L.W. [98], Pinedo M.L. [119], Танаева В.С. [23, 79, 80, 81, 82], Шкурбы В.В. [79].

Различные проблемы управления обслуживанием в моделях транспортно-технологических систем и соответствующие им задачи синтеза расписаний обслуживания исследовались в работах Blazewicz J. [89, 90, 91, 92], Gendreau M. [103], Nossack J. [103, 116, 117], Pesch E. [89, 90, 91, 92, 118], Sterna M.

[89, 90, 91], Werner F. [89, 90, 91], Батищева Д.И. [3], Беленького А.С. [11, 12], Буркова В.Н. [16], Гимади Э.Х. [19, 80], Гордона В.С. [23, 24], Зака Ю.А. [33, 34], Ковалева М.Я. [82], Корбута А.А. [47, 48], Лазарева А.А. [54, 55], Левнера Е.В. [11, 12], Новикова Д.И. [22, 44], Подчасовой Т.П. [64], Прилуцкого М.Х. [65], Серваха В.В. [75, 76], Сигала И.Х. [77, 78], Сотскова Ю.Н. [81], Струсевича В.А. [81], Ульянова М.В. [83, 84], Фазылова В.Р. [1, 15], Финкельштейна Ю.Ю. [85], Шафранского Я.М. [80, 82] и др.

В работах указанных авторов, как правило, полагается, что обслуживающие процессоры стационарны, а требующие обслуживания объекты поступают к ним в заданные моменты времени; оптимизируется только один критерий. В работах Дуничкиной Н.А. [27], Когана Д.И. [38, 39], Федосенко Ю.С.

[38, 39], Шлюгаева А.Ю. [86] объекты считаются стационарными, расположенными в рабочей зоне перемещающегося процессора. Настоящее исследование развивает работы, относящиеся к последнему направлению. При этом принципиальными являются следующие особенности:

– учет ранних сроков готовности объектов к обслуживанию;

– системные ограничения на возможные траектории перемещения обслуживающего процессора;

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

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

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

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

Большой вклад в многокритериальную оптимизацию внесли работы T’Kindt V. и Billaut J.-Ch. [122], Villareal B. и Karwan M. [124], Когана Д.И. [36], Ногина В.Д. [60, 63], Подиновского В.В. [63], и др.

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

Задачи теории расписаний – подкласс задач дискретной оптимизации.

Дискретные задачи имеют разную сложность решения. Существует два принципиально различающихся подхода к оценке сложности решающего алгоритма. Первый подход подразумевает оценку сложности создания алгоритма решения, где учитываются такие параметры, как количество операторов, количество циклов, количество итераций и т.п. Второй подход подразумевает оценку, характеризующую трудоемкость реализации алгоритма при компьютерных вычислениях; здесь фигурируют такие параметры, как количество элементарных операций, объем памяти, скорость центрального процессора (ЦП) и т.д., т.е. оценка описывает время вычислений на рабочей станции. Именно второй подход является целесообразным при классификации задач по их вычислительной сложности [36].

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

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

Задача Z полиномиально разрешима, если для нее существует решающий алгоритм A такой, что TA L P L, P L – некоторый полином от одной переменной L.

Задача Z экспоненциально разрешима, если для нее существует решающий алгоритм А такой, что TA L C a L, здесь а – произвольная константа, большая единицы.

Алгоритм А решения задачи Z с целочисленными начальными данными называется псевдополиномиальным, если TA L не превышает значения некоторого полинома от двух переменных PA L, M Z, где M Z – максимальное из чисел в составе начальных данных по этой задаче.

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

Для каждой задачи распознавания определена некоторая совокупность U, в которой выделено подмножество V. Требуется определить, принадлежит ли х подмножеству V по произвольному элементу х, x U.

Для многих задач распознавания полиномиальные алгоритмы известны, например, такой алгоритм есть для задачи определения по графу, является ли он эйлеровым [52], и для задачи определения по сети с ограниченными пропускными способностями дуг, возможен ли в ней поток заданной мощности [17]. Для множества других задач таких алгоритмов построить не удалось.

Для следующих задач распознавания известны решающие алгоритмы, имеющие экспоненциальную оценку вычислительной сложности, однако ни для одной из них не удалось построить полиномиальный решающий алгоритм [26]:

1) «3-Выполнимость»; 2) «Трехмерное сочетание»; 3) «Вершинное покрытие»;

4) «Клика»; 5) «Гамильтонов цикл»; 6) «Разбиение».

Задачу распознавания « U ?» назовем полиномиально сводимой к задаче « V ?», если существует вычислимая в полиномиальном времени функция такая, что U тогда и только тогда, когда V. Задачи « U ?» и « V ?» считаются полиномиально эквивалентными, если задача « U ?» полиномиально сводима к « V ?», а задача « V ?» полиномиально сводима к « U ?». Если задача « U ?» полиномиально сводима к задаче « V ?» и задача « V ?» имеет полиномиальную временную сложность, то временная сложность задачи « U ?» также полиномиальная.

В [26] показано, что перечисленные выше задачи распознавания 1-6 полиномиально эквивалентны, т.е. создание полиномиального решающего алгоритма для одной из них влечет за собой полиномиальную разрешимость остальных задач этой совокупности.

Известно, что любой алгоритм может быть реализован соответствующим образом построенной машиной Тьюринга [26, 59]. Задача распознавания относится к классу NP, если может быть построена решающая ее недетерминированная машина Тьюринга [26], функционирующая в полиномиально зависящем от размера входной информации времени. Задачи распознавания, разрешимые на детерминированных машинах Тьюринга за время, ограниченное значением полинома от объема входной информации, называются задачами класса P. Так как концепция недетерминированной машины Тьюринга является обобщением понятия детерминированной машины, класс задач P является подклассом класса задач NP, т.е. P NP.

Задача распознавания называется NP-полной, если:

она принадлежит классу NP;

1) к ней полиномиально сводима любая принадлежащая классу NP 2) задача.

Доказано, что любая задача распознавания класса NP полиномиально сводима к классической задаче «3-Выполнимость» [26]. Учитывая, что перечисленные выше задачи 1-6, принадлежащие классу NP, полиномиально эквивалентны, то получаем, что каждая из них NP-полна.

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

Задача распознавания называется NP-полной в сильном смысле, если для нее не существует псевдополиномиального решающего алгоритма.

Любая задача оптимизации индуцирует соответствующую ей задачу распознавания. Например, задача максимизации критерия K x при x D порождает задачу распознавания, в которой необходимо определить имеется ли в D элемент x* такой, что K x* C, где С – константа. Из NP-полноты индуцированной задачи распознавания вытекает NP-трудность задачи оптимизации.

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

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

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

Пусть Z – произвольная массовая задача, а P x – полином с целыми коэффициентами. Через Z P будем обозначать совокупность входящих в Z индивидуальных задач, в которых M Z не превышает P L.

Задача Z называется NP-трудной в сильном смысле, если:

она является NP-трудной;

1) существует такой полином Р, что задача Z P также NP-трудна.

2) Из гипотезы P NP следует, что для NP-трудных в сильном смысле задач псевдополиномиальных решающих алгоритмов не существует.

Различие в возможностях использования полиномиальных и экспоненциальных по вычислительной сложности алгоритмов значительно. Таблица 1.1 позволяет сравнить скорости роста нескольких типичных полиномиальных и экспоненциальных функций [26]. В ячейках таблицы указана продолжительность решения задач при определяемых столбцами значениях параметра n и определяемых строками функциях временной сложности; быстродействие ЭВМ считается равным 106 операций в секунду.

–  –  –

Принципиальная разница между алгоритмами полиномиальной и экспоненциальной временной сложности проявляется также при анализе влияния быстродействия ЭВМ на размеры реально решаемых задач. Таблица 1.2 показывает, как увеличатся размеры решаемых за один час задач при увеличении быстродействия ЭВМ в сто и тысячу раз в сравнении с современными машинами [26].

<

–  –  –

Заметим, что для функции TA (n) 2n увеличение скорости вычислений в 1000 раз приводит к тому, что размер наибольшей решаемой за 1 час задачи возрастает только на 10, в то время как при квадратичной функции временной сложности этот размер увеличивается более чем в 30 раз.

Множество примеров полиномиальных, NP-полных и NP-полных в сильном смысле задач дискретной математики, в том числе и теории расписаний, имеется в книге Garey M., Johnson D. [26]. Вопросы вычислительной сложности задач теории расписаний подробно рассмотрены в двухтомной монографии Танаева В.С. с соавторами [80, 81]. Отдельно сложность задач с перемещающимся процессором исследована в статьях Дуничкиной Н.А., Когана Д.И. и Федосенко Ю.С. [38, 39].

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

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

§ 1.3. Регулярные методы решения задач теории расписаний Выделяют три класса методов решения: точные алгоритмы, приближенные алгоритмы и эвристические алгоритмы.

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

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

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

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

1.3.1. Метод динамического программирования Динамическое программирование [13, 36] в системном анализе – способ решения сложных задач путём разбиения их на более простые подзадачи. Он применим к задачам с оптимальной подструктурой, выглядящим как набор перекрывающихся подзадач, сложность которых меньше исходной.

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

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

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

1) разбиение задачи на подзадачи меньшего размера;

2) рекурсивное нахождение оптимального решения подзадач, выполняя такой же трехшаговый алгоритм;

3) использование полученного решения подзадач для конструирования решения исходной задачи.

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

1.3.2. Метод ветвей и границ Метод ветвей и границ [37, 48, 78, 108] относится к числу наиболее используемых способов сокращения переборных операций в процессе решения задач дискретной оптимизации. Основная идея метода заключается в отсеве подмножеств допустимых решений, заведомо не содержащих оптимальных значений.

Центральным в методе ветвей и границ является понятие дерева вариантов для решаемой задачи Z оптимизации критерия K X. Процесс построения дерева начинается с его корня, которому соответствует задача Z в целом (обозначим ее Z D, где D – конечное множество допустимых решений). При построении дерева вариантов каждой получаемой вершине ставится в соответствие некоторая подзадача Z M, M D. Ветвление в произвольной вершине предусматривает разбиение совокупности Z M на некоторое число k попарно непересекающихся подмножеств M j, j 1, k. Полученные таким образом новые вершины j, j 1, k, соответствуют возникающим под

–  –  –

j 1, k.

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

1) стратегия выбора вершины для очередного ветвления;

2) способ ветвления;

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

4) способ отыскания нижних оценок для тех же подзадач.

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

Текущим рекордом называется наибольшая из всех вычисленных нижних оценок (в случае максимизации критерия) или наименьшая из всех вычисленных верхних оценок (в случае минимизации критерия).

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



Pages:   || 2 | 3 | 4 |
Похожие работы:

«Попов Александр Сергеевич ИССЛЕДОВАНИЕ И РАЗРАБОТКА ИНТЕРАКТИВНЫХ УСТРОЙСТВ ДЛЯ ПОВЫШЕНИЯ ПОМЕХОУСТОЙЧИВОСТИ СИСТЕМ ЭФИРНОГО ЦИФРОВОГО ТЕЛЕВИЗИОННОГО ВЕЩАНИЯ Специальность 05.12.04 – радиотехника, в том числе системы и устройства телевидения Диссертация на соискание учёной степени кандидата...»

«Туляков Юрий Михайлович РАЗРАБОТКА МЕТОДОВ ПОВЫШЕНИЯ НАДЕЖНОСТИ ПОДВИЖНОЙ РАДИОСВЯЗИ Специальность 05.12.04. Радиотехника, в том числе системы и устройства телевидения Диссертация на соискание ученой степени доктора технических наук Научный консультант доктор технических наук, профессор М.Д. Венедиктов Москва 2015 г. ОГЛАВЛЕНИЕ Введение ГЛАВА 1. Анализ развития передачи данных в системах и сетях 25 подвижной наземной...»

«ВОЛОВАЧ ВЛАДИМИР ИВАНОВИЧ РАЗВИТИЕ ТЕОРИИ, ПРИНЦИПОВ ПОСТРОЕНИЯ И СРЕДСТВ РЕАЛИЗАЦИИ ЭФФЕКТИВНЫХ РАДИОТЕХНИЧЕСКИХ СИСТЕМ ОБНАРУЖЕНИЯ И КОНТРОЛЯ ПРОТЯЖЕННЫХ ОБЪЕКТОВ Специальность 05.12.04 – Радиотехника, в том числе системы и устройства телевидения ДИССЕРТАЦИЯ на соискание ученой степени доктора технических наук Научный...»

«УДК 621.371 ШУЛЯТЬЕВ Аркадий Андреевич МОДЕЛИРОВАНИЕ АКТИВНЫХ МЕТОДОВ РАДИОМОНИТОРИНГА ЛЕСНЫХ ПОКРОВОВ Специальность 05.12.04 – радиотехника, в т.ч. системы и устройства телевидения ДИССЕРТАЦИЯ на соискание учёной степени кандидата технических наук Научный руководитель доктор технических наук, профессор Никитин О. Р. Владимир 2015 г. Содержание Введение 1. Анализ методов радиомониторинга лесных покровов....»

«Самищенко Алексей Сергеевич Научные основы дактилоскопии и перспективы их развития Специальность 12.00.12 — криминалистика; судебно-экспертная деятельность; оперативно-розыскная деятельность Диссертация на соискание ученой степени кандидата юридических наук Научный руководитель:...»

«СМИРНОВА ЛАРИСА ПЕТРОВНА ДИЗАЙН ИЗДЕЛИЙ ПО УХОДУ ЗА РЕБЁНКОМ ПЕРВОГО ГОДА ЖИЗНИ Специальность: 17.00.06 – Техническая эстетика и дизайн ДИССЕРТАЦИЯ на соискание ученой степени кандидата искусствоведения Научный руководитель: доктор искусствоведения, профессор Грашин Александр...»

«Попов Александр Сергеевич ИССЛЕДОВАНИЕ И РАЗРАБОТКА ИНТЕРАКТИВНЫХ УСТРОЙСТВ ДЛЯ ПОВЫШЕНИЯ ПОМЕХОУСТОЙЧИВОСТИ СИСТЕМ ЭФИРНОГО ЦИФРОВОГО ТЕЛЕВИЗИОННОГО ВЕЩАНИЯ Специальность 05.12.04 – радиотехника, в том числе системы и устройства телевидения Диссертация на соискание учёной степени кандидата...»









 
2016 www.konf.x-pdf.ru - «Бесплатная электронная библиотека - Авторефераты, диссертации, конференции»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.