СодержаниеВведение 2
Глава 1. Описание технологической области 5
1.1. Формулировка задачи составления расписания 5
1.1.1. Общая формулировка задачи составления расписаний 5
1.1.2. Формулировка задачи составления расписания в применении к расписанию учебных занятий. 10
1.2. Анализ существующего ПО 11
1.3. Постановка задачи 15
Глава 2. Разработка математической модели и практическая реализация системы автоматического составления расписания 17
2.1. Математическая модель расписания в вузе 17
2.2. Размещение на раскрашенных СП 24
2.2.1. Разработка метода моделирования 24
2.2.2. Математическая модель размещения 24
2.2.3. Выполнение СП 28
2.3. Оптимизация в задаче размещения на СП 32
2.4. Алгоритм распределения ресурсов 35
2.4.1 Эволюционный алгоритм оптимизации 41
2.4.2. Алгоритм стохастической оптимизации 43
2.4.3. Алгоритм размещения и оптимизации 45
3. Применение разработанных математических моделей и алгоритмов к задаче расписания 47
3.1. Задача расписания как задача размещения 47
3.1.1. Характеристика задачи 47
3.1.2. Психолого-педагогические требования к учебному процессу 50
3.2. Формирование целевой функции в задаче расписания 57
3.2.1. Целевая функция расписания учебных занятий 57
3.2.2. Математическое выражение целевой функции 60
3.3. Проведение и анализ результатов эксперимента 61
3.3.1. Программная реализация алгоритмов 61
3.3.2. Составление расписания при различных исходных данных 64
3.3.3. Обработка и анализ результатов эксперимента 65
Выводы 73
Литература 74
Приложение 1. Разработки систем составления расписания 75
Приложение 2. Разработка базы данных для составления расписания 76ВведениеПо существу, вся человеческая деятельность планируется во времени путем составления расписания. Без этого невозможна координированная работа предприятий и производственных участков, по графику должно идти строительство и т.д. Одновременно с появлением первых школ в странах Древнего Востока родилась задача составления расписания уроков. Дата этого события точно неизвестна, можно лишь утверждать, что на территории бывшего СССР первыми с ней встретились педагоги Грузии и Армении в IV веке. В России школы появились примерно тысячу лет назад. С тех пор мало что изменилось - завучи тех времен, вероятно, точно так же перекладывали карточки, заставляя сойтись пресловутый «летний пасьянс».
Расписание – это символ организованности, одно из важнейших средств эффективного выполнения любого рода деятельности, любого рода работ, и их надо уметь составлять возможно лучше – оптимально.
Расписания – и часто неплохие – люди научились составлять давно, но составление оптимального расписания для сравнительно сложных комплексов работ, например, для обеспечения учебного процесса в высшем учебном заведении, стало возможным с тех пор, как к этой работе были привлечены новые аккуратные и быстрые «информационные помощники» человека – ЭВМ.
Для составления вузовского расписания нужны методы, учитывающие особенности учебной работы студентов, удовлетворяющие психолого-педагогическим требованиям.
Однако для этого, прежде всего надо поставить задачу составления оптимального расписания как математическую задачу, и хотя это сделать сравнительно просто, но на первый взгляд все же неочевидно. С этой целью необходимо рассмотреть более общую задачу – задачу размещения.
Формально задача размещения имеет следующие характеристики.
Для размещения любого требования необходимо одновременное использование по крайней мере одной единицы каждого ресурса (например, ресурсов типа A, G, L). При размещении каждое требование имеет длительность – целое число элементарных моментов времени, которые группируются в отрезки и составляют все дискретное ограниченное время. Размещение, как правило, производится в одни и те же моменты времени для нескольких требований в зависимости от доступности ресурсов. Целевая функция системы учитывает различные количественные характеристики ресурсов и требований. Существует большое количество вариантов размещения с соответствующими значениями целевой функции, которую следует оптимизировать.
Здесь важное значение приобретают методы оптимизации.
Методы оптимизации эффективно применяются в самых различных областях человеческой деятельности. Особенно значительные успехи достигнуты при проектировании и анализе больших технических систем. Ускоренные темпы внедрения теоретических разработок в инженерную практику в существенной степени обусловлены широким распространением и интенсивным совершенствованием средств вычислительной техники.
В настоящее время для инженера знание методов оптимизации является столь же необходимым, как знание основ математического анализа, физики, химии, теории сопротивления материалов, радиоэлектроники и ряда других дисциплин, ставших традиционными.
В последние десятилетия ХХ века в области исследования дискретных систем разработано много новых методов. Произошли качественные изменения в скорости их анализа. Тем не менее, в данной области все еще остаются нерешенные проблемы, имеющие высокую сложность алгоритмов. Нахождение алгоритма составления оптимального расписания является одной из ключевых проблем. По данной тематике проводятся исследования различными авторами, такими как Н.Н.Вахания, В.В.Шаф-ранский, Р.В. Конвей, В.А. Максвелл, Л.В. Миллер, М.И. Рубинштейн, В.В.Шкурба.
Ими рассмотрена классификация задач теории расписаний, согласно которой имеется два вида задач: статические (или детерминированные) и динамические. В статических производится одновременное поступление определенного числа работ, после этого работы не поступают. В динамических работы поступают в некоторые моменты времени, которые можно предсказать только в статистическом смысле. Задача составления расписания учебных занятий является статической.
Если алгоритм решения данной задачи анализирует полный набор всех вариантов расписания, то возникают большие трудности в решении задачи в связи с огромным числом вариантов. Просмотр вариантов будет занимать много времени, несмотря на быстродействие ЭВМ, поэтому это неприменимо. Сложность здесь заключается в нахождении алгоритма, реализация которого позволяла бы составить расписание на обычном компьютере за приемлемое время. Предлагаемая работа касается данной темы.
Расписание учебных занятий — это документ, непосредст¬венно регламентирующий учебную работу студентов и препода¬вателей. Расписание занятий содержит информацию о конкрет¬ных занятиях по дисциплинам, днях и времени их проведения, участвующих в них преподавателях и учебных группах, подгруппах, потоках, курсах, используемых аудиториях. В практике учебных заведений, как правило, составляются расписания на типовую неделю или на две недели (в таких расписаниях не-. большое количество занятий чередуется с периодом в две неде¬ли, а остальные занятия проходят с периодом в одну неделю), а также семестровые понедельные расписания.
В ходе составления расписания вручную необходимо вы¬полнить большую рутинную работу: поиск возможных вариан¬тов внесения очередных занятий в расписание, проверку выпол¬нения ограничений, поиск случайных ошибок в готовом расписании, оформление расписания на бумаге в виде различ¬ных таблиц (для преподавателей, классов или групп, аудиторного фонда). Расписание должно удовлетворять многочисленным тре¬бованиям организационного, методического и психолого-физиологического характера, имеющим различные степени обя¬зательности, часто взаимно противоречивым или даже взаимо¬исключающим. Это затрудняет создание даже допустимых рас¬писаний, не говоря уже об оптимальных.
В связи с указанными свойствами задача автоматизации со¬ставления расписания выделяется руководителями учебных за¬ведений как наиболее актуальная в планировании работы учеб¬ного заведения. Интерес администрации учебных заведений к этой задаче вызвал большое количество исследований и разра¬боток как автономных программных систем, так и подсистем АСУ учебными заведениями. Первые работы по рассматривае¬мой тематике выполнялись в начале 60-х годов, когда в вузах появились ЭВМ массовых моделей.
Стремительное распространение ПЭВМ за последнее деся¬тилетие вызвало большое количество как практических, так и теоретических разработок в этой области. На настоящий момент автору известно более 50 программных средств автоматизиро¬ванного составления расписания занятий (экзаменов) в вузе, колледже, школе и 700 научных публикаций (включая моногра¬фии, результаты теоретических исследований и вычислительных экспериментов, концептуальные проекты программных систем, опыт разработки и эксплуатации, обзоры и библиографии, дис¬сертации, дискуссионные статьи), единиц технической докумен¬тации, промышленных каталогов и частных сообщений по рас¬сматриваемой теме.
Качество подготовки специалистов в вузах и особенно эффективность использования научно-педагогического потенциала зависят в определенной степени от уровня организации учебного процесса.
Одна из основных составляющих этого процесса - расписание занятий - регламентирует трудовой ритм, влияет на творческую отдачу преподавателей, поэтому его можно рассматривать как фактор оптимизации использования ограниченных трудовых ресурсов - преподавательского состава. Технологию же разработки расписания следует воспринимать не только как трудоемкий технический процесс, объект механизации и автоматизации с использованием ЭВМ, но и как акцию оптимального управления. Таким образом, это - проблема разработки оптимальных расписаний занятий в вузах с очевидным экономическим эффектом. Поскольку интересы участников учебного процесса многообразны, задача составления расписания - многокритериальная.
Задачу составления расписания не стоит рассматривать только как некую программу, реализующую функцию механического распределения занятий в начале семестра, на которой ее (программы) использование и заканчивается. Экономический эффект от более эффективного использования трудовых ресурсов может быть достигнут только в результате кропотливой работы по управлению этими трудовыми ресурсами. Расписание здесь является лишь инструментом такого управления, и для наиболее полного его использования необходимо, чтобы программа сочетала в себе не только средства для составления оптимального расписания, но и средства для поддержания его оптимальности в случае изменения некоторых входных данных, которые на момент составления расписания считались постоянными. Кроме этого оптимальное управление такой сложной системой невозможно без накопления некоей статистической информации о процессах, происходящих в системе. Потому сама задача составления оптимального расписания является лишь частью сложной системы управления учебным процессом.Литература1. Архангельский СИ. Учебный процесс в высшей школе, его закономерные основы и методы: Учеб.-метод. пособие. М.:Высш. шк., 1980. 368 с.
2. Бардадым В.А. Исследование оптимизационных задач, связанных с составлением расписаний учебных занятий: Автореф. дис... канд. физ. мат. наук. Киев: ИК АН Украины. 1991. 30 с.
3. Бардадым В.А. Составление расписаний учебных занятий с помощью ЭВМ // Управл. сист. и машины. 1991. №8. С.119-126.
4. Криволуцкая Н.В. Программы составления расписания занятий для образовательных учреждений/ М.: Московский институт повышения квалификации работников образования, 1999. Web-страница: /http://ito.bitpro.ru/1999/IV/IV19.html/
5. Неверов Г.С. АСРЗ в действии // Вестн. высш. шк. 1970. №5. с.57-61.
6. Бардадым В.А. Составление расписаний учебных занятий с помощью ЭВМ // Управл. сист, и машины. 1991. №8. С. 119-126.
7. Баткина И.Б. О гигиене умственного труда студентов /Педагогика высшей школы. Воронеж, 1974, 128 с.
8. Бачериков Н.Е., Воронцов МП., Добромиль Э.И. Психогигиена умственного труда учащейся молодежи. Киев: Здоровье, 1988. 168 с.
9. Богомолов А.И. Важнейшая задача вуза // Вестн. высш. шк. 1967. №10. С.3-8.
10. Вяльдии М.В. Планирование учебного процесса на основе современных психолого-педагогических требований и информационного подхода как средство повышения эффективности обучения физике в средней школе / Моск. гос. пед. ин-т. М., 1987.
11. Горбатов В.А. Основы дискретной математики: Учеб. пособие для студентов вузов. М.: Высш. шк., 1986. 311с.
12. Максвелл В.А., Миллер Л.В. Теория расписаний: Пер, с англ. М.: Наука, 1975. 359 с.
13. Костюк В.И., Мартинес Х.О., Зорин В.В. Использование алгоритмов последовательной обработки для составления расписаний // Вопр. создания АСУ ВУЗ. М.: НИИВШ, 1976. С.3-5.
14. Кофман С.А. Теория расписаний и вычислительная математика. М.: Наука, 1984. 335 с.
15. Лоскутов СИ. О построении расписания занятий в учебном заведении // Математические методы управления и обработки информации. М.: МФТИ, 1983. С. 151-157.
16. Лукьянец Н.Б. Составление и изменение расписания учебных занятий в школе с помощью ЭВМ // Вопр. совершенствования системы управления в просвещении на основе использования вычислительной техники. М.: НИИ общей педагогики, 1980. С.70-82.
17. Медведский М.В. Рационализировать составление расписания//Вестн. высш. шк. 1970. № 5. С.53-57.
18. Шапорев С.Д. Дискретная математика. Курс лекций и практических занятий.
|
|
