Об особенностях формирования целевой функции и ограничений в задаче составления расписания занятий
Рассматривается задача формирования расписаний занятий в высших учебных заведениях. Предложены новые подходы, модели и метод формирования целевой функции с ее последующей оптимизацией на основе применения эволюционных технологий и матричного представления расписания. Розглядається задача формування...
Saved in:
| Published in: | Математичні машини і системи |
|---|---|
| Date: | 2014 |
| Main Authors: | , |
| Format: | Article |
| Language: | Russian |
| Published: |
Інститут проблем математичних машин і систем НАН України
2014
|
| Subjects: | |
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/84434 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Cite this: | Об особенностях формирования целевой функции и ограничений в задаче составления расписания занятий / В.Е. Снитюк, Е.Н. Сипко // Математичні машини і системи. — 2014. — № 3. — 88-95. — Бібліогр.: 21 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
nasplib_isofts_kiev_ua-123456789-84434 |
|---|---|
| record_format |
dspace |
| spelling |
Снитюк, В.Е. Сипко, Е.Н. 2015-07-07T17:13:04Z 2015-07-07T17:13:04Z 2014 Об особенностях формирования целевой функции и ограничений в задаче составления расписания занятий / В.Е. Снитюк, Е.Н. Сипко // Математичні машини і системи. — 2014. — № 3. — 88-95. — Бібліогр.: 21 назв. — рос. 1028-9763 https://nasplib.isofts.kiev.ua/handle/123456789/84434 004.94 Рассматривается задача формирования расписаний занятий в высших учебных заведениях. Предложены новые подходы, модели и метод формирования целевой функции с ее последующей оптимизацией на основе применения эволюционных технологий и матричного представления расписания. Розглядається задача формування розкладів занять у вищих навчальних закладах. Запропоновано нові підходи, моделі й метод формування цільової функції з її подальшою оптимізацією на основі застосування еволюційних технологій та матричного представлення розкладу. The problem of the timetabling in universities is considered. New approaches, models, and a method for forming the objective function and its subsequent optimization through the use of evolutionary technologies and matrix representation of the timetable are suggested. ru Інститут проблем математичних машин і систем НАН України Математичні машини і системи Моделювання і управління Об особенностях формирования целевой функции и ограничений в задаче составления расписания занятий Про особливості формування цільової функції і обмежень у задачі складання розкладу занять On peculiarities of the objective function formation and limitation in the problem of timetabling 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 |
2014 |
| language |
Russian |
| container_title |
Математичні машини і системи |
| publisher |
Інститут проблем математичних машин і систем НАН України |
| format |
Article |
| title_alt |
Про особливості формування цільової функції і обмежень у задачі складання розкладу занять On peculiarities of the objective function formation and limitation in the problem of timetabling |
| description |
Рассматривается задача формирования расписаний занятий в высших учебных заведениях. Предложены новые подходы, модели и метод формирования целевой функции с ее последующей оптимизацией на основе применения эволюционных технологий и матричного представления расписания.
Розглядається задача формування розкладів занять у вищих навчальних закладах. Запропоновано нові підходи, моделі й метод формування цільової функції з її подальшою оптимізацією на основі застосування еволюційних технологій та матричного представлення розкладу.
The problem of the timetabling in universities is considered. New approaches, models, and a method for forming the objective function and its subsequent optimization through the use of evolutionary technologies and matrix representation of the timetable are suggested.
|
| issn |
1028-9763 |
| url |
https://nasplib.isofts.kiev.ua/handle/123456789/84434 |
| citation_txt |
Об особенностях формирования целевой функции и ограничений в задаче составления расписания занятий / В.Е. Снитюк, Е.Н. Сипко // Математичні машини і системи. — 2014. — № 3. — 88-95. — Бібліогр.: 21 назв. — рос. |
| work_keys_str_mv |
AT snitûkve obosobennostâhformirovaniâcelevoifunkciiiograničeniivzadačesostavleniâraspisaniâzanâtii AT sipkoen obosobennostâhformirovaniâcelevoifunkciiiograničeniivzadačesostavleniâraspisaniâzanâtii AT snitûkve proosoblivostíformuvannâcílʹovoífunkcíííobmeženʹuzadačískladannârozkladuzanâtʹ AT sipkoen proosoblivostíformuvannâcílʹovoífunkcíííobmeženʹuzadačískladannârozkladuzanâtʹ AT snitûkve onpeculiaritiesoftheobjectivefunctionformationandlimitationintheproblemoftimetabling AT sipkoen onpeculiaritiesoftheobjectivefunctionformationandlimitationintheproblemoftimetabling |
| first_indexed |
2025-11-27T08:21:42Z |
| last_indexed |
2025-11-27T08:21:42Z |
| _version_ |
1850805644370640896 |
| fulltext |
88 © Снитюк В.Е., Сипко Е.Н., 2014
ISSN 1028-9763. Математичні машини і системи, 2014, № 3
УДК 004.94
В.Е. СНИТЮК*, Е.Н. СИПКО**
ОБ ОСОБЕННОСТЯХ ФОРМИРОВАНИЯ ЦЕЛЕВОЙ ФУНКЦИИ И
ОГРАНИЧЕНИЙ В ЗАДАЧЕ СОСТАВЛЕНИЯ РАСПИСАНИЯ ЗАНЯТИЙ
*
Киевский национальный университет имени Тараса Шевченко, Киев, Украина
**
Черкасский государственный технологический университет, Черкассы, Украина
Анотація. Розглядається задача формування розкладів занять у вищих навчальних закладах. За-
пропоновано нові підходи, моделі й метод формування цільової функції з її подальшою оптимізаці-
єю на основі застосування еволюційних технологій та матричного представлення розкладу.
Ключові слова: розклад занять, цільова функція, обмеження, матричне представлення розкладу,
еволюційні технології.
Аннотация. Рассматривается задача формирования расписаний занятий в высших учебных заве-
дениях. Предложены новые подходы, модели и метод формирования целевой функции с ее после-
дующей оптимизацией на основе применения эволюционных технологий и матричного представ-
ления расписания.
Ключевые слова: расписание занятий, целевая функция, ограничения, матричное представление
расписания, эволюционные технологии.
Abstract. The problem of the timetabling in universities is considered. New approaches, models, and a
method for forming the objective function and its subsequent optimization through the use of evolutionary
technologies and matrix representation of the timetable are suggested.
Keywords: timetable, objective function, limitation, matrix representation of the timetable, evolutionary
technologies.
1. Введение
Решение задачи составления расписаний является актуальным для многих промышленных
и инфраструктурных отраслей. Определяющую роль оно играет для дискретных произ-
водств и учебных заведений. Финансовый и ресурсный дефицит являются причиной того,
что к составлению эффективных расписаний возвращаются вновь и вновь. Известно, что
оптимальное решение такой задачи возможно получить только методом полного перебора
возможных вариантов, но разнообразие подходов, требований и ограничений не дает осно-
ваний предполагать ее разрешимость в общем виде. Вместе с тем существуют сотни, если
не тысячи методов и систем, предназначенных для формирования расписаний.
Для высших учебных заведений Украины разработка общих подходов, методологии
формирования расписаний занятий – одна из важнейших проблем оптимизации учебного
процесса. Динамика требований работодателей, постоянно изменяющаяся законодательная
основа, сокращение материальной базы и увеличение количества специальностей приводят
к необходимости оптимизации процесса использования кадрового потенциала, ауди-
торного фонда и экономии энергетических ресурсов.
Еще одним важным фактором является значительное количество субъектов учебно-
го процесса, заинтересованных в качественном решении задачи составления расписаний, к
которым относятся преподаватели, студенты, административные сотрудники. Количество
публикаций на эту тему имеет тенденцию к постоянному росту. Так, на запрос «складання
розкладу занять» Google выдает 125000 ссылок, а на запрос «составление расписания заня-
тий» их уже 512000. При этом украиноязычный Интернет презентует модели и методы со-
ставления расписаний, а русскоязычный – разработанные системы. Природу такого разде-
ления еще предстоит объяснить специалистам.
ISSN 1028-9763. Математичні машини і системи, 2014, № 3 89
2. Анализ современных технологий составления расписаний
Определим основные тенденции современного научного поиска в направлении технологий
решения задачи составления расписаний занятий в учебных заведениях. Особенности про-
цесса составления расписания занятий для дистанционного обучения рассмотрены в статье
[1]. Выполнен анализ различных методов составления расписаний: имитации отжига, рас-
крашивания графа, имитационного моделирования, логического программирования с ог-
раничениями. Критерием оптимальности расписания определено максимальное уплотне-
ние преподавательской нагрузки и сделано ударение на использовании генетического ал-
горитма для максимизации целевой функции. Аспекты применения генетического алго-
ритма рассмотрены и в работе [2]. Тот же генетический алгоритм рассмотрен и в [3], кри-
териальной функцией здесь выступает усредненное значение уровня выполнения требова-
ний преподавателей: нежелание проводить пары в определенное время, минимизация ко-
личества «окон», равномерность занятий. Продолжается тема использования генетических
алгоритмов в статье [4] с уклоном в сторону параллелизации вычислительного процесса и
использования Grid-систем.
Метод формирования расписания, которое определяется пожеланиями студентов,
описан в [5]. Предложенные идеи имеют нечто общее с известными технологиями, подоб-
ными методу Дельфи, поскольку присутствуют все те же атрибуты: заочность, многоуров-
невость, анонимность. Автор [6] предлагает информационную модель на базе ограничений
связей элементов расписаний, расписание формируется с использованием метода анализа
иерархий. В [7] тема использования такой модели развита в направлении использования
генетического алгоритма. В статье [8] предложено применение элементов тензорного ис-
числения для описания процессов составления расписаний для учебных комплексов.
В работе [9] сделан вывод о нецелесообразности полностью автоматизированного
составления расписания из-за трудоемкости построения точных математических конст-
рукций и предлагается использование диалогового процесса. Основные ограничения и ви-
ды критериальных функций систематизированы в [10]. Автор утверждает, что существуют
два критерия поиска целевой функции: минимизация затрат и максимизация эффективно-
сти составленного расписания. И если со вторым критерием вполне можно согласиться
при условии уточнения понятия «эффективного расписания», то первый критерий вызыва-
ет, как минимум, недоумение. Возможно, это минимизация вычислительных ресурсов, не-
обходимых для получения опорного или квазиоптимального решения, или минимизация
затрат ручного труда диспетчера. Оптимизация структуры информационной базы предла-
гается в [11]. Еще одним направлением, превалирующим в некоторых работах [12–14], яв-
ляется использование элементов нечеткой логики, что является естественным, учитывая
природу требований субъектов учебного процесса.
Подводя итоги проведенного анализа, делаем вывод о том, что значительное коли-
чество работ посвящено обзору полученных к этому времени результатов, или оптимиза-
ции процесса получения эффективного расписания с использованием современных вычис-
лительных технологий, таких как генетические алгоритмы. Надо заметить, что они явля-
ются методами хоть и направленного, но случайного поиска, и их реализация и выполне-
ние зачастую является ресурсоемким процессом, который, вместе с необходимостью про-
верки выполнения значительного количества ограничений, зачастую не приводит к полу-
чению приемлемого результата за приемлемое время.
3. Целевая функция и особенности проверки расписаний на адекватность
Для решения задачи построения эффективного расписания ранее авторами предложена це-
левая функция и указаны ограничения [15]:
90 ISSN 1028-9763. Математичні машини і системи, 2014, № 3
( ) { } { } { }
1 1 1 1
max,
i
j
nl K M
Tv j
S j j j i j il il
j j i l
F r x Z y L T d Zα χ χ χ
= = = =
= + ∈ ⋅ →∑ ∑ ∑ ∑ (1)
( , , , ),r P S L A∈Ω (2)
где r – расписание, ,S Lα α – весовые коэффициенты, указывающие на приоритеты препо-
давателей и студентов как субъектов учебного процесса, jx – приоритеты требований сту-
дентов и преподавателей, v
jZ – требования групп студентов, iL – преподаватели, jT – груп-
пы преподавателей, jT
ilZ – предпочтения преподавателей, j
ild – приоритеты таких предпоч-
тений, l – количество требований студентов, K – количество групп преподавателей, опре-
деляемое их должностями, научными степенями и учеными званиями, M – количество
преподавателей, in – количество преподавателей в i -й группе, Ω – область ограничений,
, ,P L A – множество учебных дисциплин, преподавателей и аудиторий, соответственно.
В задаче (1) – (2) учтены значение коллективов студентов и преподавателей как не-
которых совокупностей, а также интересы студенческих групп и отдельных преподава-
телей с учетом их должностей, степеней и званий. Однако формирование целевой функции
является скорее теоретическим изыском, конструктивное нахождение решения задачи (1) –
(2) – гораздо более сложный процесс. Учитывая предыдущий опыт и тенденции, было
предложено поиск эффективного расписания осуществлять, используя эволюционные тех-
нологии. Разработав структуру потенциального решения и используя целевую функцию из
(1), можно оценить его перспективность. Но в отличие от многих оптимизационных задач,
вычисление значений целевой функции, равно как и проверка выполнения ограничений
(2), является длительным и ресурсоемким. Метод оптимизации целевой функции будет
описан ниже.
Остановимся на определении адекватности того или иного расписания. С этой це-
лью необходимо проверить выполнение ограничений (2). Для оптимизации вычислитель-
ного процесса предполагается использовать матрично-эволюционный метод. С этой целью
расписание занятий представим как некоторую таблицу с полями
, , , , , , , ,Sh Day Time Year Group Course Lecturer Type Room=< > (3)
где Day – день проведения занятий, Time – номер пары, Year – год обучения студента
(курс), Group – шифр группы (идентификатор), Course – название учебной дисциплины,
Lecturer – преподаватель, Type – тип занятия, Room – номер аудитории.
Такое количество полей усложняет проверку расписания на адекватность. Упро-
стим его и визуально представим некоторой трехмерной решетчатой структурой. Такая
структура будет иметь вид прямоугольного параллелепипеда со сторонами, лежащими на
осях:
1 2 3, , .X День Пара X Курс Группа X Аудитория=< − > =< − > =< > (4)
В узлах решетки параллелепипеда будут находиться значения
.Z Преподаватель Предмет Форма занятия=< − − > (5)
Предположив, что количество учебных дней в неделе 6, а возможное количество за-
нятий в день (пар) – 6, получим, что 1 {1, 2,...,36}.X ∈ Пусть максимальное количество кур-
сов студентов в университете 6, количество групп варьируется (предположим 200), тогда
2 {1,2,..., 200}.X ∈ В таком случае общее количество узлов трехмерной решетки составит
2160000 при условии, что число возможных аудиторий 300. Содержимое узлов решетки
ISSN 1028-9763. Математичні машини і системи, 2014, № 3 91
может быть различным. В качестве первого варианта там может быть любое число
{1,2,...,800000},Z ∈ учитывая то, что количество преподавателей 200, предметов – 1000, а
форм возможных занятий – 4.
Таким образом, расписание будет представлять собой совокупность фрагментов
1 2 3{ , , , }X X X Z . Поскольку определение структуры потенциального решения задачи фор-
мирования расписания имеет большое значение для оптимизации вычислительного про-
цесса, то заметим, что преобразование триады <Преподаватель-Предмет-Форма занятия> в
целое число должно осуществляться по некоторому алгоритму. Приведем его особенности.
На первом этапе выписываем все формы занятий по одному предмету определенного пре-
подавателя. Далее, то же самое для другого предмета, но того же преподавателя. На сле-
дующем шаге выписываем предметы и формы занятия другого преподавателя и т.д. Отме-
тим, что преподаватели упорядочены по должностям, степеням и званиям. Если указанные
атрибуты совпадают, то преподаватели выписываются по алфавиту. После получения спи-
ска в указанном формате производим кодирование так, что первой записи будет отвечать
1, а последней – 800000.
Во втором варианте в узлах решетки могут быть кодированы только предметы и
формы занятий, поскольку по первым двум атрибутам и базе данных можно однозначно
установить преподавателя. Однако этот процесс может быть более ресурсоемок, что пред-
стоит установить дополнительно.
Предложенный метод формирования фрагмента потенциального решения позволит
ускорить вычислительный процесс за счет обеспечения непрерывности получаемых реше-
ний. В частности, если будет выявлено, что некоторый преподаватель не может провести
определенное занятие по данному предмету, то более вероятно, что в первую очередь на
следующем шаге ему будет предложено изменить форму занятия или предмет.
Одновременно с построением параллелепипеда расписания рационально строить
еще один параллелепипед такой же размерности, но в узлах решетки которого будут нахо-
диться единицы, указывающие, что в такой-то день на такой-то паре для группы студентов
в аудитории проходит занятие, и ноль, если там занятия нет. Такой параллелепипед необ-
ходим для ускорения процесса построения потенциальных решений-расписаний и про-
верки их адекватности, а также для вычисления значений целевой функции
В отличие от традиционного варианта использования генетических алгоритмов
предлагаем сделать ударение на обеспечении непрерывности поиска новых потенциальных
решений, что соответствует логике процесса формирования расписания: «Если расписание
является неудовлетворительным, то наиболее эффективными будут его минимальные из-
менения».
Дополнительный параллелепипед предназначен для проверки адекватности форми-
руемого расписания как потенциального решения. Наличие или отсутствие единиц в узлах
его решетки позволит, с использованием технологий OLAP, определить, выполняются ли
«жесткие» ограничения. Такая проверка проводится для каждой генерируемой записи, яв-
ляющейся составляющей расписания занятий.
4. Элементы направленной оптимизации целевой функции
В основе направленной оптимизации целевой функции лежит композиция элементов не-
скольких техник: эволюционных стратегий [16, 17], методов анализа иерархий [18] и тео-
рии нечетких множеств [19]. Рассмотрим одномерный случай и выполним обобщения [20].
Необходимо решить задачу поиска max ( )
x
f x
∈Ω
, где Ω – некоторый компакт. На мак-
роуровне предложенный метод имеет такие шаги:
Шаг 0. Номер итерации 1i = .
92 ISSN 1028-9763. Математичні машини і системи, 2014, № 3
Шаг 1. Определяем начальное количество потенциальных решений λ и генерируем равно-
мерно распределенные на Ω потенциальные решения 1 2, ,...,i i ix x xλ .
Шаг 2. Вычисляем значения функции f в точках 1 2, ,...,i i ix x xλ : 1 1 2 2( ), ( ),...,i i i if f x f f x= =
( )i if f xλ λ= .
Шаг 3. Нормируем значения i
jf так, чтобы
1
[0;1], 1ni ni
j j
i
f f
λ
=
∈ =∑ .
Шаг 4. Формируем матрицу попарных сравнений Саати S таким образом. Среди нормиро-
ванных значений функции находим минимальное ,ni
jf разбиваем отрезок [0;1] на 10 ин-
тервалов: [0;0,1),[0,1;0,2),..., [0,9;1]. Тогда для всех {1,2,..., }h λ∈ , если
[0,1 ;0,1 0,1 )ni
jf k k∈ + и [0,1 ;0,1 0,1 )ni
hf l l∈ + , где , {0,1,...,9}k l ∈ , то 1jhs l k= − + . Другие
элементы матрицы S рассчитываются так: jq
pq
jp
s
s
s
= .
Шаг 5. Рассчитываем собственные числа матрицы S и для максимального собственного
числа maxa находим соответствующий собственный вектор w . Если вектор w по разным
причинам найти проблематично, то его элементы приближенно рассчитывают по формуле
1 2
1
...j
j j j
w
s s sλ
=
+ + +
. Значения jw указывают на меру оптимальности (квазиоптимально-
сти) потенциального решения i
jx .
Шаг 6. Известно, что следующим этапом должна стать генерация «потомков» и формиро-
вание новой популяции потенциальных решений. Авторы эволюционной стратегии пред-
лагают получать «потомков» таким образом:
1 ( (0,1)), 1, ,i i
j jx x N jξ µ+ = + = (6)
где ( (0,1))Nξ – нормально распределенная случайная величина с нулевым средним и еди-
ничной дисперсией, η – количество «потомков» у одного «родителя». По концепции эво-
люции Ч. Дарвина 1µ > , а в [17] рекомендовано выбирать 7µ λ≥ . Последнее неравенство
является малодоказуемым.
Мы считаем, что для эффективного поиска оптимального решения необходимо учи-
тывать меру оптимальности jw потенциальных решений i
jx . Это позволит более детально
исследовать область Ω . При этом возникают две гипотезы:
– чем большим является значение jw , тем большими должны быть значения jσ при
генерации «потомков» потенциального решения i
jx , что позволит расширить область по-
иска в окрестности лучшего решения, а в области наименее потенциально оптимального
решения область будет максимально суженой, в т.ч. и из-за неперспективности ее исследо-
вания;
– наоборот, большее значение jw является причиной для глубокого исследования
окрестности перспективнейшего решения, а большее значение отклонения позволит де-
тально исследовать область, удаленную от неперспективного потенциального решения.
Такие две гипотезы требуют подтверждения, обе они являются эвристическими, не
противоречат теории и практике стохастической оптимизации. Мы склоняемся к правиль-
ности второй гипотезы, что подтверждается первыми экспериментами, но нужны и более
глубокие исследования.
ISSN 1028-9763. Математичні машини і системи, 2014, № 3 93
Еще одной задачей является определение оптимального количества потомков в за-
висимости от оптимальности решения. Очевидно, что такое количество ( )i
jN x зависит от
меры области Ω и заданной точности потенциального решения ε . Для случая, когда Ω
является отрезком ( ) ( ([ , ]))i
jN x g L a b= , где (*)L является длиной, определение величины
jµ также является эвристическим. На первом этапе рационально считать, что
{1, 2,..., }j iµ µ λ= ∀ ∈ . Такой вывод базируется на том, что, взяв за основу вторую гипо-
тезу, для перспективного решения необходимо более глубокое исследование окрестности,
а для неперспективного – более широкое. И то, и другое одинаково важно.
Наиболее сложной является задача восстановления значения дисперсии для каж-
дого отдельного решения. Очевидно, что 2
jσ будет зависеть, как и в предыдущем случае,
от ([ , ])L a b и ε , а также от расстояния к ближайшим соседям-решениям. Находим
( , ), ( , )i i
j L j Rd x x d x x (расстояние к ближайшему левому (или точке a ) и правому (или точке
b ) соседу-решению). Пусть max max{ ( , ), ( , )}i i
j L j Rd d x x d x x= , тогда max
1
3j dσ = , поскольку по
правилу 3-х сигма именно 9973 точки из 10000 при генерации по формуле (6) будут на-
ходиться на интервале ( 3 , 3 )i i
j j j jx xσ σ− + .
Шаг 7. На предыдущем шаге выполнена генерация λ µ⋅ потенциальных решений. Нахо-
дим соответствующие значения функции f . По этим значениям, а также по значениям
1 2, ,...,i if f ifλ определяем λ лучших решений 1 1 1
1 2, ,...,i i ix x xλ
+ + + и переходим на шаг 1.
Поиск оптимального решения заканчивается на v -й итерации тогда, когда на шаге 2
,
max ,i j
i j
f f− , 1,i j λ= будет меньше некоторого наперед заданного 0δ > , так, что и
,
max ,v v
j i
i j
x x ε− < что свидетельствует о сходимости метода. Тогда то решение v
ix , которое
соответствует значению maxv v
i j
j
f f= , и будет решением поставленной задачи.
Проведенные исследования свидетельствуют в пользу предложенного метода на-
правленной оптимизации. Его верификация на известных тестовых наборах сложных по-
лиэкстремальных функций [21] свидетельствует об эффективности предложенных идей и
техник.
5. Заключение
Учитывая специфику задачи составления расписаний для учебных заведений, можно кон-
статировать, что направление ее решения выбрано правильно. Использование эволюцион-
ных технологий для оптимизации сложных недифференцируемых и полиэкстремальных
зависимостей – одна из наиболее популярных современных идей, имеющая множество
конструктивных реализаций.
Формирование целевой функции, генерация потенциальных решений-расписаний,
определение их структуры, сложности кодирования, проблема обеспечения качественной
непрерывности – аспекты, не позволяющие осуществить эффективный поиск приемлемых
(квазиоптимальных) решений. Поэтому предложенный метод формирования расписания в
университете, базирующийся на разработке и использовании целевой функции, в основе
которой лежат предпочтения преподавателей и студентов, имеет преимущества.
В частности, целевая функция имеет комплексный характер, в которой учтены по-
желания субъектов учебного процесса, она является открытой для внесения дополнений и
изменений. Оптимизирована структура потенциальных решений в виде узлов решетки па-
94 ISSN 1028-9763. Математичні машини і системи, 2014, № 3
раллелепипеда, генерация потенциальных решений осуществляется с учетом «жестких»
ограничений, а новые решения получают путем вариации возможных оставшихся вариан-
тов с учетом их проверки на противоречивость. Использование эволюционной стратегии
не требует перекодирования решений, специфика формирования потенциальных решений
гарантирует соблюдение принципа непрерывности процесса генерации решений. Деталь-
ное исследование области потенциальных решений и соответствующая генерация новых
решений ускоряют процесс оптимизации.
Предложенные подходы и метод не позволяют гарантировать получение оптималь-
ного решения, они направлены на поиск расписаний, эффективность которых можно срав-
нить и, соответственно, выбрать наилучшее из них.
СПИСОК ЛИТЕРАТУРЫ
1. Томашевський В.М. Складання розкладів занять у дистанційних системах навчання / В.М. То-
машевський, Ю.Л. Новіков, П.А. Камінська // Вісник НТУУ «КПІ». Інформатика, управління та
обчислювальна техніка: збірник наукових праць. – 2010. – № 52. – С. 118 – 130.
2. Глибовец Н.Н. Генетические алгоритмы и их использование для решения задачи составления
расписания / Н.Н. Глибовец, С.А. Медвидь // Кибернетика и системный анализ. – 2003. – № 1. –
С. 95 – 108.
3. Астахова И.Ф. Cоставление расписания учебных занятий на основе генетического алгоритма /
И.Ф. Астахова, А.М. Фирас // Вестник ВГУ. – (Серия «Системный анализ и информационные тех-
нологии»). – 2013. – № 2. – С. 93 – 99.
4. Годлевський М.Д. Розробка та налаштування паралельних генетичних алгоритмів для
розв’язання задачі створення розкладу занять вузу на основі GRID-системи / М.Д. Годлевський,
О.О. Абабілов // Вестник НТУ "ХПИ": Системний аналіз, управління та інформаційні технології. –
2010. – № 67. – С. 17 – 23.
5. Соуса Ф. Повністю евристичний розклад занять, керований побажаннями студентів / Ф. Соуса,
А. Алвес / Наукові праці ВНТУ. – 2009. – № 2. – С. 1 – 4.
6. Разумов Ю.А. Спеціалізована модель задачі про призначення для складання розкладу занять ви-
щих навчальних закладів [Електронний ресурс] / Ю.А. Разумов. – Режим доступу:
http://stp.diit.edu.ua/article/viewFile/14094/11909.
7. Вишнякова И.Н. Моделирование и автоматизация составления расписания учебных занятий ву-
зов [Електронний ресурс] / И.Н. Вишнякова, С.Ю. Разумов. – Режим доступа:
stp.diit.edu.ua/article/download/17545/15284.
8. Шостак И.В. Автоматизация процесса составления расписания занятий на основе тензорного
исчисления в учебном комплексе / И.В. Шостак, К.Э. Яновская, C.В. Россоха // Авиационно-кос-
мическая техника и технология. – 2012. – № 9 (96). – C. 263 – 266.
9. Семенов С.П. Cравнительный анализ подходов к автоматизации составления расписаний учеб-
ных занятий в образовательных учреждениях / С.П. Семенов, Я.Б. Татаринцев // Известия Алтай-
ского государственного университета. – 2010. – С. 103 – 105.
10. Леонова М. В. Моделювання задач складання розкладу занять у ВНЗ: огляд та різні підходи до
розв’язування / М. Леонова // Вісник Запорізького національного університету. – 2013. – № 1. –
С. 52 – 59.
11. Семенюта И.С. Методика анализа информационной структуры базы данных автоматизирован-
ной системы составления расписаний / И.C. Семенюта // Научный журнал КубГАУ. – 2011. – № 73
(09). – С. 1 – 11.
12. Безгинов А.Н. Многокритериальный подход к оценке расписания занятий на основе нечеткой
логики / А.Н. Безгинов, С.Ю. Трегубов // Control Sciences. – 2011. – № 2. – P. 52 – 59.
13. Галузин К.С. Математическая модель оптимального учебного расписания с учетом нечетких
предпочтений: дис. ... канд. физ.-мат. наук: 05.13.18 / Галузин Константин Станиславович. – Пермь,
2004. – 148 c.
14. Сироджа И.Б. Нечеткий дедуктивный вывод в системе квантов знаний для поддержки принятия
решений в условиях неопределенности / И.Б. Сироджа, С.В. Россоха // Открытые информационные
и компьютерные интегрированные технологии. – 2006. – Вып. 30. – С. 50 – 56.
ISSN 1028-9763. Математичні машини і системи, 2014, № 3 95
15. Снитюк В.Є. Аспекти формування цільової функції в задачі складання розкладу занять у ВНЗ /
В.Є. Снитюк, О.М. Сіпко // Матеріали IX міжн. наук-практ. конф. «Математичне та імітаційне мо-
делювання систем. МОДС 2014». – Київ, Жукін, 2014. – С. 349 – 352.
16. Rechenberg I. Evolutionsstrategie ”94” / Rechenberg I. – Stuttgart-Bad GannStatt: Frommann Halz-
boog, 1994. – 434 p.
17. Beyer H.-G. Evolution Strategies: A Comprehensive Introduction / H.-G. Beyer, H.-P. Schwefel //
Journal Natural Computing. – 2002. – N 1 (1). – P. 3 – 52.
18. Саати Т. Принятие решений. Метод анализа иерархий / Саати T. – М.: Радио и связь, 1993. –
278 с.
19. Zadeh L. Fuzzy sets / L. Zadeh // Information and control. – 1965. − N 8. – P. 338 – 353.
20. Снитюк В.Е. Параметрическая оптимизация процесса эволюционного направленного поиска /
В.Е. Снитюк // Матеріали II Міжн. наук.-техн. конф. «Обчислювальний інтелект». – Черкаси, 2013.
– С. 14 – 15.
21. http://www.gamsworld.org/performance/selconglobal/selcongloballib.htm.
Стаття надійшла до редакції 04.07.2014
|