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

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

Семенюта Ирина Сергеевна

СИСТЕМНЫЙ АНАЛИЗ И ОПТИМИЗАЦИЯ ТЕХНОЛОГИЧЕСКОГО

ПРОЦЕССА АВТОМАТИЗАЦИИ СОСТАВЛЕНИЯ РАСПИСАНИЯ ЗАНЯТИЙ ВУЗА С ДЕТЕРМИНИРОВАННЫМИ ОГРАНИЧЕНИЯМИ

Специальность: 05.13.01 - Системный анализ, управление и обработка информации (информационные и технические системы)

АВТОРЕФЕРАТ

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

Л 2 ЯНВ 2012

Краснодар - 2011

005007734

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

Научный руководитель:

Официальные оппоненты:

I.

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

доктор технических наук, профессор Лойко Валерий Иванович;

кандидат технических наук, профессор Бухонский Михаил Иванович

Ведущая организация: Военный учебно-научный центр

военно-воздушных сил Военно-воздушной академии им. Н.Е. Жуковского и Ю.А. Гагарина (филиал г. Краснодар)

Защита диссертации состоится 18 января 2011 г. в 16.00 часов на заседании диссертационного совета Д 212.100.04 в Кубанском государственном технологическом университете по адресу: г. Краснодар, ул. Московская 2, ауд. Г-251.

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

Автореферат разослан « 3 » декабря 2011 г. Ученый секретарь

диссертационного совета Д 212.100.04, //

канд. тех. наук, доцент ч Жи^Г A.B. Власенко

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

Цель и задачи исследования. Целью настоящей работы является разработка методического аппарата для проектирования АИС СРЗ ВУЗа. В связи с этим решены следующие задачи исследования:

- разработка методики системного анализа информационной среды ЛИС СРЗ с детерминированными ограничениями;

- разработка методики оптимизации технологического процесса АИС СРЗ ВУЗа;

- разработка методики проектирования базы данных для АИС СРЗ ВУЗа;

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

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

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

1. Разработана методика системного анализа модели предметной области базы данных АИС СРЗ ВУЗа.

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

3. Разработана методика ранжировки критериев выбора альтернатив размещения учебного занятия.

4. Разработана методика проектирования оптимальных структур баз данных информационной среды ВУЗа в объектно-ориентированном виде.

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

6. Разработана АИС СРЗ с различными детерминированными ограничениями.

Практическая ценность работы заключается в реализации и использовании разработанных методик в учебном процессе ВУЗа при

проектировании баз данных АИС СРЗ и исследования эффективности их применения.

Реализация результатов работы. Методика выбора альтернатив размещения учебных занятий использована в Армавирской государственной педагогической академии при составлении автоматизированного расписания ВУЗа; а также в организации учебного процесса Кубанского государственного технологического университета. Апробация работы.

Результаты работы докладывались и обсуждались на 8 конференциях: XV Юбилейная Всероссийская научно-практическая конференция «Инновационные процессы в высшей школе», (г. Краснодар, 2009 г.).

Международная практическая научная конференция «Технические и технологические системы» (г. Краснодар, 2009 г.).

VII Международная научно-практическая конференция «Экопром 2009» (г. Санкт-Петербург, 2009 г.).

Международная научно-практическая конференция «Современные направления теоретических и прикладных исследований 2010» (г. Одесса,

2010 г.).

Межвузовская научно-практическая конференция «Автоматизированные, информационные и электроэнергетические системы» (г. Краснодар, 2010 г.)

Международная научно-практическая конференция «Научные исследования и их практическое применение. Современное состояние и пути развития 2010» (г. Одесса, 2010 г.).

Международная научно-практическая конференция «Перспективные инновации в науке, образовании, производстве и транспорте» (г. Одесса,

2011 г.).

Международная научно-практическая конференция «Современные телекоммуникационные системы и компьютерные сети: перспективы развития» (г. Санкт-Петербург, 2011 г.).

Получено два акта об использовании результатов диссертационного исследования при организации учебного процесса в двух ВУЗах.

Публикация результатов работы. По теме диссертации опубликовано 13 печатных работ, из них 3 статьи - в рекомендуемых ВАК: изданиях, получено 6 свидетельств о государственной регистрации программы для ЭВМ.

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

- методика системного анализа и описания предметной области информационной среды ВУЗа;

- теоретико-графовая модель предметной области информационной среды ВУЗа;

- методика нормализации информационных структур баз данных информационной среды ВУЗа;

- методика проектирования оптимальных структур баз данных информационной среды ВУЗа в объектно-ориентированном виде;

- методика оптимизации составления автоматизированного расписания;

- оценка экономического эффекта от внедрения методического аппарата для разработки базы данных АИС СРЗ ВУЗа.

Структура и объем диссертации. Диссертационная работа состоит из введения, четырех глав, заключения и двух приложений, изложенных на 125 страницах. Работа содержит 23 рисунка, 24 таблицы и библиографию из 89 наименований.

КРАТКОЕ СОДЕРЖАНИЕ ДИССЕРТАЦИИ

Во введении. Обоснована актуальность темы диссертации, научная новизна и практическая значимость, сформулированы цель и задачи работы, рассмотрены предпосылки создания научно-методического аппарата для разработки базы данных АИС СРЗ ВУЗа.

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

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

В зависимости от способа задания заявок на обработку в ЛИС СРЗ, решением задачи составления расписания могут быть либо оптимальное размещение работ с учетом ограничений, либо определение приоритетов очередности выполнения операций. То есть, модели теории расписаний можно разделить на два класса. К первому классу моделей теории расписаний относят такие, в которых множество работ, операций и их характеристик считается полностью заданным к нулевой точке отсчета системного времени. Цель данного вида моделирования - оптимальное размещение работ и дисциплин в рамках конкретного расписания с учетом установленных ограничений. Модели первого класса более эффективны для решения нормативных (плановых) задач календарного планирования, задач управления на конкретных объектах. Во втором классе моделей теории расписаний номенклатура и моменты поступления на обслуживание конкретных работ и операций представлены потоками событий (заявок) и заданы вероятностными законами распределения. При этом целью моделирования является определение приоритетов очередности выполнения работ и операций (обслуживания заявок) при заданных параметрах потока и объекта управления. Модели второго класса следует использовать для решения дескриптивных задач управления в целях изучения и системного анализа протекания технологических процессов и выбора оптимальных характеристик объекта исследования. Кроме того, для исследования модели календарного планирования второго класса можно применить математический аппарат теории массового обслуживания.

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

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

Рисунок 1.1 - Структурная функциональная модель информационной

системы ВУЗа

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

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

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

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

Используя методику системного анализа была разработана теоретико-графовая модель предметной области базы данных ЛИС СРЗ ВУЗа. Модель предметной области в задаче составления расписания занятий может быть представлена в виде совокупности семи множеств:

М,1р0 = <Р,Н,Р,0,Увх,У»",хД>) (2.1)

где Г = =/,// - множество пользовательских функций; //=///(|/'=/,.// -множество задач обработки данных; 0={от\т = I,М / - множество объектов автоматизации; Р = {рк\ к = \,К} - множество пользователей; V"4 = Iе } - множество входящих данных;К""'Л =/у/|/е Ькых} -множество выходных данных; V = V" и У'""* - полное множество информационных элементов предметной области; Я = {г^у=1,У} -множество отношений (взаимосвязей) между компонентами Мвр0 = <Р,Н,Р,0,У",У,нх,К>.

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

компонентами предметной области. Элементы данных матриц равны I, если между соответствующими компонентами имеется отношение (взаимосвязь), и равны 0, в противном случае. На следующем этапе выделяется отношение г(0, V) - отношение «объекты - информационные элементы». Далее необходимо построить полное множество структурных элементов предметной области О. Оно образуется путем объединения множеств информационных элементов К, объектов автоматизации О и соответствующей индексации полученного множества й.

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

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

= /,(*„)>-/¡(хь)}- (2.2)

Выражение (2.3) определяет подмножество критериев, по которым ха эквивалентно лт,.

1"(х„.хь) = {1:/,(ха)*/,(хь)}. (2.3)

Выражение (2.4) определяет подмножество критериев, по которым X/, предпочтительнее хп.

Г(ха,хь) = {1: Ыха )■<])( хь)}. (2.4)

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

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

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

Упорядочение информационных элементов по уровням иерархии производится на основании матриц смежности и достижимости. Под матрицей семантической смежности В = Ц Ьу || понимается квадратная бинарная матрица проиндексированная по обеим осям множества структурных элементов йк и содержащая запись Ьц = I, если на основании информации пользователей о семантической связности элементов между структурными элементами ¿У, и сосуществует отношение Я такое, что элемент с/, составляет (расширяет, дополняет и т.д.) смысловое содержание элемента с/, и Ьу = 0 - в противном случае. Изображение матрицы В = || /),, || приведено на рис. 3.1.

Матрице В ставится в соответствие граф информационной структуры (¡(О. С), множеством вершин которого являются структурные элементы множества Д а дуга (с/, , ^) соответствует записи = !, в матрице Вк. Таким образом, дуги орграфа О отражают наличие или отсутствие семантической связности между структурными элементами. Изображение орграфа О представлено на рисунке 3.2.

Под матрицей достижимости А (рисунок 3.3) понимается квадратная бинарная матрица, проиндексированная одинаковым образом по обеим осям

V

10СКХ>С>К)СО000С<ХКХХЧ>ЗОСК>>0(>Э00|3

ооосфооосоооск!юооооо1с<>ооооо0оо оооооо 1 ос<юооосхх>эоооос-с-ооооооо оооооо ] ооосююе<ххш>оооооо<^

000000! СУ>!>ОООООООООС<КХХШХХХ>Э СООООО1 <Х<ЮОСУ}УХ/ХХ>У>ЭЭС<}СОООО

оооооо 1 сооооо<х:юоос<хч:>сос<к>оооо «хюос^хххшххэоссоо \ оооооосюоо СООСООООСЮСО 3. оооооскхххкххюоооо оооооооооооо 1 ооооооот оооооооооэ оооооооооооо 1 О<хуу;нуухухюосоууэ оооооооооооо юэоооооооооооооооо

ОООООООООООО 3 ООООООООСОООООООСО ОООЭСООСОООО 1 ОЭСССОЭОСОСЮОООООЭ СОС^т^ХХХОООСФ^ Гц"Х)СЮ£У.>|ХХУХХйХКХ>00010<)00000000

СОООООООООООСООООООО1 ахюдоохо соо<>схх)соооооог«оооо1 сосооосюоо 1 оооооооооо ЭОСЖСООССЪЮОСОСШ) 1 оооооеоооо

00000 10с000сюс<х<хэс<50000<хз00000

000001 схэоооосшхюо^гт^озсо СОООСЮОСОХСОСОООООО 1 охоскххзоо

оооооооооо

\

У

Рисунок 3.1 - Матрица семантической смежности В = || Л,у

0000000 Рисунок 3.2- Граф С информационной структуры

А=

05»м00000ОСОООООООЗ1СЮ009ЖХШЧ

1 есосос<*эоооскх>соос<> з эсоооооооо 1сю0000&30<»0с000000330000<:><м09 1ОСООСООООООООООООС013000000000 !<ух>с00000000000<>с1003^0с0000000 ОООСОООООООООООСОООО1 ОООЭОСОООЭ оооооо з соосооеоооооо 1 ооокоосоо 0000м10сю00«»0<>с0010«»3с00с0

000000 I соооооооооеоо 1 &ос<х>хкх»

0000001 ООООООООООООО1 оооог^оооэ

000000 1ооооооооосс<» юоохсоооа

СЮОООаЮТОСтдаООООЗМОСКдаООЭ оооосооооооо 1 сжюэоо 1 оооскеткоо оо<»сюосо0оа1ссоа>эо1оооой%0оо

0000000000001 С*УХХХЮ 10500000000 ОООООООСОССО1СОСОООО ЛХ500000300 ОйОООМОООООЮООООООЮвОООООООЙ СОООССОСОООО1 ООООК» 1 осоосооооо ок>э<>ооооооо1скюоо<>01соеосооооо ООООООООООООЗООООЙЗО1 ООООЙХХХ» ООООООСдаХХХЗООСОССО 1 мдасооосо 030000000000000000001£>жх>к>0а00 000000000?С0000050031 оолозооосо

оро>хосоооох'>!х>оооо 1 сооооооххз оатмсосюоскхюоаэооозсооссоооад ООООСКХЮОООООООСКХИО! ОСОООМООО оооооюсоосоосооосоонххюоооосо 1! оозо 1 осохогооохоо з оосос ооооо '1ЮСО9ЭОО0ОС60ОО0О£ОО10000000000

оозос<юоодаооооста>о10о<>?:>ооозо/

Рисунок 3.3 - Матрица достижимости /I

множества структурных элементов О . Запись я,у = I матрицы соответствует наличию или смь!слового отношения достижимости /?о элемента <г/, из элемента с/,', с/ДД. При этом считается, что элемент с^ семантически достижим из элемента ¿/„ если на графе й существует путь от вершины к вершине (¡¡, имеющий определенное смысловое содержание. При этом отношение достижимости удовлетворяет условию транзитивности, т.е. если с1Д„с1„ и с1„Я„с]'¡, то '../, " I. 2, ..., Р(0).

Матрица А дает возможность определения множества предшествования С((]() и достижимости /'Т<яУ V Множество С((1Ц формируется из элементов, соответствующих единичным записям в 1-м столбце, а множество Р((1) - из элементов, соответствующих единичным записям в 1-й строке матрицы А. Анализ множества С(с/,) позволяет выделить базовые типы структурных элементов - информационные элементы и группы. Информационным

элементам соответствуют те структуры, для которых С(с1,)-0. На графе О им соответствуют висячие вершины.

Для определения информационных элементов необходимо

Р(П)

просуммировать элементы каждого столбца/ матрицы А. Если =^ то /'-й

элемент структурного множества является информационным. В противном случае структурный элемент является групповым элементом (группой). В данном случае имеем выражения (3.1) и (3.2):

Л' Л' .и .12 .12

Ха-2 =••■= = 1% =•••= !>//<=.•• =2>ш = /■=/ /-/ /=/ / = / /'=/

32 .¡2 V .V

= X <•!, „ = ... = X = ¿С/.?; = ¿»/.и = 0

»'=/ /=/ Ы! 1=1

Ь'п > 0.1 а,в > 0. Х«,.7 > 0, £апз > 0, > 0, £аш > 0 . (3.2) /=/ /=/ ;--=/ ;=/ ;=/ ¡=;

Пусть множество информационных элементов обозначается через О":

= {^2 ~^з/'^а:)■ (3.3)

Множество групп О' определяется из выражения:

О'' = О \ Бд = {<*,. , ¿7. </„. с121, с! т}. (3.4)

С целью упорядочения групп по уровням иерархии в матрицей выделяется подматрица (удалением индексов элементов множества О''), А = || а' ¡,- || (рисунок 3.4), где а у = 1 при наличии связи между группами е С.

1 6 7 13 2Д_

1 0 0 0 0 1 0

6 1 0 0 0 1 0

7 0 0 0 0 1 0

13 0 0 0 0 1 0

7.1 0 0 0 0 0 0

30 0 0 0 0 1 0

Рисунок 3.4 - подматрица А

Матрице А соответствует подграф графа С . Изображение графа б представлено на рисунке 3.5.

Группа (/:' 6Е принадлежит множеству групп верхнего уровня р,, если Р(с1:)ПС(с/:')=Р(с1/:). Принадлежность остальных групп уровням иерархии р„„ т>2 определяется итеративным образом из соотношения (3.5):

л„,=К'е о; \р,\...\р,„.,№„,_,((!■:ю ст./(с1:)= (3.5)

Проанализировав множества предшествования и достижимости можно сделать вывод, что в данной предметной области верхний уровень иерархии представлен группой с/21 «Учебное занятие». Упорядоченный по иерархии граф представлен на рисунке 3.6:

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

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

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

отношений: Т = {/,,...,/■„} - «Преподаватели», где /,• - код /-го преподавателя, /</<)!. УУ = {IV,,....IV,-}, 1 = 1.„б - «Дни недели». Н = {/;,„..,/;,}, 1-1,..,6 -«Учебные часы». О = - «Дисциплины», где с1/ - код 1-го

преподавателя, 1<1<т. С = {&/.....} - «Группы студентов» (каждый элемент

^.представляет собой целочисленное множество - количество студентов в

группе). А = {а,.....а,.} - «Аудитории» (каждый элемент аг представляет собой

также целочисленное множество - вместимость аудитории под номером /•). Отношения между элементами приведенных выше множеств можно представить в виде следующих булевых матриц.

I. Матрица <7(/ = ¡<?,«■„>!• Отношение «У группы gk под номером к есть в соответствии с учебным планом дисциплина <1т под номером ш».

( / ¿2 ■ • ■ <1т ^

8 >8,111 8,11! 8,11т

82 8,/ и 8,1:; "' 8<!2т

(4.1)

у£к8,1к1 8м: 8лкт ,

1, у группы иод номером к есть дисциплина т

гДе ё.1кт = 1Л

[О и противном случае. 2. Матрица =|{«,/„„|. Отношение «Аудитория а,, по специализации подходит для проведения дисциплины </„,».

( <11 (,2 Лт

Ал = а<т а(/2т

(4.2)

где

1, аудитория подходит, О в противном случае.

Аналогично определяются остальные булевы матрицы отношений:

3. Матрица =|акг/[|. Отношение «Аудитория иг вмещает группу ^ ».

4. Матрица С,„=||£1И(7-||. Отношение «У группы Яа под номером к есть занятия в день недели щ ».

5. Матрица Тл = ||/,/,„„||. Отношение «Преподаватель 1П ведет дисциплину

6. Матрица ГИ1 = ||/ш)/1|. Отношение «Преподаватель ¡п работает в день недели н';».

В соответствии с Федеральным Государственным образовательным стандартом аудиторная нагрузка студента составляет 36 часов в неделю при 6-дневной нагрузке. Используя множество учебных часов Н = [к,,..../(/}, I = 1....6 и полученные булевы матрицы отношений (1)-(6) составим булевы матрицы соответствия отношения каждому учебному часу. Матрица определяет отношение «У группы £д под номером к есть в соответствии с учебным планом дисциплина с1т под номером т в конкретный час /».

Ч// 4/2 Чм*,я

СМ = /Ь б,!/,,/ (>М22 ''' С</1,2к*„11

(4.3)

6(Ш2 ■■■ С1М1к*т

Аналогично для каждого часа занятий составляются остальные матрицы Ам.А^.С^.Тм.Т»,,. Тогда блочная матрица-столбец 2 определяет все

возможные состояния конкретного занятия в конкретный час:

(г \ Ч//;

Z =

Л/л 4gl:

J\vh

Ldk

(4.4)

т

V 1 Н'Л У

Учебное занятие может состояться только тогда, когда элементы матрицы X равны I. Все элементы матрицы Z являются блочными булевыми матрицами, содержащими по 6 строк и различному количеству столбцов.

Представим множество дней недели IV = {ну.....и-;} в виде матрицы строки:

IV = (ту, и', и», и>4 и'5 ну,). Для нахождения плановой аудиторной нагрузки студента следует перемножить матрицы 2 и IV, в результате получится блочная матрица '¿\\г\

V*

Juh

'dh

V Tvl,

W = (w, W, W, w4 W; W(j) =

ZW ■■

G,lhwl Gdhw2 Gdl,w3 Gdhw4 Gdl,wS Gdhw6

(4.5)

A ,„, и

¡11, "7

Adhw2 Adl,w3 AJhw4

A M и

ilh " 5

Adhw(,

Aghw! Aghw2 Aghw3 Aghw4 AghwS Aghw6

Gui,"'i G»hw2 G,,hw3 GKhw4 Gwh\V; Guhw6

T,lhwl. Tclhw2 Tdhw3 Tdhw4 Tdhw5 Tdhw6 KT»-I,WI T»hW2 T*l,w3 T«hw4 T*hw5 T»l,w6 )

Матрицу ZW можно разбить на 6 блочных матриц-столбцов ZWj.i = 1,...,6, каждая из которых будет представлять вариант проведения занятия в день w,- и час ht. Тогда соответствие аудитории А варианту проведения занятия /И' можно представить, перемножив матрицы А (размером

/хл) и 7АУ1 (размером бхб). Результатом умножения является матрица А(размером 1x6). Аналогично соответствие группы (? варианту проведения занятия Щ, определяется матрицей С (размером 1x6). Матрицы А-2\У и С ■ 7ЛУ имеют одинаковые размерности, следовательно, их можно использовать в выражении (4.6) для целевой функции 17( А.С):

А. С,) = А ■ гм - С • гш -> 0. Р(А,О>0. £к < а,.. (4.6)

То есть, для максимальной загрузки аудиторного фонда А = {а,,....аг} необходимо, чтобы разница между вместимостью аудиторий А и количеством студентов в группе С была равна нулю, но учитывать необходимо только те группы, у которых возможно занятие при совпадении всех возможных условий /А¥ и только те аудитории, которые подходят для проведения конкретной дисциплины в конкретный час и день.

Экономическая эффективность от внедрения методического аппарата рассчитывается по выражению (4.7):

К = (4.7)

С/

где С; - предполагаемая трудоемкость создания АСКУЭ без использования методического аппарата; С? - предполагаемая трудоемкость создания АСКУЭ с использованием методического аппарата. При этом расчет трудоемкости производился с использованием выражения (4.8):

С=1С,, (4.8)

1=1

где С, - трудоемкость отдельных этапов работ; п - количество этапов по созданию АСКУЭ. Эффективность полученного методического аппарата составила 24 %.

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

В приложениях представлены листинги программного кода АИС СРЗ, руководство пользователя, акты внедрения диссертационной работы.

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

1. Разработана и внедрена методика исследования, моделирования, анализа предметных областей АИС СРЗ ВУЗа, которая позволяет исследовать и описывать типичные структуры информации в процессе автоматизации организации учебного процесса; строить аналитические, теоретико-графовые модели предметной области типичных АИС СРЗ; проводить анализ полученной модели, выявлять избыточные и противоречивые элементы модели.

2. Разработана и внедрена методика нормализации информационных структур предметных областей АИС СРЗ. Данная методика позволяет выявлять дублируемые структурные элементы и избыточные взаимосвязи между ними.

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

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

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

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

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

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

9. Произведена оценка экономической эффективности использования методического аппарата.

СПИСОК ПУБЛИКАЦИЙ ПО ТЕМЕ ДИССЕРТАЦИИ

1. Атрощенко В.А., Дьяченко P.A., Чигликова Н.Д., Семешота И.С. К вопросу построения автоматизированных систем составления расписаний // Труды XV Юбилейной Всероссийской научно-практической конференции «Инновационные процессы в высшей школе». - Краснодар: Изд. ГОУ ВПО КубГТУ, 2009.-С. 17-21.

2. Атрощенко В.А., Чигликова Н.Д., Коновалов Д.П., Семешота И.С. К вопросу построения оптимальных структур баз данных автоматизированной системы составления расписания занятий вуза // Технические и технологические системы: материалы международной практической научной конференции. - Краснодар: КубГАУ, 2009. - С. 350-354.

3. Атрощенко В.А., Семешота И.С. Обобщенный критерий эффективности задачи принятия решений в системе составления расписания занятий вуза // Труды VII Международной научно-практической конференции Экопром 2009. - Санкт-Петербург: Изд-во Политехи, ун-та, 2009 - С. 451-455.

4. Атрощенко В.А., Семешота И.С. К вопросу совместимости интерфейсов взаимодействия программных средств для обработки данных в объектно-ориентированном виде // Сборник трудов международной научно-практической конференции «Современные направления теоретических и прикладных исследований 2010». Том 2. Технические науки. - Одесса: Черноморье, 2010.-С. 11-13.

5. Атрощенко В.А., Семешота И.С. К вопросу проектирования объектно-ориентированной базы данных вуза для составления расписания // Сборник трудов I Межвузовской научно-практической конференции «Автоматизирован-

ные, информационные и электроэнергетические системы». - Краснодар: Издательский дом - Юг, 2010. - С. 141-144.

6. Атрощенко В.А., Семенюта И.С. К вопросу проектирования автоматизированной системы составления расписаний с учетом приоритетов заявок // Сборник международной научно-практической конференции «Научные исследования и их практическое применение. Современное состояние и пути развития 2010». Том 5. - Одесса: Черноморье, 2010. - С. 55-58.

7. Семенюта И.С., Коляндра А.Г., Ананко Д.С. Анализ существующих систем составления расписаний занятий вуза // Издательство КубГТУ, Сборник трудов факультета КТАС, 2010 - Краснодар.

8. Атрощенко В.А., Семенюта И.С. Разработка алгоритма принятия решений в условиях неопределенности в задаче составления расписаний занятий вуза // Сборник научных трудов по материалам международной научно-практической конференции «Перспективные инновации в науке, образовании, производстве и транспорте». Том 5. Технические науки. - Одесса: Черноморье, 2011.-С. 11-16.

9. Семенюта И.С. Использование метода попарного сравнения в задаче составления расписания // Журнал «Научно-технические ведомости СПбГПУ». Серия «Информатика. Телекоммуникации. Управление». - Санкт-Петербург: Изд-во Политехи, ун-та.-2011.-№3 (126).- С. 151-155.

10. Атрощенко В.А., Семенюта И.С. Предметная область базы данных для автоматизированной системы составления расписания занятий вуза // Современные телекоммуникационные системы и компьютерные сети: перспективы развития / Под ред. канд. техн. наук, д-ра экон. наук, проф. A.B. Бабкина, д-ра техн. наук, проф. В.А. Кежаева: Труды междунар. конф. -СПб.: СПбГАСУ, 2011.-С. 185-193.

11.Атрощенко В.А., Семенюта И.С. Разработка математической модели автоматизированной системы составления расписания / Под ред. канд. техн. наук, д-ра экон. наук, проф. A.B. Бабкина, д-ра техн. наук, проф. В.А. Кежаева: Труды междунар. конф. - СПб.: СПбГАСУ, 2011. - С. 193-201.

12.Семенюта И.С. Исследование эффективности системы составления расписаний методами теории массового обслуживания // Автоматизация и современные технологии. - Москва: Машиностроение.-2011. -№ 10.

И.Семенюта И.С. Методика анализа информационной структуры базы данных автоматизированной системы составления расписаний / И.С. Семенюта // Политематический сетевой электронный научный журнал Кубанского государственного аграрного университета (Научный журнал КубГАУ) [Электронный ресурс]. - Краснодар: КубГАУ, 2011. - № 09 (73). Режим доступа: http://ej.kubagro.ru/2011/09/рс!Г/06.рс1Г

Подписано в печать 07.12.2011. Печать трафаретная. Формат 60x84 '/щ. Усл. печ. л. 1,35. Тираж 100 экз. Закач № 577. Огпечатаио в ООО «Издательский Дом-Юг» 350072, г. Краснодар, ул. Московская 2, корп. «В», оф. В-120, тел. 8-918-41-50-571

e-mail: olfomcnko@yandex.ru Сайт: http://id-yug.narod2.ru

61 12-5/1419

Кубанский государственный технологический университет

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

Семенюта Ирина Сергеевна

СИСТЕМНЫЙ АНАЛИЗ И ОПТИМИЗАЦИЯ ТЕХНОЛОГИЧЕСКОГО ПРОЦЕССА АВТОМАТИЗАЦИИ СОСТАВЛЕНИЯ РАСПИСАНИЯ ВУЗА С ДЕТЕРМИНИРОВАННЫМИ

ОГРАНИЧЕНИЯМИ

Специальность 05.13.01 - «Системный анализ, управление и обработка информации (информационные и технические системы)»

Диссертация на соискание учёной степени кандидата технических наук

Научный руководитель: д-р техн. наук, профессор В.А. Атрощенко

Краснодар-2011

ВВЕДЕНИЕ..............................................................................................................6

ГЛАВА 1 АНАЛИЗ СОСТОЯНИЯ ВОПРОСА АВТОМАТИЗИРОВАННЫХ СИСТЕМ ОРГАНИЗАЦИИ УЧЕБНОГО ПРОЦЕССА ВУЗА..........................12

1.1 Классификация и особенности задач составления расписаний...............12

1.1.1 Классификация моделей теории расписаний......................................12

1.1.2 Классификация задач теории расписаний...........................................13

1.2 Анализ основных методов решения задачи автоматизации составления

расписаний...............................................................................................14

1.2.1 Функциональная модель информационной системы ВУЗа..............14

1.2.2 Решение задачи составления расписания методами линейного целочисленного программирования.............................................................16

1.2.3 Объектно-ориентированный подход к задаче составления расписания.......................................................................................................17

1.2.4 Использование задачи раскраски графа в задаче составления расписания.......................................................................................................19

1.2.5 Генетические алгоритмы в задачах составления расписания..........19

1.3 Современное состояние вопроса существующих автоматизированных

систем составления расписания занятий..............................................20

1. 4 Выводы..........................................................................................................23

ГЛАВА 2 РАЗРАБОТКА МЕТОДИКИ СИСТЕМНОГО АНАЛИЗА МОДЕЛИ ИНФОРМАЦИОННОЙ СРЕДЫ ВУЗА В ЗАДАЧЕ СОСТАВЛЕНИЯ РАСПИСАНИЯ......................................................................................................25

2.1 Разработка основных множеств модели информационной среды ВУЗа 25

2.2 Определение структурных элементов информационной модели............27

2.3 Разработка методики оптимизации составления расписания занятий

ВУЗа..........................................................................................................30

2.3.1 Постановка задачи оптимизации..........................................................30

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

2.3.3 Разработка методики построения критерия эффективности задачи принятия решений в системе составления расписания занятий ВУЗа......41

2.3.4 Разработка методики ранжировки в задаче составления расписаний занятий ВУЗа...................................................................................................43

2.3.5 Исследование процесса выбора альтернатив методом попарного сравнения порогов совместимости...............................................................45

2.3.6 Расчет индексов согласия и несогласия..............................................46

2.4 Выводы..........................................................................................................52

ГЛАВА 3 РАЗРАБОТКА МЕТОДИКИ ПРОЕКТИРОВАНИЯ БАЗЫ ДАННЫХ ИНФОРМАЦИОННОЙ СИСТЕМЫ ВУЗА В ЗАДАЧЕ СОСТАВЛЕНИЯ РАСПИСАНИЯ.......................................................................53

3.1 Разработка методики анализа информационной структуры базы данных

автоматизированной системы составления расписания ВУЗа...........53

3.1.1 Разработка модели предметной области базы данных автоматизированной системы составления расписания ВУЗа...................53

3.1.2 Формирование матриц смежности и достижимости, построение соответствующих им графов.........................................................................57

3.1.3 Упорядочение групп информационных элементов по уровням иерархии...........................................................................................................60

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

данных......................................................................................................63

3.2.1 Разработка методики нормализации информационных структур базы данных автоматизированной информационной системы составления расписания.......................................................................................................63

3.2.2 Выявление дублируемых элементов информационных структур....66 3.2 3 Исследование информационных структур на избыточность............67

3.3 Разработка автоматизированной информационной системы составления

расписания занятий ВУЗа.......................................................................69

3.3.1 Разработка методики проектирования объектно-ориентированной базы данных автоматизированной системы составления расписания занятий ВУЗа...................................................................................................69

3.3.2 Обеспечение совместимости интерфейсов взаимодействия программных средств для обработки данных в объектно-ориентированном виде...................................................................................72

3.3.3 Выбор системы управления базами данных.......................................74

3.3.4 Разработка программного обеспечения для автоматизированного составления расписания занятий ВУЗа........................................................76

3.4 Выводы..........................................................................................................80

ГЛАВА 4 РАЗРАБОТКА МЕТОДИКИ ОЦЕНКИ ЭФФЕКТИВНОСТИ МЕТОДИЧЕСКОГО АППАРАТА АВТОМАТИЗИРОВАННОЙ СИСТЕМЫ СОСТАВЛЕНИЯ РАСПИСАНИЯ ВУЗА...........................................................82

4.1 Оценка технологической эффективности применения разработанной

методики в учебном процессе ВУЗа......................................................82

4.1.1 Исследование технологического процесса автоматизации составления расписания ВУЗа методами теории массового обслуживания ...........................................................................................................................82

4.1.2 Расчет и анализ финальных вероятностей состояний автоматизированной системы составления расписания ВУЗа...................84

4.2 Оценка структурной эффективности разработанной методики..............87

4.2.1 Разработка целочисленных множеств и булевых матриц отношений информационных элементов предметной области базы данных автоматизированной системы составления расписания ВУЗа...................87

4.2.2 Разработка блочных матриц состояний учебного занятия................90

4.2.3 Анализ целевой функции эффективного использования аудиторного фонда автоматизированной системой составления расписания................93

4.3 Расчет экономического эффекта от применения разработанного

методического аппарата.........................................................................94

4.3.1 Стадии и этапы создания АИС СРЗ..................................................95

4.3.2 Расчёт экономического эффекта от применения методического

аппарата.........................................................................................................101

4.4 Выводы.........................................................................................................104

ЗАКЛЮЧЕНИЕ....................................................................................................106

БИБЛИОГРАФИЧЕСКИЙ СПИСОК................................................................108

ПРИЛОЖЕНИЕ А................................................................................................117

ПРИЛОЖЕНИЕ Б................................................................................................119

ВВЕДЕНИЕ

Актуальность работы.

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

Модели теории расписаний позволяют, например, решать следующие задачи:

- определение оптимальной последовательности выполнения операций, обработки деталей;

- планирование работ производственного участка;

- определение оптимальной последовательности обработки массивов информации;

- составление календарных планов работы организации;

- определение наилучших маршрутов движения;

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

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

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

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

Если проанализировать все задачи, которые решает методист учебного отдела, составляющий расписание занятий, то следует выделить две группы задач. Во-первых, задачи, содержащие перебор большого количества исходных данных, заданных вполне конкретно (количество аудиторий, дни недели). Эти задачи должны быть автоматизированы, и в дальнейшем решаться с помощью математических алгоритмов, заложенных в некоторую автоматизированную систему генерирования расписания. Во-вторых, задачи с исходными данными, которые содержат неполную, неточную, недостоверную или неявную информацию (преподаватели, студенты). Кроме того, необходимо принять во внимание территориальную разбросанность учебных корпусов. В связи с этим необходимо разработать методику составления расписаний занятий ВУЗа с учетом совокупности разнотипных ограничений.

Постановка задачи и цели исследования.

Цель диссертационной работы

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

Поставленные задачи

Поставленная научная задача подразумевает решение частных научных

.................%с -............................у

задач исследования: £

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

- разработка методики оптимизации технологического процесса автоматизации составления расписания ВУЗа;

- разработка методики разделенных множеств информационной среды ВУЗа;

разработка методики проектирования базы данных для автоматизированной системы составления расписания занятий ВУЗа;

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

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

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

Научная новизна диссертации г

^ ' ' ■ с.

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

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

•Разработана методика ранжировки критериев выбора альтернатив размещения учебного занятия.

•Разработана методика проектирования оптимальных структур баз данных информационной среды ВУЗа в объектно-ориентированном виде.

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

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

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

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

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

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

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

определена целевая функция оптимального использования аудиторного фонда в процессе автоматизированного составления расписания. В главе представлен расчет экономической эффективности по требованиям ГОСТ 34.601-90.

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

Методика выбора альтернатив размещения учебных занятий использована в учебном процессе Армавирской государственной педагогической академии при составлении автоматизированного расписания ВУЗа (Приложение А).

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

В Федеральной службе по интеллектуальной собственности, патентам и товарным знакам получены 6 свидетельств о государственной регистрации программы для ЭВМ: «Автоматизированная система расчетов структурно-топологических характеристик ориентированных графов «ГрафМастер» (соавтор - Дьяченко P.A.) - № 2010614204, «Программный модуль вычислительной системы с произвольным доступом к памяти» (соавторы -Атрощенко В.А., Дьяченко P.A., Двинянинов М.В.) - № 2010614203, «Программа для создания тестов и электронного тестирования студентов в ВУЗе при выполнении лабораторных работ» (соавторы - Дьяченко P.A., Литвинов Ю.А., Решетняк М.Г., Щеголев Д.С., Терехов) - № 2011615204, «Система управления лабораторными работами студентов в вузе» (соавторы - Дьяченко P.A., Литвинов Ю.А., Решетняк М.Г., Щеголев Д.С., Терехов В.В.) - № 2011615205, «Программа для проверки и корректировки текста студенческих работ на плагиат» (соавторы - Дьяченко P.A., Литвинов Ю.А., Решетняк М.Г., Щеголев Д.С., Терехов В.В.) - № 2011615202, «Программа для визуализации баз данных. OnlineDataBaseVisualisator (ODBV)» (соавторы

- Дьяченко P.A., Литвинов Ю.А., Решетняк М.Г., Щеголев Д.С., Фишер A.B., Терехов В.В.) - № 2011615203 (Приложение Б).

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

Основные положения и результаты диссертационной работы докладывались на региональных, Российских и международных конференциях КУБГАУ, КубГТУ, СПбГПУ, заседаниях кафедры информатики КУБГТУ, опубликованы в сборниках трудов КУБГАУ, КубГТУ, материалах научно-практической конференции СПбГАСУ, научных журналах «Научно-технические ведомости СПбГПУ» и «Автоматизация и современные технологии», электронном научном журнале «Научный журнал КубГАУ» и получили положительную оценку.

ГЛАВА 1 АНАЛИЗ СОСТОЯНИЯ ВОПРОСА

АВТОМАТИЗИРОВАННЫХ СИСТЕМ ОРГАНИЗАЦИИ УЧЕБНОГО ПРОЦЕССА ВУЗА

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

1.1 Классификация и особенности задач составления расписаний 1.1.1 Классификация моделей теории расписаний

Многочисленность и определенная неоднородность существующих моделей теории расписаний делает затруднительной их классификацию. Однако �