Введение к работе
Актуальность темы. Проблема составления расписания возникает в различных областях науки и техники: в работе сетей передачи данных, при распределении процессорного времени между программами, при формировании расписаний учебных занятий, при составлении расписания движения транспорта и во многих других.
Несмотря на многолетние поиски ряда исследователей, для большинства задач теории расписаний не удается найти точные эффективные алгоритмы. На практике, как правило, используют приближенные и эвристические алгоритмы. Объясняется это тем, что большинство задач составления расписаний относится к классу NP-полных задач, для которых не найдены алгоритмы с полиномиальной вычислительной сложностью. Более того, если известная гипотеза P^NP верна, такие алгоритмы не существуют. Поэтому актуальным является рассмотрение подзадач, имеющих важное теоретическое и практическое значение и допускающих решение за полиномиальное время.
В наиболее общей формулировке задача составления расписания состоит в следующем. Заданное множество обслуживающих приборов должно выполнить некоторый фиксированный набор требований. В зависимости от области приложения под парой приборы-требования могут пониматься процессоры-программы, учителя-классы, станки-детали и т.д. Цель заключается в том, чтобы запланировать моменты выполнения требований приборами таким образом, чтобы длина расписания была минимальной.
На практике часто возникает задача составления расписаний для систем, в которых необходимо минимизировать количество стартов-остановок выполнения обслуживающими приборами требований. Интерес к ней обусловлен тем, что затраты ресурсов (временных, энергетических и др.) на данные операции часто сравнимы с затратами на собственно полезную работу устройства.
Расписания, составленные так, что каждый обслуживающий прибор выполняет весь набор своих требований без остановок, называют расписаниями без прерываний. Создание корректных и полных математических моделей и эффективных алгоритмов составления расписаний без прерываний является актуальной задачей.
Диссертационная работа является частью комплексных исследований по проблеме „Теоретические и алгоритмические аспекты современных задач оптимизации расписаний", проводимых на кафедре дискретной математики и информатики Дагестанского государственного университета. Исследования по теме диссертации были поддержаны грантом РФФИ №09-01-96504-р_юг_а.
Целью работы является разработка и исследование математических моделей и методов составления оптимальных расписаний без прерываний,
анализ вычислительной сложности, построение эффективных алгоритмов составления таких расписаний и рассмотрение компьютерных аспектов проблемы. Для достижения поставленной цели решались следующие задачи:
исследование математических моделей составления расписаний без прерываний;
разработка алгоритмов полиномиальной вычислительной сложности для поиска оптимального расписания при различных ограничениях на свойства приборов и требований;
проведение вычислительных экспериментов для сравнения работы предложенных методов в системах с различным ограничениями на назначение требований приборам.
создание комплекса программ, реализующего методы составления расписаний без прерываний для различных областей приложений.
Методы исследования. В диссертационной работе использованы методы математического моделирования, теории вычислительной сложности, теории графов, комбинаторного анализа, теории расписаний.
Научная новизна. На основе анализа математических моделей интервальной раскраски графа, инциденторной раскраски и дефрагментации матриц предложена методика построения математических моделей составления расписаний без прерываний.
При разноплановых ограничениях на исходные данные разработаны новые методы поиска оптимальных расписаний, допускающие полиномиальные оценки вычислительной сложности.
Сформулированы необходимые и достаточные условия составления расписания без прерываний для модельного случая, когда число требований, запланированных каждому прибору на выполнение, - четно, а длина расписания равна шести единицам времени.
Разработан комплекс программ, реализующий алгоритмы составления расписаний без прерываний. Вычислительными экспериментами выявлены численные характеристики предложенных потоковых методов в системах с различным ограничениями на назначение требований приборам.
Разработан комплекс программ для проектирования и анализа беспроводных сенсорных сетей.
Предложен новый подход к решению задач сжатия и передачи информации, использующий модель дефрагментации матриц.
Практическая и теоретическая значимость. Предложенные в работе модели и разработанные на их основе подходы способствуют дальнейшему развитию аналитического аппарата теории расписаний и теории графов.
Задача составления расписаний без прерываний тесно связана с вопросами теории алгоритмов и ее наиболее интенсивно развиваемого раздела - теории вычислительной сложности, тж. в общей формулировке является NP-пол-ной. В этой связи, разработанные в данном диссертационном исследовании алгоритмы полиномиальной сложности могут способствовать исследованию других NP-полных задач.
Предложенные методы составления расписаний могут быть применены при организации и оптимизации работы беспроводных сенсорных (и других) сетей, в которых энергоэффективность и быстродействие относятся к важнейшим характеристикам при передаче информации.
Основные научные результаты, выносимые на защиту:
методика построения математических моделей, основанных на методах интервальной раскраски графов, раскраски инциденторов и дефрагмен-тации матриц, для составления расписаний без прерываний;
методы с полиномиальной вычислительной сложностью, предназначенные для поиска расписаний без прерываний при различных характеристиках исходных данных;
необходимые и достаточные условия составления расписания без прерываний для модельного случая, когда длительность всех требований, запланированных каждому прибору на выполнение, - четна, а длина расписания равна шести единицам времени;
комплекс программ для проведения вычислительных экспериментов по выявлению численными методами характеристик работы предложенных алгоритмов в системах с различными значениями основных параметров;
комплекс программ для проектирования и анализа беспроводных сенсорных сетей.
Достоверность научных результатов. Достоверность и обоснованность результатов работы обеспечивается строгими математическими доказательствами, верификацией алгоритмов, вычислительными экспериментами, а также корректным использованием в проведенных исследованиях хорошо апробированных методов математического моделирования, теории алгоритмов и вычислительной сложности, теории графов, комбинаторного анализа, теории расписаний.
С целью исследования реальных границ применимости теоретических положений, а также для выявления и анализа потенциальных проблем их реализации, разработан комплекс программ; экспериментальные исследования для определения практической эффективности предложенных методов составления расписаний проведены на системах больших размеров.
Апробация работы. Результаты диссертационной работы и материалы исследований представлялись на:
XXIII Международной научной конференции „Математические методы в технике и технологиях - ММТТ-23" (Саратов, 2010 г.);
Всероссийских научно-практических конференциях с международным участием „Информационные технологии в профессиональной деятельности и научной работе" (Йошкар-Ола, 2008 и 2010 гг.);
IV Всероссийской конференции „Проблемы оптимизации и экономические приложения" (Омск, 2009 г.);
X региональной научно-практической конференции „Компьютерные технологии в науке, экономике и образовании" (Махачкала, 2009 г.);
VI Всероссийской открытой научно-практической конференции „Актуальные задачи математического моделирования и информационных технологий" (Сочи, 2010 г.);
научном семинаре отдела математики и информатики Дагестанского научного центра Российской Академии Наук (Махачкала, 08.04.2010);
Публикации. По материалам диссертации опубликованы 11 печатных работ, в том числе три — в ведущих журналах, рекомендованных ВАК РФ. Список работ приведен в конце автореферата.
Личный вклад соискателя. Основные результаты, на которых базируется диссертация, принадлежат соискателю. Все работы, за исключением одной, опубликованы без соавторов. В совместной работе с научным руководителем соискателю принадлежит равное участие в выборе направления исследования, получении и интерпретации результатов, а также разработка алгоритма решения задачи; конфликт интересов отсутствует.
Структура и объем диссертации. Диссертация состоит из введения, четырех глав, заключения и списка литературы. Работа изложена на 105 страницах машинописного текста, включая 16 рисунков, 2 таблицы и библиографию, содержащую 94 названия.
