автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.18, диссертация на тему:Теоретико-графовые модели и методы составления расписаний без прерываний

На правах рукописи

ы

Лугуев Тимур Садыкович

Теоретико-графовые модели и методы составления расписаний без прерываний

05.13.18 - Математическое моделирование, численные методы и комплексы программ

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук

Астрахань - 2011

4852322

Работа выполнена на кафедре дискретной математики и информатики ГОУ ВПО «Дагестанский государственный университет»

Научный руководитель: кандидат физико-математических наук, доцент

Магомедов Абдулкарим Магомедович

Официальные оппоненты: доктор физико-математических наук,

профессор

Мусаев Гапиз Мусаевич

Защита диссертации состоится 16 июня 2011 г. в 11 часов на заседании диссертационного совета ДМ 212.009.06 при Астраханском государственном университете по адресу: 414056, г.Астрахань, ул.Татищева,20а.

С диссертацией можно ознакомиться в библиотеке Астраханского государственного университета.

Автореферат разослан 14 мая 2011 г.

Ученый секретарь

диссертационного совета ДМ 212.009.06, кандидат физико-математических наук,

доктор технических наук, профессор Камаев Валерий Анатольевич

Ведущая организация: Учреждение Российской академии наук

Санкт-Петербургский институт информатики и автоматизации РАН, г. Санкт-Петербург

доцент

В.В. Смирнов

Общая характеристика работы

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

Несмотря на многолетние поиски ряда исследователей, для большинства задач теории расписаний не удается найти точные эффективные алгоритмы. На практике, как правило, используют приближенные и эвристические алгоритмы. Объясняется это тем, что большинство задач составления расписаний относится к классу ЫР-полных задач, для которых не найдены алгоритмы с полиномиальной вычислительной сложностью. Более того, если известная гипотеза Р/^ТР верна, такие алгоритмы не существуют. Поэтому актуальным является рассмотрение подзадач, имеющих важное теоретическое и практическое значение и допускающих решение за полиномиальное время.

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

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

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

Диссертационная работа является частью комплексных исследований по проблеме „Теоретические и алгоритмические аспекты современных задач оптимизации расписаний", проводимых на кафедре дискретной математики и информатики Дагестанского государственного университета. Исследования по теме диссертации были поддержаны грантом РФФИ №09-01-96504-р_юг_а.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Основные научные результаты, выносимые на защиту:

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

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

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

4. комплекс программ для проведения вычислительных экспериментов по . выявлению численными методами характеристик работы предложенных алгоритмов в системах с различными значениями основных параметров;

5. комплекс программ для проектирования и анализа беспроводных сенсорных сетей.

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

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

Апробация работы. Результаты диссертационной работы и материалы исследований представлялись на:

1. XXIII Международной научной конференции „Математические методы в технике и технологиях - ММТТ-23" (Саратов, 2010 г.);

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

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

4. X региональной научно-практической конференции „Компьютерные технологии в науке, экономике и образовании" (Махачкала, 2009 г.);

5. VI Всероссийской открытой научно-практической конференции „Актуальные задачи математического моделирования и информационных технологий" (Сочи, 2010 г.);

6. научном семинаре отдела математики и информатики Дагестанского научного центра Российской Академии Наук (Махачкала, 08.04.2010);

Публикации. По материалам диссертации опубликованы 11 печатных работ, в том числе три — в ведущих журналах, рекомендованных ВАК РФ. Список работ приведен в конце автореферата.

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

Структура и объем диссертации. Диссертация состоит из введения, четырех глав, заключения и списка литературы. Работа изложена на 105 страницах машинописного текста, включая 16 рисунков, 2 таблицы и библиографию, содержащую 94 названия.

Содержание работы

Во введении формулируется тема диссертации, обоснована ее актуальность, изложены цель работы, научная новизна, полученные результаты и структура диссертации, сформулированы основные положения, выносимые на защиту.

В первой главе на основе анализа современного состояния области диссертационного исследования обоснована постановка задачи диссертации.

Рассматривается система приборов £, = {1,2,..., /}, обслуживающих множество требований N = {1,2, ...,п}. Длительность обслуживания ¿у прибором г е Ь требования ] е N задана целым неотрицательным числом.

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

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

= "» = тах^у

¿ем

последнее удобно записать в виде системы неравенств: 7* < т Уг £ Ь\ понятно, что т играет роль нижней грани для длительности (длины) расписания.

Задачи, возникающие при указанных условиях, имеют следующие формулировки.

Задача 1. Построить оптимальное по быстродействию расписание. Другими словами, найти матрицу М из I строк и ц столбцов с элементами 0,1,..., п, в которой строка г 6 Ь содержит ровно Ц- элементов, равных € И, ненулевые элементы в каждом столбце различны п ц принимает наименьшее возможное значение.

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

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

Выявлены наиболее перспективные математические модели рассмотрения задачи составления расписании без прерываний: модель раскраски ин-цидепторов, модель интервальной раскраски графа, модель дефрагментации матриц.

Задача 1 ИР-полна. Задача 2 становится ОТ-полной, если ограничить поиск совершенными расписаниями длины то. Модификация задачи 2, когда требуется выяснить существование такого совершенного расписания длины т, где не только выполнение требований каждым из приборов, но и обслуживание каждого требованиями выполняется приборами в последовательные кванты времени, также ОТ-полна; уточним, что такая модификация задачи при то = 3 и т = 4 разрешима за полиномиальное время, но ИР-полна уже при то = 5. Данная модификация задачи 2 является ИР-полной и при т = 6, даже если Тг = ■ ■ ■ = Т/ = 3 и = 6 <ЧЛЯ каждого 3 € N.

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

Во второй главе для исследования задачи составления расписаний без прерываний выбрана модель дефрагментации матриц.

Задача проверки существования совершенного расписания может быть сформулирована в терминах матриц.

Пусть {1,..., т} — множество допустимых для расписания квантов времени, в которые может осуществляться выполнение требований. Расписание может быть задано (I х т)- матрицей М (I строк, т столбцов) с элементами 0,1,..., п, где каждая г-я строка содержит £ц экземпляров числа у 6 Лг, набор ненулевых элементов каждого столбца равен N (такое расписание соответствует задаче, где в каждый допустимый квант времени все требования выполняются). Класс таких матриц, где множество мощностей наборов ненулевых элементов строк равно некоторому множеству О, будем обозначать

Интерпретация. Если = е Ы, то в к-й квант времени г-й прибор выполняет' j-oe требование. Если же М1к = 0, то г-й прибор не выполняет в к-й квант времени никаких требований.

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

Элемент МЦ. матрицы М будем называть дефектом, если

Мг,к = 0, Зки к2 : 1 < Ь < к < к2 < т, ^ 0, ф 0.

Если строка не содержит дефектов, то размещение ненулевых элементов в такой строке будем называть непрерывным; матрицу, в каждой строке которой ненулевые элементы размещены непрерывно — уплотнением. Преобразование матрицы, сохраняющее наборы элементов каждой строки и каждого столбца (но необязательно — порядок следования элементов), назовем консервативным преобразованием, а консервативное преобразование к уплотнению — дефрагментацией.

Через МЩ будем обозначать г-ю строку матрицы М, наборы ненулевых элементов г-й строки и ]-го столбца матрицы М обозначим М[г, *] и М[*,у] соответственно; множество строк матрицы М, в каждой из которых наборы ненулевых элементов содержат точно з элементов, обозначим через М {;')).

В главе рассмотрена задача поиска условий, необходимых и достаточных для дефрагментации матриц класса Р^б}' разработаны эффективные алгоритмы проверки этих условий и построения уплотнения матрицы. С помощью модели дефрагментации матриц сформулированы необходимые и достаточные условия составления расписания без прерываний. Для проверки этих условий построен полиномиальный алгоритм вычисления потока, обла-

дающего специальными свойствами.

« 2 2 2 2 0

1 1 0 0 1 1

0 0 1 3 3

4 0 1 3 0 2

3 4 4 4 1 А

2 3 0 0 0 0

Рис. 1. Матрица класса Г^Сву которая не допускает дефрагыснтации.

Заметим, что не каждая матрица класса -Р^Гс} Д0ПУскает дефрагмен-тацшо. Действительно, рассмотрим матрицу М е ■Р^^б}' изображенную на рис. 1. Если для матрицы М существует уплотнение М', то элементы в третьей позиции каждой из первых пяти строк М' должны быть отличны от пуля. Но это противоречит определению консервативного преобразования, коль скоро третий столбец матрицы М содержит лишь четыре ненулевых элемента. Таким образом, дефрагментация матрицы, изображенной на рис. 1, невозможна.

Будем говорить, что множество N является частичной трансверсалъю семейства наборов {М[г, *],г= 1,...,г}, если N содержит не более одного элемента каждого из этих наборов, и при этом N включает в точности один элемент из каждой строки множества М(4) и М(6).

Две частичные трансверсали N1 и N2 семейства наборов {М[г, *], г = 1,..., I}, будем называть близнецами, если:

1) из каждой строки множества М(4) и М(6) в N1 и Ы2 включаются различные элементы (возможно, с одинаковыми значениями);

2) если один из элементов набора

{М[г, *] : М\г] е М(2)}

входит в N1, то другой элемент набора М[г, *] входит в N2 и наоборот.

Для уплотнения М' матрицы М е ^2°4б} обозначим через А(г) начальную позицию размещения элементов набора М'[г, *] в строке М'\г]\ г € Ь. Доказана следующая лемма.

Лемма 1. Если М'-уплотнение, матрицы М класса Р^щ, то А(г) 6 {2,4,6 г е Ь.

Следствие. Пусть матрица М € Р{'36£6} допускает дефрагментацию и М' - ее уплотнение. Тогда для любого г е Ь

либо М(3 = М[Л = 0, либо М-3 ф О, М[± ф О.

На основе этих результатов доказана Теорема 1.

Теорема 1. Матрица М € -Р^б} допускает дефрагментацию тогда и только тогда, когда обладает близнецами.

Показано, что вопрос существования близнецов сводится к вопросу существования потока специального вида в транспортной сети.

Для проверки существования близнецов построена транспортная сеть Net(M), которая определяется для матрицы М е Р^.б следующим образом. Множество вершин:

5 (источник), X = {хи ...,а:п}, У = {уи ...,уг}, £ = {г2,г4,г6}, Т (сток). Множество дуг:

Е = {(5,*,)} и {(Хз,уг) : з € М[г, *]} и {(уи гк) : МЩ € М(к)} и {(^,Т)};

г&Ь, з к = 2,4,6. Пропускные способности:

Ш (5, я,-) = 2; Ш у,:) = 1; Ш (уи гк) = 2; Ш (гь Т2) = оо; г е Ь, з € И, к = 2,4,6. Нижние потоковые ограничения:

Ьо (51, х,-) = 2; Ьо (х,, уг) = 0; Ьо (уи г2) = 0; Ьо (уи г4) = Ьо (уи г6) = 2, Ьо (г2,Т) = Ьо (24.Т) = Ьо (г6,Т) = 0-i е Ь, j & N.

Схематичное изображение сети Ые^М) приведено на рис. 2.

Рис. 2. Транспортная сеть Net(M). Lo(yuz2) = 0, z4) = Io(j/t, г6) = 2.

Подмножество вершин множества У, смежных вершине г* в сети Net, будем обозначать Y):; к = 2,4, 6.

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

что если допустимый поток в Ие^М) существует, то его величина равна 2п и через каждую вершину множества X и У4 и Уо протекают ровно две единицы потока; при этом через множество У2 протекает поток величины 2(п — |М(4)| — |М(6)|). При этом через произвольно выбранную вершину множества может протекать поток величины 0, 1 или 2. Для построения близнецов нам понадобится такой допустимый поток, что через каждую вершину множества У2 протекают 0 или 2 единицы потока. Допустимый поток / в сети Лгeí(M), обладающий подобным свойством, будем называть бездефектным]; любой другой допустимый поток / — дефектным, а вершины множества Уг, через которые протекает точно одна единица потока. — дефектами потока /. Множество дефектов потока / обозначим О¡.

Легко видеть, что условие «бездефектности» потока / равносильно условию:

/(хр, уг) = 1(хч,уг), Уг, р, <? : ¡/; е У2, (хр< 2/0. 2/0 £ ЛГе£(М).

Имеет место следующая теорема.

Теорема 2. Существование близнецов у матрицы М из класса -Р^Ге} равносильно существованию бездефектного потока в сети Аге£(М).

Пусть подмножество {(амножества дуг сети Ие^М) разбито на два непересекающихся семейства: Ео и Е\\ например, Ео — множество дуг, вдоль которых некоторый поток / равен нулю: Е0 = (/)о, Е\ — множество дуг, вдоль которых поток / равен единице: Е\ = (/)х- Порожденный подграф на множестве дуг вида (xj,yi) сети ТУе^М) обозначим через С?(М).

Пусть Л — некоторый неориентированный путь в графе (?(М), V — внутренняя вершина пути Д; будем говорить, что для вершины V выполняется свойство периодичности (непериодичности), если любые два последовательных ребра пути, инцидентные вершине V, принадлежат разным (одинаковым) множествам Ео и Е\.

Если свойство периодичности выполнено для всех вершин пути Я, отличных от вершин некоторого множества Уо, а для каждой вершины из Уо выполнено свойство непериодичности, то путь Я будем называть Уо-частично-периодическим (или просто частИчпо-периодическим, если множество Уо однозначно определяется из контекста).

Следующая теорема призвана выполнять роль алгоритмического сопровождения Теоремы 2.

Теорема 3 [о бездефектном потоке]. Если в сети ИеЬ(М) существует бездефектный поток, то для любого допустимого потока f в сети Л/е£(М) с£>/^0ыУо = {г: у1 е Уг, /(г/О Ф 1} найдется Уо-чаетично-периодичехкий

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

Алгоритм вычисления бездефектного потока в Net(M) заключается в следующем.

В сети Net(M) ищется допустимый поток. Если его не существует, то алгоритм завершается с отрицательным ответом. Если найденный допустимый поток оказался дефектным, то делаются попытки последовательно в цикле удалять по два дефекта потока. Для этого ищется частично-периодический путь из произвольно выбранного дефекта во множество остальных дефектов потока. На ребрах найденного пути значение потока /(е) заменяется на 1 —/(e). По Теореме 3, если на каком-то шаге цикла частично-периодический путь не удается построить, то бездефектный поток в сети Net(M) отсутствует и алгоритм завершается с отрицательным ответом. Поиск частично-периодических путей выполняется до тех пор, пока поток в сети не станет бездефектным.

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

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

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

Эксперимент проводился на компьютере с процессором AMD Sempron 3000 с 1Гб оперативной памяти под управлением операционной системы Linux (дистрибутив Ubuntu 9.05).

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

1) Для произвольных сетей с заданным коэффициентом разреженности — отношением количества имеющегося количества ребер к максимально возможному количеству.

2) Для двудольных сетей с заданной степенью вершин.

Генерация сетей первого типа осуществлялась следующим образом.

Для каждой пары вершин (г^,^) генерировалось случайное число от 0 до 1. Если полученное число меньше заданной величины коэффициента разреженности, то к множеству дуг добавлялась дуга

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

Таблица 1. Время выполнения алгоритмов для сетей с 3000 вершин, для которых коэффициент разреженности задавался от 0.05 до 0.85

Коэффициент ' Алгоритм Highest-label, FIFO, с Highest-label

разреженно- Диница, с с без эв-

сти ристики пропусков, с

0.05 0.02 0.02 0.02 0.02

0.25 0.02 0.14 0.14 0.2

0.45 0.06 0.29 0.32 0.37

0.65 0.21 0.4 0.43 0.41

0.85 0.12 0.73 0.78 0.68

С использованием первого алгоритма были получены сети, состоящие из 3000 вершин и имеющие различные коэффициенты плотности от 0.05 до 0.85.

На этих сетях выполнялись три алгоритма, основанные на проталкивании предпотока (Highest-label, FIFO и Highest-label без эвристики удаления зазоров), а также алгоритм Диница. Каждый алгоритм выполнялся по 5 раз. Среднее время выполнения для каждого из алгоритмов приведено в таблице 1.

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

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

Можно видеть, насколько важным является использование эвристики удаления зазоров, особенно когда степень сети относительно невелика. Также

Таблица 2. Время выполнения алгоритмов для двудольных сетей с 1000000 вершин и заданными степенями

Степень дву- Алгоритм Highest-label, FIFO, с Highest-label

дольной се- Диница, с с без эв-

ти ристики пропусков, с

5 5.68 6.48 8.72 129.62

30 19.39 3.8 4.26 16.14

55 22.82 4.65 4.94 7.04

80 30.65 5.44 5.71 8.65

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

На основе полученных результатов молено сделать вывод, что эффективность вычислений гораздо меньше определяется выбором алгоритма той или иной „теоретической" сложности, чем это принято считать. Значительный вклад привносят такие параметры, как память и быстродействие (типы данных, динамические и статические массивы, используются ли указатели). Зачастую сравнение алгоритмов корректно лишь для сетей, у которых размеры и пропускные способности дуг находятся в определенных диапазонах.

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

Поиск совершенного расписания в ситуации Tj = • • • = 7) = 2 приобретает важное значение при построении беспроводных сенсорных сетей.

Беспроводные сенсорные сети — это беспроводные сети, состоящие из распределенных в пространстве автономных устройств, в которых используются сенсоры для совместного контроля над такими характеристиками, как температура, уровень звука, вибрация, давление, движение. Они отличаются от обычных беспроводных коммуникационных сетей тем, что частота обмена данными очень мала, а устройства, составляющие эти сети, работают от аккумуляторных батарей, подзарядка которых невозможна, поэтому энергия является очень дорогим ресурсом в датчиках. Существующие протоколы передачи данных для беспроводных сетей, такие как IEEE 802.11, требуют многочисленных повторных пересылок пакетов из-за возможных конфликтных ситуаций. Поскольку при каждой пересылке данных расходуется энергия, такие протоколы неприменимы при использовании датчиков с ограниченным запасом энергии.

Для сохранения энергии в беспроводных сенсорных сетях, обмен информацией между датчиками происходит периодически в определенные промежутки времени. Каждый такой промежуток передачи информации делится на т временных интервалов. Передача информации организована таким образом, что передающий единицу информации датчик отправляет ее за один квант времени т,-, а принимающий датчик осуществляет получение той же информации в следующий квант — тщ + 1. При этом датчики могут принимать либо отправлять лишь одну единицу информации за один квант. Задача составления расписания минимальной длительности, при котором весь обмен информаций между датчиками будет завершен, моделируется мультиграфом в = (У, Е) степени т, в котором каждая вершина ир V соответствует р-му сенсору, а каждое ребро е, = (ур, ь9) 6 Е — единице информации, которую нужно передать от р-го сенсора к <7~му.

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

Показана возможность применения алгоритмов нахождения подграфа максимальной плотности при определении рейтинга сайтов поисковыми системами.

В заключении формулируются основные результаты и выводы диссертационной работы.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ И ВЫВОДЫ

1. Определены наиболее перспективные модели рассмотрения задачи составления расписаний без прерываний: модель раскраски инциденто-ров, модель интервальной раскраски графа, модель дефрагментации матриц.

2. В связи с тем, что задача составления расписаний без прерываний является в общей формулировке ИР-полной, исследованы подзадачи исходной задачи, имеющие важное теоретическое и практическое значение.

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

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

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

5. Установлено, что эффективность вычислений гораздо меньше определяется выбором алгоритма той или иной «теоретической» сложности, чем это принято считать.

6. Указаны приложения разработанных методов:

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

б. установлена связь задачи дефрагментации матрицы с элементами О и 1 с задачей компактного хранения графических образов;

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

ОСНОВНЫЕ ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ

В рецензируемых журналах из списка ВАК

1. ЛугуевТ.С. О сложности построения непрерывного расписания из специального класса // Вестник Тюменского государственного университета. Серия: Физика. Математика и информатика. Химия. 2009. №6. С.142-145.

2. ЛугуевТ.С. Определение продолжительности оптимального расписания передачи сообщений в TDMA сетях // Вопросы современной пауки и практики. Университет им. В.И.Вернадского. 2010. №4-6(29). С. 87-92.

3. ЛугуевТ.С. Реализация алгоритмов проектирования и анализа беспроводных сенсорных сетей // Обозрение прикладной и промышленной математики. 2010. Т.17..№3. С. 436-437.

В других изданиях

4. Лугуев Т.С. К вопросу об оптимизации расписания // Труды молодых ученых ДГУ. Махачкала, ИПЦ ДГУ. 2008. С, 71-72.

5. Магомедов A.M., ЛугуевТ.С. Теоретико-графовый подход к задаче оптимизации расписания // Сборник материалов всероссийской научно-практической конференции с международным участием. Информационные технологии в профессиональной деятельности и научной работе. Йошкар-Ола, 2008. 4.1. С. 200-202.

6. Лугуев Т.С. К вопросу об оптимизации школьного расписания // Тезисы докладов IV Всероссийской конференции «Проблемы оптимизации и экономические приложения», Омск, 2009. С. 230.

7. Лугуев Т.С. Об одном специальном случае задачи составления расписания // Материалы Десятой региональной Научно-практической конференции «Компьютерные технологии в науке, экономике и образовании», СТ+БЕЕЗООЭ. Махачкала, 2010. С. 157-158.

8. Лугуев Т.С. Применение алгоритмов нахождения плотных графов в задачах распознавания лиц // Информационные технологии в профессиональной деятельности и научной работе: сборник материалов Всероссийской научно-практической конференции с международным участием. Йошкар-Ола, 2010. 4.1. С. 124-126.

9. Лугуев Т. С. Теоретико-графовый подход в моделировании обмена данными в беспроводной сенсорной сети // Актуальные задачи математического моделирования и информационных технологий: Материалы VI Всероссийской открытой научно-практической конференции. Сочи, 2010. С. 88-90.

10. Лугуев Т.С. Выявление загруженных участков локальной сети методами теории графов // Актуальные вопросы современной техники и технологии: Сборник докладов Международной научной заочной конференции. -Липецк: Издательский центр «Де-факто», 2010. Т. I. С. 45-47.

11.- Лугуев Т.С. Теоретико-графовые модели передачи сообщений в локальной сети // Математические методы в технике и технологиях - ММТТ-23: сб. трудов XXIII Междунар. Науч. конф.: в 12 т. Саратов, 2010. Т.9. Секция 10. С. 172-173.

Подписано в печать. Бумага офсетная. Печать офсетная. Формат 60*84 1/16. Усл. печ.л - 1,5. Заказ № 1075. Тираж 100 экз.

Отпечатано в типографии "Радуга-Г' г. Махачкала, ул. Коркмасова, 11 "а"

Введение

1 Графовые модели задачи составления расписания без прерываний

1.1 Задача составления расписаний без прерываний.

1.2 Модель интервальной раскраски графа.

1.3 Модель инциденторной раскраски мультиграфа.

2 Составление расписания без прерываний в случае четного числа требований, запланированных на выполнение для каждого прибора

2.1 Задача проверки существования совершенного расписания как задача дефрагментации матрицы.

2.2 Условия дефрагментации матриц.

2.3 Бездефектный поток и его вычисление

2.4 Поиск кратчайших периодических цепей

3 Потоковые алгоритмы, используемые при проверке условий существования расписаний без прерываний

3.1 Алгоритмы иоиска подграфов максимальной плотности

3.2 Потоковые методы, основанные на увеличивающих путях

3.3 Алгоритмы, основанные на проталкивании предпотока

3.4 Случай несбалансированной двудольной сети.

3.5 Результаты численного эксперимента.

4 Некоторые приложения разработанных методов

4.1 Задача оптимизации расписания передачи информации в беспроводных сенсорных сетях.

4.2 Программа проектирования и анализа беспроводных сетей

4.3 Некоторые МР-полные аспекты задач распознавания

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

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

Несмотря на многолетние поиски ряда исследователей, для большинства задач теории расписаний не удается найти точные эффективные алгоритмы. На практике, как правило, используют приближенные и эвристические алгоритмы. Объясняется это тем, что большинство задач составления расписаний относится к классу NP-пoлныx задач, для которых не найдены алгоритмы с полиномиальной вычислительной сложностью. Более того, если известная гипотеза Р^ШР верна, такие алгоритмы не существуют. Поэтому актуальным является рассмотрение подзадач, имеющих важное теоретическое и практическое значение и допускающих решение за полиномиальное время.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Задача составления расписаний без прерываний тесно связана с вопросами теории алгоритмов и ее наиболее интенсивно развиваемого раздела-теории вычислительной сложности, т.к. в общей формулировке является Ш-'-полной. В этой связи, разработанные в данном диссертационном исследовании алгоритмы полиномиальной сложности могут способствовать исследованию других NP-пoлпыx задач.

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

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

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

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

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

4. комплекс программ для проведения вычислительных экспериментов по выявлению численными методами характеристик работы предложенных алгоритмов в системах с различными значен им ми основных параметров;

5. комплекс программ для проектирования и анализа беспроводных сенсорных сетей.

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

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

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

Результаты диссертационной работы и материалы исследований представлялись на: XXIII Международной научной конференции „Математические методы в технике и технологиях - ММТТ-23" (Саратов, 2010 г.);

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

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

4. X региональной научно-практической конференции „Компьютерные технологии в науке, экономике и образовании" (Махачкала, 2009 г.);

5. VI Всероссийской открытой научно-практической конференции „Актуальные задачи математического моделирования и информационных технологий" (Сочи, 2010 г.);

6. научном семинаре отдела математики и информатики Дагестанского научного центра Российской Академии Наук (Махачкала, 08.04.2010);

Публикации

По материалам диссертации опубликовано 11 печатных работ, в том числе три — в ведущих журналах, рекомендованных ВАК РФ. Личный вклад соискателя

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

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

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

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

Определены наиболее перспективные модели рассмотрения задачи составления расписаний без прерываний: модель раскраски инциденторов, модель интервальной раскраски графа, модель дсфрагментащш матриц.

В связи с тем, что задача составления расписаний без прерываний является в общей формулировке NP-пoлнoй, исследованы подзадачи исходной задачи, имеющие важное теоретическое и практическое значение.

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

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

Установлено, что эффективность вычислений гораздо меньше определяется выбором алгоритма той или иной „теоретической" сложности, чем это принято считать. Значительный вклад привносят такие параметры, как память и быстродействие (типы данных, динамические и статические массивы, используются ли указатели). Зачастую сравнение алгоритмов корректно лишь на сетях, размеры которых и пропускные способности дуг находятся в определенных диапазонах. Указаны приложения разработанных методов:

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

- установлена связь задачи дефрагментации матрицы с элементами 0 и 1 с задачей компактного хранения графических образов;

- определена возможность применения алгоритмов нахождения подграфа максимальной плотности при составлении рейтинга сайтов поисковыми системами.

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

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

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

Заключение

1. Ахо А. Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. - М.: Мир, 1979. - 536 с.

2. Алгулиев P.M., Фаталиев Т.Х., Агаев B.C., Алиев Т.С. Сенсорные сети: состояние, решения и перспективы // Телекоммуникации. 2007. - № 4. - С. 27-33.

3. Альратнайда А. Оптимизация мультизадачного графика по временному критерию //Автореферат диссертации на соискание ученой степени кандидата физико-математических наук. Нальчик, 2000. 16 с.

4. Асратян A.C., Камалян P.P. Интервальные раскраски ребер мульти-графа // Прикладная математика. 1987. - № 5. - С. 25-34.

5. Берж К. Теория графов и ее применения.- М.: Наука, 1962. 319 с.

6. Визинг В.Г., Тофт Б. Раскраска инциденторов и вершин неориентированного мультиграфа // Дискрет, анализ и исслед. операций. Сер. 1. -2001. Т. 8, № 3. - С. 3-14.

7. Визинг В.Г. Жесткая раскраска инциденторов в неориентированных мультиграфах // Дискрет, анализ и исслед. операций. Сер. 1. 2005. -Т. 12, №3. - С. 48-53

8. Визинг В. Г. Об оценках инциденторного хроматического числа взвешенного ориентированного мультиграфа // Дискрет, анализ и исслед. операций. Сер. 1. 2006. - Т. 13, № 4. - С. 18-25.

9. Визинг В. Г. О раскраске ипциденторов в гиперграфе // Дискрет, анализ и исслед. операций. Сер. 1. 2007. - Т. 14, № 3. - С. 40-45.

10. Визинг В. Г. О раскраске ипциденторов в частично ориентированном мультиграфе // Дискрет, анализ и исслед. операций. Сер. 1. 2008. -Т. 15, № 1. - С. 17-22.

11. Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. М.: Мир, 1982.- 416с.

12. Камалян P.P. Интервальные реберные раскраски графов // Автореферат диссертации на соискание ученой степени кандидата физико-математических наук. ИМ СО АН СССР, Новосибирск, 1990. 18 с.

13. Карзанов A.B. Нахождение максимального потока в сети методом пред-потоков // ДАН СССР. 1974. - Т. 215, № 1. - С. 49-53.

14. Кристофидес Н. Теория графов. Алгоритмический подход. М.: Мир, 1978. - 432с.

15. Магомедов A.M. Раскраска графа с непрерывным спектром. Деп. в ВИНИТИ №478, 1985. Зс.

16. Магомедов A.M. Дефрагментация матриц перестановок с сохранением наборов элементов в линиях // Проблемы теоретической кибернетики. Тез. докладов XIV Международной конференции. М.: Изд-во МГУ, 2005. - С. 130-131.

17. Магомедов A.M. Жесткий директивный срок для многопроцессорного расписания без прерываний и отношений предшествования // Вестник Дагестанского научного центра. 2007. - № 28. - С. 5-11.

18. Магомедов A.M. К вопросу оптимизации расписания // Известия Волгоградского государственного технического университета: межвуз. сб. науч. ст. 2008. - №5 - С.40-43.

19. Магомедов A.M. К вопросу о реберной раскраске двудольного графа // Дискретная математика.- 2009. Т. 21, №. 2. - С. 153-159.

20. Магомедов A.M. Непрерывное расписание для специализированных процессоров без отношения предшествования // Вестник Московского Энерг. Института, сер. Автоматика, выч.техника, информатика. -2009. №5. - С. 14-17.

21. Магомедов A.M. Уплотнение расписания с директивным сроком, кратным количеству занятий каждого преподавателя // Матем. Заметки. 2009. Т. 85, № 1. - С. 65-72.

22. Магомедов A.M. Дефрагментация таблицы перестановок из четырех столбцов // Дискрет, матем. 2009. - Т. 21, №:4. - С. 95-104.

23. Магомедов A.M. О вычислительной сложности частного случая задачи построения расписания // Тез. докл. X Белорусской математической конференции Часть 5. Институт математики НАН Беларуси. Минск, 2008, С. 92.

24. Магомедов A.M. О модификации характеризации Бержа // Тез. докл.

25. XV международной конференции Проблемы теоретической кибернетики. Казань: Отечество. 2008. С. 77.

26. Майская В. Беспроводные сенсорные сети // Электроника: НТВ. 2005. - №2. - С. 18-22.

27. Молчанов Д.А., Кучерявый Е.А. Приложения беспроводных сенсорных сетей // Электросвязь. 2006. - N 6. - С. 20-23.

28. Новиков А. Дискретная математика для программистов. СПб.: Питер, 2003. - 304с.

29. Ope О. Графы и их применение. М.: Мир, 1965. - 174с.

30. Пападимитриу X., Стайглиц К. Комбинаторная оптимизация. Алгоритмы и сложность М.: Мир, 1985. - 112 с. j

31. Пяткин A.B. Некоторые задачи оптимизации расписания передачи сообщений в локальной сети связи // Дискрет, анализ и исслед. операций. Сер. 1. 1995. - Т/2, № 4. - С. 74-79.

32. Пяткин А. В. (к, 1)-ра,скраска инциденторов кубических мультиграфов // Дискрет, анализ и исслед. операций. Сер. 1. 2002. - Т. 9, № 1. - С. 49-53.

33. Пяткин А. В. Некоторые верхние оценки для инциденторного k, 1)-хроматического числа // Дискрет, анализ и исслед. операций. Сер. 1. -2003. Т. 10, № 2. - С. 66-78.

34. Пяткин А. В. Об(1,1)-раскраске инциденторов мулътиграфов степени4 // Дискрет, анализ и исслед. операций. Сер. 1. 2004. - Т. 11, №3. -С. 59-62.

35. Пяткии A.B. Раскраска инциденторов и другие задачи на графах: алгоритмический аспект. Автореферат диссертации на соискание ученой степени доктора физико-математических наук. Институт математики им. СЛ. Соболева СО РАН, Новосибирск, 2009. 31 с.

36. Сачков В.Н. Введение в комбинаторные методы дискретной математики М.: Наука, 1982. - 384 с.

37. Свами М., Тхуласирамап К. Графы, сети и алгоритмы. М.: Мир, 1984. 456 с.

38. Севастьянов C.B. Об интервальной раскрагциваемости ребер двудольного графа // Методы дискретного анализа в решении экстремальных задач, вып. 50. ИМ СО АН СССР, Новосибирск, 1990. - С. 61-72.

39. Севастьянов C.B. Введение в теорию расписаний. Новосибирск, 2003. -173с.

40. Танаев B.C., Гордон B.C., Шафранский Я.М. Теория расписаний: Одностадийные системы М.: Наука, 1984. - 381 с.

41. Танаев B.C., Сотсков Ю.Н., Струсевич В.А. Теория расписаний. Многостадийные системы. М.: Наука, 1989. 328 с.

42. Танаев В.С, Ковалев М.Я., Шафранский Я.М. Теория расписаний. Групповые технологии Минск: Ин-т техн. Кибернетики HAH Беларуси, 1998. - 290с.

43. Харари Ф. Теория графов. М.: Мир, 1973. - 300с.

44. Якубов А.З. Некоторые задачи дискретного разбиения и дефрагмента-ции и методы их решения // Автореферат диссертации на соискание ученой степени кандидата физико-математических наук. Саратовский гос. ун-т, Саратов, 2003. 15 с.

45. Aliuja R.K., Orlin J.В., Stein С., and Tarjan R.E. Improved algorithms for bipartite network flow problems. To appear in SI AM Journal on Computing. 1994. - V. 23, N 8. - P. 906-933.

46. Akyildiz I.F. et.al. A survey on wireless multimedia sensor networks// Computer networks. 0ct.2007. - P.75-84.

47. Alt H., Blum N., Mehlhorn K., Paul M. Computing a maximum cardinality matching in a bipartite graph in time 0{n1,b\f(mjlogn)) // Information Processing Letters. 1991. - V. 37, N 4. - P. 237-240.

48. Anderson R.J., and Setubal J.C. Parallel and sequential implementations of maximum-flow algorithms // In Dimacs Implementation Challenge Workshop: Algorithms for Network Flows and Matching. DIMACS Technical Report 92-4. 1992.

49. Asano Т., Asano Y. Recent developments in maximum flow algorithms // Journal of the operations research Society of Japan. 2000. - №43(1). - P. 2-31.

50. Asratian A.S., and Kamalian R.R. Investigation on interval edge-colorings of graphs // J. Combin. Theory. Ser. B. 1994. - V. 62, N 1. - P. 34-43.

51. Asratian A.S., and Casselgren C.J. On interval edge colorings of (o;,/3)-biregular bipartite graphs // Discrete Mathematics. 2007. - V.307. - P. 1951-1956.

52. Asratian A.S., Casselgren C.J., Vandenbussche J., and West D.B. Proper path-factors and interval edge-coloring of (3,4)-biregular bigraphs //J. Graph Theory. 2009. - V. 61. - P. 88-97.

53. Bast H., Mehlhorn K., Schafer G., Tamaki H. Matching algorithms are fast in sparse random graphs // Theory of Computing Systems. 2006. - V.39, N 1. - P. 3-14.

54. Booth K.S. PQ Tree Algorithms. Doctoral Thesis, Dept. of Electrical Engineering and Computer Science, University of California, Berkley C.A. 1975.

55. Booth K.S., Lueker G.S. Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms //J. Comput. Systems Sci. 1976. - V. 13, N 3. - P. 335-379.

56. Casselgren CJ., Some results on interval edge colorings of bipartite graphs. Master's Thesis, Linkoping University, Linkoping, Sweden. 2005.

57. Charikar M. Greedy approximation algorithms for finding dense components in a graph // In APPROX, 2000. P. 84-95.

58. Chen Z., Khokhar A. TDM A based Energy Efficient MAC Protocols for Wireless Sensor Networks // IEEE SECON 2004, October 2004. P. 223228.

59. Cook S.A. The complexity of theorem-proving procedures // Proc. 3rd Ann. ACM Symp. on Theory of Computing, Association for Computing Machinery, New York, 1971. P. 151-158.

60. Derigs U., and Meier W. Implementing Goldberg's Max-Flow Algorithm-A Computational Investigation // ZOR-Methods and Models of Operations Research. 1989. - V. 33. - P. 383-403.

61. Dijkstra E.W. A note on two problems in connexion with graphs // Numerische Mathematik.- 1959. N 1. - P. 269-271.

62. Dinic E.A. Algorithm for solution of a problem of maximum flow in networks with power estimation // Soviet Math. Doklady. 1970. - N 11. -P. 1277-1280.

63. Edmonds J., and Karp R.M. Theoretical improvements in algorithmic efficiency for network flow problems // Journal of the ACM. 1972. - V. 19. - P. 248-264.

64. Even S., Itai A., and Shamir A. On the Complexity of Timetable and Multicommodity Flow Problems // SIAM J. on Computing. 1976. - V. 5, N 4. - P. 691-703.

65. Feige U., Kortsarz G., and Peleg D. The dense k-subgraph problem // Algorithmica. 1997. - V.29. - P. 410-421.

66. Ford L.R., Ji. and Fulkerson D.R. Maximal flow through a network // Canad. J. ath. 1956. - N 8. - P. 399-404.

67. Gallo G., Grigoriadis M.D., and Tarjan R.E. A fast parametric maximumflow algorithm and applications // SIAM J. Comput. 1989. - V. 18, N 1. - P. 30-55.

68. Gibson D., Kumar R., and Tomkins A. Discovering large dense subgraphs in massive graphs // In VLDB '05, 2005. P. 721-732.

69. Giaro K., and Kubale M. Consecutive edge-colorings of complete and incomplete Cartesian products of graphs // Proc. 28th Southeastern Int. Conf. Combin., Graph Theory and Computing (Boca Raton, FL, 1997). Congr. Numer. 1997. - V. 128. - P. 143-149.

70. Giaro K. The complexity of consecutive D-coloring of bipartite graphs: 4 is easy, 5 is hard // Ars Combin. 1997. - V. 47. - P.287-298.

71. Giaro K., and Kubale M. Compact scheduling of zero-one time operations in multi-stage systems // Discrete Appl. Math. 2004. - V. 145. - P. 95-103.

72. Goldberg A.V. Finding a Maximum Density Subgraph // Technical Report Identifier: CSD-84-171

73. Goldberg A.V., and Tarjan R.E. A new approach to the maximum How problem // Journal of ACM. 1988. - V. 35. - P. 921-940.

74. Gusfield D., Marl,el C., and Fernandez-Baca D. Fast algorithms for bipartite network flow // SIAM J. Comput. 1987. - V. 16, N 2. - P. 237-251.

75. Gusfield D. Computing the strength of a graph // SIAM J. Comput. 1991. - V. 20, N 4. - P. 639-654.

76. Hajiaghayi M.T., Ganjali Y. A note on the Consecutive Ones Submatrix problem // Information Processing Letters 83. 2002. - P. 163-166.

77. Hansen H. M. Scheduling with minimum waiting periods (in Danish) // Master's Thesis, Odense University, Odense, Denmark, 1992.

78. Hanson D., and Loten C.O.M. A lower bound for interval colouring bi-regular bipartite graphs // Bull. Inst. Combin. Appl. 1996. - V. 18, N 1. - P. 69-74.

79. Hanson D., Loten C.O.M., Toft B. On interval colourings of bi-regular bipartite graphs // Ars Combinat. 1998. - V. 50. - P. 23-32.

80. Hohlt B., Doherty L., Brewer E. Flexible power scheduling for sensor networks // 3rd International Symposium on Information Processing in Sensor Networks, IPSN 2004, April 2004.

81. Hopcroft J. E., and Karp R. M. An n2 5 algorithm for maximum matching in bipartite graphs // SIAM Journal on Computing. 1973. - V. 2, N 2 -P. 225-231.

82. Hoylcr I. The NP-completeness of edge-coloring // SIAM J. Comput. -1981. V. 10, N4. - P. 718-720.

83. LAN MAN Standards Committee of the IEEE Computer Society. Wireless LAN medium access control (MAC) and physical layer (PLIY) specification n// Std. 802.11. NY. - 1997.

84. Lovasz L., Plummer M. D. Matching theory. Budapest: Akadcmiai Kiado, 2009. - 547 c.

85. Melnikov L.S., Vizing V.G. The edge-chromatic number of a directed/mixed multigraph // J. Graph Theory. 1999. - V. 23, № 4. - P. 267-273.

86. Page L., Brin S., Motwani R., and Winograd T. The pagerank citation ranking: Bringing order to the web // Technical report, Stanford University, 1998.

87. Petersen J. Die Theorie der regulären Graphen // Acta Math. 1891. - V. 15. - P. 193-220.

88. Picard J.-C. and Qucyranne M. A network flow solution to some nonlinear 0-1 programming problems, with applications to graph theory // Networks. 1982. - V. 12. - P. 141-159.

89. Pottie G.J. Wireless sensor networks // Information Theory Workshop. -1998. P. 139-140.

90. Pyatkin A.V. The incidentor coloring of multigraphs and its applications // Discrete Applied Math. 2002. - V. 120, № 1-3. - P. 209-217.

91. Pyatkin A.V. Interval coloring of (3, 4)-biregular bipartite graphs having large cubic subgraphs // J. Graph Theory. 2004. - V. 47. - P. 122-128.

92. Sahni S. Computationally related problems // SIAM J. Comput. 1974. -V.3, N 2. - P. 262-279.

93. Vishnevskiy V.M. One approach to wireless multimedia sensor network design // International conferences Proceeding, Barcelona, Information and telecommunication's technologies in intelligent systems, Mallorea Spain, 2007. P.8-11.

94. Ullman J.D. Complexity of sequencing Problems // Computer and Job Shop Theory, Coffman G.F., ed. New York: John Wiley, 1976. - P. 139164.