|
ное распределение годовой учебной нагрузки между преподавателями и максимизировать
суммарное предпочтение преподавателей при назначении дисциплин.
Для описания математической модели обозначим через
I={1,...,m} множество препода-
вателей, а через
J={1,...,n} – множество дисциплин. Пусть c
i
и
a
i
– наименьший и наибольший
© Л.А. Заозерская, В.А. Планкова, 2017
__________________________
* Работа выполнена при поддержке проекта РФФИ № 16-01-00740.
172
возможные объемы нагрузки в часах для преподавателя
i, i=1,…,m, которые зависят от долж-
ности и ставки преподавателя;
t
j
– число неделимых частей (видов нагрузки) предмета j,
j=1,…,n;
k
j
b
– объем в часах k-ой части предмета j,
k
ij
l – коэффициент предпочтения i-ым
преподавателем
k-ой части предмета j, S
j
– максимально допустимое количество частей j-го
предмета, назначаемых одному преподавателю (
S
j
≤
t
j
),
j=1,…,n.
Для перехода к задаче булева программирования введем переменные:
1
=
ij
z
, если пре-
подаватель
i читает предмет j, иначе
0
=
ij
z
;
и
1
=
k
ij
z
, если преподаватель
i читает k-ую часть
предмета
j, иначе
0
=
k
ij
z
, где
.
,...,
1
,
,
j
t
k
J
j
I
i
=
∈
∈
Построим двухкритериальную модель задачи РУН:
min
max
1
→
∑
=
∈
n
j
ij
I
i
z
(1)
max
1
1
1
→
∑∑∑
=
=
=
k
ij
m
i
n
j
t
k
k
ij
z
l
j
(2)
при условиях
,
,
1
1
I
i
a
z
b
c
i
k
ij
n
j
t
k
k
j
i
j
∈
≤
≤
∑∑
=
=
(3)
,
,...,
1
,
,
1
1
j
m
i
k
ij
t
k
J
j
z
=
∈
=
∑
=
(4)
,
,
,
1
J
j
I
i
z
S
z
z
ij
j
k
ij
t
k
ij
j
∈
∈
≤
≤
∑
=
(5)
{ }
,
,
,
1
,
0
J
j
I
i
z
ij
∈
∈
∈
(6)
{
}
.
,...,
1
,
,
,
1
,
0
j
k
ij
t
k
J
j
I
i
z
=
∈
∈
∈
(7)
В задаче требуется минимизировать наибольшее из числа предметов, назначенных пре-
подавателям, – целевая функция (1), и максимизировать суммарные предпочтения препода-
вателей – целевая функция (2). Ограничения (3) означают, что суммарная нагрузка препода-
вателя i не должна превышать максимально возможного объема часов, а также быть не
меньше минимально возможного объема часов, соответствующего его доле ставки. Равенст-
ва (4) показывают, что любая часть каждого предмета должна быть прочитана ровно один
раз. Ограничения (5) связывают переменные
ij
z и
k
ij
z следующим образом:
{
}
.
1
,...,
1
1
=
∈
∃
⇔
=
k
ij
j
ij
z
t
k
z
Это означает, что преподаватель i читает предмет j тогда и только тогда, когда он чита-
ет хотя бы одну часть предмета j. Заметим, что коэффициент
k
ij
l
можно рассматривать как ко-
эффициент эффективности назначения i-му преподавателю k-ой части предмета j. Тогда вто-
рой критерий в задаче будет интерпретироваться как максимизация суммарной эффективно-
сти распределения учебной нагрузки между преподавателями. Для решения построенной за-
дачи (1) – (7) можно применять методы поиска Парето-оптимальных решений, метод после-
довательных уступок, метод свертки критериев.
Если ввести параметры R
i
– максимально возможное количество предметов, назначае-
мых i-му преподавателю, i=1,…,m, тогда можно рассмотреть однокритериальную постановку
задачи РУН:
max
)
(
1
1
1
→
=
∑∑∑
=
=
=
k
ij
m
i
n
j
t
k
k
ij
z
l
z
f
j
173
при условиях (3) – (7) и ограничениях
.
,
1
I
i
R
z
i
n
j
ij
∈
≤
∑
=
В качестве примера с реальными данными нами была рассмотрена задача РУН для од-
ной из выпускающих кафедр Омского государственного университета (6 ставок, 13 препода-
вателей, 16 дисциплин с общим числом неделимых частей 47). На первом этапе решения за-
дачи проведено закрепление за преподавателями индивидуальной нагрузки, например, руко-
водство кафедрой, участие в ГАК, научное руководство аспирантами и студентами, чтение
спецкурсов и т.д., а также скорректированы исходные данные. На втором этапе была по-
строена указанная однокритериальная задача булева программирования с числом перемен-
ных 815 и числом ограничений 757. Для ее решения применен адаптированный алгоритм пе-
ребора L-классов и получена серия допустимых решений. Оптимальные решения этой задачи
при различных значениях параметров R
i
и S
j
получены с помощью пакета CPLEX.
Предложенные выше модели задачи распределения учебной нагрузки преподавателей
рассматриваются нами как базовые для применения на практике. В качестве дополнительных
ограничений можно учитывать квалификацию преподавателей для чтения лекций по дисци-
плинам, назначение преподавателю, например, не более одной новой дисциплины, взаимные
отношения преподавателей при ведении одной дисциплины, запрещение некоторых назначе-
ний, специфические пожелания преподавателей и др. Модифицированные модели могут
быть использованы при создании автоматизированной системы распределения учебной на-
грузки преподавателей.
Do'stlaringiz bilan baham: |
