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

• Бычков, Иван Алексеевич
• кандидат физико-математических наук
• 2013

Оглавление диссертации кандидат физико-математических наук Бычков, Иван Алексеевич

Оглавление

Введение

Глава 1. Задача построения расписания обменов в кольце с арбитражем

1.1 Понятие кольца с арбитражем

1.2 Описание задачи

1.3 Способы организации информационных обменов в кольце с арбитражем

1.3.1 Децентрализованный способ организации информационных обменов

1.3.2 Централизованный способ организации информационных обменов

1.4 Формальная модель информационных обменов и математическая постановка задачи

1.5 Выводы

Глава 2. Задача выбора порядка абонентов в кольце с арбитражем

2.1 Топологии кольца с арбитражем

2.1.1 Топология с концентратором

2.1.2 Топология без концентратора

2.2 Описание задачи

2.3 Формальная постановка задачи

2.4 Выводы

Глава 3. Существующие методы решения рассматриваемых задач

3.1 Метод полного перебора

3.2 Жадные алгоритмы

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

3.4 Генетические и эволюционные алгоритмы

3.5 Муравьиные алгоритмы

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

3.7 Алгоритмы на основе нейросетей Хопфилда

3.8 Ненаправленный случайный поиск

3.9 Направленный случайный поиск

3.10 Выводы

Глава 4. Предлагаемые алгоритмы решения рассматриваемых задач

4.1 Алгоритм решения задачи построения расписания обменов в кольце с арбитражем

4.1.1 Входные данные и результат работы алгоритма

4.1.2 Принцип работы алгоритма

4.1.3 Функции и переменные, используемые в алгоритме

4.1.4 Пошаговое описание алгоритма

4.1.5 Пошаговое описание используемых функций

4.1.6 Завершимость алгоритма

4.1.7 Корректность алгоритма

4.1.8 Достаточные условия, при которых алгоритм является точным

4.1.9 Вычислительная сложность алгоритма

4.2 Алгоритм решения задачи выбора порядка абонентов в кольце с арбитражем

4.2.1 Входные данные и результат работы алгоритма

4.2.2 Описание разработанного алгоритма

4.2.3 Корректность и завершимость алгоритма

4.2.4 Вычислительная сложность алгоритма

4.3 Выводы

Глава 5. Численные исследования разработанных алгоритмов

5.1 Методика статистической обработки результатов экспериментов

5.2 Исходные данные

5.2.1 Реальные данные

5.2.2 Модельные данные

5.3 Результаты исследований

5.3.1 Исследование алгоритма построения расписаний обменов

5.3.2 Исследование алгоритма выбора порядка абонентов

5.4 Выводы

Глава 6. Инструментальная система

6.1 Требования к инструментальной системе построения расписаний информационных обменов в кольце с арбитражем

6.2 Разработанная система

6.2.1 Структура разработанной библиотеки

6.2.2 Консольные приложения

6.2.3 Приложение с графическим интерфейсом пользователя

6.3 Выводы

Заключение

Литература

Приложение А. Математические определения

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

Приложение В. Доказательство NP-трудности рассматриваемых задач

Приложение Г. Детализированные правила передачи сообщений в кольце

с арбитражем

Приложение Д. Детализированное описание централизованного способа

организации информационных обменов

Приложение Е. Параметры кольца с арбитражем

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

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

Приложение К. Результаты численных исследований

Введение диссертации (часть автореферата) на тему «Планирование обменов в сетях с топологией кольца с арбитражем для систем реального времени»

Введение

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

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

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

Кольцо с арбитражем - это среда передачи данных, в которой информация передаётся по однонаправленному замкнутому контуру. Каждая подсистема, использующая кольцо с арбитражем для обмена информацией с другими подсистемами, выступает по отношению к кольцу с арбитражем в роли абонента - потребителя услуги, предоставляемой средой передачи данных, которая заключается в возможности передачи информационных сообщений от одного абонента другому абоненту (или сразу нескольким абонентам). Кольцо с арбитражем является одной из трёх топологий, поддерживаемых семейством открытых промышленных стандартов Fibre Channel. Практическая значимость решения задачи построения расписаний обменов в кольце с арбитражем подтверждается [27, 54, 57, 59, 60, 72] широким применением стандартов Fibre Channel в бортовых ВСРВ.

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

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

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

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

• Разработать алгоритм построения расписаний обменов в кольце с арбитражем.

• Разработать алгоритм выбора порядка абонентов в кольце с арбитражем.

• Провести исследование разработанных алгоритмов на реальных и модельных данных.

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

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

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

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

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

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

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

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

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

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

В приложении А приведены определения используемых математических величин. В приложении Б описаны пространства поиска для рассматриваемых задач и доказана их конечность. В приложении В доказана А^Р-трудность в сильном смысле рассматриваемых задач. В приложении Г приведены детализированные правила передачи сообщений в кольце с арбитражем. В приложении Д приведена формализация основных понятий центра-

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

Благодарности. Автор выражает искреннюю благодарность научному руководителю В. А. Костенко за неоценимую помощь в подготовке диссертации, заведующему лабораторией Р. Л. Смелянскому за содействие в получении доступа к суперкомпьютеру «Ломоносов», В. Балашову и В. Балаханову за ценные рекомендации, а также А. Барсукову, К. Бычкову, Г. Гурьянову, В. Ильину, А. Лобас, А. Мочаловой, А. Овсянниковой, А. Пожидаеву, В. Хлызову, Д. Хомутову, В. Черникову, В. Чугунову, Е. Шалаевой за предоставление своих вычислительных ресурсов для проведения вычислительных экспериментов.

Заключение диссертации по теме «Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей», Бычков, Иван Алексеевич

Заключение

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

1. Предложена математическая модель информационных обменов в кольце с арбитражем. которая позволяет описывать различные способы построения кольца с арбитражем. В рамках разработанной модели предложена постановка задач построения расписания обменов и выбора порядка абонентов в кольце с арбитражем. Доказана NP-трудпость поставленных задач.

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

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

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

Список литературы диссертационного исследования кандидат физико-математических наук Бычков, Иван Алексеевич, 2013 год

Литература

1. ГОСТ Р -52070-2003. Интерфейс магистральный последовательный системы электронных модулей. - Введ. 01.01.2004 - М.: Изд-во стандартов, 2001. - 23 с.

2. ANSI ХЗ.230-1994. Information Technology - Fibre Channel - Physical and Signaling Interface (FC-PH) // American National Standards Institute (ANSI), 1994.

3. ANSI X3.272-1996, Information Technology - Fibre Channel - Arbitrated Loop (FC-AL) // American National Standards Institute (ANSI), 1996.

4. ANSI X3.297-1997, Information Technology - Fibre Channel - Physical and Signalling Interface-2 (FC-PH-2) // American National Standards Institute (ANSI), 1999.

5. Information technology - Fibre Channel - Part 312: Avionics environment upper layer protocol MIL-STD-1553B Notice 2 (FC-AE-1553) : Technical Report TR 14165-312:2009 /'/ International Organization for Standardization (ISO), 2009. - 84 p.

6. ISO/IEC 14165-122:2005. Information technology - Fibre Channel - Part 122: Arbitrated Loop-2 (FC-AL-2) // International Organization for Standardization (ISO), 2005. - 144 p.

7. Абрамов С. А. Лекции о сложности алгоритмов. - M.: МЦНМО, 2009. - 253 с.

8. Балахапов В. А., Костепко В. А. Способы сведения задачи построения статико-динамического однопроцессорного расписания для систем реального времени к задаче нахождения на графе маршрута // Программные системы и инструменты. Тематический сборник № 8, М.: Изд-во факультета ВМиК МГУ, 2007. - с. 148-156.

9. Балашов В. В. Обеспечение совместимости требований к расписанию обмена по каналу с централизованным управленнем : дис. ...канд. физ.-.мат. наук : 05.13.11 / [Место защиты: МГУ им. М.В. Ломоносова]. 2010. - 171 с.

10. Батищев Д. И.. Исаев С. А. Оптимизация многоэкстремальных функций с помощью генетических алгоритмов./Межвузовский сборник научных трудов «Высокие технологии в технике, медицине и образовании», Воронеж. ВГТУ. 1997г. с. 4-17.

11. Беламан Р. Динамическое программирование. - М.: Изд-во иностранной литературы. 1960. - 400 с.

12. Бычков И. А.. Костепко В. А. Возможность использования арбитражного кольца Fibre Channel в вычислительных системах реального времени // Программные системы и инструменты. Тематический сборник N 8. М.: Изд-во факультета ВМиК МГУ, 2007. -с. 157-172.

13. Бычков И. А. Алгоритм выбора порядка абонентов в сети с топологией кольца с арбитражем // Параллельные вычисления и задачи управления (РАСО'2012). Шестая международная конференция, Москва. 24-26 окт. 2012 г. - Труды: в 3 т. - М.: ИПУ РАН. 2012. - Т. 1. - с. 238-249.

14. Бычков И. А. Алгоритм решения задачи построения расписаний для произвольно заданной функции минимально допустимых задержек !/ Мир компьютерной автоматизации: встраиваемые компьютерные системы. Л'2 2, 2013. - с. 52-64.

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

16. Винокуров А. В.. Костенко В. А. Использование сетей Хопфилда для построения расписаний // Труды Международной конференции «Параллельные вычисления и задачи управления» (РАСО'2001). Москва. 2-4 октября 2001 г. Институт проблем управления им. В. А. Трапезникова РАН. - М. Институт проблем управления им. В. А. Трапезникова РАН. 2001. с. 53-65.

17. Гладков Л. А.. Курейчик В. В., Курейчик В. М. Генетические алгоритмы. - М.: Физ-матлит. 2006. - 320 с.

18. Гуз Д. С. Разработка точных и приближенных алгоритмов составления расписаний и синаеза систем жесткого реального времени : дис. .. .канд. физ.-мат. наук : 05.13.18 / МФТИ. - М., 2005. - 132 с.

19. Гэри М.. Джонсон Д. Вычислительные машины и трудно решаемые задачи. - М.: Мир. 1982. 416 с.

20. Калинина В. Н., Панкин В. Ф. Математическая статистика. - М.: Высшая школа. 1998. - 336 с.

21. Кормен Т.. Лейзерсо'н Ч.. Ривест Р.. Штайн К. Алгоритмы: построение и анализ. -2-е изд. - М.: Издательский дом Вильяме, 2005. - 1290 с.

22. Костенко В. А. Алгоритмы оптимизации, опирающиеся на метод проб и ошибок, в совместном проектировании аппаратных и программных средств ВС / / Труды Всероссийской научной конференции «Высокопроизводительные вычисления и их приложения». (30 октября - 2 ноября 2000 г., Черноголовка). - М.: Изд-во МГУ. 2000, с. 123-127.

23. Костенко В. А. Принципы построения генетических алгоритмов и их использование для решения задач оптимизации // Труды IV Международной конференции «Дискретные модели в теории управляющих систем» (19-25 июня 2000 г.) с. 49-55.

24. Костеико В. А.. Калашников A.B. Исследование различных модификаций алгоритмов имитации отжига для решения задачи построения многопроцессорных расписаний /V Труды VII Международной Конференции «Дискретные модели в теории управляющих систем». Покровское, 4-6 марта 2006 г. - М.: МАКС Пресс:. 2006. - с. 179-184.

25. Костеико В. А. Алгоритмы построения расписаний для одиоприборных систем, входящих в состав систем реального времени // Методы и средства обработки информации: труды Третьей всероссийской научной конференции. - М.: Издательский отдел факультета ВМК МГУ им. М.В. Ломоносова, 2009. - с. 245-258.

26. Косгпенко В. А.. Гурьянов Е. С. Алгоритм построения расписаний обменов по шине с централизованным управлением и исследование его эффективности / / Программирование. - 2005. - № 6. с. 340-346.

27. Кучерявый А. А. Бортовые информационные системы: Курс лекций/ А. А. Кучерявый; под. ред. В. А. Мишина и Г. И. Клюева. - 2-е изд., перераб. и доп. - Ульяновск: УлГТУ, 2004. - 504 е.: ил.

28. Павлов A.M. Принципы организации бортовых вычислительных систем перспективных летательных аппаратов // Мир компьютерной автоматизации. № 4, 2001.

29. Пападимитриу X.. Стайглиц К. Комбинаторная оптимизация. Алгоритмы и сложность. - М.: Мир, 1984. - 512 с.

30. Растругин Л. А. Статистические методы поиска. - М.: Наука, 1968.

31. Рутковская Д.. Пилинъский М., Рутковский Л. Нейронные сети, генетические алгоритмы и нечеткие системы: Пер. с польск. И. Д. Рудинского. - М.: Горячая линия

- Телеком, 2006. - 452 с.

32. Севастьянов Б. А. Курс теории вероятностей и математической статистики. - М.: Наука. Главная редакция физико-математической литературы, 1982. - 256 с.

33. Сухарев А. Г., Тимохов A.B., Федоров В. В. Курс методов оптимизации. - М.: ФИЗ-М AT Л PIT, 2005. - 368 с.

34. Та,наев В. С.. Шкурба В. В. Введение в теорию расписаний. - М.: Наука. - 1975 г.

- 256 с.

35. Трекин А. Г. Структурный синтез вычислительной системы с помощью генетических алгоритмов : дис. ...канд. физ.-мат. наук : 05.13.11 /' МГУ им. М. В. Ломоносова. -М., 2002. - 111 с.

36. Штовба С. Д. Муравьиные алгоритмы // Exponenta Pro. Математика в приложениях, 2003. № 4, с. 70-75.

37. Юхта П. В. Планирование вычислительного процесса в навигационных комплексах : дис. ... канд. техн. наук : 05.13.11 / [Место защиты: СПб. гос. ун-т информац. технологий, механики и оптики]. - СПб. 2010. - 149 с.

38. Abbott і?.. Garcia-Molma H. Scheduling Real-Time Transactions: A performance evaluation // ACM Transactions on Database System, vol. 17, no. 3, 1992. pp. 513-560.

39. Abdoun O.. Aboachabaka J., Tajam C. Analyzing the Performance of Mutation Operators to Solve the Travelling Salesman Problem // International Journal of Emerging Sciences. 2012. vol. 2, No. 1. - pp. 61-77.

40. Balashov V. V., Kostenko V.A., Smehansky R.L. et, al. A Tool System for Automatic Scheduling of Data Exchange in Real-Time Distributed Embedded Systems // Proc. 7th IEEE International Symposium on Computer Networks (ISCN'06), 2006, pp. 179-184.

41. Bierwirth C. et a,I. Genetic Algorithm based Scheduling in a Dynamic Manufacturing Environment //' Proceedings of the IEEE Conf. on Evolutionary Computation. Perth. IEEE Press. 1995. pp.439-443.

42. Blum C.. Sampels M. Ant Colony Optimization for FOP Shop Scheduling: A case study on different pheromone representation // In Proceedings of the 2002 Congress on Evolutionary Computations. Honolulu, vol. 2. 2002. pp. 1558-1563.

43. Butazzo G. C. Rate Monotonie vs. EDF: Judgment Day // Real-Time Systems, no. 29. 2005. pp. 5-26.

44. Chetto H.. Chetto M. Some Results of the Earliest Deadline Scheduling Algorithm // IEEE Transactions on Software Engineering, vol. 15, no. 10. October 1989. pp. 1261-1269.

45. Clausen J. Branch and Bound Algorithms - Principles and Examples / / Parallel Computing in Optimization, 1997, pp. 239-267.

46. Corne D.. Fang H.-L., Melhsh C. Solving the Modular Exam Scheduling Problem with Genetic Algorithms // In Proceedings of the Sixth International Conference on Industrial and Engineering Aplications of Artificial Intelligence and Expert Systems. Gordon and Breach Science Publishers. 1993, pp. 370-373.

47. Davis L. Job-shop Scheduling with Genetic Algorithms // Proceedings of an International Conference on Genetic Algorithms and Their Applications, 1985. pp. 136-140.

48. Dams L. Order-Based Genetic Algorithms and the Graph Coloring Problem // Handbook of Genetic Algorithms. Van Nostrand Reinhold, 1991, pp. 72-90.

49. Dertonzos M. L.. Mok A. K. Multiprocessor on-line Scheduling of Hard-Real-Time Tasks // IEEE Trans, on Software Engineering, vol. 15, no. 12, 1989, pp. 1497-1506.

50. Dorigo M. Optimization. Learning and Natural Algorithms // PhD Thesis. Dipartiniento di Elettronica. Politechnico Di Milano. Milano, 1992.

51. Dongo M., Birattan M.. Stutzle T. Ant Colony Optimization: Artificial Ants as a Computational Intelligence Technique // IEEE Computational Intelligence Magazine, Singapore, vol. 1. no. 4, 2006, pp. 28-39.

52. Fang H.-L.. Ross P.. Come D. A. Promising genetic Algorithm Approach to JobShop Scheduling. Rescheduling, and OpcnShop Scheduling Problems /, Proceedings of the Fifth International Conference on Genetic Algorithms. S. Forrest (ed.). San Mateo: Morgan Kaufmann. 1993, pp. 375-382.

53. Francis J Vasko et al. Adapting Braneh-and-Bouncl for Real-World Scheduling Problems /,/ The Journal of the Operational Research Society, vol. 44, no. 5, May 1993. pp. 483-490.

54. Glass M. Buses and Networks for Contemporary Avionics: SAE Technical Paper 2007-013801 // DDC. 2007.

55. Goldberg D.E.. Deb K. A comparative analysis of selection schemes used in genetic algorithms // Foundations of Genetic Algorithms. 1991. P. 69-93.

56 Goldberg D. E.. Lingle R. Alleles, loci, and the traveling salesman problem // In Proceedings of the International Conference on Gcnetic Algorithms and Their Applications. 1985, pp. 154-159.

57. Gwaltney D. A.. Briscoe. J. M. Comparison of Communication Architectures for Spacecraft Modular Avionics Systems // NASA-TM. 2006.

58. Haritsa J. R., Livny M.. Carey M. J. Earliest Deadline Scheduling for Real-Time Database Systems // Proceedings of the IEEE Real-Time Systems Symposium. 1991, pp. 232-242.

59. Hegarty M. Avionics Networking Technology //' New York: Data Device Corporation. November, 2005.

60. Hendricks S. P. Exploration of Fibre Channel as an Avionics Interconnect for the 21st Century Military Aircraft - Storming Media, 2000.

61. Holland J. H. Adaptation in Natural and Artificial Systems. - University of Michigan Press. 1975.

62. Hoy field J. J. Neural Networks and Physical Systems with Emergent Collective Computational Abilities / / Proceedings of National Academy of Sciences, vol. 79. no. 8, April 1982. pp. 2554-2558.

63. Inyo Rechenbery Evolutionsstrategie - Optimierung technischer Svsteme nach Prinzipien der biologischen Evolution (PhD thesis. 1971). - Reprinted by Fromman-Holzboog. 1973.

64. Kirkpatrtck S.. Gelatt C. D., Vecchi, M. P. Optimization by Simulated Annealing // Science, vol. 220, no. 4598. 1983. pp. 671-680.

65. Koza, J. R. Genetic Programming: Oil the Programming of Computers by Means of Natural Selection / / MIT Press, 1992.

66. Land A. H., Doty A. G. An automatic method of solving discrete programming problems // Econometrics, vol. 28. no. 3. 1960, pp. 497-520.

67. Liu C.. Layland J. Scheduling Algorithms for Multiprogramming in a Hard Real-Time Environment // Journal of the ACM. vol. 20. No. 1. 1973. pp. 46-61.

68. Mahdavi M. et al. A Branch-and-Bound Algorithm for Single-Machine Scheduling with Batch Delivery and Job Release Times // Comput. Oper. Res., vol. 35. no. 4. April 2008. pp. 1099-1111.

69. McCulloch IV., Pitts IV. A Logical Calculus of the Ideas Immanent in Nervous Activity 11 Bulletin of Mathematical Biophysics, vol. 5. 1943. pp. 115-133.

70. Merkie D.. Middendorf M., Schrneck H. Ant colony optimization for resource-constrained project scheduling // IEEE Transactions on Evolutionary Computation, vol. 6. no. 4. 2002. pp. 333-346.

71. Michalewicz Z. Genetic Algorithms — Data Structures = Evolution Programs. - Springer-Vcrlag. 1992.

72. Moir I.. Seabridye A., Jvk.es M. Military avionics systems // John Wiley & Sons, 2006.

73. Mok A. K. Fundamental design problems of distributed systems for the hard-real-time environment: Ph.D. thesis / Massachusetts Institute of Technology. - Cambridge. MA. USA. 1983. - 186 p.

74. Ohuer I M.. Smith D. J.. Holland. J. R. C. A study of permutation crossover operators on the traveling salesman problem // In Proceedings of the second international conference, on genetic algorithms (ICGA'87). 1987, pp. 224-230.

75. Rahman M. M., Chowdhury M. Examining Branch and Bound Strategy on Multiprocessor Task Scheduling / / In Proc. International Conference 011 Computer and Information Technology. Dhaka. Bangladesh, 2009, pp. 162-167.

76. Ritchie G. Static Multi-processor Scheduling with Ant Colony Optimization and Local Search: Master's Thesis. - University of Edinburgh, Edinburgh, 2003.

77. Spall J. C. Introduction to Stochastic Search and Optimization: Estimation, Simulation, and Control. - Wilev-Interscience, Hoboken, 2003. - 618 p.

78. Starkweather T. et al. A Comparison of Genetic Sequencing Operators // Proceedings of Fourth IGCA. - 1991. - pp. 69-76.

79. Valenzuela Christine L. A Study of Permutation Operators for Minimum Span Frequency Assignment Using an Order Based Representation. - Journal of Heuristics, Kluwer Academic Publishers, vol. 7, no. 1. 2001, pp. 5-21.

80. Whitley D. The GENITOR algorithm and selection pressure: why rank-based allocation of reproductive trials is best /1 Proceedings of the third international conference on Genetic algorithms. San' Francisco, CA. USA, 1989, pp. 116-121.

81. Wong C. et al. Requirements for Static Task Scheduling in Real Time Embedded Systems // Proceedings of the 3rd Workshop on System Design Automation. 2000.