автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.17, диссертация на тему:Исследование математических моделей, критериев существования и алгоритмов построения непрерывных расписаний нечетной длительности

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

АЛЕКБЕРЛИ Джалал Маратович

Исследование математических моделей, критериев существования и алгоритмов построения непрерывных расписаний

нечетной длительности

05.13.17 - «Теоретические основы информатики»

Автореферат

диссертации на соискание ученой степени кандидата физико-математических наук

2 Э ПАР 2013

Махачкала - 2013

005051008

Работа выполнена на кафедре дискретной математики и информатики Дагестанского государственного университета.

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

доцент

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

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

профессор

Горбатов Александр Вячеславович,

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

Московского государственного горного университета

доктор физико-математических наук, профессор

Казарин Лев Сергеевич,

зав. кафедрой алгебры и математической логики Ярославского государственного университета

Ведущая организация: Институт системного анализа Российской

академии наук (ИСА РАН)

Защита диссертации состоится « 19 » апреля 2013 г. в 16 час. 30 мин. на заседании диссертационного совета Д 212.203.28 при Российском университете дружбы народов по адресу: Москва, ул. Орджоникидзе, дом 3, ауд. 110.

С диссертацией можно ознакомиться в научной библиотеке РУДН по адресу: 117198 Москва, ул. Миклухо-Маклая, дом 6 (отзывы на автореферат просьба направлять по указанному адресу).

Автореферат разослан «7с? » марта 2013 г.

Ученый секретарь диссертационного совета

М.Б. Фомин

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

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

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

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

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

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

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

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

Важные результаты по теории расписаний получены следующими авторами: A.C. Асратян, В.Г. Визинг, P.P. Камалян, A.M. Магомедов, A.B. Пят-кин, C.B. Севастьянов, Ю.Н. Сотсков, В.А. Струсевич, B.C. Танаев, S. Even, D. R. Fulkerson, A. Itai и др.

Цель работы

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

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

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

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

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

Научная новизна

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

Доказано, что всякое непрерывное расписание длительности 2к+\ (ке N) может быть приведено к такому непрерывному расписанию, у которого в любом заранее выбранном столбце с нечетным номером расположены символы кратности 2к+\ и только они.

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

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

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

Теоретическая и практическая значимость

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

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

Апробация работы

Результаты работы были представлены на следующих конференциях и семинарах:

1. 50-я Международная научная студенческая конференция «Студент и научно-технический прогресс» (Новосибирск, 2012 г.);

2. XVIII Международная школа-семинар «Синтез и сложность управляющих систем» имени академика О.Б. Лупанова (Пенза, 2009 г.);

3. V Региональная научно-техническая конференция «Информационные и телекоммуникационные системы: информационные технологии в научных и образовательных процессах» (Махачкала, 2009 г.);

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

-3-

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

Публикации

По теме диссертации автором опубликованы 9 печатных работ, в том числе две — в журналах из перечня рекомендованного ВАК.

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

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

Краткое содержание диссертации

Введение

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

Глава 1. Постановка задачи. Определения и обозначения

В первой главе вводятся определения и обозначения, используемые в работе. Рассматривается классическая постановка задачи и связанные с ней вопросы МР-полноты. Обозначается класс задач, решаемых за полиномиальное время.

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

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

Определение 1. Конечную совокупность различных символов назовем алфавитом А и введем специальный символ (обозначим его через 0), не принадлежащий А. Неупорядоченную пару необязательно различных символов

а> = (а:Ь), где а,ЬеА, будем называть 2-словом. Для набора 2-слов через

-4-

A(W) будем обозначать подмножество всех тех символов алфавита А, из которых составлены 2-слова набора W. Кратность символа а в словах набора W обозначим через repwa\ множество символов а, таких, что repwa = k, обозначим Ак (Ж).

Определение 2. Размещение 2-слов набора W в некоторой матрице М будем называть непрерывным размещением, если:

1. каждое 2-слово сое И7 записано в отдельной строке;

2. символы каждого 2-слова <ае W расположены в соседних столбцах;

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

Определение 3. Пусть G - непустое конечное мультимножество (т.е. элементы в G могут повторяться), a 5 = {Si, ...,Sn} - семейство п непустых подмножеств мультимножества G. Тогда трансверсалъ (система различных представителей) семейства S есть множество п различных элементов мультимножества G, по одному из каждого подмножества 5,, i = 1, 2.....п. Трансверсаль обозначим trv(S).

Определение 4. Пусть W - набор 2-слов над алфавитом А, такой, что

max repwa= 3.

as A(W)

Трансверсаль trv(W) будем называть полной трансверсалъю, если

A2(W) и A3(W) cfrv(W),

Полную трансверсаль будем обозначать trv(W).

Определение 5. Пусть к - некоторое натуральное число, W — набор 2-слов над алфавитом А, такой, что max repwa = 2к + 1. Разбиение набора W на

asA(W)

поднаборы И', , назовем s-разбиением, если для этих поднаборов выполняются условия:

A) герща< 3, i = lJt, VaeA(W;);

B) для каждого Wt (i=\..k) существует трансверсаль - тЩ)\

С) если в каком-либо поднаборе Wt символ а е A(W) удовлетворяет условию:

repw. а = 3, то геру/, а = 2, 1 < i, j <к.

Определение 6 (элементарное разбиение). Пусть к — некоторое натуральное число, W - набор 2-слов над алфавитом А, такой, что max repwa = 2k + 1.

azA(W)

Разбиение набора W на поднаборы Wx,...,Wk, назовем элементарным разбиением, если для этих поднаборов выполняются условия:

A) герща<Ъ, г = 1.1, Vae A(W;.);

B) 3 trv(W.), (i=l..fc).

В следующем определении (и далее) через М[к] обозначена совокупность всех символов столбца к матрицы М, отличных от специального символа. Определение 7 (к-разреженность). Пусть W — набор из р 2-слов, max repwa=n, и задано некоторое непрерывное размещение W в (рхп)-

ае A(W)

матрице М. Будем говорить, что данное непрерывное размещение обладает свойством к-разреженности, если столбец с номером к содержит (кроме специального символа) все символы а такие что repwa = n и только их; другими словами, М[к] = An(W).

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

Каждое предписание должно быть выполнено за п единиц времени, где ле {1,2,...,2£ + 1}, ке N. Общее время выполнения всех предписаний, называемое продолжительностью сессии, равно целому числу единиц времени. В течении одной рабочей единицы времени каждое устройство выполняет заданное ему предписание. В любую единицу времени каждое предписание об-

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

Если потребовать неразрывное выполнение каждого задания, то задача будет ТУР-полна даже для 2к + \ =3 и продолжительности сессии равной трем.

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

1. каждое устройство работало без прерываний;

2. продолжительность сессии была минимальной.

Формализуя, согласно приведенным выше определениям и обозначениям, поставленную задачу, получим следующее:

a) т предписаний задают алфавит А (определение 1);

b) р устройств задают количество строк матрицы М (определение 2);

c) продолжительность сессии задает число столбцов в матрице М;

с1) задание для каждого устройства образует 2-слово а> = (а\Ь) (определение 1);

е) совокупность заданий всех устройств соответствует набору 2-слов И7 (определение 1);

1) длительность исполнения предписаний задает кратность элементов алфавита А в наборе \У: гер№а, \/а е И7 (см. обозначения); g) принцип не разделяемого доступа означает то, что в каждом столбце

матрицы М все символы алфавита Л попарно различны; И) условие того, что каждое устройство работает без прерываний, будет означать, что символы алфавита А, стоящие в одной строке, располагаются в соседних столбцах. Требование: «продолжительность сессии должна быть минимальной» приводит к условию того, что количество столбцов в матрице М должно равняться максимальной кратности символов алфавита А в наборе IV. Сформулируем поставленную задачу в матричном виде.

Задача: Пусть набор 2-слов удовлетворяет условию

-7-

гер„а<2к + 1, *еЛГ, УабЛ(1У), I Д24+1(ИО 1>0. Вопрос: Когда существует непрерывное размещение набора И'в

(рх2к+1 )-матрице М, где р=\Ш, ке N ? Данная задача решается в диссертационном исследовании в три этапа. Что и составило содержание второй, третьей и четвертой глав. Итогом этих исследований явилось создание алгоритма построения непрерывных расписаний произвольной нечетной длительности.

Глава 2. Непрерывное размещение набора 2-слов в рхЗ-матрице

Во второй главе рассматривается задача составления непрерывного расписания длительности три. Получены условия существования непрерывного размещения набора 2-слов \¥ъ рхЗ-матрице {ре. N). Выявлена связь между непрерывным размещением набора W и существованием трансверсали у набора \У, а так же получены условия существования трансверсали и алгоритм построения полной трансверсали.

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

В Леммах 2.1-3 рассматриваются необходимые условия существования непрерывного расписания длительности три. Доказано, что таким условием является существование трансверсали у набора 2-слов.

Лемма 2.1.: Пусть набор 2-слов \У удовлетворяет условию геРп,а< 3, УаеД(ИО, А3(ИО*0. Тогда для того, чтобы набор IV допускал непрерывное размещение в (рхЗ)-матрице М ( р е N), необходимо, чтобы у этого набора существовала трансверсаль - Гп>(МО.

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

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

Следующий ряд теорем формирует основные результаты Главы 2.

Достаточные условия построения расписания длительности три, получены в Теореме 2.1. Доказано, что при наличии трансверсали для существования непрерывного размещения, достаточно включить в нее (трансверсаль) все трехкратные символы.

В теореме 2.2. вводится важное понятие, существенно оптимизирующее доказательства последующих теорем - «полная» трансверсаль. Показано, что если у набора 2-слов имеется трансверсаль, то у этого набора существует и полная трансверсаль. В доказательстве так же построен алгоритм приведения произвольной трансверсали к полной.

Необходимые и достаточные условия существования непрерывного размещения набора 2-слов в рхЗ-матрице, найдены в Теореме 2.З.: для существования непрерывного расписания длительности три необходимо и достаточно, чтобы существовала трансверсаль набора 2-слов.

Причем, критерием является условие вытекающее из теоремы Холла: 0< IД3(П)1 < IД,(П)1,

Теорема 2.4. подытоживает результаты Главы 2. В ней вводится понятие разреженности непрерывного размещения и доказано важнейшее свойство непрерывного размещения набора 2-слов в рхЗ-матрице о существовании 1-разреженного и 3-разреженного видов непрерывного размещения. Данное свойство плодотворно используется при доказательстве основных результатов работы. В теореме 2.4 показано, что всякое непрерывное расписание длительности три можно привести к 1 или 3-разреженному виду. Т.е. существует такое непрерывное размещение набора 2-слов \\' в рхЗ-матрице, для которого множество элементов либо первого столбца, либо третьего, совпадает с множеством все трехкратных символов множества И7, т.е.

М[1] = А3(И0, либо М[3] = Д3ОУ).

В заключении главы приводится алгоритм построения полной трансвер-сали и непрерывного размещения для набора 2-слов W, удовлетворяющего условиям:

repwa< 3, VaeA(W). A3(W)*0 и для него существует трансверсаль, т.е.

0< 1А3(П)1 < I А] (П) I, va çW.

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

Глава 3. Непрерывное размещение набора 2-слов в рх5-матрице

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

В первой из них доказывается свойство разреженности в столбцах с нечетными номерами для непрерывных расписаний длительности пять: Теорема 3.1. Если набор 2-слов W удовлетворяет условию:

repwa< 5, VaeA(W); IA5(W)l>0 непрерывно размещен врх5-матрице М, где ре N, то это непрерывное размещение можно привести к такому виду, при котором в любом заранее выбранном столбце с нечетным номером будет выполняться равенство:

M[2;-1] = A5(W), j = 1..3. Кроме свойства разреженности из алгоритма доказательства следует важный факт того, как перераспределяются символы в матрице при построении 3-разреженности.

Во второй теореме показано в каком случае два набора, каждый из которых имеет свое непрерывное размещение в рхЗ-матрице, смогут в совокупности иметь непрерывное размещение в /?х5-матрице:

Теорема 3.2. Пусть два набора 2-слов XV! и \У2 над алфавитом Л удовлетворяют условиям:

геРп,. а< 3, У а € АЩ>,¿=1,2; существует 1п'(\У1), / = 1, 2; гер^ а < 5, Уа 6 Л(И0, Ж = IV, + \У2, здесь набор \¥ = \¥1+\¥2, понимается как сумма мультимножеств, т.е. для любого 2-слова а

герка>~ герщсо + герп,2а>, й)е ^ +\У2).

Тогда набор допускает непрерывное размещение в (/?х5)-матрице М, ре N.

Третья теорема является обратной к теореме 3.2. В ней вводится понятие ¿-разбиения непрерывного размещения набора 2-слов в /зх5-матрице. Понятие ¿-разбиения является ключевым инструментом для доказательства целого ряда последующих теорем. Оно интересно тем, что приводимая в нем модель распределение символов имеет широкое приложение в доказательстве важных свойств непрерывных размещений и является масштабируемой на непрерывные размещения в рх2к+1-матрицах, где р,ке N. На основе понятия ¿-разбиения, в работе доказаны необходимые и достаточные условия существования непрерывного размещения в матрицах с любым нечетным количеством столбцов.

Теорема 3.3. Если набор 2-слов IV, удовлетворяющий условию

гер„а <5, \/а е А(1У); I А5 (IV) I > 0, допускает непрерывное размещение в (рх5)-матрице М (ре К), то для него существует ¿-разбиение на два поднабора.

В заключении главы получен критерий существования непрерывного расписания длительности пять:

Теорема 3.4. Для того, чтобы набор 2-слов IV, удовлетворяющий условию

герц,а< 5, \/а<= А(УУ)\ 1^0^)1 >0, мог быть непрерывно размещен в (рх5)-матрице М (р е N), необходимо и достаточно, чтобы он допускал элементарное разбиение.

Глава 4. Непрерывное размещение набора 2-слов в рх2А'+1-матрице

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

В теореме 4.1 определяются необходимые условия существования непрерывного расписания, сформулированные в терминах кратности символов, входящих в расписание. Что позволяет заглянуть глубоко в структуру непрерывного расписания:

Теорема 4.1. (Необходимое условие существования непрерывного размещения). Для того, чтобы набор 2-слов удовлетворяющий условию

герк,а<2к + 1, УаеЛ(И'), к<Е I А2Ы(У/) 1>О, мог быть непрерывно размещен в (рх2к+1 )-матрице М ( р,к £ N), необходимо, чтобы для символов алфавита любого поднабора £1 набора IV выполнялось условие:

¡=1

В теореме 4.2 показано, что всякий набор 2-слов, допускающий элементарное разбиение на к поднаборов, имеет ^-разбиение.

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

Результаты теорем 4.2-3 подводят нас к критерию существования непрерывного расписания произвольной наперед заданной нечетной длительности для набора 2-слов.

Теорема 4.4. (Критерий существования непрерывного размещения набора 2-слов в матрице с произвольным наперед заданным нечетным количеством столбцов).

Для того, чтобы набор 2-слов \У, удовлетворяющий условию

герп,а<2к+1, УаеЛ(1У), кеЫ; М2А+1(И')1>0, мог быть непрерывно размещен (рх2к+1 )-матрице М (р,к е И) необходимо и достаточно, чтобы набор IV допускал элементарное разбиение на к поднабо-ров.

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

В теореме 4.5, опираясь на понятие .^-разбиения, доказывается, что любой непрерывное расписание может быть приведено к расписанию, обладающему разреженностью, в любом заранее выбранном столбце с нечетным номером. Теорема 4.5. (Разреженность непрерывного размещения). Если набор 2-слов IV, удовлетворяющий условию

герКа<2к + 1, УаеЛ(1У), кеЫ; I А2М(ЦГ) |> 0,

непрерывно размещен в (рх2&+1)-матрице М (р,ке (V), то существует размещение этого набора с разреженностью в любом наперед выбранном столбце с нечетным номером.

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

Заключение

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

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

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

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

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

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

5. Третья подзадача состояла в необходимости объединить к (произвольное натуральное число) наборов 2-слов, для каждого из которых существует непрерывное расписание длительности три, в непрерывное расписание длительности 2к+\. На этом этапе также были получены как условия, нала- 14-

гаемые на наборы 2-слов, так и алгоритм составления искомого расписания.

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

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

Основные публикации по теме диссертации В рецензируемых журналах из перечня ВАК:

1. Алекберли Д.М. Критерий существования непрерывного размещения дву-символьных слов в матрице размера Lx(2k+1) // Информационные технологии и вычислительные системы. - 2010. -№2. - С. 50-58.

2. Алекберли Д.М. Построение трансверсали набора двусимвольных слов // Информационные технологии и вычислительные системы. - 2012. - №1. -С. 65-68.

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

3. Алекберли Д.М. Частные случаи дефрагментации (0-1)-матриц // Труды молодых ученых ДГУ. Махачкала. - ИПЦ ДГУ. - 2005. - С. 3.

4. Алекберли Д.М. К вопросу о достаточных условиях оптимизации для одного специального случая учебного расписания // Информационные технологии в профессиональной деятельности и научной работе: сборник материалов Всероссийской научно-практической конференции с международным участием. Йошкар-Ола. - 2008. - 4.1. - С. 14-16.

5. Алекберли Д.М. Частичная декомпозиция одной задачи оптимизации расписания // Материалы IV Всероссийской конференции «Проблемы оптимизации и экономические приложения». Омск. - Изд-во «Полиграфический центр КАН». - 2009. - С. 109.

6. Алекберли Д.М. Строковое размещение набора 2-слов в матрице М (¿хш), т=5,1 II Материалы V Региональной научно-технической конференции «Информационные и телекоммуникационные системы: информационные технологии в научных и образовательных процессах. Махачкала. - Изд-во ДНЦ РАН. - 2009. - С. 145-148.

7. Алекберли Д.М. Условия оптимизации частного случая расписания из 2-нагрузок // Материалы XVIII Международной школы-семинара «Синтез и сложность управляющих систем» имени академика О.Б. Лупанова. Пенза. - М.: Изд-во мех.-мат. фак-та МГУ. - 2009. - С. 5-6.

8. Алекберли Д.М. ^-разреженность непрерывного размещения 2-слов в матрице с любым нечетным числом столбцов // Вестник ДГИНХ. Махачкала. -2010.-№14.-С. 183-191.

9. Алекберли Д.М., Магомедов М.А. Расписание замены оборудования // Материалы 50-й Международной научной студенческой конференции «Студент и научно-технический прогресс»: Информационные технологии. Новосибирск. - Изд-во НГУ. - 2012. - С. 97.

Алекберли Джалал Маратович (Россия)

Исследование математических моделей, критериев существования и алгоритмов построения непрерывных расписаний

нечетной длительности

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

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

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

Alekberli Dzhalal Maratovich (Russia)

Research of mathematical models, criterions of the existence

and algorithms for constructing regular schedules of odd duration

Criterions of the existence and algorithms for constructing regular schedules of arbitrary odd duration were found. Based on the matrix representation proposed the new approaches to solving problems of constructing regular schedules, allowing to receive a number of important properties, which expanding toolkit of building proofs and also algorithms bringing the schedules to the regular form.

During the solution of the central problem of dissertation was identified a number of subtasks. As the result, criterions of the existence and algorithms for constructing regular schedules of three and five duration were found.

Proved, that every regular schedule of arbitrary odd duration can be divided into a set of schedules duration three. Based on the obtained solutions, was found a complex of methods which provides a simplified proof mechanisms the existence of regular schedules and also algorithms for constructing regular schedules.

- 17-

Подписано в печать 15.03.2013 г.

Заказ №12668 Тираж: 100 экз.

Копицентр «ЧЕРТЕЖ.ру» ИНН 7701723201 107023, Москва, ул.Б.Семеновская 11, стр.12 (495) 542-7389 www.chertez.ru

Министерство образования и науки Российской Федерации Государственное учреждение высшего профессионального образования «Дагестанский государственный университет»

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

04201355586

Алекберли Джалал Маратович

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

05.13.17 - Теоретические основы информатики

Диссертация на соискание ученой степени кандидата физико-математических наук

Научный руководитель доктор физико-математических наук Магомедов А.М.

Махачкала 2013

Оглавление

Введение 4

1. Постановка задачи. Определения и обозначения 13

1.1. Определения и обозначения........................................................................................13

1.2. Постановка задачи............................................................................................................17

2. Непрерывное размещение набора 2-слов в/?хЗ-матрице 23

2.1. Необходимое условие существования непрерывного размещения набора 2-слов в рхЗ-матрице..................................................23

2.2. Достаточные условия существования непрерывного размещения набора 2-слов в рхЗ-матрице....................................................26

2.3. Критерий существования непрерывного размещения набора 2-слов в /?хЗ-матрице......................................................................................................29

2.4. Алгоритм построения полной трансверсали и

непрерывного размещения........................................................................................38

3. Непрерывное размещение набора 2-слов в/?х5-матрице 46

3.1. Разреженность непрерывного размещения набора 2-слов в /7х5-матрице............................................................................................................................46

3.2. Непрерывное размещение набора 2-слов в /?х5-матрице..............63

4. Непрерывное размещение набора 2-слов в ^х2А:+1-матрице 68

4.1. Необходимое условие существования непрерывного

размещения набора 2-слов в рх2к+\-матрице..........................................68

4.2. Критерий существования непрерывного размещения набора

2-слов в рх2к+1 -матрице.............................................. 74

4.3. Разреженность непрерывного размещения набора 2-слов в рх2к+\ -матрице......................................................... 82

4.4. Алгоритм построения непрерывного размещения набора

2-слов в рх2к+1 -матрице.............................................. 84

Заключение 91

Литература 93

Введение

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

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

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

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

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

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

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

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

Важные результаты по теории расписаний получены следующими авторами: A.C. Асратян, В.Г. Визинг, P.P. Камалян, A.M. Магомедов, A.B. Пяткин, C.B. Севастьянов, Ю.Н. Сотсков, В.А. Струсевич, B.C. Танаев, S. Even, D. R. Fulkerson, A. Itai и др.

Цель работы

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

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

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

Научная новизна

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

Доказано, что всякое непрерывное расписание длительности 2к+\ (кg N) может быть приведено к такому непрерывному расписанию, у которого в любом заранее выбранном столбце с нечетным номером расположены символы кратности 2к+1 и только они.

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

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

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

Теоретическая и практическая значимость

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

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

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

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

2. Необходимые и достаточные условия существования непрерывных расписаний длительности три, в которых каждый прибор работает точно две единицы времени, основанные на понятии «полной транс-версали».

3. Алгоритм построения полной трансверсали.

4. Метод «¿-разбиения», который наряду с ^-разреженностью является эффективным инструментом составления и исследования условий существования непрерывных расписаний.

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

6. Алгоритм преобразования расписаний произвольной наперед заданной нечетной длительности к непрерывному виду.

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

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

Апробация работы

Результаты работы были представлены на следующих конференциях и семинарах:

1. 50-я Международная научная студенческая конференция «Студент и научно-технический прогресс» (Новосибирск, 2012 г.);

2. XVIII Международная школа-семинар «Синтез и сложность управляющих систем» имени академика О.Б. Лупанова (Пенза, 2009 г.);

3. V Региональная научно-техническая конференция «Информационные и телекоммуникационные системы: информационные технологии в научных и образовательных процессах» (Махачкала, 2009 г.);

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

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

Публикации

По теме диссертации автором опубликованы 9 печатных работ, в том числе две - в журналах из перечня, рекомендованного ВАК.

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

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

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

В первой главе вводятся используемые в работе определения и обозначения. Рассматривается классическая постановка задачи и связанные с ней вопросы ./УР-полноты. Обозначается класс задач, решаемых за полиномиальное время.

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

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

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

В леммах 2.1, 2.2 и 2.3 сформулированы необходимые условия существования непрерывного расписания длительности три. Доказано, что таковым условием является существование трансверсали у набора 2-слов. Опираясь на известную теорему Холла [26] были получены условия существования трансверсали для наборов 2-слов, сформулированные в терминах кратности символов, входящих в эти наборы.

В теореме 2.1 получены достаточные условия построения расписания длительности три.

В теореме 2.2 показано, что набор 2-слов, обладающий трансверсалью, обладает и полной трансверсалью.

В теореме 2.3 доказано, что для существования непрерывного расписания длительности три необходимо и достаточно, чтобы существовала трансверсаль набора 2-слов.

В теореме 2.4 показано, что всякое непрерывное расписание длительности три можно привести к 1- или 3-разреженному виду.

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

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

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

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

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

В теореме 3.3 доказывается, что если набор 2-слов имеет непрерывное расписание длительности пять, то этот набор допускает 5-разбиение на два поднабора.

В теореме 3.4 получен критерий существования непрерывного расписания длительности пять.

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

В теореме 4.1 определяются необходимые условия существования непрерывного расписания, сформулированные в терминах кратности символов, входящих в расписание.

В теореме 4.2 показано, что всякий набор 2-слов, допускающий элементарное разбнение, имеет ¿--разбиение.

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

Теорема 4.4 дает критерий существования непрерывного расписания произвольной наперед заданной нечетной длительности для набора 2-слов.

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

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

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

Список публикаций

По теме данного исследования автором опубликованы следующие работы.

В рецензируемых журналах из перечня ВАК:

1. Алекберли Д.М. Критерий существования непрерывного размещения двусимвольных слов в матрице размера Lx(2k+1) // Информационные технологии и вычислительные системы. - 2010. -№2. - С. 50-58.

2. Алекберли Д.М. Построение трансверсали набора двусимвольных слов // Информационные технологии и вычислительные системы. - 2012. -№1. - С. 65-68.

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

3. Алекберли Д.М. Частные случаи дефрагментации (0-1)-матриц // Труды молодых ученых ДГУ. Махачкала. - ИПЦ ДГУ. - 2005. - С. 3.

4. Алекберли Д.М. К вопросу о достаточных условиях оптимизации для одного специального случая учебного расписания // Информационные . технологии в профессиональной деятельности и научной работе: сборник материалов Всероссийской научно-практической конференции с международным участием. Йошкар-Ола. - 2008. - 4.1. - С. 14-16.

5. Алекберли Д.М. Частичная декомпозиция одной задачи оптимизации расписания // Материалы IV Всероссийской конференции «Проблемы оптимизации и экономические приложения». Омск. - Изд-во «Полиграфический центр КАН». - 2009. - С. 109.

6. Алекберли Д.М. Строковое размещение набора 2-слов в матрице М (Lxw), /»=5,7 // Материалы V Региональной научно-технической конференции «Информационные и телекоммуникационные системы: информационные технологии в научных и образовательных процессах. Махачкала. - Изд-во ДНЦ РАН. - 2009. - С. 145-148.

7. Алекберли Д.М. Условия оптимизации частного случая расписания из 2-нагрузок // Материалы XVIII Международной школы-семинара «Синтез и сложность управляющих систем» имени академика О.Б. Лупанова. Пенза. - М.: Изд-во мех.-мат. фак-та МГУ. - 2009. - С. 5-6.

8. Алекберли Д.М. ^-разреженность непрерывного размещения 2-слов в матрице с любым нечетным числом столбцов // Вестник ДГИНХ. Махачкала.-2010.-№14.-С. 183-191.

9. Алекберли Д.М., Магомедов М.А. Расписание замены оборудования // Материалы 50-й Международной научной студенческой конференции «Студент и научно-технический прогресс»: Информационные технологии. Новосибирск. - Изд-во НГУ. - 2012. - С. 97.

Глава 1

Постановка задачи. Определения и обозначения

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

§1.1 Определения и обозначения

Определение 1. Конечную совокупность различных символов назовем алфавитом А и введем специальный символ (обозначим его через 0), не принадлежащий А. Неупорядоченную пару необязательно различных символов а) = {а\Ь), где а,Ье А будем называть 2-словом. Набор 2-слов будем обозначать - У/.

Определение 2. Размещение 2-слов набора Ш в некоторой матрице М будем называть непрерывным размещением, если:

1. каждое 2-слово сое У/ записано в отдельной строке;

2. символы каждого 2-слова сое У/ расположены в соседних столбцах;

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

Определение 3 [8]. Пусть С - непустое конечное мультимножество (т.е. элементы в С могут повторяться), а 5,= {5,ь ...Д,} - семейство п непустых подмножеств мультимножества С. Тогда трансверсаль (система различных представителей) семейства £ есть множество п различных элементов мультимножества С, по одному из каждого подмножества 5, ,1 = 1,2,..., п. Трансверсаль обозначим гл^).

Введем следующие обозначения:

• 1ЭД1 - количество 2-слов, входящих в набор W (мощность мультимножества \¥у,

• А(ТУ) - подмножество символов алфавита А, в�