Электронная библиотека Веда
Цели библиотеки
Скачать бесплатно
Доставка литературы
Доставка диссертаций
Размещение литературы
Контактные данные
Я ищу:
Библиотечный каталог российских и украинских диссертаций

Вы находитесь:
Диссертационные работы России
Технические науки
Системный анализ, управление и обработка информации

Диссертационная работа:

Воронин Иван Викторович. Модели и методы решения задачи автоматизированного составления расписаний с интеллектуальной поддержкой принятия решений : диссертация ... кандидата технических наук : 05.13.01 / Воронин Иван Викторович; [Место защиты: С.-Петерб. гос. электротехн. ун-т (ЛЭТИ)]. - Санкт-Петербург, 2008. - 159 с. : ил. РГБ ОД, 61:08-5/659

смотреть содержание
смотреть введение
Содержание к работе:

ВВЕДЕНИЕ 4

1 АНАЛИЗ ЗАДАЧИ И СРЕДСТВ ЕЕ РЕШЕНИЯ 15

1.1 Общая характеристика задачи 15

1.2 Обзор существующих средств решения 21

1.3 Обзор методов решения

1.3.1 Математическое программирование 28

1.3.2 Комбинаторный подход 32

1.3.3 Эвристические и вероятностные методы 34

1.4 Выводы по разделу 36

2 ФОРМАЛИЗАЦИЯ ЗАДАЧИ 38

2.1 Общая модель задачи 38

2.2 Формализация задачи на основе аппарата теории множеств 42

2.3 Формирование элементов расписания 54

2.4 Принципы анализа исходных данных 56

2.5 Выводы по разделу 61

3 РАЗРАБОТКА МЕТОДА РЕШЕНИЯ ЗАДАЧИ 62

3.1 Последовательный метод составления расписания 62

3.2 Расчет коэффициентов сложности с применением нейронных сетей 81

3.3 Выводы по разделу 84

4 РАЗРАБОТКА АВТОМАТИЗИРОВАННОЙ СИСТЕМЫ 85

4.1 Разработка структуры автоматизированной системы составления расписания занятий 85

4.2 Аппаратная подсистема 86

4.3 Программная подсистема 88

4.4 Разработка логической структуры базы данных 93

4.5 Разработка алгоритма составления расписания 101

4.6 Разработка модуля анализа исходных данных 110

4.7 Разработка модуля корректировки расписания 117

4.8 Методическая подсистема 133

4.9 Выводы по разделу 133

5 АНАЛИЗ РЕЗУЛЬТАТОВ ПРАКТИЧЕСКОГО ПРИМЕНЕНИЯ 134

5.1 Разработка критериев оценки качества расписания занятий 134

5.2 Результаты внедрения автоматизированной системы 138

5.3 Исследование влияния объема аудиторного фонда на качество расписания 144

5.4 Реализация нейросетевого подхода подсчета КС 150

5.5 Выводы по разделу 151

ЗАКЛЮЧЕНИЕ 152

Список использованных источников 153  

Введение к работе:

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

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

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

В последние 10-15 лет для высшего образования в России характерен процесс постоянных изменений, причем наиболее существенных изменений можно ожидать при планируемом переходе к двухступенчатой кредитно-модульной системе высшего образования. Высшие учебные заведения должны иметь возможность быстрого и гибкого реагирования на возможные изменения. Такую возможность дает автоматизация планирования учебного процесса ВУЗа. В условиях роста разнообразия образовательных программ, острой нехватки бюджетного финансирования и аудиторного фонда задачи рационального распределения ресурсов приобретают первостепенное значение. Составление расписания занятий в новых условиях без автоматизации этого процесса не представляется возможным [31]. Составление расписания в ВУЗе характеризуется рядом проблем, которые перечислены ниже на примере Балтийского государственного технического университета «Военмех» им. Устинова Д.Ф. (БГТУ).

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

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

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

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

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

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

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

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

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

С математической точки зрения задача составления расписания является задачей упорядочения и характеризуется очень высокой размерностью [29]. Математи ческие методы решения таких задач рассматриваются в рамках теории расписаний (ТР). «Временной» характер задач теории расписаний выделяет их в особый класс, существенно отличающийся от «объемных» экономических задач. Если в последних требуется ответить на вопрос, что и сколько производить, то в задачах ТР необходимо определить, когда и в какой последовательности выполнять работы. Это различие в существе задач определяет различие в методах и возможностях их решения. Для задач объемного характера развит достаточно мощный аппарат, главным образом математического программирования, позволяющий, с успехом добиваться их решения. Для задач ТР решающий аппарат развит в гораздо меньшей степени [35].

Поиск оптимального или близкого к оптимальному расписания осуществляется с помощью одного из 3 подходов:

- математического программирования [1,23];

- комбинаторного [35,62,75];

- эвристического [35].

Задача составления расписания может быть сформулирована в терминах линейного целочисленного программирования. Описывается система из работ, состоящих из операций, и машин, выполняющих конкретные операции. В виде неравенств представлена система ограничений. Также вводятся дополнительные целочисленные переменные для описания ограничений типа «или-или», которые нельзя описать в рамках обычного линейного программирования. Далее записывается сама система и формируется целевая функция. Целевые функции могут быть различными. Конкретный вид целевой функции зависит от того, что нам необходимо минимизировать [45].

При применении методов математического программирования для решения рассматриваемой задачи ТР неизбежно показательное возрастание времени решения задачи в зависимости от ее размерности в силу неизбежного использования приемов перебора вариантов:

Т = С-кт", где С-некоторая константа, -количество пар в неделю, m-среднее количество типов занятий проводимых преподавателем, и-количество преподавателей.

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

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

При комбинаторный подходе используются такие понятия, как задачи класса Р, эффективные алгоритмы иіУР-полньїе задачи[82].

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

Класс NP-задач обладает следующими свойствами:

- никакую TVP-полную задачу нельзя решить никакими известными полиномиальными алгоритмами;

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

Практическое значение понятия TVP-полноты состоит в следующем: такие задачи по существу трудно решаемы с вычислительной точки зрения, они не поддаются эффективному алгоритмическому решению и для алгоритма, корректно решающего ІУР-полную задачу, потребуется в худшем случае экспоненциальное количество времени и, следовательно, он не будет применим на практике ни к каким, за исключением очень малых, задачам [75]. 

Неудовлетворительное состояние развития точных методов решения задач ТР обусловило разработку приближенных методов, позволяющих получать приемлемые решения при сравнительно небольших затратах времени и средств. Условно приближенные методы делятся на эвристические и вероятностные [75].

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

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

Еще одно из направлений эвристических методов решения задач ТР состоит в формировании правил или функций предпочтения (приоритетов). Для каждой /-й работы из множества ожидающих выполнения работ, вычисляется значение функции /. предпочтения и выбирается та работа, для которой /. достигает максимума или минимума.

Задачу составления расписания можно представить в виде задачи упорядочивания, где дисциплины из учебного плана являются операциями, а группы, преподаватели и аудитории - обслуживающие приборы [66]. Модель в этом случае удобно представлять в виде сети, дуги которой представляют операции. Каждой дуге соответствует некоторый весовой коэффициент, который является значением целевой функции, определяющей степень предпочтения выполнения данной операции. Вершины сети, называемые событиями и обозначаемые Е„ могут интерпретироваться как результаты выполнения отдельных частных работ. Таким образом, задача составления расписания сводится к построению сети с учетом всех требуемых условий. В случае, когда сетей можно построить несколько, необходимо рассчитать для каждой из них критический путь, и выбрать сеть с наименьшим критическим путем. Данный метод хорошо подходит для классической задачи упорядочения, а для решения задачи составления учебного расписания, его применение проблематично, так как в учебном расписании надо не просто упорядочить операции, а выбрать еще и время их проведения, что не предусматривается данной моделью и приведет к необходимости построения дискретной уровневой сети с запрещенными состояниями.

При применении всех этих методов также неизбежно возрастание по экспоненте времени работы программы при увеличении объема задачи [27].

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

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

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

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

- разработка системы критериев оценки качества решения задачи,

- поиск метода решения,

- разработка алгоритмов, реализующих данный метод,

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

Диссертация состоит из введения, пяти разделов и заключения. Содержит 159 страниц сквозной нумерации, в том числе 152 основного текста, список использованных источников из 123 наименований на 7 страницах и иллюстрирована 57 рисунками.

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

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

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

В четвертом разделе описаны основные этапы разработки автоматизированной системы составления расписания занятий, реализующей разработанные алгоритмы. Описана аппаратная, программная и методические подсистемы. На основе техноло гии клиент-сервер разработана база данных (БД), позволяющая вводить, хранить и редактировать исходные данные и все необходимые требования и ограничения. По принципам, описанным в предыдущих разделах, разработан модуль анализа исходных данных и модуль составления расписания занятий. Для обеспечения устойчивости получаемых результатов разработан модуль корректировки расписания, позволяющий в автоматизированном режиме осуществлять назначение нерасставленных занятий и производить корректировку расписания. Разработанная система составления расписания является подсистемой информационной системы учебно-методического управления (ИС УМУ), комплексно автоматизирующей подготовку и планирование учебного процесса.

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

Результаты диссертационного исследования:

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

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

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

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

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

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

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

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

Достоверность результатов диссертационного исследования определяется:

- корректным использованием математического аппарата системного анализа, теории множеств, нечеткой логики и нейронных сетей;

- результатами практического применения автоматизированной системы для составления расписания занятий в БГТУ «ВОЕНМЕХ» им. Д.Ф.Устинова в течение двух лет.

Практическая ценность результатов диссертации состоит в следующем:

1. На основе полученных в диссертации результатов построена и внедрена в эксплуатацию автоматизированная система составления расписания занятий в высшем учебном заведении.

2. Эксплуатация автоматизированной системы в БГТУ «Военмех» им.

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

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

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

Результаты диссертационного исследовании внедрены в процесс планирования и подготовки учебного процесса в БГТУ «Военмех» им. Д.Ф. Устинова, а также в учебном процессе при проведении лекционных, практических и лабораторных занятий.

Апробация работы. Основные результаты диссертационного исследования докладывались и обсуждались на X международной конференции «Региональная информатика - 2006» и на семинарах кафедры «Систем обработки информации и управления» БГТУ «Военмех» им. Д.Ф. Устинова.

Публикации. Самостоятельно и в соавторстве по теме диссертации опубликовано 13 работ, в том числе 6 статей из которых 1 в рецензируемом журнале, 2 тезисов докладов на международных научно-технических конференциях, получено 5 свидетельств об официальной регистрации программ для ЭВМ [12, 13, 14, 15, 16].  

Подобные работы
Швецов Анатолий Николаевич
Модели и методы построения корпоративных интеллектуальных систем поддержки принятия решений
Дамбаева Сэсэгма Викторовна
Модели и методы принятия решений задачи формирования учебного плана специальности в условиях неопределенности
Медникова Оксана Васильевна
Методы, модели и алгоритмы принятия решений о состоянии здоровья студентов в зоне действия неблагоприятных экологических факторов
Ефремов Михаил Александрович
Разработка методов и средств прогнозирования и дифференциальной диагностики остеохондрозов поясничного отдела позвоночника на основе нечетких моделей принятия решений
Ходеев Денис Владимирович
Разработка методов, моделей и алгоритмов прогнозирования и донозологической диагностики кожных болезней, имеющих представительство на проекционных зонах, с использованием нечеткой логики принятия решений и рефлексодиагностики [Электронный ресурс]
Сорокина Марина Игоревна
Разработка моделей, методов и средств решения комплекса задач управления персоналом
Нгуен-Ань-Чинь 0
Разработка методов решения задач векторной оптимизации по неточным моделям
Секаев, Виктор Гилячевич
Модели и методы планирования загрузки оборудования участка ГПС при решении задач оперативного управления
Шилов Николай Германович
Разработка моделей для интеллектуальной поддержки принятия решений при конфигурировании виртуальных предприятий
Королев Антон Сергеевич
Модели и алгоритмы интеллектуальной поддержки принятия решений при создании открытых информационных систем

© Научная электронная библиотека «Веда», 2003-2013.
info@lib.ua-ru.net