Исследование математических моделей, критериев существования и алгоритмов построения непрерывных расписаний нечетной длительности тема диссертации и автореферата по ВАК РФ 05.13.17, кандидат физико-математических наук Алекберли, Джалал Маратович

• Алекберли, Джалал Маратович
• кандидат физико-математических наук
• 2013

Оглавление диссертации кандидат физико-математических наук Алекберли, Джалал Маратович

Оглавление

Введение

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Заключение

Литература

Введение диссертации (часть автореферата) на тему «Исследование математических моделей, критериев существования и алгоритмов построения непрерывных расписаний нечетной длительности»

Введение

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

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

Значительная часть задач теории расписаний относится к разряду полных [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.

Заключение диссертации по теме «Теоретические основы информатики», Алекберли, Джалал Маратович

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

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

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

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

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

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

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

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

Заключение

Список литературы диссертационного исследования кандидат физико-математических наук Алекберли, Джалал Маратович, 2013 год

Литература

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

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

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

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

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

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

7. Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К. Алгоритмы: построение и анализ. - М.: Вильяме, 2007. - 1296 с.

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

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

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

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

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

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

14.Магомедов A.M. Непрерывность расписания для 3-элементных предписаний // Вопросы современной науки и практики. Университет им. В.И. Вернадского. - 2010. № 10-12(31). - С. 82-89.

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

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

П.Магомедов A.M., Сапоженко A.A. Условия существования непрерывных расписаний длительности 5 // Вестник Московского Университета, сер. Вычислительная математика и кибернетика. - 2010. - №1.

- С. 39-45.

18.Магомедов Т.А. Непрерывное 3-тестирование // Материалы XVIII международной школы-семинара «Синтез и сложность управляющих систем» им. ак. О.Б. Лупанова. - М.: Изд-во МГУ, 2009. - С. 6162.

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

- С. 49-53.

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

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

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

23.Севастьянов, С.В. Об интервальной раскрашиваемости ребер двудольного графа // Методы дискретного анализа - 1999. - Т. 50, - С. 61-72.

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

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

26.Холл М. Комбинаторика. - М.: Мир, 1970. - 424 с.

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

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

29.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. - Pp. 151-158.

30.Even S., Itai A., Shamir A. On the complexity of timetable and multi-commodity flow problems // SIAM J. on Computing. - 1976. - V.5, N 4. -Pp. 691-703.

© /

31 .Gotlieb C.C. The construction of class-teacher time-tables // Proc. IFIP Congr. 62. - 1963. - Pp. 73-77.

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

33.Karp R.M. Reducibility among combinatorial problems // Complexity of Computer Computation, Miller R.N. and Thatcher J.W., eds., Plenum Press, New York, 1972. - Pp. 85-104.

34.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.

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