Автоматизированная система составления школьного расписания

СОДЕРЖАНИЕ

Введение
1Техническое задание
1.1Наименование разработки
1.2Цель выполнения разработки
1.3Технические требования к разработке
2Технико-экономическое обоснование
2.1Характеристика объекта автоматизации
2.2Назначение автоматизированной системы
2.3Основные требования АС
2.4Подходы к оценке эффективности
2.5План маркетинга
2.6Технико-экономические показатели
2.7Оценка рисков
3Выбор направления решения
3.1Состав, содержание и организация работ по созданию АС
3.2Обзор существующих систем-аналогов
4Разработка алгоритма
4.1Моделирование процессов и потоков данных
4.2Моделирование данных и состояний
4.3Инфологическое моделирование предметной области
4.4Математическая модель
4.5Выбор алгоритма
5Разработка программы реализующий алгоритм
5.1Построение структурно-функциональной схемы
5.2Разработка проекта системы
5.2.1Разработка физической структуры базы данных
5.2.2Разработка программы
6Контрольный пример работы программы
7Руководство пользователя
7.1Общие положения
7.2Настройка базы данных программы
8Организационно-экономическая часть
9Безопасность и экологичность проекта
Заключение
Литература
Приложение

Автоматизированная система составления школьного расписания

построение структуры программного комплекса, определение функций составных частей и их взаимосвязи; разработка, тестирование и отладка приложения с использованием экспериментальных данных.
Кроме того, необходимо выполнить следующие задачи:
рассчитать затраты на разработку системы и оценить экономический эффект ее применения;
оценить эргономические и эстетические показатели системы;
создать документацию на разработанную систему (руководства по эксплуатации, модификации, доработке).
3.2 Обзор существующих систем-аналогов
Для школьников всё важно – не только питание, но и режим дня и расписание учебных занятий. Ведь правильно распланированные уроки – залог оптимальной работоспособности учеников.
Составлению расписания всегда уделяют пристальное внимание. Дело это сложное, ведь нужно учесть множество нюансов.
Процесс составления расписания без применения компьютера – весьма трудоемкий процесс, отнимающий много времени у завуча.
Существует множество различных компьютерных программ, предназначенных для решения данной задачи. На рынке присутствуют такие программные продукты, как «Расписание ONLINE», «АСТРА», «1С: ХРОНОГРАФ 3.0 МАСТЕР», «Ректор-Школа».
Программа «Расписание ONLINE» предназначена для составления школьного расписания занятий. Программа эффективно составляет школьное расписание занятий даже при сложной структуре классов. Может использоваться в школах и других учебных заведениях подобной структуры. Распространяется бесплатно для некоммерческого использования.
Ниже перечислены основные возможности:
любое количество учебных дней (пяти-, шестидневка и т.п.);
одна или две смены;
оптимизация свободных дней, возможность исключения любого дня из расписания учителя или класса;
оптимизация расписания учителя параллелями (например, понедельник – 7а, 7б, 7в; вторник 8а, 8б, 8в и т.п.);
оптимизация по расположению некоторых предметов, например, предпочтительно в начале или предпочтительно в конце учебного дня;
составление расписания занятий по кабинетам.
Программа содержит много недостатков. Расписание, составленное с помощью «Расписания ONLINE» не отвечает гигиеническим требованиям.
Если внесенные данные с ошибками или конфликтуют между собой, то никаких результатов программа не выдаст. Также лучше разделить этап составления расписания на две части. Сначала внести минимально необходимые исходные данные без пожелания учителей, расписания кабинетов и т.д. Попробовать составить расписание. Далее внести некоторые более жесткие требования, проанализировать, приводит ли это к улучшению составления расписания или к ухудшению. Этот процесс занимает много времени.
Если после начала составления расписания первый вариант не находится через несколько минут, возможно, исходные данные или слишком сложные или содержат противоречия и ошибки.
Работа программы основана на алгоритме случайного поиска, так что процесс поиска вариантов может продолжаться бесконечно.
К результатам работы программы «АСТРА» относятся следующие составляющие:
расписание недели - распределение занятий классов по дням;
расписание недели - распределение занятий преподавателей по дням;
индивидуальные формы расписания классов;
индивидуальные формы расписания преподавателей;
индивидуальные формы расписания аудиторий;
сводное расписание классов;
сводное расписание преподавателей;
протокол замен по всем датам;
листок замен на определенную дату.
Недостатком программы является то, что вместо вывода форм на печать возможен их вывод в текстовый файл в кодировке Windows-1251 или DOS (CP-866).
«1С: ХроноГраф 3.0 Мастер» - это оригинальная компьютерная технология, оптимально сочетающая многофункциональный механизм составления расписания учебных занятий и оперативного управления учебным процессом с широкими дополнительными возможностями создания и ведения базы данных учебной деятельности. Программный продукт адресован руководителям средних общеобразовательных учреждений, отвечающим за организацию и контроль качества учебно-воспитательного процесса; руководящим работникам и специалистам органов управления образования и учебно-методических центров.
«1С: ХРОНОГРАФ 3.0 МАСТЕР» обеспечивает создание методически выдержанного расписания школы на основе:
формирования и оптимизации графиков работы преподавателей с учетом нагрузки, режима занятий классов и совместной работы в группах;
работы со всеми срезами расписания – недельной и дневной сеткой, по классам и преподавателям – на одном экране, с использованием усовершенствованных интерактивных поисковых алгоритмов в режиме ручного редактирования;
применения расширенных возможностей интерактивного автоматического алгоритма составления расписания с использованием: функций предварительного расчета; настроек расчета занятий по школе/параллелям/ классам/учебным группам; настроек расчета по одному/группе/методическому объединению преподавателей; расчета по одному/нескольким предметам; функций наложения /снятия ограничений в организации учебного процесса;
визуального контроля за графиками загруженности учащихся по неделе, а также количеством «окон» и подготовок учителей;
динамического контроля над распределением аудиторного фонда и автоматической расстановки кабинетов, с возможностями ручного редактирования и учетом предметной специализации и закрепления за преподавателями или классами.
Недостатком же является то, что для работы «1С: ХРОНОГРАФ 3.0 МАСТЕР» необходима дополнительная покупка платформы «1С:Предприятие».
«Ректор-Школа» - программа для составления расписания занятий/уроков в общеобразовательных школах с профильным обучением.
Функции программы:
учет санитарных правил и норм;
учет распределения классов по сменам;
объединение классов в поток;
деление класса (потока) на группы;
расписание классов без "окон";
различные формы таблиц расписания;
сокращение "окон" в расписании учителей;
представление таблиц в Excel, Word и HTML форматах;
планирование замен.
«Ректор-Школа» - простая, легкая в освоении и эффективная программа.
Расписание занятий/уроков можно составлять в автоматическом, ручном или комбинированном режиме; переходить от одного режима к другому можно в любой момент времени.
При составлении расписания в автоматическом режиме программа учитывает все сформулированные требования к расписанию, включая требования СанПиН.
При составлении расписания в ручном режиме программа подсказывает возможные варианты расстановки уроков выбранного учителя, возможные варианты заполнения пустых клеток в расписании класса, следит за количеством мест в кабинетах.
Программа «Ректор-Школа» полностью удовлетворяет требования по автоматизации функции формирования и контроля расписания в школе, но она платная, поэтому разработаем собственную автоматизированную систему составления школьного расписания.
В результате обзора аналогов систем, делаем вывод, что существующие системы не удовлетворяют нашим требованиям, поэтому разработаем собственную систему, которая должна выполнять:
ввод информации об учителях (ФИО, расчасовка);
ввод информации о предметах (название, сложность);
ввод информации об учебном плане;
ввод информации о классах;
ввод информации об кабинетах.
Данная система должна быть простой в использовании, иметь удобный интерфейс, наглядное предоставление информации как при выводе на экран, так и при выводе на печатающие устройства. Введение данных в память ЭВМ приведет последующему автоматическому формированию расписания.
4 МОДЕЛИРОВАНИЕ СИСТЕМЫ И Разработка алгоритма
4.1 Моделирование процессов и потоков данных
Считаю что диаграммы очень красивые и наглядные, и не надо их перерисовывать. Требования по оформлению ставятся до начала разработки, а не потом, когда уже все сделано, так можно до бесконечность переделывать…….
Создание проекта начинается с формирования принципов использования системы. Визуальное моделирование в UML можно представить как некоторый процесс поуровниевого спуска от наиболее общей и абстрактной концептуальной модели исходной системы к логической, а затем и к физической модели соответствующей программной системы. Для достижения этих целей вначале строится модель в форме, так называемой диаграммы вариантов использования (use case diagram), которая описывает функциональное назначение системы или, другими словами, то, что система будет делать в процессе своего функционирования.
Суть данной диаграммы состоит в следующем: проектируемая система представляется в виде множества сущностей или актеров, взаимодействующих с системой с помощью, так называемых вариантов использования. При этом актером (actor) или действующим лицом называется любая сущность, взаимодействующая с системой извне. Это может быть человек, техническое устройство, программа или любая другая система, которая может служить источником воздействия на моделируемую систему так, как определит сам разработчик. В свою очередь, вариант использования (use case) служит для описания сервисов, которые система предоставляет актеру [7].
Для данной задачи в качестве актера выделен заместитель директора по УВР, так как этот актер является основным и единственным пользователем системы.
Проведя анализ требований и определив функционирование проектируемой системы, была построена диаграмма вариантов использования (рисунок 4.1).
Рисунок 4.1 – Диаграмма вариантов использования
Разработка диаграммы последовательностей
Для моделирования взаимодействия объектов в языке UML используются соответствующие диаграммы взаимодействия. Говоря об этих диаграммах, имеют в виду два аспекта взаимодействия. Во-первых, взаимодействия объ­ектов можно рассматривать во времени, и тогда для представления времен­ных особенностей передачи и приема сообщений между объектами исполь­зуется диаграмма последовательности.
Диаграмма последовательности отражает поток событий, происходящих в рамках варианта использования. В верхней части диаграммы показываются все действующие лица и объекты, требуемые системе для выполнения варианта использования. Стрелки соответствуют сообщениям, передаваемым между действующим лицом и объектом или между объектами для выполнения требуемых функций.
Для данной системы были выделены следующие действующие лица и объекты: «Зам. директора по УВР», «Список классов», «Список преподавателей», «Список предметов», «Кабинеты», «Система формирования расписания».
Проведя анализ требований к данной информационной системе, создана диаграмма последовательности, представленная на рисунке 4.2.
Рисунок 4.2 – Диаграмма вариантов использования
Разработка диаграммы классов
Диаграмма классов (class diagram) служит для представления статической структуры модели системы в терминологии классов объектно-ориентированного программирования. Диаграмма классов может отражать, в частности, различные взаимосвязи между отдельными сущностями предметной области, такими как объекты и подсистемы, а также описывает их внутреннюю структуру и типы отношений. Диаграмма классов отражает структуру объектов (классов) системы. Является одной и самых важных и необходимых диаграмм в объектно-ориентированном проектировании.
Под классом понимается описание объектов, обладающих общими свойствами (атрибутами), поведением, общими взаимоотношениями с другими объектами и общей семантикой. Класс является шаблоном для создания новых объектов.
Каждый класс может иметь атрибуты (свойства). Кроме того, каждый класс может содержать методы (operations) – некоторые действия, которые описывают поведение объектов класса. Классы способны иметь взаимосвязи (relationship), называемые отношениями.
На данной диаграмме не указывается информация о временных аспектах функционирования системы. С этой точки зрения диаграмма классов является дальнейшим развитием концептуальной модели проектируемой системы.
Для автоматизированной системы формирования и контроля школьного расписания выделены следующие классы: «Дни недели», «Классы», «Преподаватели», «Расписание», «Кабинеты», «Дисциплины», «Учебный план».
Для данной системы спроектирована диаграмма классов (рисунок 4.3)
Рисунок 4.3 – Диаграмма классов
4.2 Моделирование данных и состояний
Диаграмма состояний отображается жизненный цикл одного объекта, начиная с момента его создания и заканчивая разрушением. С помощью таких диаграмм удобно моделировать динамику поведения класса.
Главное предназначение этой диаграммы — описать возможные последовательности состояний и переходов, которые в совокупности характеризуют поведение элемента модели в течение его жизненного цикла. Диаграмма состояний представляет динамическое поведение сущностей, на основе спецификации их реакции на восприятие некоторых конкретных событий.
Для проектируемой системы разработана диаграмма состояний, которая представлена на рисунке 4.4.
Рисунок 4.4 – Диаграмма состояний
4.3 Инфологическое моделирование предметной области
Диаграмма размещения (deployment diagram) отражает физические взаимосвязи  между  программными  и  аппаратными  компонентами системы.  Она  является  хорошим  средством  для  того,  чтобы  показать маршруты  перемещения  объектов  и  компонентов  в  распределенной системе.
Представление размещения отображает все узлы сети, связи между ними и процессы, выполняющиеся на каждом узле.
Процессором называется любая машина, имеющая вычислительную мощность, то есть способная производить обработку данных. Устройством называется аппаратура, не обладающая вычислительной мощностью.
Диаграмма размещений для АС формирования и контроля школьного расписания представлена на рисунке 4.5.
Таким образом, разработанный проект является необходимой и достаточной основой для программной реализации системы.
4.4 Математическая модель
После установки программного продукта для дальнейшей работы необходимо определиться с входными и выходными данными. Входными данными для автоматизированной системы служат учебный план, данные о классах, предметах, кабинетах, преподавателях.
Множество IN = U + K + P + Kb + Pr, где
U – учебный план;
K – данные о классах;
P – предметы;
Kb – кабинеты;
Pr – преподаватели.
Первоначальные данные:
данные о классах: название класса, максимальное количество учебных дней в неделю, максимальное количество уроков в день;
данные о предметах: название предмета, его сложность в баллах;
данные о преподавателях: ФИО преподавателя.
классы, где преподает данный учитель; кабинет, закрепленный за учителем, предметы, которые он преподает.
Далее необходимо ввести данные учебного плана – количество часов дисциплин в неделю по учебным годам.
Важным аспектом системы является заполнение справочника спецификации учителей, где каждому учителю в соответствие ставятся предметы, классы, кабинеты.
Главная задача автоматизированной системы – печать расписания учебных занятий. Таким образом, выходными данными в программе правильно сформированное расписание, отчет о расчасовке преподавателей.
IN => OUT – множество соответствия P – K – Pr – Kb.
4.5 Выбор алгоритма
Как правило, одни и те же цели могут быть достигнуты различным образом различными затратами труда и материальных ресурсов. Выбрать наиболее экономичный и целесообразный путь, принять обоснованное, наиболее правильное решение – далеко не простая задача и для своего решения требует привлечения современных научных методов. В середине пятидесятых годов начались интенсивные исследования по построению и анализу моделей календарного планирования и разработке методов принятия плановых решений с использованием этих моделей. Наряду с улучшением качества плановых решений необходимо было также сократить их выработки, повысить оперативность и гибкость управления. В теории расписаний используется большинство известных в настоящее время методов принятия наилучших решений посредствам построения соответствующих операционных моделей. Поиск оптимального или близкого к оптимальному расписания осуществляется с помощью одного из 4 подходов:
математического программирования;
комбинаторного;
эвристического;
статистического (вероятностного).
Основы теории расписаний (ТР) развивались в ту пору, когда математические модели начали применяться для решения экономических задач. Были предприняты попытки построить математические модели и для задач ТР. При этом столкнулись с трудностью следующего рода. В математической модели система ограничений отражает то положение вещей, что некоторая совокупность условий должна выполняться совместно. В задаче ТР ряд условий должны выполняться альтернативно: или i-я работа запускается раньше j-й, или наоборот. К этим методам относятся методы линейного программирования, которые используются в основном для решения задач временного согласования и распределения планируемых работ и ресурсов. Использование линейных моделей для описания реальных ситуаций приводит к необходимости решения задач большого размера. Специфические особенности этих задач позволяют предложить эффективные декомпозиционные подходы к их решению [2].
Для решения многих задач теории расписаний может быть непосредственно использован аппарат динамического программирования [2].
В простейших случаях оптимальные расписания могут быть построены в результате весьма простых рассуждений относительно изменения характеристик расписания при некоторых элементарных его преобразованиях. Совокупность такого рода приемов составляет основу так называемых комбинаторных методов [2]. Данный подход сводится к целенаправленной перестановке пар работ в некоторой исходной последовательности, пока не будет получено оптимальное (близкое к оптимальному) решение.
Неудовлетворительное состояние развития точных методов решения задач ТР обусловило разработку приближенных методов, позволяющих получать приемлемые решения при сравнительно небольших затратах времени и средств. Условно приближенные методы делятся на эвристические и вероятностные [3].
Эвристические алгоритмы основаны на приеме, который называется приемом снижения требований. Он заключается в отказе от поиска оптимального решения за приемлемое время. Эвристические алгоритмы используют различные разумные соображения без строгих обоснований. Широко применяется так называемый метод локального поиска. При этом заранее выбранное множество перестановок используется для последовательного улучшения начального решения до тех пор, пока такое улучшение возможно, в противном случае оказывается достигнутым локальный оптимум. Достоинством эвристических методов является удобство реализации их на ЭВМ даже при решении громоздких задач. Недостатки эвристических методов заключаются в сложности оценки близости полученных расписаний к оптимальному. Кроме того для каждой функции предпочтения существуют задачи, для которых применение данной функции приводит к плохим результатам.
Вероятностные методы связаны с k-кратным моделированием расписаний. Выбор работ из множества ожидающих выполнения осуществляется случайным образом. После k-кратного проигрывания выбирается наилучшее расписание, которое принимается за решение задачи. При этом различают:
ненаправленный случайный поиск;
направленный случайный поиск без самообучением;
направленный случайный поиск с самообучением.
Существует большое количество алгоритмов используемых для составления расписания:
алгоритм Шилда и Фридмана;
алгоритм Джонсона;
алгоритм последовательного включения работ;
алгоритме поочередного включения работ;
упорядочением по минимуму длительностей работ SPT;
алгоритм, минимизирующий среднюю длительность прохождения;
Лившица;
Мак-Ньютона;
Ходжсона;
Мура.
Все эти алгоритмы носят достаточно общий характер и в основном направлены на составление расписания работы производственных процессов [1].
Все выше перечисленные алгоритмы имеют свои достоинства и недостатки, а нам необходимо создать автоматизированную систему, которая удовлетворяет принципам экспертной системы, но в ней не разрабатывается база знаний, в которой хранятся все знания специалиста в данной области необходимые для принятия решения. В данной автоматизированной системе алгоритм составления расписания выбран на основе правил, которые позволяют наиболее оптимально распределить данные в таблице.
Формирование и контроль расписания осуществляется следующим образом:
1. выбирается первый преподаватель;
2. строится список предметов, классов и учебных часов, которые должен провести преподаватель в неделю (согласно специализации преподавателей);
3. из списка выбирается первый предмет, класс и количество часов в неделю согласно учебному плану;