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

То, что вы здесь прочтете в большинстве своем чушь. Тем не менее в некоторых местах по моему мнению присутствуют здравые мысли, к сожалению таких мест получилось не так уж и много 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.

Из приведенного списка пожалуй только программа "Методист" более или менее соответствует требуемой функциональности программного продукта составления расписания в вузе. Такое положение вещей легко объясняется тем, что школьное образование на сегодняшний день более "стандартизовано" (в смысле организации учебного процесса), чем вузовское. Такая стандартизация ведет к большому объему потенциального рынка продаж программного обеспечения и окупаемости разработки путем продажи большого числа копий продукта по сравнительно низкой цене.

В случае вузов спрос на системы составления расписаний пожалуй даже больше, чем для школ, но дело осложняется большой спецификой организации учебного процесса в каждом отдельно взятом вузе. Создать унифицированное программное обеспечение не представляется возможным, а стоимость создания специализированного продукта у сторонних разработчиков оказывается неоправданно велика. Кроме того, обязательным условием является наличие "устоявшегося" расписания, что предполагает наличие возможности осуществлять замену преподавателей или время проведения занятий. Пока ни один программный продукт не позволяет достаточно просто этого делать (хотя некоторые возможности и есть в "Методисте").

1.3. Постановка задачи.

Целью данной работы было создание такой математической модели расписания в вузе, которая позволяла бы эффективно (в заданные сроки и с заданной степенью оптимальности) решать задачу автоматического составления расписания и обладала бы гибкостью (незначительных изменений в случае изменений входной информации) для адаптации системы в рамках конкретной практической задачи. Для некоторого упрощения задачи на начальном этапе проектирования были сделаны некоторые допущения:

- расписание составляется из расчета не более двух пар в день (что вполне подходит для случая вечерней формы обучения);

- все пары проводятся в одном корпусе;

- задача ставится в терминах линейного программирования;

- дальнейшая декомпозиция модели не производится;

- все коэффициенты модели и искомые переменные целочисленны;

Поставленная задача должна решаться одним из универсальных (не зависящих от целочисленных значений коэффициентов) методов целочисленного линейного программирования.

2. Разработка математической модели и практическая реализация системы автоматического составления расписания 2.1. Математическая модель расписания в вузе

Построим математическую модель расписания в вузе в терминах линейного программирования. Введем обозначения и определим переменные и ограничения.

2.1.1. Обозначения

ГРУППЫ

В вузе имеется N учебных групп, объединенных в R потоков; r – номер потока, r = 1, ..., R, k_r – номер учебной группы в потоке r, k_r = 1, …, G_r.

Разбиение на групп на потоки осуществляется исходя из принципов:

1. Использование двумя группами одного и того же аудиторного фонда для своих лекций автоматически предполагает помещение их в 1 поток (предполагается, что все лекции учебных групп проходят вместе).

2. Группа(или ее часть), как единица учебного процесса в вузе, может входить в разные потоки, но только по одному раз в каждый из них.

3. Количество потоков не лимитируется.

ЗАНЯТИЯ

Занятия проводятся в рабочие дни в полуторочасовые интервалы, которые будем называть парами.

Обозначим:

t – номер рабочего дня недели, t Є T_kr, где

T_kr–множество номеров рабочих дней для группы k_r;

j – номер пары, j = 1 ,…, J;

J – общее количество пар.

С каждой учебной группой k_r потока r в течение недели, согласно учебному плану, проводится W_kr занятий, из которых S_r лекционных и Q_kr практических. Обозначим:

s_r – номер дисциплины в списке лекционных занятий для потока r, s_r = 1 ,…,S_r;

q_kr – номер дисциплины в списке практических занятий для группы k_r, q_kr = 1 ,…, Q_kr.

Предполагается, что лекции проводятся у всех групп потока одновременно и в одной аудитории. Тогда, если по какой-то дисциплине в течение недели проводится более одного занятия, эта дисциплина упоминается в списке лекций или практических занятий столько раз, сколько их предусматривается учебным планом для каждого потока или группы.

ПРЕПОДАВАТЕЛИ

Пусть p – номер (имя) преподавателя, p = 1 ,…, P. Введем в рассмотрение булевы значения и :

1, если на потоке r лекцию sr читает преподаватель p; 0 – в противном случае;

1, если в группе kr практическое занятие qkr проводит преподаватель p; 0 – в противном случае;

=

Учебная нагрузка преподавателей планируется до составления расписания занятий, вследствие чего на данном этапе величины и можно считать заданными. Для каждого преподавателя p, p = 1 ,…,P, задана также его аудиторная нагрузка - N_p часов в неделю.

АУДИТОРНЫЙ ФОНД

Занятия каждого потока могут проводиться только в определенных аудиториях (например, практические занятия по информатике могут проводится только в дисплейных классах). Пусть:

{A_1r} – множество аудиторий для лекций на потоке r;

{A_2r} – множество аудиторий для практических занятий на потоке r;

A_1r – число элементов множества {A_1r};

A_2r – число элементов множества {A_2r};

A_1r + A_2r – число аудиторий объединения множеств {A_1r}∩{A_2r}.

Аудиторный фонд определяется до начала составления расписания, поэтому множества можно считать заданными.

2.1.2. Переменные

Задача составления расписания заключается в определении для каждой лекции (на потоке) и практического занятия (в группе) дня недели и пары в этот день с учетом выполнения конструируемых ниже ограничений и минимизации некоторой целевой функции.

Введем следующие искомые булевы переменные:

1, если на потоке r в день t на паре j читается лекция sr; 0 – в противном случае;

1, если на потоке r в день t на паре j у группы kr проводится практическое занятие qkr; 0 – в противном случае;

=

=

В случае составления расписания для групп вечерней формы обучения J=2. Обобщение модели на все формы обучения см. [1], стр. 669.

2.1.3. Ограничения

Для каждой группы k_r должны выполняться все виды аудиторной работы в течение недели:

(1)

В любой день t на каждой паре j для каждой группы k_r может проводиться не более одного занятия:

(2)

Каждые лекция s_r и практическое занятие q_kr соответственно для всех потоков r и всех групп k_r могут проводиться не более одного раза в любой день t:

(3)

Если переменные и увязывают все виды занятий с временем их проведения, то произведения и связывают время проведения с именем преподавателя.

В каждый день t и в каждой паре j преподаватель p может вести не более одного занятия по одной дисциплине на одном потоке или в одной группе:

(4)

Каждый преподаватель p в течение недели должен провести аудиторные занятия:

(5)

Наконец, в каждый день на каждой паре число лекций и практических занятий не должно превышать имеющийся в вузе аудиторный фонд:

(6)

(7)

Кроме того, для всех совокупностей пересекающихся множеств {A_1r} и {A_2r} должны выполняться условия:

(8)

Представленными соотношениями исчерпываются безусловные ограничения, с которыми всегда считаются при составлении расписания. Могут, однако быть и специфические условия, прежде всего проведение отдельных видов работы по “верхней” или по “нижней” неделе (т.е. один академический час в неделю). Не исключены и другие специальные условия, но для упрощения модели они не рассматривались.

2.1.4. Целевая функция

Чтобы полноценно вести научную, учебно-методическую работу, готовиться к занятиям, преподаватель вуза должен иметь свободное время. Это условие недостаточное, но необходимое. Очевидно, что свободным временем он должен располагать не в “рваном” режиме, каковым, например, являются “окна” между занятиями со студентами, а по возможности в полностью свободные рабочие дни. Этому эквивалентна максимизация аудиторной нагрузки преподавателей в те дни, когда они ее имеют (см. (5)). Однако при этом претензии на свободное время у преподавателей неравны, так как у них разный творческий потенциал. Поэтому необходимо ввести весовые коэффициенты, посредством которых должен учитываться соответствующий статус преподавателя – его ученые степени и звание, занимаемая должность, научно-общественная активность и т.п. В некоторых случаях можно на основании экспертных оценок использовать индивидуальные весовые коэффициенты, учитывающие другие факторы.

Итак, выберем критерий качества составления расписания занятий в виде максимизации взвешенного числа свободных от аудиторной работы дней для всех преподавателей, что при условии фиксированной длины рабочей недели эквивалентно максимальному совокупному уплотнению аудиторной нагрузки.

Рассмотрим выражение для величины аудиторной нагрузки в день t преподавателя p:

(9)

Вводятся ограничения вида:

	(10)

где M – произвольное положительное достаточно большое число; - искомая булева переменная.

Из (10) вытекает, что если , то = 1, и если , то = 0.

С учетом указанного выше содержательного смысла критерия оптимизации в дополнительных ограничениях (10), а также вводя весовые коэффициенты статуса преподавателя , получаем искомый критерий оптимальности:

	(11)

Введенная целевая функция не является единственно возможной. Введение других целевых функций не меняет ограничений математической модели и методов решения задачи, но может существенно повлиять на результаты вычислений.

2.2. МЕТОДЫ РЕШЕНИЯ ПОСТАВЛЕННОЙ ЗАДАЧИ

Поставленная в предыдущем пункте задача максимизации линейной целевой функции при заданной системе ограничений является задачей линейного целочисленного булева программирования, поскольку все коэффициенты ограничений целочисленны в силу дискретности исходных данных задачи; кроме этого искомые переменные математической модели могут принимать только два значения. На данный момент времени существует несколько возможных методов решения такого рода задач.

В [3] – [8] описаны методы упорядоченной индексации и модифицированных пометок, основанные на лагранжевой декомпозиции исходной модели на ряд однострочных задач, решаемых соответственно методами упорядочивающей индексации или модифицированных пометок. К сожалению количество операций каждого из методов не допускает полиномиальной оценки; кроме того, размерность таблицы наборов (промежуточных значений) методов резко возрастает при увеличении размерности решаемой задачи, что недопустимо в нашем случае. Возможно, изменение алгоритма декомпозиции под конкретную математическую модель позволит уменьшить размерность таблиц, но пока такого алгоритма не существует.

В связи с этим в качестве методов решения были выбраны описанные в [2] модификации симплекс-метода для случая задачи целочисленного линейного программирования. В общем случае количество операций симплекс-метода не допускает полиномиальной оценки (был даже показан класс задач, для которых количество операций составляет O(eⁿ)), но для случая нашей задачи среднее число операций допускает полиномиальную оценку: O(n³m^1/(n-1)) (n – количество переменных; m – количество ограничений).

2.2.1. ПОЛНОСТЬЮ ЦЕЛОЧИСЛЕННЫЙ АЛГОРИТМ

Этот алгоритм назван полностью целочисленным, потому что если исходная таблица состоит из целочисленных элементов, то все таблицы, получающиеся в процессе работы алгоритма, содержат только целочисленные элементы. Подобно двойственному симплекс-методу, алгоритм начинает работать с двойственно допустимой таблицы. Если a_i0 (i = 1 ,…, n+m; a_i0 – коэффициенты целевой функции) – неотрицательные целые, то задача решена. Если для какой-нибудь строки a_i0