Введение к работе
Актуальность темы. Задачи теории расписаний, которым посвящена диссертация, возникают в самых различных областях. Это и составление школьных и вузовских расписаний, и распределение деталей по станкам, параллельные компьютерные вычисления, хранение информации и ее обработка и т.п. Прикладное значение исследования таких задач трудно переоценить. Вместе с тем рассматриваемые задачи теории расписаний тесно связаны с классическими задачами о раскраске из теории графов и легко формулируются на языке теории графов. Продвижение в задачах теории расписаний ведет к прогрессу в теории графов и комбинаторике. Большинство задач теории расписаний относится к так называемым NP-полным или трудно решаемым комбинаторным задачам. При этом возникают вопросы доказательства NP-полноты задач, выделения эффективно решаемых случаев, построения эффективных (полиномиальных) алгоритмов и алгоритмов сокращённого перебора с оценками сложности. Все эти аспекты задач теории расписаний в той или иной мере нашли отражение в данной работе. Таким образом, тема диссертация актуальна как в теоретическом, так и в прикладном отношении.
Основное внимание в диссертации уделяется вопросам существования и построения так называемых непрерывных расписаний. Суть задачи о непрерывном расписании заключается в «жёстком уплотнении» матрицы с элементами 0,1,...,п, в каждом столбце которой ненулевые элементы попарно различны, — в преобразовании её к матрице тех же размеров, где:
набор элементов к каждой строке — такой же, что в соответствующей строке исходной матрицы;
в каждом столбце ненулевые элементы попарно различны;
ненулевые элементы в каждой строке размещены в подряд идущих ячейках.
В общем случае задача о непрерывном расписании NP-полна. Исследование каждой частной задачи о непрерывном расписании целесообразно начинать с проверки разрешимости за полиномиальное время, поскольку для задач о расписаниях с реальными исходными данными различие алгоритмов, трудоёмкость которых ограничена полиномом от длины входа задачи, нивелируется в результате повышения быстродействия компьютеров. Из NP-полноты задачи вытекает актуальность поиска успешно проверяемого способа характеризации подзадач, допускающих решение за полиномиальное время.
Объектом изучения диссертации являются комбинаторные задачи и задачи теории расписаний, предметом изучения — условия существования и алгоритмы жёсткого уплотнения расписания. Основным предметом изучения в диссертации являются различные задачи рёберной раскраски графов, «ассоциированных» с семейством предписаний. Модель ассоциированных графов оказывается эффективной для исследования сложностного статуса задачи о непрерывном расписании, формулировки условий его существования и разработки алгоритмов построения расписания, удовлетворяющего заданным условиям. С её помощью можно выразить разнообразные ограничения на предписания семейства входных данных, структуру и длительность расписания. При этом изменяются лишь структура ассоциированных графов и требования к рёберной раскраске, сама же задача остается в границах рёберной раскраски ассоциированных графов.
Результаты, полученные для задач интервальной и инциденторной раскраски графов, находят применение в вопросах жёсткого уплотнения. В свою очередь, исследование задачи о непрерывном расписании способствует развитию некоторых направлений теории графов. Так, например, получены: новый подход к поиску наибольшей плотности подграфа, что, в свою очередь, находит применение в вычислении рейтинга сайтов и социальных сетей; новое доказательство теоремы об NP-полноте задачи о 3-раскраске графа; формулировка полиномиальной подзадачи известной NP-полной потоковой задачи; обобщение знаменитой теоремы Петерсена о разбиении регулярного графа чётной степени на 2-факторы 1> и т.д.
Исходными для исследования явились результаты ряда авторов: S. A. Even, A. Itai, A.Shamir, S. Salmi, В.В. Шкурба, Т. А. Танаев,
B. А. Струсевич, Ю. Н. Сотсков, D. R. Fulkerson, О. A. Gross и др.
Важные результаты по теории расписаний получены также следующими авторами: С.В.Севастьянов, В.А. Перепелица, Э.Х. Гимади, В.М. Котов, В.В.Топорков, А.В.Пяткин, А.С.Асратян, P.P. Камалян,
C. J. Casselgren, K.Giaro, H.M.Hansen, D.Hanson, C.O.M. Loten, В. Toft,
В.В.Сервах, А.А.Лазарев и др.
Задачи жёсткого уплотнения и эквивалентные задачи раскраски ассоциированных графов составляют новое направление в комбинаторных задачах на графах и задачах теории расписаний.
Целью работы является исследование условий существования жёсткого уплотнения и разработка алгоритмов построения непрерывных расписаний путём анализа структурных свойств различных классов расписаний, позволяющих определить статус сложности задачи и, в случае
1Petersen J. Die theorie der regularen graphen // Acta Math. - 1891. - 15. - P. 193-220.
установления свойства NP-полноты, выделение подзадач, допускающих решение за полиномиальное время.
Методика исследований. В работе используются как известные методы, так и новые методы, разработанные автором. К числу известных относятся методы теории графов, комбинаторики, теории алгоритмов. Новые методы и подходы: метод «компьютерной формулировки» рекуррентных соотношений (гл. 1); метод построения непрерывного расписания длительности 4 (гл. 3), метод вычисления бездефектного потока, модификация метода 2-факторизации (гл. 5), а также новый подход к вычислению наибольшей плотности подграфа (гл. 6).
Научная новизна. Все представленные в диссертации результаты являются новыми. В работе сформулирован класс задач жёсткого уплотнения, исследование которого является новым направлением в теории расписаний. Уточнены или решены некоторые актуальные проблемы теории графов.
Практическая и теоретическая ценность. Работа носит теоретический характер. Вместе с тем, полученные результаты могут применяться при составлении и оптимизации расписаний учебных занятий, для компактного хранения данных и оптимизации передачи сообщений по многоканальной сети.
Основными результатами диссертации являются:
Формулировка задач жёсткого уплотнения и задач рёберной раскраски графов, ассоциированных с семейством предписаний Г2, как удобной модели для поиска необходимых и достаточных условий существования непрерывных расписаний длительности m(Q) (где m(Q) — наибольшее количество операций, которое требуется выполнить над требованиями из обслуживаемого множества).
Условия существования расписаний учебных занятий, удовлетворяющих заданным ограничениям на количество аудиторий, и алгоритм разбиения исходных данных по "дням недели" и "академическим часам".
Доказательство NP-полноты задачи о непрерывном расписании и задачи уплотнения (ОД)-матрицы. Структура непрерывного нагруженного расписания.
Условия существования непрерывного нагруженного расписания длительности 4.
Модификация теоремы о 2-факторизации регулярного графа.
Теорема о бездефектном потоке и процедура проверки его существования.
Условия и алгоритм уплотнения для семейства Г2, состоящей из предписаний мощности 2, m(Q) — 2 и m(Q).
Доказательство непланарности простого (6, 3)-графа. Построение примера простого (6,3)-графа, не допускающего рёберной раскраски в два цвета, где в каждой вершине степени 3 представлен только один цвет, а в каждой вершине степени 6 каждый из двух цветов представлен три раза.
Доказательство разрешимости за полиномиальное время задачи о непрерывном расписании для семейства 2-предписаний.
10. Алгоритмы "компьютерного исполнения": уплотнение таблицы
сдвигами по полупустым циклам, жёсткое уплотнение методом динамиче
ского программирования, компьютерная генерация системы рекуррентных
формул для решения задачи о перечислении расписаний с разделяемым до
ступом.
Апробация работы. Результаты работы были представлены на следующих международных и российских (до 1991 г. — всесоюзных) конференциях и семинарах.
Всесоюзная научная конференция по моделированию и оптимизации учебного процесса с использованием ЭВМ (Московский Энергетический Институт, 1985); Всесоюзный семинар "Системное моделирование производства, распределения и потребления" (Воронеж, 1986); Всероссийская научно-методическая конференция "Компьютерные технологии в высшем образовании" (Санкт-Петербург, 1994); Международный симпозиум "Интеллектуальные системы" (МГТУ им. Баумана, Махачкала, 1994); Всероссийская научно-техническая конференция "Современные информационные технологии в управлении" (Махачкала, 2003); Международная конференция "Современные проблемы математики" (Махачкала, 2004); XIV международная конференция "Проблемы теоретической кибернетики" (Пенза, 2005); IX Международный семинар "Дискретная математика и её приложения", посвященный 75-летию со дня рождения академика О.Б.Лупанова (МГУ, 2007); V международная конференция по математическому моделированию, посвященная 75-летию академика В. Н. Монахова (Якутск, 2007); Всероссийская научно-практическая конфереренция "Информационные технологии в профессиональной деятельности и научной работе" (Йошкар-Ола, 2008); XV международная конференция "Проблемы теоретической кибернетики" (Казань, 2008); X Белорусская математическая конференция (Минск, 2008); IV Всероссийская конференция "Проблемы оптимизации и экономические приложения" (Омск, 2009); VIII Международная научная конференция "Дискретные модели в теории управляющих систем" (МГУ, 2009); III Всероссийская научная конференция "Методы и
средства обработки информации" (МГУ, 2009); Международная научная конференция "Дискретная математика, алгебра и их приложения" (Минск, 2009); International conference "Optimization and applications" (Petrovac, Montenegro, 2009); XVIII международная школа-семинар "Синтез и сложность управляющих систем" им. академика О.Б.Лупанова (Пенза, 2009); X международная школа-семинар "Дискретная математика и приложения" (МГУ, 2010); XXIII Международная научная конференция "Математические методы в технике и технологиях" (Саратов, 2010).
Диссертация прошла апробацию на заседаниях семинаров: отдела математики и информатики Дагестанского научного центра РАН 11.02.2010 (руководитель И. И. Шарапудинов); отдела математических проблем распознавания и методов комбинаторного анализа сектора математических методов распознавания и прогнозирования ВЦ РАН 20.04.2010 (руководитель В.К.Леонтьев); кафедры математической кибернетики факультета ВМиК МГУ 22.05.2009 и 23.04.2010 (руководитель А. А. Сапоженко), вузов г.Махачкала 23.11.2010 (руководитель А. К. Рамазанов).
Публикации. По теме диссертации автором опубликованы три учебных пособия и 68 статей (включая тезисы и депонированные статьи).
В журналах из списка ВАК опубликованы 12 статей, три компьютерные программы автора зарегистрированы в Федеральной службе по интеллектуальной собственности, патентам и товарным знакам (РОСПАТЕНТ).
Структура и объем диссертации. Диссертация состоит из введения, шести глав, содержащих в совокупности 19 параграфов, заключения и списка литературы (119 наименований). Полный объем диссертации — 183 страницы.
Благодарности. Выражаю глубокую благодарность
А.А. Сапоженко за постоянное внимание к работе. Считаю своим долгом поблагодарить В.К.Леонтьева, А.А. Вороненко и И.И. Шарапудинова за ценные советы и рекомендации.
