1. Введение
1.1. Описание предметной области
Задача составления расписания занятий для учебных заведений имеет давнюю историю. Она интересовала людей, занятых в процессе формирования учебного процесса с момента появления образовательных учреждений массового характера: школ, гимназий, колледжей, институтов и университетов.
Традиционно эта задача решалась вручную каким-либо человеком, который, на основании определенных критериев, вручную чертил на бумаге расписание, традиционно имеющее вид таблицы, удовлетворяющее определенным свойствам.
С появлением новых предметов, с увеличением числа преподавателей и студентов, с делением студентов на группы и подгруппы, с появлением таких понятий как потоковые лекции, номера аудиторий, выходные дни, максимальная нагрузка в день, пожелания преподавателей на возможность проведения лекций, приглашение на проведение некоторых лекций преподавателей из других учебных заведений и невозможность их присутствия в определенные дни/часы, а также многие другие факторы привели к значительному усложнению проблемы составления расписания.
Хотя за довольно долгий срок существования данной проблемы были выработаны некоторые методические указания и рекомендации по разработке и формированию расписания занятий, но при достаточно большом наборе исходных данных и при множестве ограничивающих факторов (критериев), они довольно часто оказывают мало пользы, и процесс формирования расписания продолжает оставаться довольно сложным и трудоемким занятием.
Хотя имеющиеся математические достижения в области исследования операций и методах оптимизации можно довольно успешно использовать при относительно небольшой сложности задачи, то при значительном увеличении количества критериев, по которым проводится оптимизация, как в случае составления расписания занятий для университетов, эти методы оказываются не очень эффективными (а очень часто даже и очень неэффективными), хотя для таких образовательных учреждений как школа эти методы вполне приемлемы [19].
Следуют заметить, что в наше время всеобщей автоматизации и компьютеризации производства и общества в целом во многих образовательных учреждениях задача составления расписания решается по старинке, т.е. вручную.
Составить оптимальное расписание, удовлет¬воряющее всем дидактическим требованиям, по¬зволяющим реализовать все возможности струк¬турно-логических схем и обеспечивающим мето¬дически правильное планирование учебной рабо¬ты на семестр студентам и преподавателям, с ис¬пользованием известных алгоритмов и подходов очень сложно, так как необходимо учесть много ограничивающих факторов: число учебных ауди¬торий и их структуру, число лекторов, пропуск¬ную способность учебных аудиторий и их особен¬ности, требования, обеспечивающие качество, и выполнить большое количество заявок препода¬вателей по планированию их рабочего дня [8].
Поэтому основной задачей при составлении расписания является планирование и обеспечение методически правильного процесса изучения всех учебных дисциплин учебного плана: их взаимосвязи, правильной последовательности и чередования всех форм учебной работы по дисциплинам на основе учета множества факторов [18].
Из описания проблемы видно, что она не является чем-то новым, но явно нуждается в упрощении труда человека, занятого ее решением. Т.е. налицо необходимость автоматизации решения данной задачи посредством разработки и реализации компьютерной программы.
1.2. Основные понятия
Расписание учебных занятий – это документ, регламентирующий работу студентов, преподавателей, всего учебного заведения, распределяющий содержание учебного плана и рабочих программ по календарным дням учебного года и обеспечивающий их реализацию. Расписание учебных занятий должно удовлетворять педагогическим требованиям, основанным на принципах аналитической дидактики и кибернетической аналогии. Оптимально составленное расписание учебных занятий не должно изменяться в течение семестра или учебного цикла, чтобы не нарушить учтенные в расписании межпредметные связи и выполненные требования [8].
Целью задачи генерации расписания является задача оптимизации, в которой из имеющего множества порожденных расписаний необходимо выделить то, которое имеет целевую функцию с наименьшим значением (наиболее близким к нулю), т.е. задачей всего процесса является минимизация значения целевой функции.
Основными условиями, определяющими корректность расписания, являются:
• Соответствие требуемого количества пар в неделю каждого предмета каждого преподавателя их количеству в расписании;
• Невозможность ведения одним преподавателем в одно и то же время различных предметов у нескольких групп;
• Соответствие количества пар в единицу времени (равной продолжительности одной пары) у всего института количеству свободных аудиторий в эту же единицу времени.
• Свободность (незанятость) аудитории, в которой проводится лекция, в определенное время;
• Проверка на «вмещаемость» группы в аудиторию (либо нескольких групп в аудиторию при проведении потоковых лекций);
• Необходимость проведения лекции в определенной аудитории (например, это может быть химическая лаборатория или компьютерный класс);
• Возможность проведения потоковых лекций;
• Возможность проведения лекций по числителю/знаменателю;
• Необходимость проведения лекций в строго фиксированное время (в конкретное время в определенный день недели);
• Возможность задания дня, в который нельзя проводить занятия (например, если в этот день у группы должна проводиться Военная подготовка, которая занимает весь учебный день и место ее проведения находится достаточно далеко от здания университета);
• Желание преподавателя вести определенные пары в определенные интервалы времени;
• Невозможность или какие-либо затруднения у преподавателя с прибытием к какому-то времени в определенные дни;
• Добиться оптимального распределения количества пар по дням для каждой из групп (не сильно мало и не сильно много);
• Одинаковые пары желательно проводить непосредственно друг за другом;
• Стараться избегать «окон», т.е. такого времени между парами, когда у группы нет занятий.
Под окном понимается пара, расположенная между двумя лекциями, во время которой лекции у группы не читаются. Таким образом, под данное определение окна не попадает свободная пара в начале (конце) дня. Пара, во время которой лекции не читаются, расположенная между двумя окнами, либо между окном и лекцией, тоже считается окном.
Генетические алгоритмы - адаптивные методы поиска, которые часто используются для решения задач функциональной оптимизации. Они основаны на генетических процессах биологических организмов: биологические популяции развиваются в течение нескольких поколений, подчиняясь законам естественного отбора и по принципу "выживает наиболее приспособленный".
Кроссинговер (кроссовер, скрещивание) - операция, при которой из двух хромосом порождается одна или несколько новых хромосом.
Мутация - преобразование хромосомы, случайно изменяющее одну или несколько ее позиций (генов).
Хромосома - некоторый числовой вектор, соответствующий подбираемому параметру, а набор хромосом данной особи определяет решение задачи.
1.3. Неформальная постановка задачи
Требуется разработать программу генерации семестрового расписания занятий для факультета, в которой, для увеличения производительности работы, предполагается использование генетических алгоритмов в совокупности с распределенными вычислениями.
Под распределенными вычислениями будем понимать процесс одновременного решения задачи на нескольких терминалах с использованием технологии клиент-сервер.
Для достижения поставленной цели предлагается создать два различных приложения: клиент и сервер, при взаимодействии которых стало бы возможным получение желаемого результата.
Клиенты запускаются на различных машинах и занимаются непосредственно генерацией расписания, а сервер синхронизирует их действия, т.е. управляет ими с помощью механизма обмена сообщениями по одному из сетевых протоколов.
На основании результатов, полученных сервером от клиентов, пользователь может выбрать наиболее удовлетворяющее его критериям решение, сохранить его для дальнейшей обработки, либо экспортировать в формат Microsoft Excel для просмотра, редактирования и распечатки.
1.4. Обзор существующих методов решения
1.4.1. Подходы к решению задачи
|