Разработка математической модели и ПО для задач составления расписания
- тарификацию.
АВТОР-2+ имеет пpиятный дизайн и
дpужеcтвенный сеpвис. Программа достаточно проста в освоении. Имеется подробное
руководство, в котором описаны все возможности и способы работы с программой.
Программа работает на любых IBM-совместимых компьютерах, начиная с
486DX с оперативной памятью 4Mb (и выше), занимает около 1 Mb на жестком диске.
Операционная система: MS DOS, либо WINDOWS 95/98.
Время работы зависит от размерности учебного заведения и мощности
компьютера. Полный расчет и оптимизация расписания школы среднего размера (30
классов, 60 преподавателей, две смены) идет около 15 минут на компьютере типа
Celeron-400.
Программа отличается уникальным и очень мощным алгоритмом построения и оптимизации расписания. Полученное автоматическое расписание практически не требует ручной доработки, то есть даже при очень сложных и жестких ограничениях автоматически размещаются все возможные занятия. Если в исходных данных имеются неразрешимые противоречия, то их можно обнаружить и устранить, используя специальный блок анализа.
АВТОР-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 (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 (j 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