Xreferat.com » Рефераты по информатике и программированию » Разработка математической модели и ПО для задач составления расписания

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

планы;

- тарификацию.

АВТОР-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 (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)

Если Вам нужна помощь с академической работой (курсовая, контрольная, диплом, реферат и т.д.), обратитесь к нашим специалистам. Более 90000 специалистов готовы Вам помочь.
Бесплатные корректировки и доработки. Бесплатная оценка стоимости работы.

Поможем написать работу на аналогичную тему

Получить выполненную работу или консультацию специалиста по вашему учебному проекту
Нужна помощь в написании работы?
Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Пишем статьи РИНЦ, ВАК, Scopus. Помогаем в публикации. Правки вносим бесплатно.

Похожие рефераты: