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

• Автор: Балашов, Василий Викторович
• Шифр специальности: 05.13.11
• Научная степень: Кандидатская
• Год защиты: 2010
• Место защиты: Москва
• Количество страниц: 171 с. : ил.

ОГЛАВЛЕНИЕ
Введение.

1 Описание проблемы.

1.1 Организация информационного обмена но каналу с централ изованны м управлением

1.2 Задача обеспечения совместимости требований к расписанию обмена

1.3 Анализ проблемы несовместимости требований к расписанию обмена

2 Модель предметной области и формальная постановка задачи.

2.1 Расписание для одноприборной системы без прерывания работ.

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

2.3 Формальная постановка задачи обеспечения совместимости требований к расписанию Р.

3 Свойства требований к расписанию информационного обмена, допускающих

ослабление
3.1 Формальная модель и свойства требований, допускающих ослабление.
3.2 Задача обеспечения совместимости требований к расписанию, допускающих ослабление
4 Совместимость требований к расписанию информационного обмена.
4.1 Достаточные условия принципиальной несовместимости требований.
4.2 Инвариантность принципиальной совместимости требований относительно максимального числа работ в цепочке.
4.3 Структура области решений задачи .
4.4 Выводы
5 Существующие методы решения задачи Рю
5.1 Характеристика задачи обеспечения совместимости требований
5.2 Исчерпывающий поиск.
5.3 Детерминированный направленный поиск
5.4 Случайный поиск.
5.5 Метод ветвей и границ.
5.6 Динамическое программирование.
5.7 Алгоритмы имитации отжига и генетические алгоритмы
5.8 Жадные алгоритмы
5.9 Выводы
6 Решение задачи обеспечения совместимости требований к расписанию информационного обмена
6.1 Конечная сетка на множестве решений
6.2 Общее описание алгоритма решения задачи Росг.
6.3 Случайный поиск решений с сужением множества поиска
6.4 Поиск по направлению наискорейшего убывания целевой функции
6.5 оследователыюс усиление требований.
6.6 Эвристическое сужение области поиска на основе свойств требования
6.7 Алгоритм обеспечения совместимости требований
7 Экспериментальное исследование разработанного алгоритма.
7.1 Структура методики исследования
7.2 Цели исследования
7.3 Выбор алгоритмов решения задачи для сравнительного исследования
7.4 Выбор алгоритмов построения расписания.
7.5 Формирование исходных данных для экспериментов.
7.6 Методика статистической обработки результатов эксперимент ов.
7.7 Схемы проведения и результаты экспериментов
7.8 Выводы
8 Инструментальные средства обеспечения совместимости требований к расписанию информационного обмена
8.1 Инструментальная система планирования обмена по каналу с централизованным управлением
8.2 Подсистема обеспечения совместимости требований к расписанию обмена
Заключение.
Литература


Отметим, что каждое из этих требований характеризуется числовым значением (гтсо, ггГ и т. Ограничения на расписание обмена, соответствующие перечисленным требованиям, приведены в приложении А. Технологические требования к расписанию, наряду с директивными сроками, определяют набор ограничений на корректность расписания. На рисунке 2 показано, как перечисленные выше требования влияют на расположение цепочки работ относительно подцикла. На этом рисунке также проиллюстрировано требование по максимальному отклонению от периода для двух последовательных работ одного задания (показаны вертикальной штриховкой). Рисунок 2. Индексы в предлагаемых обозначениях происходят от словосочетаний: “minimum chain offset”, “reserved fraction”, “maximum chain contents”, “reserve for shift”, “maximum period error”. Для отдельных заданий, или для групп заданий с одинаковым периодом (и, как правило, одинаковым отправителем) могут быть определены фазовые сдвиги, сужающие диреюнвный интервал, определяемый периодом задания. Фазовые сдвиги также можно отнести к количественным требованиям к расписанию обмена. На рисунке 3 показано, как левый ((р}) и правый (<р2) фазовые сдвиги влияют на директивные интервалы работ задания. Требования по левому и правому фазовым сдвигам, определенные для задания т, будем обозначать ЯфДт) и Яф2(т). Рисунок 3. Если для задания определены фазовые сдвиги, то при учете требования для работ этого задания должен рассматриваться запас времени от конца интервала выполнения до директивного срока завершения работы, рассчитанного с учётом правого фазового сдвига. Требования к расписанию информационного обмена могут быть несовместимыми, что означает невозможность построения конкретным алгоритмом расписания, которое включает все работы из заданного набора работ (является полным) и удовлетворяет всем требованиям (является корректным). Для решения проблемы несовместимости, количественные требования могут быть откорректированы путём изменения их значений в рамках допустимых интервалов, определяемых ограничениями на разрабатываемую ВСРВ. В данной работе будем рассматривать случай, когда задан единственный алгоритм построения расписания, а состав требований к расписанию, состав и длительности работ изменять недопустимо. Предлагаемый в работе подход к решению проблемы несовместимости требований основан на варианте 4. Расширим процедуру построения расписания, введя в неё дополнительный этап корректировки требований к расписанию, который выполняется в случае выявления несовместимости требований. Результатом этого этапа являются новые совместимые требования, отличающиеся от исходных своими значениями (см. Под планированием далее будем понимать процедуру, включающую в себя построение расписания, корректировку требований к расписанию, а также (в зависимости от специфики рассматриваемой системы) некоторые действия по подготовке исходных данных. В работах [6,] при планировании информационного обмена по каналу МКИО к таким действиям относятся группировка информационных слов в сообщения и формирование работ по полученному набору сообщений. Рисунок 4. Корректировка требований к расписанию информационного обмена требует внесения изменений в разрабатываемую ВСРВ. Гак, если сокращается резерв времени в конце подцикла, предусмотренный для повторного выполнения отдельных работ в случае помех на канале, необходимо выполнить доработку ПО ВСРВ для повышения устойчивости к потере данных. Следовательно, изменения значений требований должны быть минимальными. Для количественного выражения суммарной сложности корректировки требований целесообразно для каждого требования ввести «стоимость» изменения его значения, и минимизировать взвешенную сумму3 абсолютных величин изменений значений отдельных требований. Задавая «стоимости» изменения значений требований, разработчик ВСРВ может определять, какие из требований более желательно корректировать, а какие - менее желательно. Возможны и другие способы выражения суммарного изменения значений требований; некоторые из них приведены в заключении.