Исследование математических моделей, критериев существования и алгоритмов построения непрерывных расписаний нечетной длительности

• Автор: Алекберли, Джалал Маратович
• Шифр специальности: 05.13.17
• Научная степень: Кандидатская
• Год защиты: 2013
• Место защиты: Махачкала
• Количество страниц: 96 с. : ил.

Оглавление
Введение
1. Постановка задачи. Определения и обозначения
1.1. Определения и обозначения
1.2. Постановка задачи
2. Непрерывное размещение набора 2-слов врхЗ-матрице
2.1. Необходимое условие существования непрерывного размещения набора 2-слов в рхЗ-матрице
2.2. Достаточные условия существования непрерывного размещения набора 2-слов в рхЗ-матрице
2.3. Критерий существования непрерывного размещения набора 2-слов в рхЗ-матрице
2.4. Алгоритм построения полной трансверсали и
непрерывного размещения
3. Непрерывное размещение набора 2-слов в/?х5-матрице
3.1. Разреженность непрерывного размещения набора 2-слов в рх5-матрице
3.2. Непрерывное размещение набора 2-слов в рх5-матрице
4. Непрерывное размещение набора 2-слов в/?х2£+1-матрице
4.1. Необходимое условие существования непрерывного размещения набора 2-слов в р*2к+ -матрице
4.2. Критерий существования непрерывного размещения набора

2-слов в рх2к+1 -матрице
4.3. Разреженность непрерывного размещения набора 2-слов в рх2к+-матрице
4.4. Алгоритм построения непрерывного размещения набора
2-слов в рх2к+1 -матрице
Заключение
Литература

Введение
Актуальность темы
Задачи составления расписаний возникают в производственных, образовательных, вычислительных процессах, в процессах хранения и передачи информации, а также при организации логистических систем.
Значительная часть задач теории расписаний относится к разряду №-полных [7], поэтому особый интерес приобретает проблема выделения и рассмотрения круга задач, имеющих важное теоретическое и практическое значение и допускающих решение за полиномиальное время.
В прикладных областях часто требуется составление таких расписаний, в которых необходимо минимизировать количество переключений для системы приборов, обслуживающих набор исходных предписаний. Интерес к таким задачам обусловлен тем, что затраты временных, энергетических и других ресурсов на старты и остановки приборов нередко сравнимы с затратами на обеспечение их полезной работы. В частности особую остроту проблема уменьшения энергозатрат передающих устройств, приобретает в беспроводных сенсорных сетях.
Расписания, составленные так, что все обслуживающие приборы выполняют весь заданный набор предписаний без простоев, называются непрерывными расписаниями. Построение корректных математических моделей и эффективных алгоритмов составления непрерывных расписаний является весьма актуальной задачей.
В настоящей работе рассматривается задача составления расписания работы р приборов, где общее время выполнения всех предписаний (другими словами, длительность расписания) задано натуральным числом п, что свидетельствует о ее актуальности.
Каждый прибор работает точно две единицы времени и функционирует без простоев с момента включения вплоть до выключения. Для выполне-

e) f)
Рис. 2.3 Пример построения полной трансверсали (окончание)
Такой символ есть и ему соответствует 2-слово (2:5). Символ у=5 проверяем на соответствие условиям (2.5), (2.6) и (2.7). Так как он уже содержится во множестве А(Т), то он удовлетворяет условию (2.5). Поэтому 2-слово заносим в набор Т(рис. 2.3.d)) и вновь ищем в нижней части второго столбца символ кратности не менее двух. Таких символов больше нет, т.е. множество (2.6) пусто, но множество (2.7) не пусто, т.к. символ Ь—6 трехкратен и не содержится во множестве А(Т). Выбираем любое 2-слово, содержащее этот символ. Пусть это будет - (1:6). Запишем его в виде -(6:1), затем занесем в набор Т (рис.2.3.е)). Теперь множества (2.6) и (2.7) пустые. Таким образом, построение полной трансверсали завершено. Результат запишем в матрице без пустых строк (рис. 2.3.f)).
Теорема 2.3. (Критерий существования непрерывного размещения набора 2-слов Wв (рхЗ)-матрице М, ре N). Для того чтобы существовало непрерывное размещение в (рхЗ)-матрице М (ре N) набора 2-слов W, удовлетворяющего условию (2.1):