Разработка математической модели и ПО для задач составления расписания

АВТОР-2+ позволяет:

- оптимизировать "окна" в расписании;

- учитывать требуемый диапазон дней/часов как для классов, так и для

преподавателей;

- оптимально pазмещать занятия по кабинетам (аудиториям) с учетом

особенностей классов, предметов, пpеподавателей и вместимости

кабинетов;

- учитывать хаpактеp pаботы и пожелания как штатных сотpудников, так и

совместителей-почасовиков;

- легко соединять ("спаpивать") несколько классов (учебных групп) в

потоки пpи пpоведении любых занятий;

- pазделять классы пpи пpоведении занятий по иностранному языку,

физической культуре, тpуду, информатике (и любым другим предметам) на

любое количество подгрупп (до десяти!);

- вводить (помимо основных пpедметов) спецкуpсы и факультативы;

- оптимизировать равномерность и трудоемкость расписания.

По желанию заказчика АВТОР-2+ модифициpуется под условия конкретного

учебного заведения.

2. Система “Расписание” ver 4.0 Москва – ЛинТех

Необходимо сразу же отметить, что программа “Расписание” ориентирована на

составление школьного расписания, использование в ВУЗ`ах и колледжах

возможно лишь с некоторыми оговорками. Составление расписания производится

в рамках комплекса условий, которые определяются на шагах ввода исходных

данных. Полный перечень возможных условий приведен ниже:

- Ограничен максимальный номер урока – т.е. количество уроков,

максимально допустимое в день;

- Равномерность распределения нагрузки преподавателей между днями

расписания;

- Равномерность распределения нагрузки классов между днями

расписания;

- Контроль окон в расписании преподавателей;

- Программа учитывает то обстоятельство, что классы могут

произвольно объединяться и дробиться (классы могут объединяться

в потоки или же дробиться на более мелкие подгруппы, причем эти

подгруппы, в свою очередь, могут служить основой для объединения

в более крупные группы. Пример: в школе №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 (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=0) do Inc(j);

if j0) 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 =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]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 (i0) and (a[i,0]/a[i,j1]0) and (a[i,0]/a[i,j1]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=m-1 then x[m-1]:=1 else x[m-1]:=0;

Finalize(b);Finalize(b1);

end;

-----------------------

1, если на потоке r лекцию sr читает преподаватель p;

0 – в противном случае;

[pic]

[pic]

1, если в группе kr практическое занятие qkr проводит преподаватель p;

0 – в противном случае;

[pic]

1, если на потоке r в день t на паре j читается лекция sr;

0 – в противном случае;

[pic]

1, если на потоке r в день t на паре j у группы kr проводится практическое

занятие qkr;

0 – в противном случае;

(1)

(2)

[pic]

[pic]

(3)

[pic]

(4)

(5)

(6)

(7)

(8)

(9)

(10)

(11)

(12)

(13)

(15)

(14)

(16)

(17)

(18)

(19)

(20)

(21)

(22)

(23)

(24)

(25)

(26)

Н_пр-ля (pk)

Имя

Фамилия

Отчество

Адрес

Телефон

Уч. степень

Уч. звание

Кафедра

Н_группы(pk)

Название

Количество

Н_потока(pk)

Описание

Н_потока(pk,fk)

Н_группы(pk,fk)

.

1

M

M

1

1

M

M

1

.

Н_ауд-ии(pk,fk)

Н_об-ия (pk,fk)

Описание

Н_ауд-ии(pk)

Н_пр-та(pk)

Описание

Н_об-ия (pk)

Число часов

Название

1

Н_записи (pk)

Н_пр-ля (fk)

Н_потока (fk)

Н_пр-та (fk)

Н_об-ия (fk)

Пара

Нач_неделя

Кон_неделя

.

M

M

M

M

.

1

1

1

A Xa B Xb C Xc D Xd E

Страницы: 1, 2, 3, 4