ВУЗ:
Составители:
Рубрика:
37
носятся в таблицу. Здесь n – общее число предметов, q - количество учеб-
ных групп, р – общее количество уроков, которые можно провести в течение
недели (например: пятидневка, по 6 уроков в день, p = 30).
Заполненная таблица представляет собой некоторое расписание. Заштри-
хованные ячейки означают, что они не участвуют в построении расписания.
То есть, например, в
группе 1 в понедельник предусмотрено 4 урока, в груп-
пе 2 − пять и т.д. Заранее зафиксированная структура расписания гаранти-
рует отсутствие “окон” у школьников и позволяет изначально выполнять не-
которые требования СанПин (например, что максимальное количество уро-
ков должно быть в среду и т.д.) .
Представление учебного расписания
Учебные г
ру
ппыДень
недели
Номер
урока
Гр.1 Гр.2 … Гр. q
1 1 g
1
+1 … g
q-1
+1
2 2 … … …
3 3 … … …
4 4 … … …
5 … … …
Понедельник
6 …
… … … … …
… p g
1
g
2
… n
Для каждого предмета k (
n=k 1,
) вводится в рассмотрение множество
I(k) – номера уроков, на которых он может проводиться (в соответствии с
учебным планом или обязательными требованиями преподавателя). Соот-
ветственно, множества
(i)K
j
- это номера предметов j–й уч. группы, которые
могут быть проведены на i-ом уроке.
Рассмотрим матрицу совместимости предметов S, которая вводится сле-
дующим образом:
⎩
⎨
⎧
.1,1,1,
0,
n=k,n=rиначе,
rпредметомссовместимkпредметесли
=S
kr
Предметы являются несовместимыми, если они используют общий ре-
сурс (преподаватель или кабинет). Такие предметы не могут находиться в
расписании на одной строке.
Обязательные требования к расписанию могут быть описаны следующей
математической моделью:
min
11
1
→
∑∑ ∑ ∑
≤
−
ilik
p
=i
q
=j
jj
g
j
g>l
lk
zzS
gk<
n=kI(k),i=z=z
ik
I(k)i
ik
1,0,1, ∉
∑
∈
37
носятся в таблицу. Здесь n общее число предметов, q - количество учеб-
ных групп, р общее количество уроков, которые можно провести в течение
недели (например: пятидневка, по 6 уроков в день, p = 30).
Заполненная таблица представляет собой некоторое расписание. Заштри-
хованные ячейки означают, что они не участвуют в построении расписания.
То есть, например, в группе 1 в понедельник предусмотрено 4 урока, в груп-
пе 2 − пять и т.д. Заранее зафиксированная структура расписания гаранти-
рует отсутствие окон у школьников и позволяет изначально выполнять не-
которые требования СанПин (например, что максимальное количество уро-
ков должно быть в среду и т.д.) .
Представление учебного расписания
День Номер Учебные группы
недели урока Гр.1 Гр.2 Гр. q
1 1 g1+1 gq-1+1
Понедельник
2 2
3 3
4 4
5
6
p g1 g2 n
Для каждого предмета k ( k = 1, n ) вводится в рассмотрение множество
I(k) номера уроков, на которых он может проводиться (в соответствии с
учебным планом или обязательными требованиями преподавателя). Соот-
ветственно, множества K j (i) - это номера предметов jй уч. группы, которые
могут быть проведены на i-ом уроке.
Рассмотрим матрицу совместимости предметов S, которая вводится сле-
дующим образом:
⎧0, если предмет k совместим с предметом r
S kr =⎨
⎩1, иначе, r = 1, n , k = 1, n.
Предметы являются несовместимыми, если они используют общий ре-
сурс (преподаватель или кабинет). Такие предметы не могут находиться в
расписании на одной строке.
Обязательные требования к расписанию могут быть описаны следующей
математической моделью:
p q
∑∑ ∑ ∑ S k l z k i z l i → min
i=1 j=1 g
j −1
g j
∑ z k i = 1, z k i = 0, i ∉ I(k),k = 1, n
i∈I(k)
