Введение к работе
Актуальность темы
Задачи составления расписаний возникают в производственных, образовательных, вычислительных процессах, в процессах хранения и передачи информации, а также при организации логистических систем.
Значительная часть задач теории расписаний относится к разряду NP-полных, поэтому особый интерес приобретает проблема выделения и рассмотрения круга задач, имеющих важное теоретическое и практическое значение и допускающих решение за полиномиальное время.
В прикладных областях часто требуется составление таких расписаний, в которых необходимо минимизировать количество переключений для системы приборов, обслуживающих набор исходных предписаний. Интерес к таким задачам обусловлен тем, что затраты временных, энергетических и других ресурсов на старты и остановки приборов нередко сравнимы с затратами на обеспечение их полезной работы. В частности особую остроту проблема уменьшения энергозатрат передающих устройств, приобретает в беспроводных сенсорных сетях.
Расписания, составленные так, что все обслуживающие приборы выполняют весь заданный набор предписаний без простоев, называются непрерывными расписаниями. Построение корректных математических моделей и эффективных алгоритмов составления непрерывных расписаний является весьма актуальной задачей.
В настоящей работе рассматривается задача составления расписания работы p приборов, где общее время выполнения всех предписаний (другими словами, длительность расписания) задано натуральным числом n, что свидетельствует о ее актуальности.
Каждый прибор работает точно две единицы времени и функционирует без простоев с момента включения вплоть до выключения. Для выполнения каждого предписания требуется целое количество единиц времени, которое не превосходит числа n.
Важные результаты по теории расписаний получены следующими авторами: А.С. Асратян, В.Г. Визинг, Р.Р. Камалян, А.М. Магомедов, А.В. Пяткин, С.В. Севастьянов, Ю.Н. Сотсков, В.А. Струсевич, В.С. Танаев, S. Even, D. R. Fulkerson, A. Itai и др.
Цель работы
Целью работы является построение и анализ таких математических моделей исходных данных, которые позволяют найти критерии существования непрерывных расписаний, а также получить алгоритм построения таких расписаний.
Методы исследования
Для достижения поставленной цели в работе использовались как известные методы, так и новые, разработанные автором. К числу известных относятся методы математического моделирования, комбинаторики и теории матриц. Новые методы: метод построения трансверсали, метод построения непрерывного расписания длительности три, метод построения непрерывного расписания из нескольких расписаний длительности три.
Достоверность научных результатов
Достоверность и обоснованность результатов работы обеспечены строгими математическими доказательствами и корректным использованием методов математического моделирования, теории алгоритмов, комбинаторного анализа и теории расписаний.
Научная новизна
В работе получены критерии существования непрерывных расписаний нечетной длительности и разработаны алгоритмы построения таких расписаний.
Доказано, что всякое непрерывное расписание длительности 2k+1 () может быть приведено к такому непрерывному расписанию, у которого в любом заранее выбранном столбце с нечетным номером расположены символы кратности 2k+1 и только они.
На основе матричного представления найден ряд важных свойств расписаний, расширяющих инструментарий построения доказательств и алгоритмов преобразования расписаний к непрерывному виду.
Разработан ряд алгоритмов, приводящих исследуемые в работе расписания к непрерывному виду.
Предложены новые подходы к решению задач построения непрерывных расписаний.
Теоретическая и практическая значимость
Так как большинство задач теории расписаний является NP–полными, особое значение приобретает выделение важных для теории подзадач, разрешимых за полиномиальное время. Как показывают полученные алгоритмы построения непрерывных расписаний, исследуемая в работе задача разрешима за полиномиальное время.
Работа носит теоретический характер. Полученные в ней результаты относятся к области непрерывных расписаний и реберной интервальной раскраски графов. Вместе с тем, разработанные в работе методы могут быть использованы при решении прикладных задач составления и оптимизации расписаний в производственных, образовательных, логистических, вычислительных процессах, а также в процессах хранения и передачи информации.
Апробация работы
Результаты работы были представлены на следующих конференциях и семинарах:
-
50-я Международная научная студенческая конференция «Студент и научно-технический прогресс» (Новосибирск, 2012 г.);
-
XVIII Международная школа-семинар «Синтез и сложность управляющих систем» имени академика О.Б. Лупанова (Пенза, 2009 г.);
-
V Региональная научно-техническая конференция «Информационные и телекоммуникационные системы: информационные технологии в научных и образовательных процессах» (Махачкала, 2009 г.);
-
IV Всероссийская конференция «Проблемы оптимизации и экономические приложения» (Омск, 2009 г.);
-
Всероссийская научно-практическая конференция с международным участием «Информационные технологии в профессиональной деятельности и научной работе» (Йошкар-Ола, 2008 г.).
Публикации
По теме диссертации автором опубликованы 9 печатных работ, в том числе две – в журналах из перечня рекомендованного ВАК.
Структура и объем диссертации
