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

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

.

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

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

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

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

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

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

Важные результаты по теории расписаний получены следующими авторами: A.C. Асратян, В. Г. Визинг, P.P. Камалян, A.M. Магомедов, A.B. Пяткин, C.B. Севастьянов, Ю. Н. Сотсков, В. А. Струсевич, B.C. Танаев, S. Even, D. R. Fulkerson, A. Itai и др.

Цель работы.

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

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

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

Научная новизна.

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

Доказано, что всякое непрерывное расписание длительности 2к+ (кg N) может быть приведено к такому непрерывному расписанию, у которого в любом заранее выбранном столбце с нечетным номером расположены символы кратности 2к+1 и только они.

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

Разработан ряд алгоритмов, приводящих исследуемые в работе расписания к непрерывному виду.

Предложены новые подходы к решению задач построения непрерывных расписаний.

Теоретическая и практическая значимость.

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

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

Основные положения и результаты, выносимые на защиту.

1. Матричное представление исходных данных как удобная модель исследования и составления непрерывных расписаний.

2. Необходимые и достаточные условия существования непрерывных расписаний длительности три, в которых каждый прибор работает точно две единицы времени, основанные на понятии «полной транс-версали».

3. Алгоритм построения полной трансверсали.

4. Метод «¿—разбиения», который наряду с^{-разреженностью} является эффективным инструментом составления и исследования условий существования непрерывных расписаний.

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

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

Достоверность научных результатов.

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

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

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

1. 50-я Международная научная студенческая конференция «Студент и научно-технический прогресс» (Новосибирск, 2012 г.);

2. XVIII Международная школа-семинар «Синтез и сложность управляющих систем» имени академика О. Б. Лупанова (Пенза, 2009 г.);

3. V Региональная научно-техническая конференция «Информационные и телекоммуникационные системы: информационные технологии в научных и образовательных процессах» (Махачкала, 2009 г.);

4. IV Всероссийская конференция «Проблемы оптимизации и экономические приложения» (Омск, 2009 г.);

5. Всероссийская научно-практическая конференция с международным участием «Информационные технологии в профессиональной деятельности и научной работе» (Йошкар-Ола, 2008 г.).

Публикации.

По теме диссертации автором опубликованы 9 печатных работ, в том числе две — в журналах из перечня, рекомендованного ВАК.

Структура и объем диссертации

.

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

Основные результаты и выводы.

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

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

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

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

Третья подзадача состояла в необходимости объединить к (произвольное натуральное число) наборов 2-слов, для каждого из которых существует непрерывное расписание длительности три, в непрерывное расписание длительности 2к+. На этом этапе также были получены как условия, налагаемые на наборы 2-слов, так и алгоритм составления искомого расписания.

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

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

Заключение

.