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

Табуров Денис Юрьевич

ПОВЫШЕНИЕ ЭФФЕКТИВНОСТИ ИНФОРМАЦИОННО-

ИЗМЕРИТЕЛЬНЫХ СИСТЕМ ГИБКОГО АВТОМАТИЗИРОВАННОГО ПРОИЗВОДСТВА З А СЧЕТ ОПТИМИЗАЦИИ ВЫЧИСЛИТЕЛЬНЫХ ПРОЦЕССОВ

Специальносгь 05.11.16 - Информационно-измерительные и управляющие системы (промышленность)

Автореферат

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

4641060

Москва-2011

4841060

Работа выполнена в Московском государственном университете приборостроения информатики (МГУПИ)

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

Слепцов Владимир Владимирова

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

Данилин Николай Семенович

кандидат техгаиеских наук Тарасенков Георгий Андреевич

Ведущая организация: ОАО «Центральный научно-

исследовательский технологическ институт» (ЦНИТИ)

Защита диссертации состоится «24» февраля 2011 г. в 12 часов на заседании диссертационного Совета Д 212.119.01 в Московском государственном уннверси приборостроения и информатики по адресу: 107996, г. Москва, ул. Стромынка, д.

С диссертацией можно ознакомиться в библиотеке Московского государственной университета

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

Ученый секретарь

диссертационного совета Д 212.119.01 доктор технических наук, профессор

Филинов В.В

1.0БЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы.

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

• резко (в 7-10 раз) повысить производительность труда;

• сократить длительность производственного цикла;

' повысить технический уровень и качество выпускаемой продукции;

• снизить материало- и энергоемкость продукции;

• увеличить коэффициент сменности оборудования;

• высвободить значительную часть специалистов, работающих на производстве;

■ сократить производственные площади.

Эффективность применения ГАП в значительной мере зависит от качества используемых в них информационно-измерительных и управляющих систем (ИИУС ГАП).

Характерными особенностями ИИУС ГАП являются:

• сложные взаимосвязи структурных элементов, размещаемых на обширной территории;

• способность выполнять возложенные на ИИУС функции при выходе из строя ряда подсистем, блоков или узлов;

• значительные затраты ресурсов;

■ длительные сроки создания ИИУС.

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

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

Как показывает анализ практической деятельности, при рациональном использовании средств автоматизации, доля времени на сбор и обработку информации может быть снижена до 10-15%, а общий цикл управления может сократился в 3-5 раз. Существенно (в 10-100) раз может возрасти достоверность доведения информации.

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

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

Состояние проблемы

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

В работах В.М. Глушкова, В.В. Слепцова, В.И. Картавцева излагаются основные принципы построения ИИУС ГАП, организация передачи данных и связи, их анализ и синтез. В работе Г.Т. Артамонова и В.Д. Тюрина исследуются влияние топологических характеристик систем на их надежность, пропускную способность, стоимость и ряд других системных характеристик. В работе Г.Ф. Янбых и Б.А. Столярова рассматривается проблема оптимизации физической структуры информационно-вычислительных систем. Математические постановки задач формулируются в терминах нелинейного дискретного программирования. Методы и алгоритмы синтеза и оптимизации структуры централизованных и распределенных систем с единых методологических позиций рассмотрены Ю.П. Зайченко и Ю.В. Гонта, Гарипова В.К..

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

Работы В.В. Хорошевского, E.H. Турута, O.K. Кондратьева посвящены отражению прогресса, достигнутого при решении задач повышения устойчивости информационно вычислительных процессов. Работы А.Г. Мамиконова, В.В. Кульбы, С.К. Сомова, А.Б. Шелкова посвящены решению вопросов повышения достоверности и сохранности программных модулей и информационных массивов в вычислительных системах за счет организации оперативного и восстановительного резервирования.

Практическое решение вопросов синтеза систем и организации их функционирования связано с развитием теории и практики оптимизации, которым посвящены работы О.Г. Алексеева, B.C. Михалевича, И.В.Сергиенко.

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

Цель диссертационной работы - повышение эффективности организации вычислительного процесса в ИИУС ГАП. Для достижения поставленной цели необходимо решить ряд задач:

• выбрать критерии оптимизации вычислительных процессов в ИИУС ГАП;

• разработать математические модели и методы оптимизации вычислительных процессов в верхнем контуре ИИУС ГАП;

• разработать математические модели и методы оптимизации вычислительных процессов в нижнем контуре НИУС ГАП;

• провести анализ функционирования ИИУС ГАП в условиях функциональной деградации ее элементов;

• адаптировать метод ветвей и границ для решения задач оптимизации вычислительных процессов в ИИУС ГАП.

Объектом исследования являются информационно-вычислительные процессы в существующих и перспективных ИИУС ГАП.

Предметом исследования являются математические модели, методы и алгоритмы комплексного решения задач оптимизации распределения программных средств в системе вычислительных средств ИИУС ГАП.

Методы исследований

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

Научная новизна работы заключается в том, что:

1. Предложен универсальный подход к решению задачи повышения надежности и эффективности функционирования ИИУС ГАП за счет рациональной организации вычислительных процессов в элементах ИИУС.

2. Разработаны математические модели оптимизации распределения вычислительных задач и программных модулей по элементам ИИУС ГАП;

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

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

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

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

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

Положения, выносимые на защиту

1. Математические модели оптимизации вычислительного процесса на уровне контуров (структурных элементов ИИУС ГАП верхнего уровня), позволяющие осуществлять распределение и перераспределение задач, решаемых в системе на этапах проектирования, эксплуатации и совершенствования ГАП.

2. Математические модели распределения программных модулей, составляющих решаемые задачи по узлам локальных УВК (структурных элементов ИИУС ГАП низшего уровня).

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

4. Методика применения разработанного математического аппарата оптимизации вычислительного процесса в ИИУС ГАП.

Апробация работы

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

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

Публикации.

По теме диссертации опубликовано 9 печатных работ в виде статей в журналах, трудах российской и международных научно-технических конференций, из них 4 работ в изданиях, рекомендованных ВАК РФ для опубликования научных положений диссертационных работ.

Реализация результатов работы.

Результаты исследований внедрены в учебный процесс кафедры «Приборы и информационно-измерительные системы» Московского государственного университета приборостроения и информатики, использованы в НИР, проводимых в ОАО «Центральный научно-исследовательский технологический институт» при разработке, эксплуатации и совершенствовании существующих и разрабатываемых ИИУС ГАП, что подтверждено соответствующим актом об использовании.

Структура и объем работы.

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

2. СОДЕРЖАНИЕ РАБОТЫ

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

В первой главе показано, что эффективность современных и перспективных ИИУС ГАП в значительной степени зависит от качества организации вычислительного процесса (ВП), протекающего в ней. Дан анализ принципов построения ИИУС ГАП.

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

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

Для сокращения размерности задач оптимизации ВП предлагается рассматривать ИИИУС ГАП в виде совокупности вложенных контуров (рис.1).

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

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

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

Рисунок 1. Пример структурной декомпозиции

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

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

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

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

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

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

Данные модели позволяют поэтапно и взаимосвязано решать задачи распределения информационных ресурсов по узлам ИИУС.

Пусть задана ИИУС (контур управления), состоящая из I УВК, каждая из которых имеет пу (¡=1, ...,1) пунктов обработки информации (микро-ЭВМ, дисплеев и т.п.).

В ИИУС решается Л" задач. На каждом Л-ом пункте у-го УВК (/'=/, 2,.... Ц (й=/, 2,. ... т^ решается строго определенный круг задач с генерацией соответствующих запросов (сообщений).

Распределение ПМ по узлам ИИУС определяется планом распределения задаваемым

матрицей X = ; |,

\1, если к-й ПМ размещается на у -й ЭВМ, где дг,. = < к = 1, 2,.. .,л, у = .....Ь.

[0. в противном случае

При постановке задач оптимизации вычислительного процесса в ИИУС могут быть использованы следующие критерии:

• максимум вероятности решения всех задач;

• минимум времени решения всех задач;

• минимум объема Информации циркулирующей в ИИУС.

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

Определить значения хч(к=1,2, ...,К;]-1,2, ...,£) такие что

Р = шахП П

Л-1 *.]

при ограничениях

а) на время решения к-ой задачи й-ым абонентом у-го УВК

* Т-7к>;=1>2,..,Ь;Ь=1,2.....к=1,2,...,М;

б) на объем информации циркулирующей в сети при решении й-ым абонентом у'-го узла к-оп задачи

Л^ < Л^,у = 1,2.....¿.'А = 1,2.....т,;к = 1.2....М;

в) на объем ВЗУу-го УВК

^хк1щ<У1,] = 1,2.....Ъ;

к-1

г) на значения переменных

2Х = = .....К;

{0,1};* = и,= 1,2,...Д.

>•1

где V] -объем ВЗУ у'-го УВК; иа - объем *-го ПМ; - максимально допустимое время решения й-ым абонентом у'-го УВК *-й задачи; Л^, - максимально допустимый обьем информации циркулирующей в ИИУС при решении Л-ым абонентом у'-го УВК *-ый задачи; 2 - максимально возможное число ПМ, которое может быть распределено в один узел ИИУС;

1-1

I С

7"и" =_ Уг /г + )

ГУМ

к,

■ вероятность успешной передачи информации между узлами у и I при решении

/¡-ьт абонентом у-го УВК к-ой задачи;

Р' = Р< р-1 ЦАЦ '/«Л* г1/1<> '

%- вероятности доведения запроса на решение и сообщения содержащего результаты решения А-ым абонентом у-го УВК к-оа задачи в ;'-м узле; среднее число информационных сообщений передаваемых при передаче из /-го узла в у'-й ; Т,;нк -

среднее время передачи сообщения из 1-го абонентом } • го УВК к - й задачи

узла ИИУС в у'-й при решении А-м

т = т' +Т"

лик '/¡кк /Нк '

т

11>1>к

, 7"',,, - среднее время передачи запроса на решение и сообщения, содержащего результаты решения А-ым абонентом у'-го УВК к-ой задачи в 1-м узле ИИУС соответственно ; - время решения к - го ПМ на / - ый УВК Л - ым абонентом у-го узла при наличии всех исходных данных ; = /, если А-й абоненту'-го УВК имеет право решать к-ую задачу , -0 - в противном случае : - интенсивность

решения к-ой задач» А-ым абонентом /-го УВК; 1!/1:1 - длина запроса на решение к-ый задачи Л -ым абонентом у-го УВК; - длина сообщения получаемого в результате решения Л-го ПМ А-ым абонентом у-го УВК .

Третья глава посвящена разработке математических моделей и алгоритмов оптимизации вычислительного процесса в нижнем уровне ИИУС ГАП.

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

о-

""V ✓ ' к *

' / V

*г (

-•л'" 1 *

V, ✓

Рисунок 2. Граф решения м-ой задачи

Пусть задана ИИУС, в которой работают IV абонентов. Система состонг из Ь УВК, в ней решается N задач. Каждая задача представляет собой совокупность из А',, (л = /,2,...,./У) взаимосвязанных программных модулей.

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

По критерию минимума объема информации, циркулирующей по узлам ИИУС

постановка задачи распределения ПМ по узлам ИИУС может быть сформулирована следующим образом.

Определить значения = /=1,2.....1; п-1,2.....АО такие, что

£ А'

Л= тш]Г]Г£ Л,,,„(.*)

/-1 Л«*, »-I

при офаничениях:

а) на время решения А - ым абонентом / - го УВК н - ой задачи

ТкТ. 2 С Л е ; / =1,2,...,£;„ = 1,2,....ЛГ;

б) на вероятность решения я - ой задачи А - м абонентом /- го УВК

А?: * С Л е /=1,2.....и =1,2....,

в) на объем ВЗУ /- го УВК

г) на значения переменных

г = {0.1}; к = 1,2,..., АГ„; / =1,2.....Ц п =1,2,...,Лг;

= 2,..и = 1,2,.

,ы

Г/, если к - й ПМ п-й задачи размещается на / - й ЭВМ где: = 4

[0, в противном случае,

* = 1,2,...,К„ /1 = 1,2,...,^, у = 1,2,...,Ь ; ^и/п ' максимальн0 допустимое время решения А - м абонентом / - го УВК п - ой задачи; - максимально допустимый объем информации циркулирующей в системе

при решении А- м абонентом /-го УВК п- ой задачи; - объем к - го ПМ п- ой задачи; Ку- объем ВЗУ /- го УВК; 2лутях - максимапьное количество ПМ п - ой задачи в / - го УВК; Рк/и - вероятность решения А - м абонентом /- го УВК 1- го модуля и-ой задачи (й = 1,2,...,Ь; п =1,2,...,М)

I 1-1

Р кп„ - вероятность решения А - м абонентом / -го УВК к - го модуля и - ой задачи [кеВп;к = г,...,^, -1;Л елг;/= 1,2,...,£; т =2,3,..., М„ -I;« = 1,2,..., А*)

I.

Р/,/л»= П РьГг'ШРь") ??•*/» • ' веР°ЯТН0СТЬ решения к - м абонентом / - го УВК п - он задачи

/'а-я/ " веРОЯТИОСТЬ решения к- го модуля л- ой задачи на_/'- го УВК при наличии

исходных данных; р вероятность доведеши запроса А - го абонента /-го УВК на

решение п- ой задачи на у - м УВК,( р^у)^ 1; рц- вероятность доведения

сообщения эталонной длины из 1-го УВК в ]- й; /э- длина эталонного сообщения; длина запроса А- го абонента /-го УВК на решение п- ой задачи; р"щ„-

вероятность доведения информационного сообщения, передаваемого от к- то ПМ, распределенного в / - м УВК, к g - му ПМ, распределенного в ] - ом УВК, при решении

п- он задачи, Рь4,„= (^; длина информационного сообщения,

передаваемого от к- го ПМ к £ - му ПМ при решении п- ой задачи; вероятность

получения Л - ом абонентом го УВК результатов решения «-ой задачи из _/- го УВК,

Рк[»г ( Р?/) " ; Чг,- длина сообщения, получаемого Л - м абонентом /- го УВК и содержащего результаты решения п - ой задачи; Sj - множество номеров абонентов АСУ

г

] - го УВК, такое что = Я; R - множество номеров абонентов системы, такое что

|й \ = Вт(т- 1,2,...,Л/в) - множество номеров ПМ т-то уровня; = /, если Л -й абонент /- го УВК имеет право решать п- ю задачу, гпАу — О-в противном случае. у-рш . время решения А - м абонентом / - го УВК п- ой задачи

(*еВ„;* = 2,...,ДГ.-1;Ле.1/;/=1,2)...,£;т=2,3.....Л/„-1;п=1,2.....ы)

1

■ .

Ти/Ы ' вРемя решения А - м абонентом /-то узла к - го модуля п - ой задачи ( Лб5/;/=1,2,...,1;А: = 1)...А'„-1;л=1,2.....ы),

£

шах 7\,„„ + У(/4„,.>

при к е Вш , от = 2,..., .V/, -1,к = 2.....А'„ -1,

£

+Е * 6 Д.,« = 1, * = 1;

- время решения А'- го ПМ и- ой задачи в _/- м узле; '¡¡¡,у„= " вРемя

доведения информационного сообщения, передаваемого от А - го ПМ, распределенного в /- ый узел, к £ - му ПМ, распределенного в }- ый узел, при решении п- ой задачи;

= 'и»./''[" время доведения до А - го абонента /-го узла результатов решения и - ой задачи из / - го узла; I - время доведеш1я сообщения эталонной длины из I - го узлав ]-й; / ¡у„ ,■ = ''0] /■„/''[ -время доведения запроса А-го абонента /-гоузлана решение п - ой задачи в _/' - й узел; ЛА/л - объем информации циркулирующей в системе при решении А - м абонентом / - го УВК п - ой задачи;

71 Р"" _

чг. +

Л л/л - Л*/

1 «£-1 л

4$]- среднее количество передач из /-го узла в у - й по критерию минимального суммарного времени передачи; - интенсивность решения п- ой задачи Л- м абонентом /- го узла.

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

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

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

• включение в схему ветвления нелинейных ограничений;

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

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

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

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

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

Определить такие составляющие вектора решения Х=(х<, которые

максимизируют функцию:

т = £сл

(1)

в области заданной ограничениями:

х: ={0,1},У = 1,2.....и

(2)

Ха„.дг,. <г>,. ¡=1,2.....т (3)

Для оценки границ решения условие (2) ослабляется и заменяется условием

0<=х1 <=/ Г-=1,п; (4)

Тогда двойственной по отношению к задаче (1), (3), (6) является задача

при ограничениях:

Z = min ЁЬ.у.+ Хи I (5) V. t«l i»m+l J

Ij = 1,2,...А (6)

y,>0, i = 1,2.....m + n. (7)

Обозначим

(2 = {де., е = 0,1,.... п, 1 = 1.2.....т + п}, как матрицу, к-ая строка которой представляет собой решение двойственной задачи (5) -(7), но при ) = г';, 12,--, 1к;

5 = и - множество индексов переменных, включенных в Б-частичное решение (здесь = {/ \ Х) = 4 = {/ \ х, = 0\у,

О' = У: ) = 1,2,...,п) - множество индексов переменной основной задачи. Тогда, приближенный алгоритм оценки границ решением двойственной задачи с определением порядка ветвления переменных включает следующие шаги.

1. Определить величину

с!^^-, 1 = 1,2,...,т+ п, Ьт+) =1, ) ~ 1,2,...,п,

¡«г

где к = 1,2,— - номер итерации, /* - множество индексов условий (6), для которых неравенство не выполняется (/' = {¡,2.....л})-

2. Выбрать двойственную переменную _у/, для которой выполняется условие

(1,"=пип (1>.

3. Вычислить значение переменной у,к и индекс переменной для ветвления на (п-к-/)-ом ярусе дерева ветвлений

т+п к-1

уг -Ш1П - -,

1 a'i

где у," s 0, i = 1,2,...,т + и.

Индекс i , который определяет минимум _>>/■ является индексом переменной х,к для ветвления на (л - к + /)-ом ярусе. Записать Р(к) = iq.

4. Определить значение элементов k-ой строки матрицы

+Уг*. ¡ = ¡.2....."' + ».

где qIM=0, i=l,2.....т + п.

5. Исключить из множества /* индекс уравнения, для которого выполняется условие

> с,, У = 1,2.....и,.

Проверить условие к-п, если условие не выполняется, то положить к = к+1 и перейти к пункту 1, в противном случае - к пункту 6.

6. Рассчитать

к т т^п

У,=1уЛ (1 = 1,2,...,т+п) и г= Е У|-

и ¡-1 1=111+1

Таким образом, при решении задачи (1), (3) порядок ветвления переменных определяется массивом Р - /„ }, и первой ветвится переменная .г, , а затем х,

и т.д.

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

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

В четвертой главе приводятся результаты экспериментальной проверки разработанных математических моделей, алгоритмов и методов оптимизации вычислительного процесса в ИИУС ГАП.

Экспериментальная проверка эффективности математических моделей оптимизации в распределения задач и ПМ по узлам ИИУС проводилась на примере ИИУС ГАП, состоящей из 12 УВК, структурно объединенных в три контура. Системой решалось 16 задач, функционально состоящих из 26 программных модулей.

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

По сравнению со случайным распределением решаемых задач в случае оптимального распределения задач вероятность решения всех поставленных задач возрастает в 1,5 - 2 раза.

Таким образом, оптимизация распределения задач по контурам системы позволяет снизить общий объем информации передаваемой по каналам связи на величину порядка 27% с одновременным значительным увеличением вероятности решения всех задач.

При решении задачи оптимизации распределения программных модулей задач в коотуре №3 по критерию минимума времени решения всех задач получено, что время решения всех задач в данной системе составило 12.57 сек. при объеме информации передаваемой по каналам связи 797854 и вероятности решения всех задач 0.94 при вероятности решения каждой из задач не менее 0.97. При произвольном распределении ПМ данные величины составили соответственно 17.29 сек., 911592. 0.89, 0.95, что говорит об эффективности разработанных математических моделей.

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

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

Следует отметить стабильность подобного поведения стратегий ветвления вне

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

Результаты экспериментальной проверки эффективности влияния предварительного определения порядка ветвления переменных приведены в табл. I. Расчеты производились с использованием глобально-поисковой стратегии ветвления переменных, симплекс-метода и приближённого с применением теории двойственности методов оценки границ решения. Из табл. 1 видно, что применение способа предварительного определения порядка ветвления переменных совместно с симплекс - методом оценки границ решения позволяет сократить время решения задач в 5-20 раз.

Таблица 1.

Оценка влияния предварительного определения порядка ветвления переменных на эффективность метода ветвей и границ_

ЫхМ Время решения задач ((с)

Без определения порядка ветвления С определением порядка ветнления

Симплекс-метод Приближённый метод Симплекс-метод Приближённый метод

15x10 0.59 0.34 0.01 0.03

20x10 1.62 0.45 0.03 0.12

30x10 17.54 19.82 0.57 0.84

50x10 245.63 141.93 9.7 14.95

100x10 19499 - 1002.3 4002.68

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

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

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

ОСНОВНЫЕ ВЫВОДЫ И РЕЗУЛЬТАТЫ РАБОТЫ

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

1. Эффективность функционирования ИИУС ГАП в значительной степени определяется качеством организации и построения вычислительного процесса в целом и программного обеспечения в частности.

2. Для обеспечения надежности и эффективности программного обеспечения в ИИУС ГАП, его целесообразно строить по модульному принципу.

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

4. Анализ путей повышения эффективности вычислительного процесса в ИИУС ГАП выдвигает задачу разработки моделей и методов оптимизации вычислительного процесса в системе вычислительных средств ИИУС ГАП.

5. В рамках подхода к построению вычислительного процесса в ИИУС ГАП, изложенного в главе I, разработаны следующие математические модели:

• математическая модель оптимизации распределения задач по контурам ИИУС ГАП;

• математическая модель оптимизации распределения программных модулей по узлам локальной вычислительной ИИУС (контура низшего уровня).

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

7. Для решения разработанных задач, связанных с реализацией математических моделей оптимизации вычислительного процесса в ИИУС ГАП предложены две схемы:

■ включение в схему ветвления метода ветвей и границ нелинейных ограничений;

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

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

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

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

11. Экспериментальная проверка разработанных математических моделей и алгоритмов оптимизации вычислительного процесса в ИИУС ГАП подтвердила их эффективность и целесообразность практического применения.

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

13. Экспериментально подтверждено, что снижение точности оценки границ решения в методе ветвей и границ ниже 5%, за счет использования более простых методов решения

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

ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ

Публикации в изданиях, рекомендованных ВАК

1. Есиков О.В., Акиншин Р.Н., Барышников Д.Ю., 'Габуров Д.Ю. Анализ дестабилизирущих факторов, воздействующих на информацию в распределенных вычислительных сетях// Известия ТулГУ. Серия Вычислительная техника Информационные технологии. Системы управления. Тула: ТулГУ, 2004. с. 37-42

2. Акиншин PH., Буркин В.В., Табуров Д.Ю. Постановка задач управления структурной динамикой аналитических информационных систем // Известия ТулГУ. Серия: Проблемы специального машиностроения. Вып. 7, 4.1,2004. с. 254-263.

3. Акиншин Р.Н., Буркин В.В., Табуров Д.Ю. Метод решения задачи управления структурной динамикой аналитических информационных систем// Известия ТулГУ. Серия Проблемы специального машиностроения. Вып. 7, ч. 1,2004. с. 264-271.

4. Табуров Д.Ю. Решение задач оптимизации вычислительного процесса в локальных сетях информационно-измерительных и управляющих систем с использованием метода ветвей и границ // Приборы. - М .: МНТО приборостроителей и метрологов, 2010, № 7, С. 50-56.

Публикации в других изданиях.

1. Акиншин Р.Н., Барышников Д.Ю., Табуров Д.Ю. Математическая модель определения рациональной длины пароля в системах аутентификации пользователей // Материалы 20-й Научной Сессии, посвященной Дню Радио, Тула: 2004.С. 29-31.

2. Акиншин PH., Кравченко A.B., Барышников Д.Ю. Табуров Д.Ю. Принципы повышения надежности и устойчивости функционирования современных АСУ за счет обеспечения защищенности и сохранности информации. //Материалы 20-й Научной Сессии, посвященной Дню Радио, Тула: 2004.C. 47-54.

3. Табуров Д.Ю., Акиншин P H., Борисов О.Н. Математические модели оптимизации информационно-вычислительных процессов в корпоративных сетях //Электродинамика и техника СВЧ и КВЧ. Москва, 2005 г.- т. X, № 5 с. 29-34.

4. Табуров Д.Ю., Акиншин Р.Н., Борисов О.Н. Обоснование общего подхода к оптимизации информационно-вычислительных процессов в корпоративных сетях//Элекгродинамнка и техника СВЧ и КВЧ. Москва, 2005 г.-т. X, № 5 с. 39-43.

5. Табуров Д.Ю. Математические модели оптимизации вычислительного процесса на уровне локальной вычислительной сети ЭВМ // Научные труды Международной НПК «Фундаментальные проблемы и современные технологии в машиностроении». - М.: Машиностроение, 2010. - с. 502-506.

Подписано к печати 17.01.2011г. Формат 60x84. 1/16 Объем 1, 0 п.л. Тираж 100 экз. Заказ № 5.

Московский государственный университет приборостроения и информатики

107996, Москва, ул. Стромынка, 20

ВВЕДЕНИЕ

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

1.1. Анализ схем построения типовых структур ГАП и разработка обобщенной схемы ИИУС ГАП.

1.2. Особенности современных технологий обеспечения надежности программного обеспечения ИИУС ГАП.

1.3. Обоснование общего подхода к построению вычислительного процесса в ИИУС ГАП.

1.4. Постановка задачи исследования.

Выводы.

ГЛАВА 2. МАТЕМАТИЧЕСКИЕ МОДЕЛИ И МЕТОДЫ

ОПТИМИЗАЦИИ ВЫЧИСЛИТЕЛЬНОГО ПРОЦЕССА В ВЕРХНЕМ КОНТУРЕ ИИУС ГАП

2.1. Анализ структур ИИУС ГАП.

2.2. Математическая модель оптимизации вычислительного процесса в верхнем контуре ИИУС ГАП.

2.3. Учет функционирования ИИУС ГАП в условиях функциональной деградации ее элементов.

Выводы.

ГЛАВА 3. МАТЕМАТИЧЕСКИЕ МОДЕЛИ И МЕТОДЫ

ОПТИМИЗАЦИИ ВЫЧИСЛИТЕЛЬНЫХ ПРОЦЕССОВ В НИЖНЕМ КОНТУРЕ ИИУС ГАП

3.1. Математические модели оптимизации вычислительного процесса в нижнем контуре ИИУС ГАП.

3.2. Применение метода ветвей и границ для решения задач оптимизации вычислительного процесса в ИИУС ГАП.

3.3. Общие принципы применения метода ветвей и границ для решения задач оптимизации вычислительного процесса в ИИУС ГАП.

3.4. Особенности применения методов оценки границ решения в методе ветвей и границ при решении задач оптимизации вычислительного процесса в ИИУС ГАП.

3.5. Применение теории двойственности для оценки границ решения и определения порядка ветвления переменных в методе ветвей и границ.

3.6. Особенности применения градиентного метода Эрроу-Гурвица для оценки границ решения в методе ветвей и границ.

Выводы.

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

4.1. Результаты экспериментальной проверки разработанных математических моделей оптимизации вычислительного процесса в ИИУС ГАП.

4.2 . Оценка эффективности применения метода ветвей и границ для решения задач оптимизации вычислительного процесса в

ИИУС ГАП.

4.3. Методические рекомендации по применению математического аппарата оптимизации вычислительного процесса в ИИУС ГАП.

Выводы.

г

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

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

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

Именно поэтому проектированию ИИУС ГАП в последнее время и уделяется большое внимание [1 - 10]. Однако, в целом, задачи анализа и синтеза ИИУС ГАП в целом недостаточно проработана. Существующие методики анализа и синтеза ИИУС ГАП и алгоритмов обмена информацией либо требуют больших вычислительных мощностей, либо не позволяют найти наилучший вариант.

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

Необходима систематизация и обобщение структур и алгоритмов работы современных ИИУС ГАП, а также разработка и представление материала, являющегося базой для-повышения их эффективности.

В этих условиях первостепенное значение приобретает совершенствование, и дальнейшее: развитие методов? и повышения эффективности ИИУС и широкое их практическое внедрение на основе использования современных средств вычислительной? техники; • и программного обеспечения;

Следует отметить, что в настоящее время однозначного решения: по использованию} той или иной методологии- для построения и оптимизации« ИИУС не существует. Промышленность предлагает не только сотни видов, различного? оборудования от множества производителей; но? и ряд принципиально отличающихся подходов к решению создания ИИУС ГАП.

Такое; направление развития ИИУС ГАП выявляет тенденцию усложнения; их структуры. Эта1 тенденция? ведет к необходимости решения, задач коммутации, так- как. качество решения данных задач; напрямую влияет на производительностьиэффективностьиспользованияИИУС в целом [11 -43];

В общем, решение проблемы повышения* эффективности ИИУС ГАГЕ зависит от многих факторов: структуры. ИИУС, интенсивности изменения? данных, времени^ задержек в узлах коммутации, пропускной способности каналов, и т.п.

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

Кроме того,, анализ данных, полученных от некоторых сложных объектов измерений показывает, что для определения результатов измерений с погрешностью, не превышающей. 2%, достаточно иметь 1/70 - 1/20 часть общего объема полученных сообщений. Столь существенная избыточность увеличивает информационную производительность ИИУС и влияет на пропускную способность канала связи, что приводит к увеличению времени-обработки измеряемых данных.

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

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

Выводы

1. Экспериментальная проверка разработанных математических моделей и алгоритмов оптимизации вычислительного процесса в ИИУС ГАП подтвердила их эффективность и целесообразность практического применения.

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

3. Экспериментально подтверждено, что снижение точности оценки границ решения в методе ветвей и границ ниже 5%, за счет использования более простых методов решения двойственных задач, не приводит к повышению общей эффективности метода. Предложено выделить способ определения порядка ветвления переменных в отдельную процедуру для совместного использования с точными методами оценки границ решения, что позволяет снизить время решения задач оптимизации вычислительного процесса в ИИУС в 2.5-20 раз.

ЗАКЛЮЧЕНИЕ

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

1. Эффективность функционирования ИИУС ГАП в значительной степени определяется качеством организации и построения вычислительного процесса в целом и программного обеспечения в частности.

2. Для обеспечения надежности и эффективности программного обеспечения в ИИУС ГАП, его целесообразно строить по модульному принципу.

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

4. Анализ путей повышения эффективности вычислительного процесса в ИИУС ГАП выдвигает задачу разработки моделей и методов оптимизации вычислительного процесса в системе вычислительных средств ИИУС ГАП.

5. В рамках подхода к построению вычислительного процесса в ИИУС ГАП, изложенного в главе 1, разработан комплекс взаимосвязанных математических моделей, состоящий из следующих задач:

• математическая модель оптимизации распределения задач по контурам ИИУС ГАП;

• математическая модель оптимизации распределения программных модулей по узлам локальной вычислительной ИИУС (контура низшего уровня).

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

7. Для решения разработанных задач, связанных с реализацией математических моделей оптимизации вычислительного процесса в ИИУС ГАП предложены две схемы:

• включение в схему ветвления метода ветвей и границ нелинейных ограничений;

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

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

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

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

11. Экспериментальная проверка разработанных математических моделей и алгоритмов оптимизации вычислительного процесса в ИИУС ГАП подтвердила их эффективность и целесообразность практического применения.

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

13. Экспериментально подтверждено, что снижение точности оценки границ решения в методе ветвей и границ ниже 5%, за счет использования более простых методов решения двойственных задач, не приводит к повышению общей эффективности метода. Предложено выделить способ определения порядка ветвления переменных в отдельную процедуру для совместного использования с точными методами оценки границ решения, что позволяет снизить время решения задач оптимизации вычислительного процесса в ИИУС в 2.5-20 раз.

1. Системное проектирование интегральных производственных комплексов /А.Н. Домогацкий, А.А. Лескин, В.М. Пономарев и др.; Под ред. В.М. Пономарева. Л.: Машиностроение. Ленинградское отделение, 1986. — 319 с.

2. Гибкое автоматизированное производство / Под ред. С.А. Майорова, А.Г. Ворловского, С.Н. Халиопова. -Л.: Машиностроение, 1985.- 454 с.

3. Гибкие производственные комплексы./ Под ред. П.Н. Белянина, В.А. Лещенко.-М.: Машиностроение, 1984.-384 с.

4. Промышленная робототехника / А.В. Бабич, А.Г. Баранов, И.А. Калабин и др. / Под ред. Шифрина. -М.: Машиностроение, 1982.- 415с.

5. Имитационное моделирование производственных систем / Под ред. А.А. Вавилова.-М.: Берлин, Машиностроение, Техника, 1983.- 416с.

6. Wernicke Н., Gericke Е. Modeling and simulation of automated manufacturing process. / Proc. of the IF AC Intern. Sympos. On information control problem in manufacturing technology. Japan, Tokyo, 17-20 oct. 1977, Pergamon Press, Oxford ets, 1978/ p. 1-6.

7. Spur G., Krause F., Pistorues E. Computer international representation of products for integrations of design and technological planning. Integration of CAD/CAM. Elsevier science publishers B.V. (North Holland) IFIP, 1985.-p.79-105.

8. Hegland D. E. Flexible manufacturing a strategy for winners // production engineering. - 1982, sept. - p. 41-46.

9. Системы управления промышленными роботами и манипуляторами / Е.И. Юревич, Ю.Д. Андрианов, С.И. Новаченко и др.; Л.: ЛГУ, 1980. 184 с.

10. Управляющие системы промышленных роботов / Ю.А. Андрианов, Л.Я. Глейзер, М.Б. Игнатьев и др. / Под ред. И.М. Макарова, В.А. Чиганова. -М.: Машиностроение, 1988.- 288 с.

11. Лескин А.А., Пономарев В.М., Смирнов А.В. Принципы автоматизированного проектирования технологических структур гибкихавтоматизированных производств. Системы автоматизации в науке и производстве. -М.: Наука, 1984. с. 209-216.

12. Кини Р.Л., Райфа X. Принятие решений при многих критериях: предпочтения и замещения: Пер. с англ. М. : Радио и связь, 1981.-560 с.

13. Левин Т.М., Тапаев В. С. Декомпозиционные методы оптимизации проектных решений. Минск: Наука и техника, 1978.-240 с.

14. ГОСТ 26228-85. Гибкие автоматизированные производства.

15. Солодовников В.В., Бирюков В.Ф., Тумаркин В. И. Принцип сложности в теории управления: О проектировании технически оптимальных систем и о проблеме корректности . М.:, Наука, 1977. -344 с.

16. Гибкие производственные комплексы / Под ред.П.Н.Белянина, В.А.Лещенко. М.: Машиностроение, 1984.- 384 с.

17. Мишкинд С.И. Применение промышленных роботов в механосборочном производстве. М.: Машиностроение, 1981.-60 с.

18. Патон Б.Е., Спыну Г.А., Тимошенко В. Г. Промышленные роботы для сварки. Киев: Науковая думка, 1977.-277 с.

19. Мишкинд С.и., Ефремов Е.В. Развитие робототехники за рубежом (по материалам 3-го международного симпозиума по промышленным роботам) Обзор, М.: НИИМАШ, 1976.-88с.

20. Попов Е.Л. Роботы манипуляторы. М.: Знание, 1974.-64 с.

21. Конструкция и наладка станков с программным управлением и роботизированных комплексов: Учеб. Пособие для ПТУ / Л.Н.Грачев, В.А.Косовский, А.Н.Ковшов и др. 2-е изд, М., Высш. шк. 1989.-271 с.

22. Коган М.С., Агафонов Ю.Г., Шишулин А. Л. Опыт эксплуатации промышленных роботов "Циклон-36". станки и инструменты, 1978, №11, с.17-19.

23. Липаев В.В., Яшков С.Ф. Эффективность методов организации вычислительных систем. М.: Статистика, 1975г.,. 255 с.

24. Промышленная робототехника / А.В.Бабич, А.Г.Баранов, И.В.Калабини др. Под ред. Я.А.Шифрина М.: Машиностроение, 1982. - 415 с.

25. Гибкие сборочные системы / Под ред. У.Б.Хегинботама;

26. Пер. с англ. Д: Ф.Миронова; Под ред. А.М.Покровского. М.: Машиностроение, 1988.-400 с.

27. Гибкое автоматизированное .производство / Под общ. ред. С.А.Майорова, Г.В.Орловского, С.Н.Халкиопова. -JI.¡Машиностроение, 1985.-454 с.

28. Пятибратов А.П., Гудыно Л.П., Кириченко A.A. Вычислительные системы, сети и телекоммуникации. -М.: Финансы и статистика, 2001.

29. Дмошинский Г.М., Серегин A.B. Телекоммуникационные сети в России. -М.: Архитектура и строительство в России, 1993.

30. Глушков В.М. Сети ЭВМ.-М.: Связь.1977.

31. Флинт Д. Локальные сети ЭВМ: архитектура, принципы построения, реализация. -М.: Финансы и статистика, 1986.

32. Якубайтис Э.А. Архитектура вычислительных сетей. -М.:Статистика, 1980.

33. Якубайтис Э.А. Информационно-вычислительные сети.-М.'Финансы и статистика, 1984.

34. Артамонов Г.Т., Тюрин В.Д. Топология сетей ЭВМ и многопроцессорных систем. -М.: Радио и связь, 1991.

35. Янбых Г.Ф., Столяров Б. А. Оптимизация информационно-вычислительныхсистем. -М.: Радио и связь, 1987.

36. Зайченко Ю.П., Гонта Ю.В. Структурная оптимизация сетей ЭВМ. Киев:Техника, 1986.

37. Балыбердин В.А. Оценка и оптимизация характеристик систем обработки данных.-М.:Радио и связь, 1987.

38. Балыбердин В.А. Методы анализа мультипрограммных систем. -М.: Радио и связь, 1982.

39. Балыбердин В.А., Белевцев A.M., Степанов O.A. Оптимизация информационных процессов в автоматизированных системах с распределенной обработкой данных. -М.:Технология, 2002.

40. Хорошевский В.Г. Инженерный анализ функционирования вычислительных машин и систем.-М.: Радио и связь, 1987.

41. Турута E.H. Обеспечение отказоустойчивых управляющих многопроцессорных систем путем перераспределения задач отказавших модулей // Системы управления информационных сетей. -М.гНаука, 1983.

42. Турута E.H., Аскеров Ч.И., Фургина JI.A. Распределение задач с целью обеспечения отказоустойчивости многопроцессорных вычислительных систем //Сетевые протоколы и управление в распределенных вычислительных системах. -М.: Наука, 1986.

43. Кондратьев К.О. Метод динамического перераспределения управляющих программ в распределенном вычислительном комплексе// Автоматика и вычислительная техника.-1987.-№6.

44. Мамиконов А.Г., Кульба В.В., Шелков А.Б. Достоверность, защита и резервирование информации в АСУ. -М.: Энергоатомиздат, 1986.

45. Мамиконов А.Г., Кульба В.В. Синтез оптимальных модульных систем обработки данных. -М.:Наука, 1986.

46. Кульба В.В, Сомов С.К., Шелков А.Б. Резервирование данных в сетях. — Казань: 1987.

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

48. Михалевич B.C. Волкович B.JI. Вычислительные методы исследования и проектирования сложных систем. — М.: Наука, 1982.

49. Михалевич B.C. Последовательные алгоритмы оптимизации и их применение. I, II//Ж. Кибернетика.- 1965.-№1.

50. Сергиенко И.В. Математические модели и методы решения задач дискретной оптимизации. -Киёв: Наукова думка, 1988.

51. Корпоративные сети связи. Вып. 3, под ред. Купермана М.Б. М.: Информсвязь, 1997.

52. Куперман М.Б., Лясковский Ю.К. Технологии и протоколы территориальных сетей связи, Корпоративные сети связи. Вып. 3. -М.; Информсвязь, 1997.

53. Майерс Г. Надежность программного обеспечения: Пер. с англ. /Под ред. В.Ш. Кауфмана. М.: Мир, 1980.

54. Липаев В.В. Надежность программных средств.- М.: СИНТЕГ, 1998.

55. Боэм Б.У. Инженерное проектирование программного обеспечения: Пер. с англ. /Под ред. A.A. Красилова.-М.:Радио и связь, 1985.

56. Котляров В.П. CASE-технологии и возможности современных CASE-средств в поддержке этапов проектирования программного продукта. // системная информатика. Новосибирск. ВО "Наука". Сибирская издательская фирма. Вып 4.1995.

57. Костогрызов А.И., Липаев В.В. Сертификация качества функционирования автоматизированных информационных систем. М.: Изд. Вооружение. Политика. Конверсия. 1996.

58. Gomory R.E. Outline of an algorithm for integer solution to linear programs/ Bull. Amer. Math. Soc. -1958.-V.64, N1. P.39-52

59. Kolesar P.J. A branch — and — bound algorithm for the knapsack problem/ Manag. Sci.-1967.-V.13N9.-p.723-735.

60. Михалевич B.C.,- Волкович В.Л.,' Волошин А.Ф. Метод последовательного анализа в задачах линейного программирования большого размера // Кибернетика.-1981.-№4.-с.114-120

61. Васильев Ф.П. Численные методы решения экстремальных задач.-М.: Наука, 1988.-549 с.

62. Первозванский A.A., Гайцгори В.Г. Декомпозиция, агрегирование и приближенная оптимизация.-М.: Наука, 1979.-276 с.

63. Емеличев В.А., Комлик В.И. Метод построения последовательных планов для решения задач дискретной оптимизации. -М.: Наука, 1981.-208 с.

64. Гене Г.В., Левнер Е.В. Дискретные оптимизационные задачи и эффективные приближенные алгоритмы. Обзор // Изв. АН СССР. Техническая кибернетика.-1973 .-№6-с. 84-92

65. Бабаев A.A. Организация поиска решений на деревьях детерминированной структуры. Электронное моделирование 1985 г., т.7, №1,стр 19-25.

66. Кузнецов О.П. Адельсон-Вельский Г.М. Дискретная математика для инженера. М.- Энергоатомиздат 1988гг.

67. Акулич И.Л. Математическое программирование в примерах и задачах. Высшая школа 1986 г.

68. Акиншин Р.Н., Барышников Д.Ю., Табуров Д.Ю. Математическая модель определения рациональной длины пароля в системах аутентификации пользователей// Материалы 20 научной сессии, посвященной дню радио, Тула: 2004.С. 29-31.

69. Акиншин Р.Н., Буркин В.В., Табуров Д.Ю. Постановка задач управленияструктурной динамикой аналитических информационных систем// Известия ТулГУ. Серия Проблемы специального машиностроения. Вып 7 ч.1,2004. с. 254-263.

70. Акиншин Р.Н., Буркин В.В., Табуров Д.Ю. Метод решения задачи управления структурной динамикой аналитических информационных систем// Известия ТулГУ. Серия Проблемы специального машиностроения. Вып. 7, ч.1, 2004. с. 264-271.

71. Табуров Д.Ю., Акиншин Р.Н., Борисов О.Н. Математические модели оптимизации информационно-вычислительных процессов в корпоративных сетях//Электродинамика и техника СВЧ и КВЧ. Москва, 2005 г.-т. X, № 5 с. 29-34.

72. Табуров Д.Ю., Акиншин Р.Н., Борисов О.Н. Обоснование общего подхода к оптимизации информационно-вычислительных процессов в корпоративных сетяхУ/Электродинамика и техника СВЧ и КВЧ. Москва, 2005 г.-т. X, № 5 с. 39-43.

73. Табуров Д.Ю. Решение задач оптимизации вычислительного процесса в локальных сетях информационно-измерительных и управляющих систем с использованием метода ветвей и границ // Приборы. — М .: МНТО приборостроителей и метрологов, 2010, № 7, С. 50-56.

74. Табуров Д.Ю. Основные математические задачи повышения эффективности информационно-измерительных и управляющих систем ГАП// Приборы. М .: МНТО приборостроителей и метрологов, 2011, № 2, С. 49-51.

75. Л.С.Ямпольский. Принципы построения роботизированныхтехнологических комплексов. Приборостроение, Киев: 1980, 116 с.

76. Рапоппорт Г.Н., Солин Ю.В. Применение промышленных роботов. — М.: Машиностроение, 1985.-272 с.

77. Балабанов A.C., Храбров Д. С. Технологическое оснащение сборочных работ. Механизация и автоматизация производственных процессов. Л.: ЛДНТП, 1979, с.6-9.

78. Великович В.Б. Анализ компоновочных схем роботизированныхкомплексов / Станки и инструменты. 1982, № 1, стр.7-8.

79. Гибкие производственные системы, промышленные роботы, робототехнические комплексы./ В 14 кн. Кн. 13. В.Н. Давыгора. ГПС для сборочных работ. Практическое пособие. / Под ред. Б.И. Черпакова.- М.: Высшая школа, 1989.- 110.

80. Соколов O.A. Контурные системы числового программного управления станками и промышленными роботами.- Л.: ЛПИ, 1982.80 с. '

81. Овнакян И.О. Использование комплектного оборудования с открытой архитектурой для создания систем с ЧПУ. // Научно-исследовательские работы в области станкостроения. М.: Тр. ЭНИМСА. Под ред. Б.И. Черпакова. 2000. - С. 39-48.

82. Чиликин М.Г., Ключев В.И., Сандлер A.C. Теория автоматизированного электропривода. М.: Энергия, 1979. - 616 с.

83. Коровин Б.Т. Системы автоматического управления промышленными роботами и манипуляторами. Л.: ЛЭТИ, 1981. - 82 с.

84. Слепцов В.В., Картавцев В.И. Основные задачи проектирования информационно-измерительных систем робототехнических комплексов сборки. //Сборник научных трудов. "Точные приборы и измерительные системы." М.: МГАПИ, 2000.- С.,91-93.

85. Цапенко М.П. Информационно-измерительные системы. М.: Энергоатомиздат, 1985. - 384 с.

86. Картавцев В.И. Основные средства информационного обеспечения робототехнических комплексов. //Сборник научных трудов. Точныеприборы и измерительные системы.- М.: МГАПИ, 2000.- Стр. 93-96.

87. Слепцов В.В., Руабхи Насир, Слепцов Т.В. Информационные измерительные системы. Учебное пособие. М.: МГАПИ, 1999. - 60 с.

88. Бушуев В.В. Динамические свойства электроэнергетических систем. -М.: Энергоатомиздат, 1987. 120 с.

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

90. Коршунов Ю.М. Математические основы кибернетики. Учебное пособие для вузов. -М.: Энергоатомиздат, 1987. 496 с.

91. Дениса A.A., Колесников Д.Н. Теория больших систем управления. Учебное пособие для вузов.-JI.: Энергоиздат, Ленинградское отделение, 1982.-288 с.

92. Кнауэр И.Б., Руабхи Насир, Слепцов В.В. Минимизация времени сборки в РТК. // СТИН, №9, 1999. с. 3-5.

93. Руабхи Насир, Слепцов В.В. Синтез алгоритмов передачи информации винформационных измерительных системах РТК.//СТИН, №1,2000.-с.30-32

94. Оллсон Г., Пиани Дж. Цифровые системы автоматизации и управления.

95. СПб.: Невский Диалект, 2001.- 557 е.: ил.

96. Опыт разработки и применения устройств ЧПУ для тяжелых иуникальных станков / П.С.Иванов, М.Б.Баранов, В.П.Росляков и др. Л.: ЛДНТП, 1983, 25 с.

97. Спиди К., Браун Р., Гудвин Дж. Теория управления. М. : Мир,1973.- 125с.

98. Кнауэр И.Б., Руабхи Н., В.В.Слепцов, Минимизация времени'''.■■'■' 146 'сборки-в РТК. Ж. "СТИН", №9; 1999г., с. 3-5;

99. Bentley J;L., Slcator D.D., Tarjan R.E., Wei V.KL. A locally adaptive datacompression scheme. Commun. ACM 29, 4 (Apr. 1986), p. 320-33

100. FialaE.R., Greene D.H. Data compression with finite windows. CACM-32, 4 (1989), p. 490-505.103; Gallager R.G. Variations on the theme by Huffman. IEEE Trans. Inf. Theory IT 24, 6 (Nov. 1978), p. 668-674. / ■

101. Golomb S.W. Run-length encoding. IEEE Tr. Inf. Theory IT-12, (1966), p. 399-401. ;

102. Huffman D.A. A method for the constmctionofminimum-redundancy codes. Proc. Inst. Electr. Radio Eng. 40^9 (Sept. 1952); p. 1098-1101.

103. Wilson N. Single-chip engine for document compression. // Electronics and wireless world 95, 1636 (Feb. 1989), pi 116-119. .

104. Ziv J., and Lempel, A. Compression of individual sequences via variablerate coding. // IEEE Trans. Inf. Theory 1T-24, 5 (Sept. 1978), p. 530-536:108: Taaffe 0. The move from capacity to capability. Telecommunications International, December, 2005.

105. Bellamy J.C. Digital Telephony. Third Edition,-John Wiley & Sons, Inc,2000r. . / ' ' " ■""■

106. Sweldens, W. Wavelets: What next? // Proc. IEEE, 1996, vol.84, p. 680

107. Yermolenko T.V. Segmentation of a speech signal with application of fast wavelet-transformation // International Journal on Information Theories and Applications. 2003. - Vol. 10, №3. - P. 306-310.

108. Прэтт У. Цифровая обработка изображений: Пер. с англ. М.: Мир, 1982. Кн.1 и 2. - 312 и 480 с.

109. Пеев Е., Боянов К., Белчева О. Методи и средства за компрессия на изображения // Автоматика и информатика.-1994.-28, №3 .-стр.3-14.

110. Cooley J.W., Tukey J.W. An algorithm for machine computation of complex Fourier series // Mach. Comput. 1965. - V. 19. - P. 297-301.

111. Rao K.R., Yip P. Discrete cosine transform algorithms, advantages, applications. - London: Academic Press inc., 1990.

112. Виленкин Н.Я. Об одном классе полных ортогональных систем // Изв. АН СССР. Сер. мат. 1947. - T.l 1. - С. 363-400.

113. Chrestenson Н.Е. A class of generalized Walsh functions // Pacific. J. Math. 1955. - V.5. - №1. - P. 17-32/

114. Столлингс В. Современные компьютерные сети.-СПб: Питер, 2003, -783с. ■ •

115. Perkins M.G. A comparison of the Hartley, Cas-Cas, Fourier, and discrete cosine transforms for image coding // IEEE Trans. Commun. 1988. - V.36. - №6. - P.758-761.

116. Умняшкин С.В. Быстрые алгоритмы вычисления дискретного мультипликативного преобразования / М.: МГИЭТ (ТУ), 1995. 15 с.— Деп. в ВИНИТИ 16.02.95, № 442-В95.

117. Липский В. Комбинаторика для программистов. М.: Мир. 1988.215 с. '

118. Майника Э. Алгоритмы оптимизации на сетях и графах. М.: Мир, 1981.-323 с.

119. Михалевич B.C., Кукса А.И. Методы последовательной оптимизации.148*-М.: Наука, 1983. -208 с/ ' ' j -'-,>!

120. Петухов А.П. Введение в теорию' базисов всплесков. — С-Пб.: СПбГТУ,1999.-132 с.

121. Timofeev A.V. Multi-Agent Information Processing and Adaptive Control in Global Telecommunication and Computer Networks. International Journal «Information Theories and Their Applications», 2003, № 10, pp. 54-60.

122. Алексеев И.В., Соколов B.A. Протокол TCP с адаптацией скорости. // Моделирование и анализ информационных систем. Т.6, № 1. 1999. — С.4-12.

123. Алексеев И.В. Математическая модель протокола TCP с адаптацией скорости. // Моделирование и анализ информационных систем. Т.6, №2. -1999.- С. 51-53.

124. Гольдштейн Б. Протоколы сети доступа. // М., Радио и связь. -1999.

125. Кораблин, М. А. Маршрутизация на основе нечеткой логики в рамках протокола RIP / М. А. Кораблин, Д. Ю. Полукаров // Информационные технологии. 2005. - № 6. - С. 11-15.

126. Алиев Т.И., Муравьева JI.A. Выбор метода диспетчеризации в системах реального времени // Третье Всесоюзное совещание по распределенным автоматизированным системам массового обслуживания. Тезисы докладов. -М.^ 1990.-С. 126-128.

127. Taqqu М., Willinger W., Sherman R. Proof of Fundamental Result in Self

128. Similar Traffic Modelling. // Computer Communications Review, n. 27. -1997.-p. 5-23.

129. Frost V., Melamed B. Traffic-modelling for telecommunications networks. //ШЕЕ Communications Magazine. 32(2). -1994.- p. 70-80.

130. Leland W., Taqqu M., Willinger W., Wilson D. On the Self-Similar Nature of Ethernet Traffic (Extended Version). // ÏT TEE/ACM Transactions on Networking. 2(1).-1994.-p. 1-15.

131. Gusella R. A Measurement Study of Diskless Workstations Traffic on an Ethernet. //ШЕЕ Trans, on Communications. 38(9). 1990.- p. 15571568.

132. Paxson V., Floyd S. Wide-Area Traffic: The Failure of Poisson Modelling. // ШЕЕ/ACM Transactions on Networking. 3(3). 1995.- p. 226-244.

133. Floyd S., Jacobson V. The Synchronization of Periodic Routing Messages. // IEEE/ACM Transactions on Networking. 2(2). 1994.- p 122-136.