Алгоритм составления расписания занятий
В статье проведен анализ задачи составления расписания занятий, предложен алгоритм составления расписания занятий и возможный путь его развития с использованием генетического алгоритма. У статті провдено аналіз задачі складання розкладу занять, запропонований алгоритм складання розкладу занять та...
Збережено в:
| Дата: | 2009 |
|---|---|
| Автори: | , , |
| Формат: | Стаття |
| Мова: | Russian |
| Опубліковано: |
Інститут проблем штучного інтелекту МОН України та НАН України
2009
|
| Теми: | |
| Онлайн доступ: | https://nasplib.isofts.kiev.ua/handle/123456789/7897 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Алгоритм составления расписания занятий / Ю.В. Береговых, Б.А. Васильев, Н.А. Володин // Штучний інтелект. — 2009. — № 2. — С. 50-56. — Бібліогр.: 7 назв. — рос. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
nasplib_isofts_kiev_ua-123456789-7897 |
|---|---|
| record_format |
dspace |
| spelling |
Береговых, Ю.В. Васильев, Б.А. Володин, Н.А. 2010-04-20T13:09:10Z 2010-04-20T13:09:10Z 2009 Алгоритм составления расписания занятий / Ю.В. Береговых, Б.А. Васильев, Н.А. Володин // Штучний інтелект. — 2009. — № 2. — С. 50-56. — Бібліогр.: 7 назв. — рос. 1561-5359 https://nasplib.isofts.kiev.ua/handle/123456789/7897 004.021 В статье проведен анализ задачи составления расписания занятий, предложен алгоритм составления расписания занятий и возможный путь его развития с использованием генетического алгоритма. У статті провдено аналіз задачі складання розкладу занять, запропонований алгоритм складання розкладу занять та можливий шлях його розвитку з використанням генетичного алгоритму. An algorithm for scheduling classes and way of its development, using genetic algorithm is proposed. The problem of scheduling classes is analysed. ru Інститут проблем штучного інтелекту МОН України та НАН України Алгоритмическое и программное обеспечение Алгоритм составления расписания занятий Алгоритм складання розкладу занять An Algorithm for Scheduling Classes Article published earlier |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| title |
Алгоритм составления расписания занятий |
| spellingShingle |
Алгоритм составления расписания занятий Береговых, Ю.В. Васильев, Б.А. Володин, Н.А. Алгоритмическое и программное обеспечение |
| title_short |
Алгоритм составления расписания занятий |
| title_full |
Алгоритм составления расписания занятий |
| title_fullStr |
Алгоритм составления расписания занятий |
| title_full_unstemmed |
Алгоритм составления расписания занятий |
| title_sort |
алгоритм составления расписания занятий |
| author |
Береговых, Ю.В. Васильев, Б.А. Володин, Н.А. |
| author_facet |
Береговых, Ю.В. Васильев, Б.А. Володин, Н.А. |
| topic |
Алгоритмическое и программное обеспечение |
| topic_facet |
Алгоритмическое и программное обеспечение |
| publishDate |
2009 |
| language |
Russian |
| publisher |
Інститут проблем штучного інтелекту МОН України та НАН України |
| format |
Article |
| title_alt |
Алгоритм складання розкладу занять An Algorithm for Scheduling Classes |
| description |
В статье проведен анализ задачи составления расписания занятий, предложен алгоритм составления
расписания занятий и возможный путь его развития с использованием генетического алгоритма.
У статті провдено аналіз задачі складання розкладу занять, запропонований алгоритм складання розкладу
занять та можливий шлях його розвитку з використанням генетичного алгоритму.
An algorithm for scheduling classes and way of its development, using genetic algorithm is proposed. The
problem of scheduling classes is analysed.
|
| issn |
1561-5359 |
| url |
https://nasplib.isofts.kiev.ua/handle/123456789/7897 |
| citation_txt |
Алгоритм составления расписания занятий / Ю.В. Береговых, Б.А. Васильев, Н.А. Володин // Штучний інтелект. — 2009. — № 2. — С. 50-56. — Бібліогр.: 7 назв. — рос. |
| work_keys_str_mv |
AT beregovyhûv algoritmsostavleniâraspisaniâzanâtii AT vasilʹevba algoritmsostavleniâraspisaniâzanâtii AT volodinna algoritmsostavleniâraspisaniâzanâtii AT beregovyhûv algoritmskladannârozkladuzanâtʹ AT vasilʹevba algoritmskladannârozkladuzanâtʹ AT volodinna algoritmskladannârozkladuzanâtʹ AT beregovyhûv analgorithmforschedulingclasses AT vasilʹevba analgorithmforschedulingclasses AT volodinna analgorithmforschedulingclasses |
| first_indexed |
2025-11-27T05:32:28Z |
| last_indexed |
2025-11-27T05:32:28Z |
| _version_ |
1850798588083306496 |
| fulltext |
«Искусственный интеллект» 2’2009 50
2Б
УДК 004.021
Ю.В. Береговых, Б.А. Васильев, Н.А. Володин
Государственный университет информатики и искусственного интеллекта,
г. Донецк, Украина
yura511@yandex.ru
Алгоритм составления расписания занятий
В статье проведен анализ задачи составления расписания занятий, предложен алгоритм составления
расписания занятий и возможный путь его развития с использованием генетического алгоритма.
Введение
Качество подготовки специалистов в вузах и особенно эффективность исполь-
зования научно-педагогического потенциала зависят в определенной степени от уровня
организации учебного процесса. Одна из основных составляющих этого процесса –
расписание занятий – регламентирует трудовой ритм, влияет на творческую отдачу
преподавателей, поэтому его можно рассматривать как фактор оптимизации исполь-
зования ограниченных ресурсов – преподавательского состава и аудиторного фонда.
Проблему составления расписания следует воспринимать не только как трудоемкий
процесс, объект автоматизации с использованием ЭВМ, но и как акцию оптимального
управления. Поскольку все факторы, влияющие на расписание, практически невозможно
учесть, а интересы участников учебного процесса многообразны, задача составления
расписания является многокритериальной с нечетким множеством факторов. Решение
таких задач, как правило, осуществляется в два этапа: получение оптимального (с точ-
ки зрения используемых критериев) варианта и его последующая доработка человеком
(диспетчером) с целью максимального учета неформализованных факторов. Наибольший
вклад в развитие теории расписаний внесли: Р. Акоф, Р. Беллман, Г. Данциг, Г. Кун,
Т. Саати, Р. Чермен, А. Кофман, Р. Форд и др. Cуществующая теория расписаний при-
менима при составлении расписаний работы машин в цехах, и в то же время имеет
существенные ограничения по применению для составления расписания занятий в
вузе. В настоящей работе предложено решение первого этапа проблемы – разработка
алгоритма получения оптимального расписания. Для разработки алгоритма в первую
очередь были выделены требования к расписанию занятий. В основу алгоритма была
положена идея оценки свободы расположения занятий в расписании, после чего раз-
работана структурная схема алгоритма, и описаны все этапы его работы, а также был
предложен вариант повышения качества составленного расписания при помощи ге-
нетических алгоритмов.
Требования к расписанию
При составлении расписания возникает проблема оптимального управления ре-
сурсами: преподавательским составом и аудиторным фондом. В процессе решения
задачи необходимо учитывать обязательные ограничения, а также дополнительные
требования, которые могут нарушаться в некоторых случаях. К обязательным огра-
ничениям относятся:
Алгоритм составления расписания занятий
«Штучний інтелект» 2’2009 51
2Б
вместительность аудиторий должна быть достаточной для групп, которые в ней за-
нимаются, при этом возможен вариант, когда в одной аудитории проводятся занятия
одновременно для нескольких групп студентов;
должны выполняться требования занятий к оборудованию аудиторий, в которых они
проводятся;
преподаватели из других вузов могут проводить занятия только в определенные дни
и часы.
К дополнительным требованиям относятся:
лекции должны проводиться в начале дня, практики – в конце;
нагрузка каждой группы должна быть равномерной, во избежание переутомления
студентов, то есть в те дни, когда проводится лекция по сложному предмету, осталь-
ные занятия должны проводиться по относительно простым;
в занятиях студентов не должно появляться окон, в то же время возможно наличие
окна в расписании преподавателя;
по возможности преподавателям должны предоставляться дни, свободные от про-
ведения занятий в вузе;
в пятницу количество занятий должно быть меньше, чем в остальные дни недели;
первым занятием в понедельник должен идти относительно простой предмет, иначе
успеваемость студентов может существенно снизиться.
Разработка алгоритма
В результате анализа требований к расписанию занятий было принято решение
о необходимости в разработке алгоритма, в котором были бы заложены возможности
по расширению списка требований к расписанию занятий, а также возможности ре-
гулирования приоритетов выполнения отдельных требований при составлении расписания.
В основе предлагаемого алгоритма составления расписания была положена идея
оценки свободы расположения отдельного занятия в полученном расписании. Было
установлено, что занятия, для проведения которых требуется выполнение обязательных
требований по специальному оборудованию, могут быть проведены только в сущест-
венно ограниченном количестве аудиторий, а занятия, которые проводит преподаватель,
приходящий только в определенные дни недели, могут быть проведены только в
определенные дни недели, а следовательно, такие занятия имеют меньшую свободу
расположения в расписании. Для успешного размещения занятий с относительно
малой свободой расположения в расписании решено начинать составление расписа-
ния с добавления в него занятий с наименьшими оценками свободы расположения.
На рис. 1 приведена структурная схема предлагаемого алгоритма.
Составление расписания занятий начинается с ввода данных об учебной нагрузке.
Также для работы алгоритма требуются данные об аудиторном фонде, в случае если
они не были введены ранее – производится их ввод. В зависимости от вариантов реа-
лизации пользовательского интерфейса списки преподавателей и групп могут фор-
мироваться автоматически, на основании данных об учебной нагрузке, и после этого
дополняться недостающими данными, либо могут быть введены в ручном режиме.
Береговых Ю.В., Васильев Б.А., Володин Н.А.
«Искусственный интеллект» 2’2009 52
2Б
Рисунок 1 – Структурная схема алгоритма составления расписания
В результате обработки данных об учебной нагрузке потоков формируется спи-
сок занятий (табл. 1).
Таблица 1 – Пример составленного списка занятий
Группа Название
дисциплины
Тип занятия Преподаватель Дополнительные
требования к аудитории
СР-06 Логика Лекция Пасько З.А. Нет
СР-06 Логика Лекция Пасько З.А. Нет
СР-06 Логика Практика Пасько З.А. Нет
СР-06 Физкультура – Бритвина Т.В. Спортивный инвентарь
ПО-06 Информатика Лекция Ногина Н.В. Нет
ПО-06 Информатика Практика Ногина Н.В. Компьютеры
Ввод данных об учебной нагрузке
(и аудиторном фонде)
Формирование списка занятий
Оценка свободы расположения
занятия в расписании
Сортировка списка занятий по
возрастанию их свободы
расположения в расписании
Поиск наиболее подходящего
времени и места проведения занятия
Выдача составленного расписания
диспетчеру
Редактирование диспетчером
сгенерированного расписания
Оценка качества составленного
расписания
Подсчет:
– количества подходящих
аудиторий для каждого занятия;
– количества занятий,
проводимых каждым
преподавателем;
– количества занятий,
проводимых для каждой группы.
Для генерации более
приемлемого расписания
занятий может использоваться
генетический алгоритм
Алгоритм составления расписания занятий
«Штучний інтелект» 2’2009 53
2Б
Как видно из примера, в списке занятий могут встречаться повторения. Это об-
условлено тем, что каждое занятие является отдельным объектом, который необходимо
расположить в расписании. Дублирование происходит вследствие того, что в течение
одной недели проводятся два занятия одинакового типа.
При оценке свободы расположения i-го занятия в расписании производится подсчет:
количества аудиторий ai, подходящих для проведения занятия, на основании тре-
бований занятия к оборудованию аудитории и количеству рабочих мест;
количества занятий в неделю pi, которые проводит преподаватель этого занятия;
количества занятий в неделю gi для заданной группы студентов.
На основании этих данных определяется оценка свободы расположения занятия
в расписании:
ii
i
i pg
aS
*
, (1)
где Si – оценка свободы расположения i-го занятия в расписании;
n – количество занятий.
После оценивания свободы расположения занятий в расписании производится
сортировка списка занятий по возрастанию их оценок свободы расположения:
1, 1..i iS S i n . (2)
После проведения сортировки в расписание в первую очередь добавляются за-
нятия, находящиеся в голове списка, то есть с наименьшей свободой расположения в
расписании. При добавлении занятий в расписание производится поиск наиболее вы-
годной аудитории и времени для ее проведения. Для этого необходим полный перебор
вариантов проведения занятия в пространстве (аудитории) и времени (номер пары,
день недели). В процессе перебора вариантов расположения занятия – в первую очередь
происходит проверка возможности проведения занятия по трем условиям:
1 – не происходит «перекрытия» занятий. В случае если оно произошло, то за-
нятие не может быть проведено;
2 – аудитория оборудована всем необходимым для проведения занятия, например
компьютерами, стендами для проведения экспериментов проектором и т.д.;
3 – количество рабочих мест в аудитории не меньше количества учащихся в группе.
В случае если обязательные условия выполняются, происходит оценка качества
расположения занятия по следующим критериям:
1 – появление окна в расписании группы студентов;
2 – появление окна в расписании преподавателя;
3 – избыточность количества мест в аудитории по отношению к количеству
учащихся;
4 – проведение занятия в неудачное время, например четвертым или пятым по
счету в этот день для этой группы студентов;
5 – исчезновение окна в расписании группы студентов;
6 – исчезновение окна в расписании преподавателя;
7 – исчезновение окна в расписании использования аудитории.
Каждый из критериев оценки качества расположения занятия в расписании дол-
жен быть реализован в виде отдельной специализированной функции, возвращаю-
щей значения в диапазоне [0;1]. Гибкость и адаптационные способности алгоритма
Береговых Ю.В., Васильев Б.А., Володин Н.А.
«Искусственный интеллект» 2’2009 54
2Б
достигнуты за счет возможности дополнять список критериев качества без существенных
изменений программного кода. Одним из возможных дополнений может быть проверка
необходимости перемещения группы студентов или преподавателя между корпусами
вуза для проведения занятия.
Оценка качества расположения занятия по всем критериям может быть исполь-
зована для получения общей оценки, необходимой в дальнейшем для выбора максимально
выгодного времени и места проведения занятия.
Для получения оценки качества расположения занятия в расписании применя-
ется формула вида:
m
j
jljil kwR
1
, (3)
где Ril – качество расположения i-го занятия на l-й позиции в расписании;
kjl – значение, полученное по j-му критерию оценки качества расположения занятия
на l-й позиции в расписании;
wj – весовой коэффициент j-го критерия оценки качества;
m – количество критериев оценки качества.
После оценки качества всех возможных вариантов расположения занятия в рас-
писании выбирается вариант, при котором достигается максимальное значение оценки
качества расположения:
max( ), 1..i ill
R R l h , (4)
где l – возможная позиция i-го занятия в расписании;
Ri – качество расположения i-го занятия в расписании;
h – количество возможных вариантов расположения занятия в расписании.
После расположения всех занятий в расписании производится оценка качества
составленного расписания. Для оценки качества расписания решено использовать сум-
му оценок качества расположения всех занятий в расписании. Ввиду того, что оценка
качества расположения каждого занятия по критериям появления и исчезновения
окна в расписаниях студентов и преподавателей зависит от взаимного расположения
занятий в расписании – необходимо произвести повторную оценку качества распо-
ложения каждого занятия в составленном расписании.
Для оценки качества составленного расписания используется формула вида:
n
i
iRR
1
, (5)
где R – качество составленного расписания;
n – количество занятий.
Полученные результаты работы алгоритма предоставляются диспетчеру, который
решает, стоит ли провести повторную генерацию расписания с новыми настроечными
коэффициентами wj, либо модифицировать полученное расписание вручную с целью
дальнейшего использования.
Генетический алгоритм
Для повышения качества полученного расписания занятий, основной алгоритм
составления расписания может быть усовершенствован. Ввиду наличия набора наст-
роечных коэффициентов алгоритма, а также критериев оценки качества полученного
расписания, возможно использовать генетический алгоритм.
Алгоритм составления расписания занятий
«Штучний інтелект» 2’2009 55
2Б
Предлагается использовать в качестве генов настроечные коэффициенты wj ал-
горитма составления расписания. В результате мутаций будут получены новые наборы
настроечных коэффициентов и как следствие – результаты работы алгоритма будут
различны. При этом оценку качества составленного расписания следует проводить с
использованием значений wj заданных диспетчером. Таким образом, учитывается воз-
можность генерации расписания наиболее удовлетворяющего оценкам качества с точки
зрения диспетчера, при использовании несколько измененных оценок качества в процессе
его генерации.
Хромосома такого генетического алгоритма будет представлять собой набор дейст-
вительных чисел:
},...,,,{ 321 mwwww , (6)
где w1…wm – гены хромосомы, настроечные коэффициенты алгоритма составления
расписания;
m – количество настроечных коэффициентов алгоритма.
Целью работы генетического алгоритма является достижение максимума функ-
ционала:
1
1
max( ), 1..
max,
m
il j jl
j
i ill
n
i
i
R w k
R R l h
R R
(7)
где Ril – качество расположения i-го занятия на l-й позиции в расписании;
kjl – значение, полученное по j-му критерию оценки качества расположения заня-
тия на l-й позиции в расписании;
wj – весовой коэффициент j-го критерия оценки качества;
m – количество критериев оценки качества;
l – возможная позиция i-го занятия в расписании;
Ri – качество расположения i-го занятия в расписании;
h – количество возможных вариантов расположения занятия в расписании;
R – качество составленного расписания.
Заключение
Предложенный алгоритм может быть использован для составления расписания
занятий в отдельном вузе. Среди преимуществ можно отметить возможность генерации
приемлемых вариантов расписания уже с первой итерации. В алгоритме предусмотрена
возможность значительного улучшения расписания благодаря добавлению дополнитель-
ных критериев оценки свободы и качества расположения занятий в расписании. На-
пример, можно модифицировать алгоритм для составления расписания занятий сразу в
нескольких корпусах вуза, добавив при этом дополнительный коэффициент качества
расположения занятия, который будет учитывать количество вынужденных переме-
щений студентов и преподавателей между корпусами – с целью их минимизации.
Использование генетического алгоритма в системе составления расписания может
значительно улучшить качество составляемого расписания. Реализация алгоритма на
Береговых Ю.В., Васильев Б.А., Володин Н.А.
«Искусственный интеллект» 2’2009 56
2Б
начальном этапе подразумевает его работу на локальной ЭВМ с использованием одной
из существующих реализаций баз данных с диалоговым интерфейсом взаимодейст-
вия.
Литература
1. Галузин К.С. Разработка модуля для автоматизации составления оптимального учебного распи-
сания в рамках единой информационной системы образовательного учреждения / К.С. Галузин,
Столбов В.Ю. // Известия Белорусской инженерной академии. – 2003. – № 1 (15).
2. Конференция iXBT.com Кто может подсказать алгоритм составления расписания. – Режим доступа:
<http://forum.ixbt.com/topic.cgi?id=40:377>
3. Минаев Ю.Л. Автоматизированное составление школьного учебного расписания / Ю.Л. Минаев :
Тезисы конференции ИТО-98/99.
4. Рубина Т.Б. Метод замещений для решения задачи составления расписаний в учебных заведениях /
Т.Б. Рубина.
5. Рутковская Д. Нейронные сети, генетические алгоритмы и нечеткие системы / Д. Рутковская,
М. Пилиньский, Л. Рутковский. – Горячая Линия – Телеком, 2007. – 452 с.
6. Кормен Т. Алгоритмы: построение и анализ / Т. Кормен, Ч. Лейзерсон, Р. Ривест // МЦНМО. –
Москва, 2000. – 960 с.
7. Гладков Л.А. Генетические алгоритмы: учебное пособие / Л.А. Гладков, В.В. Курейчик, В.М. Курейчик. –
М. : Физматлит, 2004. – 407 с.
Ю.В. Берегових, Б.А. Васильєв, М.О. Володін
Алгоритм складання розкладу занять
У статті провдено аналіз задачі складання розкладу занять, запропонований алгоритм складання розкладу
занять та можливий шлях його розвитку з використанням генетичного алгоритму.
Yи.V. Beregovykh, B.A. Vasilyev, N.A. Volodin
An Algorithm for Scheduling Classes
an algorithm for scheduling classes and way of its development, using genetic algorithm is proposed. The
problem of scheduling classes is analysed.
Статья поступила в редакцию 15.01.2009.
|