Дипломная работа: Разработка математической модели и ПО для задач составления расписания
- Равномерность распределения нагрузки классов между днями расписания;
- Контроль окон в расписании преподавателей;
- Программа учитывает то обстоятельство, что классы могут произвольно объединяться и дробиться (классы могут объединяться в потоки или же дробиться на более мелкие подгруппы, причем эти подгруппы, в свою очередь, могут служить основой для объединения в более крупные группы. Пример: в школе №1859 есть 2 старших класса, но в каждом из этих классов есть две подгруппы по специализации, занятия по общеобразовательным предметам проводятся сразу для всего класса, а предметы по специализации – отдельно. Но поскольку подгруппы по специализации слишком малы, а преподавателей не хватает, по некоторым предметам подгруппы 11а и 11б также могут объединяться (например, на ин.яз.) – это усложняет обеспечении непрерывности расписания для классов (необходимо обеспечивать непрерывность расписания для каждой из подгрупп);
- Наличие нескольких смен – в этом случае отдельные классы должны приходить позже, чем группы первой смены, кроме этого, усложняется контроль окон в расписании преподавателей, если есть преподаватели, работающие в обе смены – в этом случае в расписании этих преподавателей их занятия необходимо “стягивать” вокруг пересечения смен;
- Условие привязки преподавателей к аудитории – отдельные преподаватели имеют “свою” аудиторию, в которой проводят все свои занятия;
- Наличие “плавающей” смены – когда время начала первого урока точно не определено, т.к. оно формируется динамически, в зависимости от освобождения связанных с соответствующим классов, преподавателей, аудиторий;
- Контроль вхождения расписания объекта (класс, преподаватель, аудитория) в допустимый рабочий диапазон (в карту временных ограничений). Например, для преподавателя в карте временных ограничений обычно указываются методические дни, иногда, отдельные номера уроков – словом, указываются те позиции, на которые установка занятий с участием данного объекта невозможна;
- Наличие комбинированных предметов – типа “ин.яз./информатика” “информатика/труд” и т.п. - когда класс разбивается на подгруппы;
- Условие привязки предметов к аудиториям – проведения занятий по отдельным предметам возможно лишь в строго определенной аудитории или списке аудиторий (физкультура, труд и т.п.);
- Составление расписания с учетом того обстоятельства, что по некоторым предметам на занятия приходит не целый класс, а его подгруппа. Чтобы другая подгруппа в это время не гуляла по школе, такие занятия могут ставиться строго только первыми или последними занятиями в расписании класса;
- “Выдержать параллели” – для некоторых преподавателей необходимо учитывать то обстоятельство, что для проведения занятий требуется длительная подготовка (например, занятия по химии), в этом случае занятия в дневном расписании преподавателя стараются поставить блоками параллелей, например, сначала 5-ые классы, затем 7-ые и т.п., или же при распределении между днями разнести занятия в разных параллелях на разные дни;
- Иногда при составлении расписания требуется учитывать тот нюанс, что по некоторым предметам расписание известно заранее –в этом случае такие занятия вводятся как неперемещаемые (фиксированные);
- Контроль запрещенных комбинаций предметов, приходящихся на один день расписания класса – например, нежелательно, чтобы “физическая культура” и “труд” проводились в один и тот же день;
- Выполнение условия требуемых последовательностей предметов – когда необходимо обеспечивать установку групп занятий, в которых занятия должны идти в определенной последовательности, например, физика-астрономия и т.п.;
- Наличие классов, привязанных к аудиториям – основная масса занятий для таких классов проводится именно в этой аудитории, за исключением тех занятий, для которых требуется специализированная аудитория;
- Необходимость расстановки занятий по отдельным предметам по два занятия подряд (“парами”, “спарками”), причем это условие может быть жестким (ни в коем случае не разрывать “спарки” занятий), а может носить предпочтительный характер (если не получается перемещать по два занятия, “спарку” можно разрывать);
- Учитывается то обстоятельство, когда по некоторым предметам расстановка допустима лишь одиночными занятиями.
3. Система “Методист”
Выпускается в двух версиях.
Версия virtual.
Выпускается без модуля автоматического составления расписания. Возможности версии virtual:
- быстрый поиск в списках преподавателей, аудиторий, классов (групп), дисциплин, корпусов;
- получение справочной информации по каждому найденному элементу списка (вместимость аудитории, все ауд. корпуса Х, адрес и тел. преподавателя, список кафедры, кол-во часов по дисциплине, учебная нагрузка преподавателя и мн. др.);
- контроль и возможность перераспределения часов между неделями по любой дисциплине уч. группы;
- автоматическая проверка возможных ошибок ввода данных (соответствие общей суммы часов и по видам занятий, неназначение преподавателей по подгруппам, бюджет времени уч. группы и преподавателя, несоответствие часов в группах потока и мн. др.);
- возможность систематизированного хранения (и быстрого поиска) дополнительной (не обязательной для составления расписания) информации: фото преподавателей, кураторы учебных групп (классные руководители), данные о представителях родительских комитетов, должности, ученые степени и звания, ответственные за аудиторию, ...
- быстрое получение полной информации по сочетанию факторов (все группы потока, все дисциплины преподавателя Х с указанием нагрузки по неделям и видам занятий, какие дисциплины разрешено проводить в компьютерном классе, личные пожелания к проведению занятий любого преподавателя, перечень праздничных дат в сирийской группе и мн. др.);
- возможность просмотра, печати и редактирования готового расписания с проверкой корректности изменений (занятость ауд., преп., групп/подгрупп, ...);
- в любой момент можно заказать модуль формирования расписания для подготовленных данных;
- расписание формируется на вашем компьютере с возможностью изменения настроек, контроля, правки и т.п. (без возможности изменения часов, дисциплин, преподавателей, ...);
- если обнаружена необходимость незначительного (до 10%) изменения исходных данных (обнаружены ошибки, внезапные дополнения), возможен повторный заказ модуля формирования расписания за незначительную плату;
- в любой момент можно перейти на версию стандарт;
Методист – стандарт.
Помимо возможностей версии virtual включает в себя:
- Модуль автоматического составления расписания;
- Распределение и контроль учебной нагрузки ;
- Учет методических рекомендаций и личных пожеланий преподавателей ("окна", метод. дни, теннис по четвергам, день рождения сына, ...);
- Cтрогое выдерживание последовательности прохождения дисциплины (лекции - 2 час., практические - 4 час., лабораторные ...);
- Составление расписания для любого типа учебного заведения: недельное или семестровое (от 1 до 23 недель);
- Учет объединения групп (классов) в потоки и/или разбиение их на подгруппы;
- Закрепление специальных аудиторий (компьютерные классы, лингафонные кабинеты, бассейн, ...);
- Учет занятости преподавателей и аудиторий (совместительство, использование общей учебной базы);
- Учет времени переходов между корпусами;
- Выходные и праздничные дни - общие и для отдельных учебных групп (национальные, религиозные, государственные праздники);
- Указание причин "неудачного назначения" занятий (занята аудитория, преподаватель назначен в нежелательный для него день недели) с возможностью их "ручного" исправления;
- Возможность многократного автоматического "улучшения" расписания;
- Возможность изменения значимости учитываемых при составлении расписания факторов;
- Возможность введения приоритетов преподавателей - степени учета их индивидуальных пожеланий;
Ограничения функциональности “Методиста”:
- многосменные расписания ограничены максимальным кол-вом уроков в день – 7;
- занятия всегда начинаются с первого урока / пары (при необходимости возможно назначение на первую пару "свободного занятия" );
- не учитывется время перемен (например для проверки возможности перехода между корпусами);
- не учитывается "уровень сложности" занятий для их рационального распределения по неделе (хотя имеется возможность делать это косвенным образом) ;
- продолжительность занятий постоянна (невозможно составление расписания для 30 мин. урока в младших и 45 мин. - в старших классах).
Приложение 2. Листинг программного модуля методов решения задачи автоматического составления расписанияuses
SysUtils;
type MyArray= array of array of real;
MyArray_X = array of longint;
procedure Step_Dual_simplex(var a:MyArray; m,n,i1,j1:integer);
{производит один шаг двойственного симплекс-метода,
ведущий элемент - a[i1,j1]}
var i,j:integer;
b,b1:array of real;
begin
SetLength(b,m);Setlength(b1,n);
for i:=0 to m-1 do b[i]:=a[i,j1];
for i:=0 to n-1 do b1[i]:=a[i1,i];
for i:=0 to m-1 do
for j:=0 to n-1 do begin
if (i=i1) and (j=j1) then a[i,j]:=1/b[i1]
else
if (i=i1) then a[i,j]:=b1[j]/b[i1]
else
if (j=j1) then a[i,j]:=-b[i]/b[i1]
else a[i,j]:=a[i,j]-b[i]*b1[j]/b[i1];
end;
for i:=0 to n-1 do a[i1,i]:=0;a[i1,j1]:=-1;
Finalize(b);Finalize(b1);
end;
function Lexikogr_few(a:MyArray; m,n:integer;i,i1:integer):boolean;
{первый столбец лексикографически меньше второго}
var j:integer;
begin
Lexikogr_few:=false;
j:=0;
while (a[j,i]=a[j,i1]) and (j
if (j
end;
function Find_nu(a:MyArray;m,n:integer; i,i1:integer):longint;
{i - индекс лексикографически минимального столбца}
var j:integer;
begin
Find_nu:=1;
j:=0;
while (a[j,i]=a[j,i1]) and (j
if (j0) then Find_nu:=Round(Int(a[j,i1]/a[j,i]));
end;
procedure Full_Integer_Simplex(var x:MyArray_X; a:MyArray; m,n:integer);
{Полностью целочисленный алгоритм задачи линейного целочисленного
программирования,
см. Ху Т. "Целочисленное программирование и потоки в сетях", стр. 300-309,
a - матрица размером m+n+2*n+1, по аналогии:
Требуется найти максимум
z= - 10x1 - 14x2 - 21x3
2x1 + 2x2 + 7x3 >= 14
8x1 + 11x2 + 9x3 >= 12
9x1 + 6x2 + 3x3 >=10,
тогда матрица а будет выглядеть:
1 10 14 21
0 -1 0 0
0 0 -1 0
0 0 0 -1
-14 -2 -2 -7
-12 -8 -11 -9
-10 -9 -6 -3
0 0 0 0,
процедура возвращает вектор X, первые m компонент которого - искомое решение,
если последняя компонента вектора = 1, то решения не существует или оно = бесконечности}
var i,i1:integer;
j,j1:integer;
alfa:real;
begin
repeat
i:=1;
while (i=0) do Inc(i); {производящая строка}
if i
j:=1;
while (j=0) do Inc(j);
if j
for i1:=1 to n-1 do if (a[i,i1]
минимальный столбец}
{выбор альфа}
if j
{Writeln(i,' ',j);readln;}
alfa:=0;
for i1:=1 to n-1 do if a[i,i1]
begin
j1:=Find_nu(a,m,n,j,i1);
if (j1>0) and (-a[i,i1]/j1>alfa) then alfa:=-a[i,i1]/j1;
end;
{writeln(alfa,' ',i,' ',j);readln;}
{получение отсечения Гомори}
for i1:=0 to n-1 do if a[i,i1]>0 then a[m-1,i1]:=round(Int(a[i,i1]/alfa))
else begin
a[m-1,i1]:=round(Int(a[i,i1]/alfa));
if Frac(a[i,i1]/alfa)<>0 then a[m-1,i1]:=a[m-1,i1]-1;
end;
Step_Dual_simplex(a,m,n,m-1,j);
end;
end;
until (i>=m-1) or (j>=n);
for i:=0 to m-1 do x[i]:=round(a[i,0]);
if j>=n then x[m-1]:=1 else x[m-1]:=0;
end;
procedure Step_One_Simplex(var a:MyArray; m,n,i:integer);
var i1,i2:integer;
{Один шаг прямого целочисленного метода (производящая строка - последняя
i - производящий столбец)}
begin
for i1:=0 to m-2 do a[i1,i]:=a[i1,i]/(-a[m-1,i]);
for i2:=0 to n-1 do
for i1:=0 to m-2 do
if i2<>i then a[i1,i2]:=a[i1,i2]+a[i1,i]*a[m-1,i2];
end;
procedure Direct_Integer_Simplex(var x:MyArray_X; a:MyArray; m,n:integer);
{Прямой целочисленный алгоритм задачи целочисленного линейного программирования,
см. Ху Т. "Целочисленное программирование и потоки в сетях", стр. 344-370,
a - матрица размером m+n+3*n+1 по аналогии:
требуется максимизировать
z = x1 + x2 + x3
-4x1 + 5x2 + 2x3
-2x1 + 5x2
3x1 - 2x2 + 2x3
2x1 - 5x2
тогда матрица а будет выглядеть:
0 -1 -1 -1
4 -4 5 2
5 -2 5 0
6 3 -2 2
1 2 -5 0
0 -1 0 0
0 0 -1 0
0 0 0 -1
10 1 1 1 - в этой строке первое число - грубая max суммы небазисных переменных
0 0 0 0 - строка для отсечения Гомори,
алгоритм работает только при a[i,0]>=0
возвращает вектор X - на месте единичной матрицы искомое решение,
если в последней компоненте единица - ошибка при расчетах}
var i,j,i1,j1:integer;
bool:boolean;
b,b1,b2:array of byte;
r:real;
begin
SetLength(b,m);SetLength(b1,m);
for i:=0 to m-1 do b1[i]:=0;
{проверка условия оптимальности}
bool:=false;
for j:=1 to n-1 do if a[0,j]
while bool do begin
{поиск производящего столбца}
bool:=false;j1:=0;
for j:=1 to n-1 do begin
if a[m-2,j]>0 then
begin
for i:=0 to m-3 do a[i,j]:=a[i,j]/a[m-2,j];
if not bool then begin j1:=j;bool:=true;end else if Lexikogr_few(a,m,n,j,j1)
then j1:=j;
end;
end;
{поиск производящей строки}
for j:=1 to n-1 do
if a[m-2,j]>0 then
for i:=0 to m-3 do a[i,j]:=a[i,j]*a[m-2,j];
for i:=0 to m-1 do b[i]:=0;
i:=1; while (i
i1:=i;
while (i
if (a[i,j1]>0) and (a[i,0]/a[i,j1]
Inc(i);
end;
if i1
if a[i1,0]/a[i1,j1]
b[i1]:=1;
for i:=1 to m-2 do
if (a[i,j1]>0) and (a[i,0]/a[i,j1]
for i:=1 to m-2 do if (b[i]=1) and (b1[i]=1) then i1:=i;
end;
{формирование отсечения Гомори}
for i:=0 to n-1 do if a[i1,i]>0 then a[m-1,i]:=round(Int(a[i1,i]/a[i1,j1]))
else begin
a[m-1,i]:=round(Int(a[i1,i]/a[i1,j1]));
if Frac(a[i1,i]/a[i1,j1])<>0 then a[m-1,i]:=a[m-1,i]-1;
end;
Step_One_Simplex(a,m,n,j1);
end;
bool:=false;
if i1
b2:=b1;b1:=b;b:=b2;
for j:=1 to n do if a[0,j]
end;
{for j1:=0 to n-1 do Write(a[0,j1]:1:0,' ');Writeln;readln;}
end;
for i:=0 to m-2 do x[i]:=round(a[i,0]);
if i1>=m-1 then x[m-1]:=1 else x[m-1]:=0;
Finalize(b);Finalize(b1);
end;
