Разработка математической модели и ПО для задач составления расписания (стр. 1 из 12)
То, что вы здесьпрочтете в большинстве своем чушь. Тем не менее в некоторых местах по моемумнению присутствуют здравые мысли, к сожалению таких мест получилось не так ужи много L Невздумайте сдавать это там, где проблемами теории расписаний занимаютсясерьезно. Тем, кто захочет написать что-либо лучше этого, настоятельнорекомендую почитать книгу Ху. Т. “Целочисленное программирование и потоки всетях ”, кроме этого пожалуй стоит почитать лекцииВМиК по теории оптимизации Н.М. Новиковой (где это в инете лежит, не помню).Сейчас активно занимаюсь проблемами теории оптимизации, так что кому тожеинтересна эта тема, то всегда рад пообщаться. Пишите leb@metacom.ru.
Содержание
Введение. 8
1. Описание технологическойобласти. 10
1.1. Формулировка задачисоставления расписания. 10
1.1.1. Общая формулировказадачи составления расписаний. 10
1.1.2. Формулировка задачисоставления раписания в применении к расписанию учебных занятий. 11
1.2. Анализ существующего ПО.. 12
1.3. Постановка задачи. 15
2. Разработка математическоймодели и практическая реализация системы автоматического составления расписания. 16
2.1. Математическая модельрасписания в вузе. 16
2.1.1. Обозначения. 16
2.1.2. Переменные. 18
2.1.3. Ограничения. 19
2.1.4. Целевая функция. 21
2.2. Методы решенияпоставленной задачи. 22
2.2.1. Полностьюцелочисленный алгоритм. 23
2.2.2 Прямой алгоритмцелочисленного программирования. 28
2.2.3. Техника полученияначального допустимого базиса. 32
2.3. Особенностипрактической реализации системы.. 36
2.3.1. Выбор модели. 36
2.3.2. Описание входнойинформации. 39
2.3.3. Разработкаинформационного обеспечения задачи. 41
2.3.4. Особенностиформирования ограничений математической модели задачи составления расписания. 44
2.4. Результатыработы программы.. 45
2.5. Анализполученных результатов. 49
Выводы.. 50
Литература. 51
Приложение 1. Возможностипрограммных продуктов систем составления расписаний. 52
Приложение 2. Листингпрограммного модуля методов решения задачи автоматического составлениярасписания. 61
ВведениеКачество подготовкиспециалистов в вузах и особенно эффективность использованиянаучно-педагогического потенциала зависят в определенной степени от уровняорганизации учебного процесса.
Одна из основных составляющих этогопроцесса - расписание занятий - регламентирует трудовой ритм, влияет натворческую отдачу преподавателей, поэтому его можно рассматривать как фактороптимизации использования ограниченных трудовых ресурсов - преподавательскогосостава. Технологию же разработки расписания следует воспринимать не только кактрудоемкий технический процесс, объект механизации и автоматизации сиспользованием ЭВМ, но и как акцию оптимального управления. Таким образом, это- проблема разработки оптимальных расписаний занятий в вузах с очевиднымэкономическим эффектом. Поскольку интересы участников учебного процессамногообразны, задача составления расписания - многокритериальная.
Задачусоставления расписания не стоит рассматривать только как некую программу,реализующую функцию механического распределения занятий в начале семестра, на которой ее (программы) использование и заканчивается. Экономическийэффект от более эффективного использования трудовых ресурсов может бытьдостигнут только в результате кропотливой работы по управлению этими трудовымиресурсами. Расписание здесь является лишь инструментом такого управления, и длянаиболее полного его использования необходимо, чтобы программа сочетала в себене только средства для составления оптимального расписания, но и средства дляподдержания его оптимальности в случае изменения некоторых входных данных,которые на момент составления расписания считались постоянными. Кроме этогооптимальное управление такой сложной системой невозможно без накопления некоейстатистической информации о процессах, происходящих в системе. Потому самазадача составления оптимального расписания является лишь частью сложной системыуправления учебным процессом.
Многокритериальностьэтой задачи и сложность объекта, для которого сроится математическая модель,обуславливает необходимость серьезного математического исследования объекта дляувеличения функциональных возможностей алгоритмов составления расписаний беззначительного усложнения модели и, как следствие, увеличения объемовиспользуемой памяти и времени решения задачи.
1. ОПИСАНИЕ ТЕХНОЛОГИЧЕСКОЙ ОБЛАСТИ1.1.Формулировка задачи составления расписания
Задачатеории расписаний в общей ее постановке считается весьма привлекательной, хотядостижение даже небольшого прогресса на пути к решению связано, как правило, согромными трудностями. Несмотря на то, что задачами теории расписанийзанимались многие весьма квалифицированные специалисты, до сих пор никому неудалось получить сколько-нибудь существенных результатов. Безуспешные попыткиполучения таких результатов, как правило, не публикуются и это отчастиобуславливает тот факт, что задача продолжает привлекать внимание многихисследователей кажущейся простотой постановки.
1.1.1.Общая формулировка задачи составления расписанийВнаиболее общей формулировке задача составления расписания состоит в следующем.С помощью некоторого множества ресурсов или обслуживающих устройств должна бытьвыполнена некоторая фиксированная система заданий. Цель заключается в том,чтобы при заданных свойствах заданий и ресурсов и наложенных на них ограниченияхнайти эффективный алгоритм упорядочивания заданий, оптимизирующих илистремящийся оптимизировать требуемую меру эффективности. В качестве основныхмер эффективности изучаются длина расписания и среднее время пребывания заданийв системе. Модели этих задач являются детерминированными в том плане, что всяинформация, на основе которой принимаются решения об упорядочивании, известнызаранее.
1.1.2.Формулировка задачи составления раписания в применении к расписанию учебныхзанятий.Общая теория расписанийпредполагает, что все обслуживающие устройства (или процессоры) не могутвыполнять в данный момент времени более одного задания, что для расписанияучебных занятий не является достаточным, если в качестве процессора прираспределении заданий принять учебную аудиторию. Так в некоторых случаях водной аудитории могут проводиться занятия с более чем одной группойодновременно, например общие лекции для нескольких потоков.
Поэтому при переносе общейтеории расписаний на расписание учебных занятий были сделаны следующиедопущения:
- все процессоры (т.е. в случае учебного расписания -аудитории) имеют вместимость - некотороечисло C ≥ 1. Вместимость процессора определяет количествозаданий, которые он может одновременно 'обрабатывать' в данный моментвремени (в отношении неединичности процессоров было бы интересным рассмотретьвариант, когда в качестве процессора выступает не аудитория, а преподаватель, ав качестве задания - поток из одной или более учебных групп, с которыми онработает);
- в качестве множества заданий для распределения выступаютучебные занятия преподавателя с учебными группами;
- модель времени в системе является дискретной; всераспределение предполагается периодически повторяющимся на протяжениинекоторого временного интервала;
- все задания выполняются за одинаковое время, котороепринимается за единицу дискретизации временного интервала;
- задания имеют принадлежность к объектам, в качестве которыхвыступают учебные группы и преподаватели.
В итоге, формулировка задачисоставления расписания учебных занятий звучит следующим образом: 'Для заданного набора учебных аудиторий (в данном случае подучебной аудиторией понимается широкий круг помещений, в которых проводятсяучебные занятия (от компьютерной аудитории до спортивного зала)) и заданного наборавременных интервалов (т.е. по сути, уроков или учебных пар) построить такоераспределение учебных занятий для всех объектов (учителя и учебные группы), длякоторого выбранный критерий оптимальности является наилучшим'.
1.2. АнализсуществующегоПОНаданный момент времени сектор рынка ПО систем составления расписания занятий представлен большимколичеством различных программных продуктов. В таблице 1. представлены лишьнекоторые из известных мне.
В силу объективных причинсистема составления расписания в вузе (имеется в виду крупный государственныйвуз) обязательно должна реализовывать ряд основных функций:
- учет пожеланий преподавателей;
- закрепление обязательных аудиторий;
- указание желательных аудиторий;
- учет перехода между корпусами;
- объединение групп в потоки по любой совокупности дисциплин;
- разбиение на подгруппы;
- после составления расписания при необходимости осуществлятьзамену преподавателей или изменять времяпроведения занятия.
Кроме этого существуют еще испецифические для каждого вуза требования к функциональным возможностямпрограммного продукта.
Возможности на мой взгляд наиболеепопулярных на российском рынке программных продуктов приведены в приложении 1.
Из приведенного списка пожалуй только программа 'Методист' болееили менее соответствует требуемой функциональности программного продуктасоставления расписания в вузе. Такое положение вещей легко объясняется тем, чтошкольное образование на сегодняшний день более 'стандартизовано' (всмысле организации учебного процесса), чем вузовское. Такая стандартизацияведет к большому объему потенциального рынка продаж программного обеспечения иокупаемости разработки путем продажи большого числа копий продукта посравнительно низкой цене.