Условия существования непрерывных расписаний

2
Содержание
Введение 6
ГЛАВА 1. Построение и жесткое уплотнение расписания 22
§1.1. Двухстадийиое расслоение 22
1.1.1. Определение двухстадийного расслоения............ 22
1.1.2. Выровненные разбиения............................ 24
1.1.3. Доказательство теоремы о двухстадийном расслоении 31
1.1.4. Вычислительные аспекты........................... 32
§1.2. КР-полнота задачи о непрерывном расписании 36
1.2.1. Примеры и применения............................. 36
1.2.2. ЫР-полнота задачи о непрерывном расписании .... 38
1.2.3. Полиномиальная сводимость трех задач............. 43
1.2.4. К'Р-полнота задачи уплотнения (0,1)-матрицы .... 47
1.2.5. Приложение к задаче передачи сообщений........... 50
§ 1.3. Эвристический алгоритм уплотнения 51
1.3.1. Сдвиги по полупустым циклам. Гипотеза............ 51
1.3.2. Жадный алгоритм решения задачи уплотнения ... 53
§ 1.4. Перечисление расписаний 54
1.4.1. Расписание с разделяемым доступом................ 54
1.4.2. Построение двоичного дерева покрытий............. 55
1.4.3. Завершение построения двоичного дерева........... 59
1.4.4. Помечивание вершин, вывод рекуррентных формул . 59
1.4.5. Организация вычислений........................... 61
Глава 2. Разбивающая реберная раскраска 63
§ 2.1. Непрерывная и разбивающая раскраски 63
2.1.1. Непрерывное расписание и разбивающая раскраска . 63
3
2.1.2. Расписание длительности 4 для нагруженного семейства 2-предписаний...................................... 65
2.1.3. Разбивающая раскраска (2р,р)-графа............... 67
§ 2.2. Планарность и раскрашиваемость 68
2.2.1. Неплаиарность простого (6,3)-графа............... 68
2.2.2. Нераскрашиваемый простой (6,3)-граф.............. 70
§ 2.3. Применение динамического программирования 74
2.3.1. Примеры р-предписаний............................ 74
2.3.2. Сведения об полноте.............................. 77
2.3.3. Решение методом динамического программирования . 78
ГЛАВА 3. Нагруженные непрерывные расписания малой длительности 81
§3.1. Расписание длительности 3 81
3.1.1. Формулировка задачи составления учебного расписания 81
3.1.2. Отсутствие временных ограничений................. 82
§ 3.2. Расписание длительности 4 83
3.2.1. Примеры уплотнимых и неуплотнимых расписаний . 84
3.2.2. Теорема о дуэте.................................. 85
3.2.3. Решение за полиномиальное время.................. 90
§ 3.3. Расписания длительности 5 без 1-предписаний 94
3.3.1. Построение сети ................................. 94
3.3.2. Теорема об условиях уплотнения................... 96
Глава 4. Нагруженные непрерывные расписания для предписаний с взаимно-простыми длинами /с, т — к или т 97
§4.1. Нагруженные расписания при к < 2 97
4.1.1. Допустимый поток в сети АГ1...................... 97
4.1.2. Уточнения и замечания. Случай к = 2, т ф 0 (шос! 2) 99
§ 4.2. Трудности уплотнения для предписаний длины к) га — к или т 101
4.2.1. Каркас и пристройка расписания...................101
4.2.2. Разбиваемая пристройка...........................104
4.2.3. Проблема выбора допустимого потока...............106
4
ГЛАВА 5. Методы факторизации и бездефектных потоков 109
§5.1. Нагруженные расписания для предписаний длины 2,
771 — 2, т 109
5.1.1. Комбинаторная форма теоремы Петерсена о факторизации ............................................... 109
5.1.2. Модификация теоремы о факторизации графа . . . . 110
§ 5.2. Условия уплотнения 112
5.2.1. Структура непрерывного расписания для предписаний длины 2,т — 2 и т.................................. 112
5.2.2. Скелеты расписания и ассоциированного графа ... 113
§ 5.3. Бездефектный поток 116
5.3.1. Сеть с гомологичными парами дуг................. 116
5.3.2. Теорема о бездефектном потоке................... 117
5.3.3. Вычисление бездефектного потока................. 118
ГЛАВА 6. Расписание для семейства 2-предписаний 121
§6.1. Разделяющая факторизация 122
6.1.1. Непрерывное расписание для нагруженного семейства
1- и 2-предписапий...............................122
6.1.2. Факторизация, разделяющая два смежных ребра . . 124
6.1.3. Условия непрерывного размещения 1- и 2-прсдписаний 126
6.1.4. Факторизация, разделяющая две пары смежных рёбер 129
§ 6.2. Условия существования компромиссного разбиения для частично-4-рсгуляриого графа 135
6.2.1. Пограничные условия............................. 135
6.2.2. Компромиссное разбиение для частично-4-регулярного графа......................................135
6.2.3. Применение к построению расписания..............139
§ 6.3. Непрерывные расписания длительности 5 для 2-предписаиий. Вопросы существования 141
6.3.1. Преобразования размещений с пресыщенными столбцами .................................................. 141
6.3.2. Непрерывные расписания для 2-предписапий........ 146
5
§ 6.4. Непрерывные расписания нечетной длительности для 2-предписаний 153
6.4.1. Односторонние расписания....................... 153
6.4.2. Рёберная р-раскраска двудольного представления . . 155
6.4.3. Характеризация непрерывных расписаний .............163
6.4.4. Проверка условий. Задача вычисления плотности графа166
Заключение 168
Литература
173
6
Введение
ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ
Актуальность темы. В диссертации исследуется задача о расписании обслуживания без простоев приборов: сложностной статус, условия существования, эффективные алгоритмы.
Пусть множество N = {1,..., п} требований (деталей, учебных групп, заданий и т.п.) обслуживается в системе Ь= {1,...,/} приборов (станков, преподавателей, процессоров и т.п.). Исходные данные к расписанию обслуживания: для каждого прибора г Е Ь задано “предписание” щ (неупорядоченный набор, мультимножество) с элементами из множества М, над каждым требованием из а;* прибор г должен выполнить операцию единичной длительности; условия частичного предшествования отсутствуют, в любой момент времени каждое требование обслуживается не более чем одним прибором, и каждый прибор обслуживает не более одного требования. Обслуживание без простоев «активных» (приборов и др.) и «пассивных» компонентов (требований и др.) будем называть обслуживанием без «прерываний» и «задержек» соответственно.
Обозначим: П = {од,..., сц/}, г ер— коэффициент (ко-
личество вхождений) элемента jEN в о;2, гер^ = ^ гер^р,
т(П) = тах(гедо7‘). Всюду в дальнейшем предполагается, что наиболь-
шее число операций, предписанных отдельным приборам, не превышает наибольшее число операций, предписанных выполнить над отдельными требованиями (вертикальные скобки «| |» применены, как и в монографии |38|. и для обозначения мощности, что не приводит к путанице со стандартным применением для обозначения абсолютной величины числа):
|о;г| ^ га(£2), Уг е Ь\
для такого семейства ^ расписание длительности га(П) существует всегда. Если
герц 1 = • • • = герпп,
7
то расписание (и семейство Q) будем называть нагруженным. Процесс преобразования расписания к непрерывному расписанию, т.е. к расписанию без прерываний, будем называть уплотнением или жестким уплотнением; там, где это не вызывает разночтений, уплотнением удобно называть и само непрерывное расписание.
Обычно задача теории расписаний формулируется как задача построения оптимального по быстродействию расписания, удовлетворяющего тем или иным условиям: директивный срок, время поступления, разрешение или запрет прерываний в процессе обслуживания каждым прибором каждого требования, запрет задержек в обслуживании каждого требования и т.п. Направление нашего исследования отражено в формулировке следующей, центральной для диссертации, задачи.
Задача о непрерывном расписании: существует ли для семейства предписаний П непрерывное расписание длительности т(Г2) ?
Объектом изучения диссертации являются комбинаторные задачи и задачи теории расписаний, предметом изучения — условия существования и алгоритмы жесткого уплотнения расписания. Основным предметом изучения в диссертации являются различные задачи раскраски множества рёбер графов, ассоциированных с заданным семейством предписаний к расписанию. Это новый, введенный автором класс, включающий задачи различных типов рёберной раскраски.
Модель ассоциированных графов оказывается эффективной при исследовании сложностного статуса задачи о непрерывном расписании, формулировке условий его существования и разработке алгоритмов построения расписания, удовлетворяющего заданным условиям. С её помощью можно выразить разнообразные ограничения на предписания семейства входных данных, структуру и длительность расписания. При этом изменяются лишь структура ассоциированных графов и требования к рёберной раскраске, сама же задача остается в границах реберной раскраски ассоциированных графов.
Задачи жесткого уплотнения находят применение не только в задачах о расписаниях, но и в задачах сжатия информации (результаты Booth К. S., Lueker G.S., Fulkerson D.R., Gross О. Л. о матрице со свойством связности) и в задачах оптимизации передачи сообщений по многоканальной сети.
Они тесно связаны также с направлением интервальной раскраски графов, первоначально введенным в работе Л. С. Асратяна и Р. Р. Камаляна [1]. Наиболее важные результаты в данном направлении получили А. С. Асратян, Р. Р. Камалян, С. В. Севастьянов, В. Г. Визинг, В. А. Пяткин.
8
В разряд задач жесткого уплотнения попадают и некоторые варианты задач инциденторной раскраски — одного из новейших направлений теории графов, введенного в работе В. А. Пяткина [35]. Важнейшие результаты в данном направлении получили В. А. Пяткин и В. Г. Визинг.
Задачи жесткого уплотнения выступают катализаторами достижений в области теории графов. Так, задача о непрерывном расписании длительности тп(П) для семейства £2 двухэлементных предписаний эквивалентна задаче о минимальном количестве цветов при жесткой инциденторной раскраске [27). Её исследование, в частности, инициировало новый подход (отличный, например, от принятого в [12]) к вычислению наибольшей плотности подграфа, что, в свою очередь, находит применение в изучении рейтинга сайтов и социальных сетей. Исследование жесткого уплотнения для предписаний мощности 2, га(П) — 2 или т(£2) привело к обобщению классического результата [21] о разбиении регулярного графа четной степени на 2-факторы, а также к выявлению полиномиально разрешимой подзадачи известной ЫР-полной задачи о потоке в сети с гомологичными дугами [37]. Из результата об ИР-полноте задачи о непрерывном расписании вытекает ИР-полнота одного из вариантов задачи об интервальной раскраске. Результаты по жесткому уплотнению тем самым помогают решить некоторые задачи теории графов.
Задачи жесткого уплотнения и эквивалентные задачи раскраски ассоциированных графов составляют новое направление в комбинаторных задачах на графах и задачах теории расписаний.
Обзор результатов по теме диссертации и место результатов автора среди них. Семейство П = { щ \ г € Ь} суть гиперграф с множеством вершин /V, в каждом «ребре» щ которого вершина из N может присутствовать несколько раз. Для наглядности будем применять двудольное представление гиперграфа, для чего соотнесем семейству П двудольный ассоциированный граф б? = (X, Уу Е): X = {х\у..., хп}, У — {ш, • • • > 2//}, В котором количество ребер, соединяющих вершины € X И У{ € У, равно гер^. Отождествляя номер единицы времени обработки требования прибором т/х и номер цвета ребра (гполучим задачу о рёберной раскраске графа С = (ХуУуЕ)у эквивалентную задаче о расписании для семейства Г2.
Правильной рёберной раскраской графа (2 цветами 1,2,3,... называется отображение /: Е(0) —» {1,2,3,...}, такое, что /(е\) ф /(ег) для каждой пары смежных рёбер е\ и е<2. Если для каждой вершины графа цвета инцидентных ребер образуют некоторый интервал, правильная рёберная раскраска графа цветами 1,2,3,... называется интервальной.
9
Ассоциированный с П двудольный граф G с интервальной jхіскраской соответствует непрерывному расписанию для Q без задеро/сек в обслуживании каждого требования. Интервальная раскраска цветами из множества {1,2,....t} называется интервальной ^-раскраской, если каждый из цветов этого множества присвоен хотя бы одному ребру. Через A(G) обозначается наибольшая степень вершины графа G. Ассоциированный с Q двудольный граф G с интервальной A {G)-раскраской соответствует непрерывному расписанию для О, длительности т(0,) без задероюек в осблуживапии каоюдого требования.
А. С. Асратян и Р. Р. Камаляп ([1], 1987) получили ряд результатов об интервальной раскраске графа, в частности, показали приложение задачи раскраски двудольного графа к устранению «окон» в школьном расписании. Предположительно, впервые на приложение задачи раскраски двудольного графа к устранению «окон» расписания указано в заметке А. М. Магомедова ([66], 1985).
Не всякий граф обладает интервальной раскраской; например, полный граф /<з не является, очевидно, интервально раскрашиваемым. Двудольный граф G = (X, Y,E), в котором степени всех вершин из X равны а, а степени всех вершин из Y равны ß, будем называть (а, /?)-бирегулярным графом. Понятно, что (а, а)-бирегулярный граф G = (X, У, Е) обладает интервальной раскраской, поскольку множество рёбер Е допускает разбиение на о: совершенных паросочетаний Е\,..., Еа, поэтому для получения интервальной раскраски достаточно присвоить всем рёбрам каждого Ег цвет г. Нетривиальные примеры: интервальной раскраской обладают деревья и полные двудольные графы — результаты H. М. Hansen ([13], 1992) и Р. Р. К ам ал ян ([17], 1990), а также (2, /?)-бирегулярные графы: в случае четного ß — результат H. М. Hansen ([ 13], 1992), в случае нечетного ß — результат D. Hanson, С. О. М. Loten и В. Toft ([14], 1998) и, независимо, A. V. Kostochka ([19], 1995). Если выполнены дополнительные ограничения |^i| = ••• = \ui\ = 2, то при четном т(£1) непрерывное расписание длительности m(Q) существует всегда; при нечетном т(П) необходимые и достаточные условия существования такого расписания найдены Магомедовым А. М. ((58|,2010).
А. С. Асратян и Р. Р. Камалян ([2], 1994) доказали, что: 1) каждый ин-тервально раскрашиваемый граф G обладает правильной рёберной A(G)-раскраской; 2) задача о существовании интервальной раскраски регулярного графа является NP-полной. В работе Р. Р. Камаляна ([17], 1990) показано, что полный граф Ка,ь интервально ^-раскрашиваем, если (и только
10
если)
а + b — НОД(а,6) ^t^a + 6—1.
В статье ([16], 1995) Т. Jensen и В. Toft сформулировали утверждение, что любой бирегуляриый граф обладает интервальной раскраской. D. Hanson и С. О. М. Loten ([15), 1996) доказали, что для интервальной раскраски (а. Ь)-бирегулярного графа потребуется по меньшей мере а+Ь—НОД(а, Ь) цветов. Так, для интервальной раскраски (3,4)-бирегулярного графа потребуется не менее б цветов; вопрос существования интервальной б-раскраски для любого (3,4)-регуляриого графа до сих пор остается открытым. Для (3,4)-бирегулярного графа G А. В.Пяткин ([22], 2004) доказал, что: 1) задача о существовании кубического подграфа, содержащего все вершины, степени которых в G равны 4, NP-полиа; 2) если такой подграф существует, то граф G — интервальио б-раскраїпинаем. Опираясь на первый из упомянутых результатов, А. С. Асратян и С. Л. Casselgren доказали ([3], 2008) NP-полноту задачи о существовании интервальной б-раскраски для (3,6)-бирегулярного графа. В статье А. М. Магомедова ([85], 1991) обсуждается вопрос о роли кратных рёбер в качестве препятствий для интервальной 6-раскрашиваемости (3, б)-бирегулярного графа и построен пример простого (без кратных рёбер) (3,6)-бирегулярного графа, не допускающего интервальной б-раскраски.
Ассоциированный с семейством Q двудольный граф G = (X, У, Е) будем называть (Ajj, ^ к^)-графом, а семейство О. — соответственно (Асі, ^ А^)-семейством, если
dGXj = kl Vxj Є Х\ (ІсУі < к2 Ууі Є У. (0.1)
В статье А. М. Магомедова ([86), 1991) доказано, что задача о непрерывном расписании для (4, < 4)-семейства разрешима за полиномиальное время.
Отметим, что приведенное в [86] доказательство без существенных изменений переносится и на “близкое” утверждение о разрешимости задачи интервальной A (G)-раскраски двудольного графа G, А (С) = 4, за полиномиальное время. Это утверждение было сформулировано и доказано K.Giaro в ([11], 1997), где получен и существенно более сильный результат об NP-полноте соответствующей задачи при A(G) = 5. В заметке А. М. Магомедова ([66], 1985) рассмотрены необходимые условия раскраски для (5, ^ 5)-графа.
NP-полноту задачи об интервальной раскраске двудольного графа в общем случае доказал С. В. Севастьянов ([39], 1990). ChoY. и Salmi S. доказали ([б], 1981) NP-полноту задачи о непрерывном расписании при дополнительном условии: если начато обслуживание требования некоторым
11
прибором, то до завершения этого обслуживания (возможно, с задержками), другой прибор не может обслуживать данное требование. Доказательство NP-полноты задачи о непрерывном расписании в формулировке, несколько отличной от нашей, получили А. В. Струсевич и Е. Р. Ерошина ([40], 1989). Видоизменением идеи этих авторов А. М. Магомедов показал, что задача о непрерывном расписании является NP-полной даже при дополнительных ограничениях на мощности предписаний ([53], 2009).
Пусть расписание для семейства Q задана матрицей М размеров I х т с элементами из множества {0} U N: если М*,* = J, то при j є N прибор г обслуживает требование у в момент времени /с, при j = 0 прибор г в момент времени к не обслуживает никакого требования. Элементы множества N всюду в дальнейшем будем называть буквенными элементами {или, коротко: буквами).
Пусть все буквенные элементы матрицы М заменены на единицы и требуется проверить, можно ли, с сохранением количеств нулей и единиц в каждой линии (столбце или строке), преобразовать полученную матрицу к такому виду, где единицы в каждой строке располагаются рядом, в подряд идущих ячейках. Из результата Fulkerson D.R., Gross O.A. ([10], 1965) вытекает, что задача разрешима за полиномиальное время, если в таком преобразовании допускаются лишь операции перестановки столбцов. А. М. Магомедов показал (гл. 1), что при отсутствии ограничений на разрешённые операции задача становится NP-полной.
Если |cji| = • • • = |а;/| = 2, то для каждого щ = (іі,2г) Є Г2 заменим в двудольном ассоциированном графе конструкцию из рёбер (яХ1,у*), (х^уі) и вершины Уі одним новым ребром {хіхіХі2). Полученный граф G = {X, Е) назовем графом, ассоциированным с Q] «половинки» нового ребра, инцидентные соответственно вершинам хі, и х,-2, называются сопрло/сенными инцидеиторами (под инцидентором понимается упорядоченная пара, состоящая из вершины и инцидентного ей ребра). В докторской диссертации
А. В. Пяткипа ([36], 2009) исследованы разнообразные аспекты задачи ин-циденторной раскраски — определения минимального числа цветов, в которые можно раскрасить все инциденторы графа с соблюдением заданных условий на цвета смежных (примыкающих к одной и той же вершине) и сопряженных инциденторов. Как показал А. В. Гіяткин, модель инцидеитор-ной раскраски эффективна при исследовании задачи передачи сообщений в локальной сети связи [35]—[34] и в задачах теории расписаний. В нашей терминологии один из вопросов, поставленных в статье В. Г. Визинга ([27], 2005) формулируется как вопрос об NP-полноте задачи определения минимального количества цветов, позволяющих раскрасить инциденты неориеи-
12
тированного мультиграфа так, чтобы: а) все смежные шщиденторы имели разные цвета; б) цвета любой мары сопряженных инциденторов различались точно на 1. Задача эквивалентна задаче о существовании непрерывного расписания длительности m(f2) для семейства Q из 2-предписаний.
Связи задачи о непрерывном расписании с “иными” задачами теории расписаний, теории графов, комбинаторики, теории вычислительной сложности, хранения и передачи информации (и даже с задачами сугубо “программистского” характера) столь обширны, что результаты ряда авторов по перечисленным направлениям являются вкладом и в развитие обсуждаемого направления.
Важнейшими для нашего рассмотрения явились результаты следующих исследователей:
• А. А. Сапоженко (идеи известной книги [28] по дискретной математике явились ключевыми для некоторых из рассмотренных в работе задач; кроме того, благодаря советам проф. А. Л. Сапоженко исследованы несколько значимых для целостности работы задач),
• В. К. Леонтьев (работе «Дискретные экстремальные задачи 25» автор обязан первоначальными сведениями о проблеме NP-полиоты),
• S. A. Even, A. Itai, A. Shamir (классическая задача о составлении учебного расписания аккумулирует ряд важных направлений исследования),
• S.Sahni (NP-полнота задачи построения оптимального расписания для трех приборов, когда требование, обслуживание которого начато некоторым прибором, не может обслуживаться другим прибором до завершения его обслуживания данным прибором),
• В. А. Струсевич и Е. Р. Ерошина (NP-полнота аналогичной задачи для не менее двух приборов в предположении, что в процессе обслуживания каждого требования не допускаются задержки),
• С. В. Севастьянов (доказательство NP-полноты задачи об интервальной раскраске графов явилось толчком к выяснению сложностиого статуса ряда задач как теории графов, так и теории расписаний),
• D. R. Fulkerson и О. A. Gross (задача о матрице со свойством связности),
• В. Г. Визинг (вклад данного исследователя в теорию графов общеизвестен; в частности, исследование задачи об инциденторной раскраске имеет важное приложение к задачам о непрерывных расписаниях),
13
• А. В. Пяткин (задачи об инциденторной раскраске, о кубическом подграфе в (4,3)-бирегулярном графе и др.),
• А. С. Асратян и Р. Р. Камалян (интервальная раскраска различных видов двудольных графов),
• А. С. Асратян и C. J. Casselgren (задача о б-интервальной раскраске (6,3)-бирегулярного графа и др.),
• K. Giaro (сложность задач интервальной раскраски двудольного графа G с A(G) = 4 и 5),
• H. М. Hansen, D. Hanson, С. О. М. Loten и В. Toft (утверждение об интервальной раскрашиваомости двудольного (2, /?)-бирегуляриого гра-фа).
Целыо работы является исследование условий существования жесткого уплотнения (и разработка алгоритмов построения непрерывных расписаний) путём анализа структурных свойств различных классов расписаний, позволяющих определить вычислительную сложность задачи и, в случае установления NP-полного характера задачи, выделить подзадачи, разрешимые за полиномиальное время.
Методика исследований. В работе используются как известные методы, так и новые методы, разработанные автором для решения некоторых задач. К числу известных относятся методы теории графов (паро-сочетания в двудольных графах; реберно-вершинные инцидентные паросо-четания; потоки в сетях; разновидности реберной раскраски: правильной, непрерывной, интервальной, инциденторной), комбинаторики (разбиения; эвристические методы; методы динамического программирования), теории сложности вычислений (метод полиномиальной сводимости). Новые методы и подходы: метод построения непрерывного расписания длительности 4 (гл. 3), метод вычисления бездефектного потока и модификация метода 2-факторизации (гл. 5), а также новый подход к вычислению наибольшей плотности подграфа (гл. б).
Научная новизна. Все представленные в диссертации результаты являются новыми. В работе сформулирован класс задач жесткого уплотнения, исследование которого является новым направлением в теории расписаний. Уточнены или решены некоторые актуальные проблемы теории графов.
Практическая и теоретическая ценность. Работа носит теоретический характер. Вместе с тем, полученные результаты могут применяться при составлении и оптимизации расписаний учебных занятий, для
14
компактного храпения данных и оптимизации передачи информации по сети. Разработанная автором компьютерная программа успешно прошла многолетние испытания по составлению расписания учебных занятий для средней школы с реальными исходными данными.
Исходные данные в прикладных задачах с табличным представлением нередко зашумлены, и таблицы, наряду с полезной информацией, могут содержать помехи. Пусть полезная информация представлена элементами таблицы с целыми положительными значениями, а все элементы с несущественной информацией заменены нулями. С точки зрения оптимизации доступа и построчного считывания данных из таблицы предпочтительна концентрация значимой информации строки в непрерывном диапазоне ячеек, если элементы таблицы вытянуты в памяти “по строкам” (как принято в большинстве языков программирования). Мотивацией для компактного размещения значимой информации в строках являются также расходы времени на инициализацию процесса считывания, норой сравнимые с длительностью самого процесса считывания. Набор допустимых преобразований таблиц, приводящих к компактному размещению полезной информации внутри строк, часто ограничивается в приложениях такими преобразованиями, относительно которых свойство бесповторности элементов значимой информации в столбце является инвариантом. Данное условие нередко оказывается равносильным условию сохранения наборов элементов в каждой линии таблицы.
Основными результатами диссертации являются:
1. Формулировка задач жесткого уплотнения и задач рёберной раскраски графов, ассоциированных с семейством предписаний как удобной модели для обсуждения вопросов нахождения необходимых и достаточных условий существования непрерывных расписаний длительности ш(П).
2. Условия существования расписаний, удовлетворяющих заданным ограничениям на количество аудиторий, и алгоритм разбиения исходных данных но “дням недели” и “академическим часам”.
3. Доказательство ИР-иолноты задачи о непрерывном расписании и задачи уплотнения (ОД)-матрицы. Выяснение структуры уплотнения нагруженного расп иса!шя.
4. Условия и алгоритм уплотнения нагруженного расписания длительности 4.
5. Модификация теоремы о 2-факторизации регулярного графа.
6. Теорема о бездефектном потоке и процедура проверки его существования.
7. Условия и алгоритм уплотнения для семейства П предписаний
15
длины 2, т — 2 и т.
8. Доказательство непланарности простого (6,3)-бирегулярного графа. Построение примера простого (б, 3)-бирсгулярного графа, не допускающего такой реберной раскраски в два цвета, где в каждой вершине степени 3 представлен только один цвет, а каждой вершине степени б инцидентны по три ребра каждого из двух цветов.
9. Доказательство разрешимости задачи о непрерывном расписании для семейства П с 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 Всероссийская научная
16
конференция “Методы и средства обработки информации” (МГУ, 2009); Международная научная конференция “Дискретная математика, алгебра и их приложения” (Минск, 2009); International conference “Optimization and applications”(Pctrovac, Montenegro, September 21-25, 2009); XVIII международная школа-семинар “Синтез и сложность управляющих систем” им. академика О. Б. Лупанова (Пенза, 2009); X международная школа-семинар “Дискретная математика и приложения” (МГУ. 2010); XXIII Международная научная конференция “Математические методы в технике и технологиях” (Саратов, 2010).
Диссертация прошла апробацию на следующих семинарах: на семинаре Отдела математики и информатики Дагестанского научного центра РАН 11.02.2010 (руководитель И. И. Шарапудииов); на семинаре Отдела математических проблем распознавания и методов комбинаторного анализа сектора математических методов распознавания и прогнозирования ВЦ РАН 20.04.2010 (руководитель В. К. Леонтьев); на заседаниях семинаров кафедры математической кибернетики факультета ВМиК МГУ 22.05.2009 и 23.04.2010 (руководитель А. А. Сапожсико), на межвузовском семинаре г. Махачкала 23.11.2010 (руководитель А. К. Рамазанов).
Публикации. По теме диссертации автором опубликованы три учебных пособия и 68 статей (включая тезисы и депонированные статьи).
В журналах из списка ВАК опубликованы 12 статей, три компьютерные программы автора зарегистрированы в Федеральной службе по интеллектуальной собственности, патентам и товарным знакам (РОСПАТЕНТ). Две статьи приняты к печати редакциями журналов «Математические заметки» и «Известия Саратовского гос. ун-та».
Под руководством автора по теме диссертации защищены две кандидатские диссертации (А. Рашайда — в 2000 г., А. 3. Якубов — в 2003 г.), одна представлена к защите (М. М. Сиражудинов). Несколько студенческих работ, выполненных под руководством автора, удостоены дипломов региональных, российских и международных конкурсов.
Структура и объем диссертации. Диссертация состоит из введения. шести глав, содержащих в совокупности 19 параграфов, заключения и списка литературы (119 наименований). Полный объем диссертации — 183 страницы.
СОДЕРЖАНИЕ РАБОТЫ
В главе 1 центральное место отведено проблемам NP-иолноты, рассмотрены также вопросы построения, перечисления, интерпретации и приложений расписаний различных типов.