Содержание к диссертации
Введение
1 Анализ задачи и средств ее решения 15
1.1 Общая характеристика задачи 15
1.2 Обзор существующих средств решения 21
1.3 Обзор методов решения 27
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 CLASS
3 Разработка метода решения задачи 62 CLASS
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].
Математическое программирование
Основы теории расписаний развивались в то время, когда математические модели начали применяться для решения экономических задач. Были предприняты попытки построить математические модели и для задач ТР. При этом столкнулись с трудностью следующего рода. В математической модели система ограничений отражает то положение вещей, что некоторая совокупность условий должна выполняться совместно. В задаче ТР ряд условий должны выполняться альтернативно: или і-я работа запускается раньше у-й, или наоборот.
Рассмотрим формулировку общей задачи составления расписания в терминах линейного программирования [1, 35].
Пусть имеем систему из п работ и т машин. Каждая работа состоит из g. операций. Каждая операция имеет три индекса: /-номер работы, содержащей эту операцию; у-номер операции внутри работы,/ =1,..., g. ,
Аг-номер машины, на которой операция должна выполняться. Ограничения на время и порядок выполнения операций машинами таковы: - каждая машина выполняет одновременно не более одной операции; - операции выполняются в указанной последовательности; - никакие две операции, относящиеся к одной работе, не выполняются одновременно. Для упрощения изложения и обозначений примем, что каждая работа требует в точности одного выполнения на каждой из машин \gj=m,i=l,.,.,п). Пусть /., - длительность выполнения работы / машиной к; ijk 1, если операция j работы і выполняется машиной к, О, в противном случае; toe - момент начала выполнения работы / машиной к (равно началу выполнения соответствующей операции работы / машиной к). Из невозможности выполнения машиной в один момент времени более одной работы, следует, что для каждой пары работ /и J выполняется лишь одно из неравенств: tik tjk = / - выполнению работы I предшествует выполнение работы J или (1.1) tlh tjk =t г, - выполнению работы J предшествует выполнение работы I. Такое ограничение типа «или-или» нельзя описать в рамках обычного линейного программирования и требуется введение некоторых целочисленных переменных. Пусть Ґ1, если работа I предшествует работе J на машине к, [О, в противном случае. Теперь сформулированные выше ограничения типа «или-или» можно записать в виде двух условий, каждое из которых должно быть выполнено: (м +tJk)YIJk +(tIk -іЛ) =іл, (1.2) (М +tIk)(l -YIJk) + (tjk jk) =tIk, (1.3) где M = Yjtik - достаточно большая константа, выбранная так, чтобы выполня-( к лось только одно из двух условий: YJT, = О или Г, „ = 1.
Пусть / предшествует J, то есть tjk tik и YJJk = 1, тогда (1.3) в точности совпадает со вторым условием «или-или» в (1.1), а (2.1) благодаря большому параметру М превращается в избыточное ограничение, не противоречащее всей системе в целом.
Рассмотрим ограничения на порядок выполнения операций.
Классическая ТР рассматривает последовательную обработку операции машинами [88]. В расписании учебных занятий для выполнения операции требуется одновременно несколько машин (группы, преподаватели и аудитории, рассматриваются как машины, а учебные занятия как операции). Этот факт не позволяет отнести рассматриваемую задачу к классу простых задач теории расписаний и воспользоваться разработанными в настоящее время методами. Если допустимо одновременное выполнение операции несколькими машинами, неравенство 4 не является достаточным для исключения накладок на машины. Для определения занятости машины требуется введение дополнительной переменной. Пусть Ґ1, если машина к свободна в момент времени t, [О, если машина к занята в момент времени t.
Тогда возможность выполнения операции в заданное время можно определить следующим образом: f=bufbk2fbk3t Как видно, учет необходимости одновременного выполнения операции несколькими машинами приводит к возникновению нелинейных ограничений и не позволяет применять методы линейного программирования. Задача составления учебного расписания является дискретной, так как занятия можно планировать только в строго заданные промежутки времени.
Кроме того, составление учебного расписания является многокритериальной задачей. Например: минимизация количества окон в расписании групп и преподавателей, минимизация количества переходов из корпуса в корпус для групп и преподавателей, максимум соблюдения неформальных пожеланий преподавателей, оптимизация- (по различным критериям) использования аудиторного фонда. Объединение всех этих критериев в один комплексный критерий недопустимо [96].
Формализация задачи на основе аппарата теории множеств
На практике не всегда удается получить даже одно допустимое решение при учете всей совокупности характерных ограничений. Приходится отказываться от учета отдельных ограничений. В этом случае говорить о применении представленных выше критериев оптимальности нецелесообразно. Полученный вариант решения можно оценивать по количеству неудовлетворенных требований.
Если применить рассмотренную модель к задаче составления расписания учебных занятий в ВУЗе, то специализированные машины терминологически заменяются на преподавателей и группы, универсальные машины заменяются на аудитории, а операции на учебные занятия.
Рассмотрим средний ВУЗ с количеством занятий 10000, количеством преподавателей 1000, количеством групп 500, количеством аудиторий 300, цикл обучения состоит из двух недель (78 интервалов времени). Произведем оценку размерности системы.
Количество переменных группы (2.1) - 780 000, группы (2.2) 3 000 000, группы (2.3) - 1 170 000 000, группы (2.4) - 234 000 000. Количество ограничений (2.8) -10 000, (2.9) - 117 000, (2.10) - 23 400. Видим, что задача имеет очень высокую размерность, количество ограничений измеряется сотнями тысяч. На практике с такой высокой размерностью не в состоянии справиться ни один из известных методов, даже не говоря о критериях оптимальности.
Необходимо искать эвристический метод, основанный на принципе упорядочивания операций и усечении вариантов перебора путем поиска наилучшего времени выполнения операции. Перейдем к разработке требуемого метода на основе выбранной практической задачи - составления расписания учебных занятий в ВУЗе. 2.2 Формализация задачи на основе аппарата теории множеств
Введем основные множества, характеризующие предметную область. Совокупность этих множеств будет представлять собой исходную информацию. Впоследствии на уровне реализации алгоритмов множествам будут соответствовать списки объектов [72].
Основные множества: P = {Pi} - множество преподавателей, i=\..kP - соответствует списочному составу преподавателей университета; D = { „} - множество дисциплин, n=\..kD - соответствует полному перечню учебных дисциплин университета, занятия по которым должны быть включены в расписание наступающего семестра; Di = {Di„} — множество лекционных занятий, п—\..кщ — соответствует полному перечню лекционных занятий по названным выше дисциплинам; D2 = {D2n} — множество практических занятий, n=\..kD2 — соответствует полному перечню практических занятий по названным выше дисциплинам; D3 = {Д?и} — множество лабораторных занятий, п=1..к,з, — соответствует полному перечню лабораторных занятий по названным выше дисциплинам.
Введем константу kf=3, определяющую количество различных типов занятий (лекционные, лабораторные, практические).
Множество дисциплин представляет собой объединение множеств лекционных, практических и лабораторных занятий: {Dn}={Dln}Kj{D2n}Kj{D3n}, (2.29) а количество элементов данного множества определяется как kD=kDl+ kD2+ kD3. (2.30)
Понятие «учебная дисциплина», используемое в настоящей работе, определено в подразделе 1.1. Учебная дисциплина определяется тремя признаками: дисциплина, тип занятия и преподаватель. Z = {Zn} - множество учебных дисциплин; n=\..kz, G = {Gk} - множество групп; к=1..кс Множество учебный план. Содержит все учебные занятия всех групп. Y= {Yi} —множество всех учебных занятий; 1=1. .ку, где ку— общее количество всех учебных занятий для всех групп в учебном плане; Yi = (} - множество всех учебных занятий для группы к, где к— номер группы; 1=\..куь где &№- количество всех учебных занятий группы к.
Используя введенные ограничения запишем формулы, связывающие множество учебный план с множеством учебных занятий для групп:
Первая формула показывает, что множество учебный план состоит из объединения всех множеств - учебных планов конкретных групп. Таким образом мы видим, что множества учебных планов групп являются подмножествами множества учебный план.
Вторая говорит о том, что количество элементов в множестве учебный план складывается из количеств элементов подмножеств — учебных планов конкретных групп. S = {Sr} - множество потоков; r=\..ks, SGr= {SGrk} _ множество групп в потоке г; k=l..kSGn Szn = {Szm} — множество учебных дисциплин в потоке г; n=\..kszn А = {Ат} - множество аудиторий; т=\..кА, Ai = {Aim} —множество аудиторий для лекционных занятий; m=l..kA], Аг = {А2т} — множество аудиторий для практических занятий; m=l..kA2., A3 = {Азт} — множество лабораторий; т=\..кАз
Последовательный метод составления расписания
Предлагаемый метод составления расписания занятий предусматривает поочередную расстановку в расписании занятий по мере убывания предварительно рассчитанных коэффициентов сложности. Каждое очередное занятие назначается на наиболее подходящее место.
После назначения каждого занятия производится пересчет приоритетов ячеек расписания. Кроме того, через некоторое количество назначенных занятий осуществляем пересчет коэффициентов сложности оставшихся занятий в очереди. Обобщенная блок-схема предлагаемого алгоритма представлена на рисунке 10.
Назначая занятия, мы заполняем пространство расписания. Данный процесс удобно интерпретировать как построение дерева, узлом которого будет являться ячейка расписания. Каждый узел имеет список возможных направлений раскрытия. Этот список соответствует списку всех возможных интервалов времени (отрезки на оси времени). Количество уровней в дереве равняется общему количеству занятий для расстановки. Пройдя из корня этого дерева до любого листа, мы получим расписание университета. Каждый маршрут от корня дерева к листу даст новый вариант расписания. Задача состоит в построении этого дерева. Предлагается метод обхода этого дерева с возвратом при возникновении тупиковой ситуации.
В настоящей работе применен принцип построения раскрывающегося дерева [38]. Это означает, что дерево строится не все целиком, а вершины раскрываются по мере построения. Выбирается очередное занятие из упорядоченного списка. Из списка возможных направлений раскрытия выбирается наиболее приоритетное и осуществляется раскрытие этого направления, то есть постановка в данный момент времени выбранного занятия. Затем назначается следующее занятие на следующем уровне дерева, для чего также выбирается наиболее приоритетное направление и раскрывается. Попутно осуществляются все требуемые проверки на возможность раскрытия (которые включают в себя все многообразие разнотипных ограничений) того или иного направления. Направления раскрываются до тех пор, пока не будут назначены все учебные дисциплины или на очередном уровне не найдется ни одного возможного варианта раскрытия. В этом случае необходимо выполнить возврат -отменить последнюю постановку и попытаться раскрыть другую вершину. Если все варианты раскрытия на данном уровне будут исчерпаны, то необходимо возвратиться еще на один уровень вверх. Если будут исчерпаны все варианты раскрытия на первом уровне, то при заданных условиях расписание составить невозможно. Если же удастся раскрыть все узлы одной ветви, то эта ветвь будет представлять собой один из вариантов расписания. Порядок обхода дерева показан на рисунке 11. Следует отметить, что применение механизма возврата приводит к частичному перебору в оптимистичном варианте и полному перебору в пессимистичном варианте. Поэтому в данной работе предлагается не применять процедуру возврата, а оставлять занятия нерасставленными, так как наиболее вероятно, что для возможности их расстановки в совокупности с существующей системой ограничений, придется идти на ослабление мешающих расстановке этих занятий ограничений, решение о котором может принимать лишь человек.
Если построить дерево не удалось, необходимо проанализировать начальные условия, снять ограничения, мешающие назначению оставленных нерасставленными занятий и попытаться снова составить расписание. Для минимизации возможности возникновения таких ситуаций в рамках описанной процедуры при назначении очередного занятия целесообразно решать следующие задачи: - подбор наилучшего времени проведения занятия, - подбор наилучшей аудитории для проведения занятия в конкретное время, - пересчет приоритетов ячеек расписания.
Подбор наилучшей аудитории для проведения занятия
При составлении расписания необходимо решить задачу подбора аудитории для проведения конкретного занятия в конкретный промежуток времени. Лекционные и практические занятия требуется проводить в аудиториях общего назначения, а лабораторные работы в специализированных аудиториях. Так как список возможных аудиторий для проведения лабораторного занятия заранее задан, подбор аудитории не представляет сложности. Также при выборе аудитории необходимо учитывать преимущества кафедр на проведение занятий в отдельных аудиториях. По правам использования, аудитории делятся на следующие группы: вузовские аудитории, кафедральные аудитории, кафедрально-вузовские аудитории. В вузовские аудитории допустимо назначать занятия всех без исключения кафедр. Кафедральную аудиторию можно занимать для проведения занятий только тех кафедр, которым разрешено использовать данную аудиторию. Кафедрально-вузовскую аудиторию разрешено задействовать только в случае отсутствия в данное время свободных аудиторий другой принадлежности. Назначая занятие в аудиторию, необходимо учитывать ее вместимость (количество посадочных мест). Преподаватели имеют пожелания к корпусам, в аудиториях которых им удобно проводить занятия. При составлении расписания необходимо учитывать пожелания преподавателей к корпусу, а также переходы учебных групп и преподавателей из корпуса в корпус.
Таким образом, при выборе аудитории для проведения конкретного занятия необходимо руководствоваться следующими критериями: вместимость аудитории, пожелание преподавателей к корпусу, переходы из корпуса в корпус для групп и преподавателей. В простейшем случае имеем четыре критерия выбора аудитории: вместимость, пожелание преподавателя, переходы учебной группы и переходы преподавателя. В случае проведения занятий в потоке необходимо учитывать переходы для всех групп потока.
Разработка структуры автоматизированной системы составления расписания занятий
Разрабатываемая автоматизированная система следующую основную цель функционирования - на основе сбора данных от большого количества пользователей и их обработки составить расписание занятий в соответствии с требованиями из подраздела 1.1.
Система должна быть многопользовательской с разграничением прав доступа и функциональных возможностей. Процесс работы с системой должен регламентироваться руководящими документами, руководствами пользователей. Действия пользователей должны быть согласованы между собой организационно и синхронизированы технически. Одновременное редактирование рабочих учебных планов и работа с расписанием, даже если эти действия производятся разными пользователями с разных клиентских мест, должны синхронизироваться между собой во избежание потери логической целостности данных. При синхронизации необходимо производить целый ряд проверок согласно бизнес процессам предметной области. Например, нельзя создавать учебный поток для дисциплины, если эта дисциплина сохранена в расписании хотя бы для одной группы. Это не нарушит ссылочной целостности данных, но приведет к потере логической целостности.
Система должна иметь иерархическую структуру и состоять из следующих подсистем: аппаратной, программной и методической. Структура автоматизированной системы показана на рисунке
Аппаратная подсистема обеспечивает функционирование автоматизированной системы на уровне оборудования, предоставляя коммуникационные и вычислительные возможности а также средства хранения данных.
Вычислительные возможности предоставляет сервер автоматизированной системы составления расписания. На сервере же осуществляется хранение всех необходимых данных и обработка запросов пользователей на доступ к необходимым данным. В качестве сервера желательно использовать высокопроизводительный компьютер с широкими вычислительными возможностями. Сервер должен обеспечивать надежное хранение данных с возможностью их резервирования и быстрый доступ как на чтение так и на запись. Для обеспечения надежной работы требуется обеспечить надежное и стабильное питание сервера и укомплектовать его источником бесперебойного питания. Для быстрой обработки данных сервер должен иметь высокопроизводительную процессорную систему с одним или несколькими центральными процессорами и достаточный объем высокоскоростной оперативной памяти. Объем оперативной памяти и скорость доступа к ней очень существенно влияют на производительность всей системы в целом [4]. Для обеспечения возможности сетевой работы серверный компьютер должен быть оборудован сетевым оборудованием.
На стороне клиентов установлены персональные компьютеры, осуществляющие диалог с пользователем, организующие на аппаратном уровне запрос к серверу.
Также на стороне клиентов производится ряд некритичных проверок, которые требуются для корректного отображения информации и правильной организации запросов. К вычислительным возможностям клиентских компьютеров особых требований не предъявляется. Все клиентские машины должны быть оборудованы сетевым оборудованием.
Программная подсистема представляет собой набор программных модулей, работающих в совокупности друг с другом, направленных на реализацию требуемых функциональных возможностей системы [8, 60].
Требования, предъявляемые к подсистеме можно классифицировать следующим образом. Основные хранимые данные: - группы с указанием формы обучения и количества человек; - учебные планы групп; - профессорско-преподавательский состав; - рабочие учебные планы; - аудиторный фонд; - распределения учебных поручений по кафедрам; - пожелания к расписанию; - режим работы ВУЗа, аудиторий, преподавателей; - режим обучения форм обучения. Основные функции: - введение и корректировка учебных планов и дисциплин; - продвижение групп; - расчет нагрузки преподавателей; - формирование рабочих планов групп из учебных планов; - формирование учебных поручений кафедр; - заполнение учебных поручений кафедр; - составление расписания занятий; - составление расписания экзаменов; - просмотр расписания; - работа с профессорско-преподавательским составом; - ввод и редактирование пожеланий преподавателей; - контроль учебного процесса; - утверждения расписания.
Программная подсистема отдела расписаний должна иметь общую базу данных, хранящуюся на сервере, обеспечивать многопользовательский доступ с предоставлением данных и функциональных возможностей в соответствии с правами пользователя.
Таким образом, должно быть серверное программное обеспечение, которое анализирует запросы пользователей и выдает им данные в соответствии с их правами и клиентское, которое обеспечивает возможность работы пользователя с этими данными. Общая структура системы показана на рисунке 22.
Целесообразно выделить рабочие места (РМ) кафедры, начальника УМУ, диспетчера и учебного отдела. Для учебного отдела и диспетчера возможно создание нескольких РМ предназначенных для работы отдельных сотрудников с различными частями системы.
