Конкурентоспособность учебных заведений зависит от качества организации учебного процесса [9]. В то же время задачи управления учебным процессом настолько усложнились, что настоятельно требуют автоматизации. Большинство этих проблем могут быть решены с помощью автоматизации высшего учебного заведения [1].
Считаем, что технологию разработки расписания следует воспринимать не только как трудоемкий технический процесс, объект механизации и автоматизации с использованием ЭВМ, но и как процесс оптимального управления сложными системами [9]. Поскольку интересы участников учебного процесса многообразны, задача составления расписания — многокритериальная [2, 3, 8].
Из теории вопроса известно, что задача составления расписания — это NP-полная многоэкстремальная комбинаторная задача с большим количеством ограничений [4, 7].
Рассматриваемая задача является задачей линейного целочисленного булева программирования, поскольку все коэффициенты ограничений целочисленны в силу дискретности исходных данных задачи; кроме этого искомые переменные математической модели могут принимать только два значения. На данный момент времени существует несколько возможных методов решения такого рода задач.
Автором работы [6] описаны методы упорядоченной индексации и модифицированных пометок, основанные на лагранжевой декомпозиции исходной модели на ряд однострочных задач, решаемых соответственно методами упорядочивающей индексации или модифицированных пометок. К сожалению, количество операций каждого из методов не допускает полиномиальной оценки. Кроме того, размерность таблицы наборов (промежуточных значений) методов резко возрастает при увеличении размерности решаемой задачи, что недопустимо в рассматриваемом случае. Возможно, изменение алгоритма декомпозиции под конкретную математическую модель позволит уменьшить размерность таблиц, но пока такого алгоритма не существует.
На практике чаще всего применяют изложенные в работе [5] модификации симплекс-метода для случая задачи целочисленного линейного программирования. В общем случае количество операций симплекс-метода растет экспоненциально O(en), однако в некоторых случаях частных задач составления расписания среднее число операций может быть полиномиальным O(n3m1/(n-1)) (n — количество переменных; m — количество ограничений).
Однако в указанных работах не учитываются возможности современной вычислительной техники — повышенная разрядность и многоядерность процессоров, которые могут оказать решающую роль в снижении времени решения задачи.
Наиболее известная и часто встречающаяся в литературе NP полная задача — задача составления расписания. На сегодняшний день принято считать, что задачи составления расписания являются NP-полной многоэкстремальной комбинаторной задачей с большим количеством ограничений. Большинство исследований в этой области имеют два направления: теоретическое и практическое. В теоретической части преобладает математическая составляющая задачи, а также попытки оптимизировать решение самой задачи. Конечно, при разработке решения акцент делается на преодолении цикличности решения задачи. В практической части есть компьютерные реализации решения задачи, в основу которых положен процесс нахождения локального оптимума решения задачи, как способ уйти от большого количества вариантов при прямом переборе. Оба подхода развиваются параллельно. Однако ни один подход не предлагает методов, в полной мере учитывающих особенности и возможности современной вычислительной техники.
Необходимо разработать метод решения задачи составления расписания, ориентированный на применение современных вычислительных средств.
Для расписания можно выделить четыре типа ограничений. Современный компьютер имеет в своём арсенале 64-битные регистры памяти, это означает, что процессор способен осуществлять арифметико-логические операции над 64-битными типами данных за один такт.
Следовательно, если представить шкалу расставленных экземпляров занятия в виде 64-битного числа, где номер бита — это номер пары на неделе (начиная с 0 до 63), а значение бита 1- занятие есть, 0 — нет. Т.е. бит номер 0 соответствует первой паре понедельника. Если в вузе девять пар в день и обучение происходит шесть дней в неделю, то бит номер 8 — первая пара во вторник, а бит номер 53 — девятая пара в субботу. После бита номер 53 другие биты, зарезервированы и не используются. Такое представление данных позволяет производить операции сравнения по всей шкале.
Разработанный алгоритм решения задачи составления расписания учитывает возможность декомпозиции начальной задачи и ориентирован на обработку непосредственно на регистрах персонального компьютера. Указанный подход позволяет свести NP-полную задачу к имеющей полиномиальную вычислительную трудоемкость. На рисунке 1 показано время решения задачи (секунды) методом полного перебора и с помощью предложенного алгоритма.
Разработанный алгоритм существенно превосходит существующие алгоритмы. Декомпозиция задачи позволила выделить основную задачу и разработать алгоритм ускорения приемлемый для современных вычислительных средств. Основным достоинством данного алгоритма является возможность распараллеливания алгоритма на множество процессоров, что является преимуществом по сравнению с классическими алгоритмами линейного программирования.