Автор:М.В. Деканова
Источник: Вестник полоцкого государственного университета / Фундаментальные науки. Информационные технологии / Серия С 2014 г. с. 56 – 66.
Проанализированы существующие подходы к решению задачи составления расписания, такие как: локально-эволюционный метод, многоагентный подход, интеллектуальный метод, метод замещений, метод последовательного анализа вариантов, генетический алгоритм, метод раскраски графов. Выделены достоинства и недостатки каждого из них. Сделан вывод, что задача составления расписаний университета относится к классу дискретных задач оптимизации с конечным множеством альтернатив. Решение задачи составления расписания осложняется многокритериальностью и многовариантностью. Показано, что для разрешимости рассматриваемой задачи необходимо применить комплексный подход, учитывающий достоинства всех рассмотренных в рамках данной работы методов.
Введение. Задача составления расписаний является предметом научных исследований с середины прошлого века. Область ее применения включает в себя различные сферы человеческой деятельности: транспортные перевозки, массовое обслуживание, промышленность, образование и т.д. Практика выдвигает множество задач, которые невозможно эффективно решить путем полного перебора. Для большинства моделей теории расписаний нахождение оптимального расписания является трудноразрешимой задачей, а решение приближенных к реальным условиям задач обладает ещё большей сложностью, так как данные решения должны удовлетворять многочисленным, зачастую конфликтующим между собой ограничениям производственного, организационного и психофизиологического характера.
Количественный и качественный рост высшей школы требует нового подхода к решению задач управления учебной, научной и хозяйственной деятельностью университетов. Этот подход в последние годы находит свое воплощение в применении современных средств вычислительной техники и математических методов в управлении высшими учебными заведениями. В современном мире всё большее распространение получают различного рода системы автоматизации технических процессов, которые всегда выполнялись вручную. К таким же процессам относится и составление расписания, которое до сих пор во многих учебных заведениях создается вручную на основе многолетнего опыта. Современная же наука располагает средствами, позволяющими наилучшим образом организовать любой процесс, в том числе и учебный [1].
Задача планирования расписания учебных занятий – это задача на составление расписания комбинаторного типа, характерной особенностью которой является огромная размерность и наличие большого числа ограничений сложной формы. Фактически в настоящее время не существует универсальных методов решения таких задач. Математическая (классическая) теория расписаний [1–3] охватывает лишь узкий круг хорошо формализуемых проблем, которые обычно сводятся к следующим задачам: коммивояжера, транспортной и т.п. Прямое применение данных методов к задаче составления расписания учебных занятий не представляется возможным. Тем не менее есть ряд эвристических и переборных методов, которые вполне поддаются программированию.
Изучение опыта создания подобных систем показывает, что в последние годы предпринимались множественные попытки совершенствования планирования учебного процесса путем построения алгоритмов оптимизации задач планирования учебной работы университета и последующей их реализацией на вычислительной технике. Такие исследования в разное время проводились и продолжаются в некоторых университетах [4, 5].
В данной работе рассмотрим существующие подходы к составлению расписания учебных занятий университета.
Метод решения задач дискретной оптимизации является результатом синтеза эвристического и эволюционного подходов к решению задач данного класса. Класс задач дискретной оптимизации включает в себя такие задачи, как составление оптимального расписания, маршрутная оптимизация, задача оптимального планирования многопрофильного производства и т.п.
Эвристический метод – достаточно эффективный метод поиска решений задач дискретной оптимизации большой размерности. Из него было взято на вооружение использование локальных эвристик (локальных правил поиска решения). Из эволюционного – параллельное развитие множества поисковых процессов и модели отбора.
Особенностью локально-эволюционного подхода является возможность осуществлять поиск в сильно ограниченном пространстве поиска. Эта особенность позволяет существенно сократить временные затраты по сравнению с классическими подходами и повысить качество самого решения.
Дополнительное сжатие пространства поиска становится возможным за счет использования при построении расписания эвристик особого типа, а именно рекурсивных.
При решении задачи используются следующие исходные данные:
Недопустимым планом расписания является план, содержащий хотя бы один конфликт по преподавателю или группе, или аудитории, поэтому при решении задачи данным методом используются следующие ограничения:
Для занятий, длительность проведения которых больше одного кванта (два академических часа или «пара») планового времени, вводится дополнительное ограничение последовательного по времени захвата квантового времени.
В расписании представлены все плановые занятия из P – это требование полноты расписания.
Обычно перед составлением расписания закрепляют сочетания (w, p) в виде нагрузки преподавателя, благодаря чему сочетание (w, p) в расписании присутствует и в нагрузке.
В задаче составления оптимального расписания нужно найти расписание с минимальной ценой. Поэтому в данном методе решения задачи используется в качестве оценочной функции следующая эвристическая функция:
Q(S) = (a1G1 + a2G2 + a3G3 + a4G4 + a5G5) + (a5A1 + a6A2) + (a7W1 + a8W2 + a9W3) + a10P1, (1)
где G1 – количество межкорпусных переходов в течение дня у групп (подгрупп) учащихся; G2 – количество «форточек» в расписании групп (подгрупп); G3 – степень разнообразия занятий в течение дня у групп (подгрупп); G4 – степень отклонения от вида планирования занятий; G5 – выход за пределы рекомендуемого календаря учебного времени; A1 – количество «форточек» в расписании аудитории; A2 – степень загрузки аудиторий во время занятий; W1 – количество межкорпусных переходов в течение дня у преподавателя; W2 – выход за пределы рекомендуемого календаря рабочего времени преподавателя; W3 – количество «форточек» в течение дня у преподавателя; P1 – степень покрытия неполным расписанием учебных планов; a1, a2, a3,…a10 – масштабирующие коэффициенты.
Выбор масштабирующих коэффициентов отражает принятую оценку понятия «хорошее» расписание. Но поскольку это представление субъективно, то возникает проблема противоречивости. Осуществляется поиск компромисса между противоречащими факторами. Система правил едина, поэтому невозможно автоматически сделать идеальное расписание одному преподавателю, проигнорировав интересы других, и расписание, рассматриваемое одним преподавателем как «хорошее», будет не соответствовать представлениям о «хорошем» расписании другого преподавателя или студента.
В локально-эволюционном алгоритме разработаны две рекурсивные эвристики для рассматриваемой задачи:
1) HSG – планирование занятий; 2) HSX – перенос занятий в расписании.
Первая эвристика предназначена для выращивания расписания и способна работать с неполным расписанием; вторая – для оптимизации полного расписания.
HSG: действие данной эвристики состоит из двух шагов. Во-первых, выбирается занятие, которого еще нет в расписании. Во-вторых, выбирается время и аудитория для проведения данного занятия. При реализации вставки работают эвристики, поощряющие «хорошее» расписание и штрафующие за «плохое», выигрывает вариант, обеспечивающий максимум оценочной функции.
HSX: перенос занятия pa4 в плане sa = (aa1, ta2, wa3, pa4) в другую аудиторию и в другое время. То есть изменение значения сочетания (aa1, ta2) на (ab1, tb2). Если при этом существует sb = (ab1, tb2, wb3, pb4), то данная процедура повторяется для pb4. С целью устранения зацикливания глубина рекурсии должна быть искусственно ограничена.
Достоинство метода – получение хороших приближенных решений уже на первых итерациях и высокая вероятность получения точного решения за достаточно большое число итераций. Очевидное преимущество локально-эволюционного алгоритма – снижение вычислительной сложности алгоритма по сравнению с классическими алгоритмами. Еще одним преимуществом является гибкость, которая выражается в совместном действии различных стратегий, а также возможность видоизменять участвующие в нем эвристические стратегии.
Важная особенность локально-эволюционного алгоритма – недетерминистический характер вычислений, который является следствием внутреннего параллелизма вычислений. Это выражается в асинхронности действия различных локальных стратегий.
Основной недостаток алгоритма – его эвристический характер. Сочетание различных стратегий позволяет преодолевать большее число локальных минимумов по сравнению с обычным эвристическим алгоритмом. Еще один очевидный недостаток – располагать можно только лишь статистическими оценками эффективности данного алгоритма, что требует проведения огромного количества экспериментов на различных задачах для получения достоверной информации [6].
В информатике и программной инженерии агент – самостоятельный объект системы, обладающий свойством коммуникабельности и наделённый собственной системой принятия решений.
Коммуникабельность – способность агента обмениваться сообщениями с другими агентами и прочими объектами системы.
Сутью применения агентного подхода к какой-либо задаче является то, что задача разбивается на несколько более мелких задач. Для решения каждой мелкой задачи выделяется агент. Цель агента – найти такое решение своей задачи, чтобы оно согласовалось с решениями других агентов. Агенты добиваются согласования друг с другом путем обмена информационными сообщениями. В итоге агенты находят решения для своих задач, а значит и для исходной задачи; либо выясняется, что решения нет. Идея применения агентного подхода к задаче составления расписания состоит в том, чтобы заменить агентами каждого пользователя расписания. Цель каждого агента – найти такое расписание для пользователя, чтобы оно соответствовало ограничениям задачи и ограничениям самого пользователя, имело бы наибольший уровень пользы для пользователя и не противоречило расписаниям других пользователей.
Все агенты запускаются в рамках некоторого контейнера (агентной системы). Агенты выполняют локальные вычисления, обмениваются сообщениями, что в итоге приводит к решению задачи, то есть построению расписания занятий. В идеале пользователь расписания может один раз запрограммировать своего агента-представителя, который будет замещать его в дальнейшем по всем вопросам составления расписания проведения занятий и встреч, общаясь напрямую с агентами других агентов. Кроме того, отпадает необходимость в централизованном сборе и хранении предпочтений и пожеланий пользователей расписания, так как все эти данные хранит агент, другим агентам достаточно обратиться к нему с запросом на получение необходимых данных. Пользователь может в любой момент перепрограммировать своего агента и через некоторое время увидеть результат – новое расписание, соответствующее его новым требованиям.
Основа построения собственного многоагентного алгоритма составления учебного расписания – точная постановка задачи в виде математической модели. В целях упрощения изложения в такой модели будем называть лиц, заинтересованных в результатах процесса составления расписания, пользователями расписания. К ним относятся преподаватели и учебные группы. Роль первых – провести лекционное или практическое занятие; роль последних – присутствовать на занятиях. Введём следующие обозначения.
Учебные группы и потоки: g∈G – номер учебной группы; G – множество номеров всех учебных групп; |G| = γ – количество групп. Каждая группа входит в один или несколько потоков. При объединении групп в один поток используются следующие принципы:
4) поток может состоять из одной учебной группы.
Пусть R – множество номеров учебных потоков; R = ρ – количество потоков; r∈R – номер потока.
Каждая группа самостоятельный поток, поэтому ρ ≥ γ.
Допустим, что Cr ⊂ G – поток. Потоком называется любое подмножество множества групп. C = {C1, C2,..., Cp} – множество всех потоков. Потоки могут пересекаться между собой.
Преподаватели: p∈P – номер преподавателя; P – множество всех преподавателей. P = π – количество преподавателей.
Пользователи расписания: объединение множества всех групп с множеством всех преподавателей: M = G ∪ P, m ∈M – уникальный номер пользователя расписания.
Время: w∈Wg – номер учебного дня недели; Wg∈W = {1, 2,..., 7} – множество учебных дней группы; g, W – множество всех дней недели; j ∈J = {1, 2,..., 8} – номер учебной пары; T = {(w, j)| w ∈W; j ∈J} – множество таймслотов. Таймслотом называется элементарная единица времени в задаче составления расписания. Например, таймслот (1, 2) означает: понедельник, вторая пара. Для каждого пользователя m известно множество таймслотов, когда он свободен, т.е. в это время занятие может быть проведено Tm+ ⊂ T, и множество недоступных таймслотов Tm− ⊂ T T( m+ ∪Tm− =T T; m+ ∩Tm− = ∅), например, выходные дни, когда занятия не могут быть проведены.
Занятия: преподаватели проводят лекционные и практические занятия; лекционные занятия проводятся у всего потока сразу; практические занятия – только у одной группы; требуют другого аудиторного фонда. Например, практические занятия по информатике должны проходить в компьютерном классе. Используются следующие обозначения для занятий: Sr = {1, 2, ..., σr} – множество номеров лекционных занятий, читаемых на потоке r; sr∈Sr – номер лекционного занятий; Qr = {1, 2, ..., θr} – множество номеров практических занятий, проводимых на потоке r; qr∈Qr – номер практического занятия.
Глобально уникальным идентификатором занятия будет пара «номер потока – номер занятия на потоке». Занятия существенно зависят от потока. Лекционное занятие однозначно идентифицируется парой значений «номер потока – номер лекционного занятия»: (r, sp).
где RS – множество всех лекционных занятий. Количество лекционных занятий
Практическое занятие однозначно идентифицируется тройкой значений «номер потока – номер практического занятия – номер группы»: (r, g, qr)∈RQG.
где RQG – множество всех практических занятий. Количество практических занятий:
где Cr – количество групп в потоке.
При дальнейшем описании задачи нам в большинстве случаев будет неважно, какое занятие рассматривается – лекционное или практическое. Поэтому под занятием будем понимать элемент из объединения двух множеств – множества лекционных и множества практических занятий:
E = RS ∪ RQG. (6)
Учебный план закрепляет за каждым преподавателем предметы, которые он должен будет провести в течение семестра. Назначение лекционных занятий:
δ1 : RS → P, (7)
где P – множество преподавателей; RS – множество лекционных занятий.
В общем случае учебный план можно записать как δ1 : E → P. Отсюда следует:
δ1(e ) = { δ1(e) , e∈RS, (8)
δ2(e ) = { δ1(e) , e∈RS.
Зная учебный план, можно вычислить величину Em – множество занятий, проводимых пользователемпреподавателем (или для пользователя-группы) с номером m:
Em = {e| m∈P ∧ δ(e) = m} ∪ {e = (r, s)| m ∈ Cr ∧ s ∈ Sr} ∪ {e = (r, q, s)| m ∈ Cr ∧ q ∈ Qr}. (9)
Аудиторный фонд – множество аудиторий, где могут быть проведены занятия; A – множество всех аудиторий и помещений. Для каждого занятия e выделяется некоторое подмножество аудиторий Ae ⊂ A; аудитория для проведения занятия выбирается только из этого подмножества.
Неизвестные функции задачи: неизвестные в данной задаче – расписание времени и расписание аудиторий; расписание времени – отображение множества предметов на множество таймслотов:
τ : E → T, (10)
где E – множество всех занятий; T – множество всех таймслотов.
Расписание аудиторий – это отображение множества занятий намножество аудиторий:
α: E → A, (11)
где E – множество всех занятий; A – множество всех аудиторий.
В задаче используются следующие ограничения.
1) один преподаватель в каждый момент времени может проводить не более одного занятия:
∀p ∈ P,∀e1,e2 ∈ E: e1 ≠ e2∧δ(e1) = δ(e2) = p ⇒ τ(e1) ≠ τ(e2); (12)
2) в одной аудитории в каждый момент времени может проводиться не более одного занятия:
∀a ∈ A, ∀ e1, e2 ∈ E: e1 ≠ e2 ∧ α(e1) = δ(e2) = a ⇒ τ(e1) ≠ τ(e2); (13)
3) у одной группы в каждый момент времени может проводиться не более одного занятия:
∀g ∈ G: (e1 = (r1, …), e2 = (r2,…) ∈ E ∧ g ∈ Cr1 ∧ g ∈ Cr2∧ e1 ≠ e2) ∨;
∨(e1 = (…, g), e2 = (…, g) ∈ E ∧ e1 ≠ e2) ⇒ τ(e1) ≠ τ(e1). (14)
Другими словами, для каждых двух пересекающихся потоков в каждый момент времени не может быть разных лекционных занятий в одно и то же время, и для каждой группы не может быть разных практических занятий в одно и то же время. Это ограничение удобно проверять, предварительно разбив все занятия на γ классов. В класс входят все занятия, которые читаются группе g персонально или в каком-либо потоке:
Kg ⊂ E, g ∈ G(g1 ≠ g2 ⇒ Kg1 ∩ Kg2 = ∅). (15)
Ограничение 3 будет выполнено тогда и только тогда, когда все занятия групп одного класса проводятся в разное время.
Опишем приоритеты занятий. Очевидно, что не все занятия имеют одинаковую важность в рамках учебного процесса. Для них можно задать порядок по приоритету. Более приоритетные занятия будут в первую очередь занимать время и место; менее приоритетные занятия уже не смогут претендовать на эти ресурсы. Итак, приоритеты занятий – отношение частичного порядка на множестве занятий:
e1 > e2 ⇔ U(e1) ≥ U(e2), (16)
где U(e) – «полезность» занятия e:
(U(e) = |Me| + k1(e) + k2(e) + k3(pe); Me – множество групп, у которых проводится занятие e:
Me = {m|(e = (r, s) ∈ RS ∧ m ∈ Cr) ∨ (e = (r, q, m) ∈ RQG)};
k1(e)∈{0, 5, 10} – характеризует степень важности занятия для специальности (0 – «ненужные занятия»; 5 – важное, но не по специальности; 10 – занятие по специальности); k2(e) ∈{0, 2} – 0 – младшие курсы; 2 – старшие курсы; pe= p, δ(e) = p – номер преподавателя, который ведет занятие e; k3(pe)∈{0...5} – оценка преподавателя как научного сотрудника: больше значит, что преподаватель более ценный научный сотрудник; в случае равенства занятия упорядочиваются в лексикографическом порядке.
Предпочтения пользователей. Важная часть предлагаемой модели – предпочтения пользователей. Каждое предпочтение – это числовая оценка в диапазоне от 0 до 1; 0 соответствует наименьшему уровню предпочтения; 1 – наибольшему. В модели имеют место два вида предпочтений: предпочтения пользователя m∈M о времени проведения занятия; предпочтения пользователя m∈M о месте проведения занятия.
Качество решения ограничивается следующими критериями:
В паре критериев вначале максимизируется первый критерий (время), затем второй (место). Такая структура гарантирует, что приоритетные занятия получат лучшее время и место. Считается, что время проведения занятия важнее при составлении расписания, поэтому вначале определяется время, а затем место проведения занятия.
Решением задачи являются неизвестные функции при условии выполнения всех ограничений и максимальном значении критерия качества.
Основные достоинства агентного подхода:
К недостаткам агентного подхода можно отнести:
В основе данного метода лежит использование различного рода эвристик или эвристических алгоритмов, при разработке которых используются интуитивные предположения, не подкрепленные соответствующим математическим обоснованием. Формирование расписания занятий с помощью некоторых правил (эвристик) позволяет несколько ускорить поиск наилучшего расписания, но использование таких алгоритмов в большинстве случаев гарантирует лишь нахождение приближенного решения (достижение локального экстремума). В этом случае возникает проблема оценки близости найденного локального экстремума к глобальному экстремуму.
Эта проблема решается путем сравнения расписания, полученного эвристическим методом и расписания, полученного методом перебора для близкой задачи малой размерности. Несмотря на указанный недостаток, эвристические алгоритмы продолжают оставаться достаточно эффективным инструментом поиска «лучшего» в некотором смысле решения в тех случаях, когда нахождение наилучшего решения крайне затруднено или невозможно.
При составлении расписания занятий в образовательных системах массового обучения предлагается использовать математический аппарат нечеткой логики для перехода от «жестких» ограничений к более «мягким» требованиям.
Однако несмотря на то, что данный подход позволяет значительно упростить формализацию требований, предъявляемых к расписанию, рассмотрение наиболее важных требований в качестве «мягких» требований может привести к «плохому» расписанию (появлению «окон», «накладок» и т.д.).
Расписание учебных занятий для учебных заведений (школ, колледжей, вузов и т.п.) относится к классу задач целочисленного программирования с булевыми переменными. Французские специалисты по методам исследования операций А. Кофман и А. Анри-Лабордер называют ее задачей «планирования загрузки преподавательского состава и обеспечения студентов аудиториями».
Формально задачу составления учебного расписания можно поставить следующим образом:
Задано множество преподавателей T, множество «учебных дисциплин» (учебный план) D, множество аудиторий H и множество рабочих часов (часовая сетка) S.
Требуется найти расписание, обслуживающее все дисциплины, удовлетворяющее требованиям преподавателей к проведению занятий и не имеющее противоречий и накладок относительно аудиторий.
Для формирования допустимого расписания в работе рассматривается возможность применения метода замещений (МЗ), который является вариантом метода ветвей и границ с использованием двудольного графа со взвешенными ребрами и предписанными степенями вершин. В качестве ограничений, исходящих от преподавателей и условий конкретного учебного заведения, предлагается использовать так называемыевектора топологии.
Решение задачи составления расписания сводится к следующейсхеме:
Требуется найти каркас, удовлетворяющий целевой функции
где x∈{0,1}, сij – вес ребра, соединяющего вершины i и j.
где m – число ребер в исходном подграфе, и ограничениям Аmax = (A1, …, Ai, …, An), Аmin = (a1, …, ai, …, an), где Аmax, Amin – векторы допустимых степеней (так назывемые векторы топологии).
Алгоритм сводится к следующим построениям.
В результате получаем граф, ребра которого образуют соответствие между множеством вершин первой доли графа T и множеством вершин второй доли графа D.
Преимущество алгоритма, сформированного на основе метода замещений по сравнению с алгоритмами, реализующими метод ветвей и границ, заключается в том, что алгоритмы метода замещений позволяют следить за топологией искомого подграфа даже при существенных отличиях в степенях его вершин при решении задач со списком степеней, также позволяют формировать правило остановки алгоритма по функциям от количества исследованных узлов в дереве решений, от таймера ЭВМ и т.д., устраняя «проклятие размерности» при дефиците вычислительных ресурсов путем выдачи приближенного решения.
На основе обобщения идей теории последовательных решений и динамического программирования была разработана общая схема последовательного анализа вариантов (ПАВ). С точки зрения формальной логики схема ПАВ сводится к такой последовательности повторения процедур:
Методика последовательного развития, анализа и отсева вариантов состоит в таком способе развития вариантов и построения операторов их анализа, которые позволяют отсеивать бесперспективные начальные части вариантов до их полного построения.
Поскольку при отсеивании бесперспективных начальных частей вариантов отсеивается тем самым и все множество их продолжений, происходит значительная экономия вычислительных затрат.
На базе этой общей схемы был разработан целый ряд алгоритмов последовательного анализа вариантов, которые получили широкое применение в практике.
Приближенные методы можно разбить на следующие группы: методы локальной оптимизации, модификации точных методов; эвристические методы, максимально учитывающие специфику решаемых задач; методы случайного поиска; методы, сочетающие локальную оптимизацию со случайным поиском.
Отметим, что многие приближенные алгоритмы позволяют решать задачи дискретной оптимизации в диалоговом режиме. Это дает возможность в зависимости от выделяемых ресурсов (времени, памяти компьютера и т.п.) последовательно улучшать полученное решение путем изменения всех или некоторых исходных данных.
Значительная часть приближенных алгоритмов дискретной оптимизации базируется на использовании вычислительных схем известных точных методов, таких как метод ветвей и границ и метод последовательного анализа вариантов и прочих.
Одними из наиболее развитых приближенных методов являются методы локальной оптимизации, имеющие своей целью отыскание локально оптимальных решений. Нередко в этих методах на определенных этапах решения задачи используются методы случайного поиска, а также различные способы (эвристики), которые дают возможность сократить ход вариантов и максимально учитывают специфику задачи.
Следует отметить, что алгоритмы, в которых комбинируются различные идеи, на практике часто оказываются наиболее эффективными. С помощью этих методов были решены многочисленные сложные задачи классификации объектов, размещения, планирования и проектирования. Основное преимущество этих методов – простота реализации, а основной недостаток – это то, что они не могут адаптироваться к условиям решаемой задачи. Значительно более гибкими являются методы, у которых вероятностный закон зависит от исходов предыдущих испытаний и изменяется от итерации к итерации. Это методы случайного поиска с обучением.
Методы случайного поиска используются для приближенного решения многомерных задач о ранге, а также задач линейного булева программирования большой размерности.
Детализация схемы ПАВ происходила в нескольких направлениях. В связи с решением задач линейной или древовидной структуры был сформирован обобщенный принцип оптимальности для монотонно рекурсивных функционалов, на основе которого можно строить схему решений, свободную от некоторых ограничений, присущих каноническим процедурам динамического программирования.
Для структур, которые имеют форму дерева, были исследованы вопросы, связанные с порядком просмотра ветвей, и найдены способы минимизации числа массивов информации, необходимой для реализации процедур ПАВ.
Метод ПАВ использовался для решения большого количества важных задач оптимального планирования и проектирования, таких как: расчет транспортных сетей; размещение на сети типа дерева; проектирование распределительных электрических сетей; выбор оптимальных параметров магистральных газопроводов и т.п.
Далее на основе алгоритмической схемы ПАВ были разработаны эффективные методы конструирования, анализа и отсева вариантов для решения многочисленных задач календарного планирования. Относительно теории календарного планирования (КП) были обоснованы точные методы решения разных классов задач малой размерности, доказаны необходимые и достаточные условия приоритетной решаемости для задач КП с однотипным оборудованием, разработаны эффективные способы, которые используют правила доминирования.
Для решения задач большой размерности дискретного сепарабельного и линейного целочисленного программирования были разработаны декомпозиционные алгоритмы, которые базируются на схемах последовательного анализа и отсева вариантов. При этом сужение исходного множества вариантов осуществлялось путем отсева отдельных компонент, что дало возможность свести решение исходной задачи большой размерности к решению совокупности подзадач малой размерности.
Метод ПАВ базируется на отсеве бесперспективных элементов как по ограничениям, так и по целевой функции. Его идеи рассмотрим на примере задачи дискретного программирования. Схему метода ПАВ изложим для следующей задачи:
min f(x).
x ∈ D(XS)
При ограничениях:
где Qj = (q1j ,...,q jn ) – заданные конечные множества. Вектор x = (x1,...,xn ) назовем решением, если его компоненты xj ∈Qj , j =1,n.
Множество всех решений обозначим через Ω. Решение называется допустимым, если оно удовлетворяет неравенству (17).
Множество всех допустимых решений обозначаем через Ωj .
Вектор x(p) (x1,...,xn ), p < n будем называть частичным решением, если xj ∈Qj.
Если при этом он может быть достроен до допустимого решения (x1,...,xp ,xp+1,xn ),будем называть его допустимым частичным решением.
Множество всех частичных решений задачи схематически можно изобразить в виде дерева решений H, изображенного на рисунке. Вершинам его взаимно-однозначно соответствуют частичные решения, причемвисячим вершинам соответствуют полные решения p∈n. Процесс решения задачи с помощью метода ПАВ можно интерпретировать как продвижение на дереве H, начиная с его корня, отвечающего частичному решению x(0).
Дерево решений
Метод эффективен для задач небольшой размерности, так как при большой размерности задачи время решения задачи будет существенно увеличиваться.
Генетический алгоритм – новейший, но не единственно возможный способ решения задач оптимизации. С давних пор известно два основных класса методов решения таких задач – переборный и эвристический. Идея целесообразности использования генетического алгоритма состоит в том, что он, комбинируя переборные и эвристические методы, позволяет находить приближенное решение, точность которого возрастает при увеличении времени расчета.
Известно, что генетический алгоритм зарекомендовал себя как быстрый метод, позволяющий получать приемлемые решения за допустимое время, которому присущи как преимущества, так и недостатки.
Основные объекты генетических алгоритмов – это особь (индивидуум), хромосома, ген, генотип, фенотип, функция пригодности.
Основными операциями, или, как это принято в теории генетических алгоритмов, операторами, выполняемыми над объектами, являются селекция, скрещивание и мутация. Особь включает в себя одну или несколько хромосом, каждая хромосома в свою очередь состоит из одного или нескольких генов.
В качестве логической модели особи выступает кортеж кодов хромосом. Генотипом особи принято считать упорядоченный набор генов некоторой особи, фенотипом особи – набор значений (признаков) этих генов. Допустима такая аналогия: генотип – упорядоченная совокупность варьируемых переменных; фенотип – упорядоченная совокупность значений этих переменных; функция пригодности – целевая функция оптимизационной задачи целочисленного программирования.
Предлагается использовать в качестве генов настроечные коэффициенты wj алгоритма составления расписания. В результате мутаций будут получены новые наборы настроечных коэффициентов, а, как следствие, результаты работы алгоритма будут различны. При этом оценку качества составленного расписания следует проводить с использованием значений wj заданных диспетчером. Таким образом, учитывается возможность генерации расписания, наиболее удовлетворяющего оценкам качества с точки зрения диспетчера, при использовании несколько измененных оценок качества в процессе его генерации. Хромосома такого генетического алгоритма будет представлять собой набор действительных чисел: {w1, w2, w3,…, wm}, где w1…wm – гены хромосомы, настроечные коэффициенты алгоритма составления расписания; m – количество настроечных коэффициентов алгоритма.
Целью работы генетического алгоритма является достижение максимума функционала:
где Ril – качество расположения i-го занятия на l-й позиции в расписании; kjl – значение, полученное по j-му критерию оценки качества расположения занятия на l-й позиции в расписании; wj – весовой коэффициент j-го критерия оценки качества; m – количество критериев оценки качества; l – возможная позиция i-го занятия в расписании; Ri – качество расположения i-го занятия в расписании; h – количество возможных вариантов расположения занятия в расписании; R – качество составленного расписания. Преимущества генетического алгоритма:
Недостатки генетического алгоритма:
В процессе решения задачи построения расписания необходимо назначить каждое занятие на конкретный промежуток времени рабочего дня недели. Поскольку длительность одной пары фиксирована, то заранее известны все возможные интервалы времени, на которые могут быть назначены пары.
Обозначим через W множество всех таких известных интервалов времени в рассматриваемом при составлении расписания плановом периоде (например, в течение шестидневной рабочей недели).
Пронумеруем интервалы множества W, начиная с первого по времени интервала, и будем считать элементы множества W упорядоченными в соответствии с номерами его интервалов: N = {1, 2, …, n}, где n = |W|.
Если для проведения какого-либо занятия аудитория не была назначена заранее (до составления расписания), в процессе составления расписания необходимо также назначить аудиторию для проведения такой пары. Расписания занятий в вузе являются периодическими, поэтому достаточно составить расписание учебных занятий на один плановый период. Обычно периодом является одна неделя или же две последовательные недели (если расписания для них существенно отличаются одно от другого). Нарушения периодичности, возникающие в процессе реализации расписания, можно учитывать в режиме корректировки основного расписания, составленного на один плановый период. При построении расписания учебных занятий необходимо выполнить следующие требования (условия):
Для представления исходных данных задачи построения оптимального расписания занятий, а также для представления процесса ее решения предлагается использовать сетевую модель. При этом процесс построения расписания сводится к раскраске вершин V графа G = (V, E) с множеством ребер E и дополнительными ограничениями на множества цветов, которые разрешается использовать для различных вершиниз множества V.
Выбор теоретико-графовой модели определялся тем, что процессобучения в вузе можно считать детерминированным, поскольку для каждой группы учащихся заранее определен список предметов (курсов), и этот список не изменяется в образовательном процессе в течение длительного периода времени. Преподавательский коллектив и группы студентов, как правило, остаются неизменными во время всего планового периода. В силу такой детерминированности задача построения расписания может быть сформулирована в терминах раскраски вершин графа. Функцию φ называют раскраской (вершин) графа G = (V, E), если для каждой вершины vi ∈ V она определяет натуральное число (называемое цветом) φ(vi) ∈ N так, что из включения [vi, vj] ∈ Е следует соотношение φ(vi) ≠ φ(vj). Здесь N обозначает подмножество множества натуральных чисел. В задаче оптимальной раскраски графа требуется построить раскраску φ: V → N вершин графа G = (V, E), которая содержит минимальное число цветов. Заключение
В рамках данной работы были проанализированы следующие подходы к решению задачи составления расписаний: локально-эволюционный метод, многоагентный, интеллектуальный, метод замещений, метод последовательного анализа вариантов, генетический алгоритм, метод раскраски графов.
Таким образом, можно сделать вывод, что задача составления расписаний университета относится к классу дискретных задач оптимизации с конечным множеством альтернатив.
Решение задачи составления расписания чрезвычайно осложняется многокритериальностью и многовариантностью. Для разрешимости рассматриваемой задачи необходимо применить комплексный подход, учитывающий достоинства всех рассмотренных в рамках данной статьи методов.
ЛИТЕРАТУРА
Поступила 05.03.2014
METHODS OF SOLVING MULTICRITERIA PROBLEM SCHEDULE
OF TRAINING SESSIONS UNIVERSITY
M. DEKANOVA
The existing approaches to solving the problem of scheduling such as locally-evolutionary method, multiagent approach, intellectual method, a method of successive analysis of variants, genetic algorithm, a method of coloring of graphs have been analized. The advantages and disadvantages of them have been emphasized. As output the problem of scheduling refers to the class of the activation discrete problems with a finite set of alternatives. The solution of the scheduling problem is complicated with the multicriteriality and the multivariance. It has been shown that it is nesessary to apply the integrated approach reckoning in the advantages of all the considered in this work methods.