Автоматизированное составление расписания занятий в школе
(статья опубликована в журнале «Школьное планирование №4 2009)
Приближается начало нового учебного года и, как и прежде, десятки тысяч завучей нашей страны массово примутся за составление расписания занятий. Кто на компьютере, а кто и по старинке – при помощи миллиметровки, карандаша и ластика. Опять на несколько дней или недель (у кого как получится, бывает и по полтора месяца) они забудут свои семьи и лишатся спокойного сна. Потому как задача эта насколько ответственная, настолько и трудноразрешимая, особенно, в условиях непрерывного аврала, неопределенности и нестабильности, типичных для всех наших школ в период с конца августа по начало октября.
С одной стороны, может показаться, что автоматизация составления расписания является чисто математической проблемой и она, пусть нетривиальными методами, но может быть формализована, алгоритмизирована и переведена на язык машинных кодов. А быстродействие современных компьютеров должно обеспечить достижение требуемого результата в приемлемые сроки. Именно на таких ожиданиях в середине-конце 90-х годов в нашей стране, равно как в ближнем и дальнем зарубежье, наблюдался бум производства программ составления расписания занятий для персональных компьютеров, которые к этому времени стали массовыми, весьма производительными и, главное, доступными для учебных заведений. Печально, но остается констатировать, что со своей благородной миссией эти программы не справились.
Во-первых, они едва-едва рассчитывали самые простые варианты расписаний. Чуть только появлялись сложности в виде иностранных языков с делением до трех групп, большого количества совместителей, ограничений по кабинетам и прочее, как программы впадали в глубокую задумчивость и выдавали вердикт о невозможности расстановки часов по причине полной несовместимости исходных данных.
Во-вторых, они считали непростительно долго. Часами, а то и сутками. После запуска на расчет пользователь мог спокойно отвлечься на другие дела, а, возвратившись к программе, обнаруживал десятки нерасписанных часов и множество рекомендаций типа «… Вам следует отменить десять методических дней … разрешить учителям по пять окон … ввести шестидневку …» и прочее. Даже если программа каким-то чудом выдавала более-менее приемлемое расписание, любая непроизвольная ошибка в исходных данных или спонтанное решение пары-тройки учителей о переносе их методических дней (а это не такая уж редкость), приводили к необходимости считать все снова. Кто в теме, тот знает, что для получения приемлемого результата программу нужно запустить не менее 15-20 раз. Умножаем на часы – получаем сутки и недели «автоматического» расчета.
В-третьих, программы 90-х были разработаны под операционную систему MS DOS, в которой очень трудно было создать по-настоящему эргономичный интерфейс. В результате, ввод данных по не самой сложной школе также мог занимать несколько дней. А в дальнейшем, даже простая коррекция исходных данных требовала утомительных путешествий по многочисленным меню, спискам и справочникам. Интересно, что впоследствии, с переходом на платформу ОС Windows, многие авторы не сочли нужным воспользоваться богатыми возможностями ее графики и механически перенесли свои интерфейсные наработки из DOS в новые программы.
Не очень впечатляющие результаты применения первых программ позволили некоторым разработчикам сформулировать генеральную идею о том, что задача составления расписания занятий лежит вовсе не в плоскости математики, а в области социальных и межличностных отношений. А потому не поддается алгоритмизации в принципе. Следовательно, не стоит и огород городить. Завучу, раз уж он обзавелся персональным компьютером, нужно дать его привычный инструмент, только осовремененный новыми информационными технологиями. В результате, на рубеже веков на свет появился класс незатейливых программ-редакторов расписаний, которые, не претендуя на глубину и научность, перенесли приемы работы с миллиметровкой, карандашом и ластиком на экран компьютера. При этом за самое главное достижение было выдано то, что программа безошибочно определяет случаи наложения часов учителя в разных классах и может показать свободное место, куда можно поставить очередной час. В некоторых программах имелась кнопка с интригующей надписью «Автоматический расчет», однако их интеллекта едва хватало на расстановку часов одной параллели, после чего предлагалось снять все возможные ограничения и расставить часы вручную.
Не наливайте новое вино в старые мехи. Этой библейской мудрости две тысячи лет, но мало кто ею руководствуется. Принятые за эталон, редакторы расписания были повсеместно распространены по учебным заведениям нашей страны, как правило, за счет бюджета, то есть конечный пользователь в большинстве случаев правом выбора не располагал. Существенного выигрыша в производительности редакторы расписаний не обеспечивают, более-менее сносно могут работать только в самых простых школах, возни с вводом данных и ручной редакцией требуют, как и прежде, немало. В итоге, тысячные тиражи дисков с программами пылятся в столах у завучей и директоров. Выбросить их нельзя, так как диски с инвентарным номером стоят на балансе школы и всякие ревизии ими время от времени интересуются.
В условиях неблагоприятной конкурентной среды многие программные проекты, которые были ориентированы на совершенствование алгоритмов автоматического расчета, свое развитие прекратили и известные в свое время бренды канули в лету. Не мудрено. Высокотехнологичные продукты требуют для своего развития немалых вложений, которые в этом сегменте рынка можно взять только из текущих продаж. А продаж мало, так как государство закупает в больших объемах и раздает «бесплатно» примитивные редакторы. Наш человек, как известно, неустойчив перед словом «бесплатно» и, по крайней мере, некоторое время о приобретении чего получше помышлять не склонен. Да и, при желании купить что-либо реально работающее, школы не всегда могут провести оплату через вышестоящие органы и казначейство. Им говорят, чтобы пользовались программами, на которые уже потрачены немалые народные деньги.
Но все же, идея тотальной автоматизации составления расписания не умерла и работа на этом направлении подспудно продолжалась и продолжается. В настоящее время на рынке представлены несколько программных решений, которые во многом избавились от недостатков программ 90-х и теперь претендуют на то, чтобы стать эффективным рабочим инструментом администрации современной школы.
Одним из таких решений является программа составления расписания занятий «НИКА» производства компании «НИКА-Софт».
Разработка программы была начата в 1998 году. Изначально программа предназначалась исключительно для домашнего использования женой автора, которая только-только стала замдиректора по учебной работе и впервые столкнулась с проблемой составления расписания. О существовании программ подобного рода автору ничего известно не было и, к счастью, не было представления о том, что задача не решаема в принципе. Что и явилось, в итоге, решающим фактором того, что удалось создать вполне работоспособную и по-своему уникальную программу. Которая действительно считает расписание в автоматическом режиме от начала до конца. Которая делает это очень быстро – не более одной минуты. В которой ввод данных по самой сложной школе занимает не более полутора-двух часов. Более подробно о побудительных мотивах и истории создания программы «НИКА» можно прочитать на сайте компании по адресу http://nikasoft.ru/sources.html.
Поначалу программа имела ограниченный набор функций, достаточный для работы в отдельно взятой московской школе. Школа, правда, была довольно типичной: пятидневная рабочая неделя, две смены, один иностранный язык с делением на две группы, много совместителей и большие претензии учителей к удобству их личного расписания. Программа со всем этим справлялась довольно легко, 99.9% часов расписывались в автоматическом режиме. Когда программой заинтересовались коллеги из других школ, автору довелось узнать, что бывают и более сложные случаи. Иностранный язык может делиться на три группы. Бывает, что одна часть класса идет на математику, а другая на биологию. В результате адаптации программы к потребностям других школ в ней появилось три вида деления классов на группы. И далее, по мере расширения ареала применения, в зависимости от пожеланий пользователей, программа прирастала все новыми функциями и возможностями: учет параллелей учителей, коэффициенты сложности предметов, графики распределения нагрузки классов по дням недели и прочее, прочее. В итоге, программа стала вполне универсальной, т.е. пригодной для любой общеобразовательной школы, гимназии, лицея. При этом она сохранила свои три основных отличительных свойства: автоматический расчет, высокая скорость расчета, быстрый и удобный ввод исходных данных.
Когда программой заинтересовались учреждения профессионального образования, для них была разработана версия «НИКА-Колледж», основной особенностью которой явилась возможность составления расписания парами и, соответственно, двухнедельного расписания («четная» и «нечетная» недели).
В марте 2009 года увидела свет четвертая версия программы «НИКА», соответственно, в модификациях «НИКА-Люкс 4» (для школ) и «НИКА-Колледж 4» (для учреждений профессионального образования). Помимо того, что были внесены серьезные усовершенствования в алгоритм и программа стала считать быстрее и «глубже», основным достоинством новой версии следует признать максимально «дружественный» интерфейс пользователя, который стал еще более наглядным, удобным и интуитивно понятным. Вместо того чтобы запоминать сложные способы записи отношений в пространстве учитель-класс-предмет-урок-кабинет, пользователь теперь использует графические элементы управления, в которых предполагаемые действия достаточно очевидны и исключают совершение синтаксических ошибок ввода. Кроме того, в программу интегрирован модуль предварительного анализа на предмет исключения логических противоречий в исходных данных. Этот модуль отслеживает появление несовместимых условий и ограничений, и предлагает их исправить еще до начала основного расчета.
Теперь хотелось бы более подробно остановиться на порядке и правилах работы с новой версией программы. Недавно программа была апробирована в одной довольно типичной московской школе. У школы до этого уже была программа-редактор, но по своим функциональным возможностям она никого не устраивала и администрация решила поискать более эффективный инструмент.
Основные параметры школьного расписания: шестидневная учебная неделя, учителей – 32, классов – 12 (без начальной школы), два иностранных языка, практика в ВУЗе у выпускных классов, занятия в бассейне. Учителя, как и в других московских школах, довольно требовательны к удобству своего личного расписания.
Здесь уместно привести одно интересное наблюдение. Москва, не секрет, несколько выделяется среди остальных городов необъятной России. По многим параметрам. И особенности школьного расписания не делают исключения. Анализ присылаемых со всех концов страны расписаний показывает, что в большинстве городов и весей расписание строится «от ученика». Это выражается в строгом соблюдении всевозможных санитарных и гигиенических норм: контроль ежедневной нагрузки и ее распределение по дням недели, запрет сложных предметов в конце дня, чередование предметов и прочее. Естественно, чтобы все эти требования удовлетворить, нужно закрыть глаза на то, что у учителей в расписании появляется много окон, уроки беспорядочно разбросаны по параллелям и у них, практически, не остается свободных дней.
В Москве этот номер не проходит. Во главе угла стоит пожелание учителя по заданному количеству методических дней в строго определенные дни недели, два, максимум, три окна в неделю и каждый день приход ко второму уроку (по утрам с собакой гулять надо). Тут правы, конечно, ранее упомянутые теоретики, что проблема составления расписания выходит далеко за рамки чистой математики. Экономический, социальный, психологический факторы на определенном этапе начинают активно мешать строгим алгоритмам делать их и без того непростую работу. Вывод только из этого очевидного факта был сделан неверный. Не отказываться от идеи алгоритмизации надо, а делать алгоритмы более гибкими и настраиваемыми под ту или иную ситуацию.
В каждом конкретном случае пользователь вынужден выбирать одну из трех стратегий составления расписания: «от ученика», «от учителя» или «жесткий компромисс». Увы, в этом вопросе учителя и учащиеся однозначно находятся по разные стороны баррикад.
Если представить условную шкалу, иллюстрирующую изменение баланса интересов в ту или иную сторону и применительно к разным регионам, то функция распределения стратегий составления расписаний будет иметь примерно такой вид (Рис.1).
Крайние значения слева и справа – это, соответственно, расписание в пользу ученика и учителя. Начало координат – это жесткий компромисс. Случай компромисса представляется оптимальным, но СЭС такое расписание все равно не утвердит. Ибо, нарушения СанПиН найдутся даже в крайнем левой части шкалы. Как администрация школ решает эту проблему – вопрос отдельный, выходящий за рамки данной статьи. Однако, в любом случае, наличие автоматически составленного расписания всегда является хорошим аргументом в общении с любыми проверяющими инстанциями.
Но вернемся к нашей московской школе. Несмотря на столичную прописку, завуч всеми силами старается сдвинуть расписание в левую часть шкалы. Трудовой коллектив не очень-то этому способствует и из года в год борьба с переменным успехом ведется вокруг компромиссной вертикали. При помощи прежних программ, имевшихся в школе, компромисс достигался по результатам нескольких дней напряженной работы. Как с этим справилась программа «НИКА-Люкс 4»?
Завуч и автор программы встретились ровно в полдень солнечным майским днем. Решили опробовать возможности программы на текущем расписании на второе полугодие. Начали, как водится, с исходных данных. Первым делом откорректировали основные параметры школы: задали шестидневную рабочую неделю, максимум семь уроков в день и четыре в субботу, а также виды нагрузки вне школьного расписания (бассейн и практика в ВУЗе) (Рис.2).
Далее отредактировали список преподаваемых предметов. Программа при поставке комплектуется файлом-шаблоном, который имеет стандартный перечень дисциплин. В данном случае к нему пришлось добавить такие предметы, как второй иностранный язык (немецкий), культура здоровья, логика и спецкурс (Рис.3).
Каждому предмету соответствует значение параметра Лимит, что означает максимальное количество часов данного предмета, которые могут быть расписаны в одном классе в один день. Стандартные значения Лимита также имеются в файле-шаблоне, но пользователь может их изменить, в том числе, для отдельного класса в параллели. У предметов имеется также такой параметр, как «Вес», который характеризует относительную сложность предмета по общепринятой 12-бальной шкале. Работу с перечнем предметов завершили заданием предметов, которые могут делиться на группы. В целом, программа предусматривает три способа деления классов на группы, но в этой школе все ограничивается одним классическим типом деления, когда на каждый класс по соответствующему предмету имеется два или три учителя.
Далее определились с перечнем классов, который задается посредством матрицы, в ячейки которой ставятся галочки при наличии в структуре школы соответствующей параллели и класса. Параметры каждого класса также можно модифицировать в специальной таблице, где можно задать: в какую смену учится класс, учится ли он в субботу, можно ли ему приходить на занятия ко второму уроку и прочее (Рис.4).
Самый емкий по времени этап – ввод перечня учителей, связывание их с предметами из ранее отредактированного перечня, а также ввод недельной нагрузки учителей по классам и по предметам. Ввод осуществляется в одну таблицу и, потому, нагляден, прост и не отнимает много времени. В таблице, несмотря на ее простоту, задаются все возможные особенности расписания, как-то: спаривание часов, нестандартное деление на группы, объединение классов, методические дни учителей, часы вне расписания для классов, графики предельной нагрузки и многое другое (Рис.5).
Добрая половина российских школ испытывает затруднения с распределением кабинетов среди учителей, в особенности, если кабинеты специализированные и соответствующие предметы не могут быть проведены в любом свободном помещении. В программе этот вопрос очень серьезно проработан. Имеется возможность задать общий перечень кабинетов, вместительность кабинета, его предметная направленность, а также одного или несколько ответственных учителей (Рис.6).
При расчете расписания каждому часу ставится в соответствие кабинет. Если у учителя есть свой кабинет, то он ему достается по умолчанию. Если своего кабинета нет, то подбирается свободный кабинет по предметной направленности. Если такового не находится, то подбирается любой свободный кабинет. Само собой, учитываются и работают такие ограничения, как невозможность физкультуры расписываться в любой кабинет, кроме спортзала, равно как и любой другой предмет не может получить спортзал в качестве учебной аудитории.
На этом ввод исходных данных был, в целом, завершен. Часы показывали системное время 13.15.
Задали параметры расчета: разрешили учителям ставить не более трех окон в неделю (не более одного окна в день) и неравномерное количество уроков по дням недели (разница – не более 2 уроков). Запустили расчет. Сразу всплыло окно «Логические ошибки ввода данных», посредством которого программа честно предупредила, что из всей учебной нагрузки не сможет расставить 12 часов, потому что пользователь при вводе исходных данных задал заведомо несовместимые условия (Рис.7).
Например, в 5а классе учитель русского языка имеет 6 часов нагрузки и пять рабочих дней, со вторника по субботу. При этом значение параметра Лимит для предмета Русский для всех классов установлено не более одного часа в день. Понятно, что по одному часу в день 6 часов нагрузки в расписание со вторника по субботу вставить невозможно. Модуль предварительного анализа это противоречие выявил и предлагает на выбор три варианта: убрать методический день учителя (пусть работает шесть дней), изменить значение параметра Лимит (разрешить расписывать по два часа русского в день) или проигнорировать это предупреждение. В последнем случае программа оставляет проблемный час на усмотрение пользователя, который должен будет впоследствии его поставить в расписание вручную.
Из других предупреждений, выданных программой, были: «Невозможно расставить два часа по не «смежным» дням» и «Невозможно расставить «легкие» предметы в разные дни». Первое связано с тем, что программа по умолчанию расставляет часы по предметам с недельной нагрузкой в 2 часа (география, биология, химия и т.д.) таким образом, чтобы они стояли хотя бы через день. Однако в данном случае оказалось, что учитель физики работает только в четверг и пятницу, и на другой график работы никак не согласен. Это ведь была московская школа.
Второе предупреждение, «Невозможно расставить «легкие» предметы в разные дни», также отражает сложную ситуацию с методднями учителей. Дело в том, что при вводе данных мы назвали «легкими» пять предметов: Физкультура, МХК, Труд, ИЗО и Культура здоровья. Программа знает, что «легкие» предметы никогда не должны встречаться друг с другом в расписании в один и тот же день и, поэтому, старается их развести по разным дням недели. Но, опять же, учителя по этим предметам запросили себе методдни таким образом, что выполнить это условие не имеется никакой физической возможности.
В итоге, исправили только значения Лимит для 5а класса по русскому и математике, разрешив таким образом ставить эти предметы по два часа в день. Остальные 10 однозначно нерасписываемых часов было решено оставить на потом.
В упомянутом окне нажали кнопку «Продолжить расчет» и программа через 15 секунд выдала свой первый вариант расписания. Все часы были расставлены в соответствии с заданными условиями, за исключением упомянутых 10-ти, и к ним еще добавились 2 часа, которые также не расписались в силу несовместимости исходных данных. Но несовместимости не первого порядка, как в вышеописанных случаях, а завязанной уже на более сложные отношения, которые модуль анализа логических ошибок уловить не смог. Таким образом, осталось 12 часов, которые не вписались с первого захода в наше расписание.
С часами, которые не расписались по явным причинам, разобраться оказалось довольно легко. Очевидно, что, если с требованиями учителей ничего поделать нельзя, придется отменять ограничения, наложенные на расписание в пользу учеников. В программе имеется режим перерасчета расписания. Это когда в готовом расписании, в котором расставлено 99% часов (причем, расставлено с учетом всех заложенных изначально условий и ограничений), делается попытка дорасписать оставшиеся часы с учетом отмены отдельных ограничений. Для этого, в параметрах программы мы задали условие, что при перерасчете можно проигнорировать требования об обязательной расстановке «легких» предметов в разные дни недели, а также требования по «смежным» дням. Через пять секунд все четыре висевшие часа учителя физики встали в его рабочие дни в четверг и пятницу. И 6 часов «легких» предметов также разошлись, образовав в отдельные дни неизбежное, но, все равно, «незаконное сожительство» физкультуры с ИЗО и МХК с культурой здоровья. Это и есть тот самый компромисс, без которого никакое расписание построить в принципе невозможно.
Тут завуч вспомнила, что в прежней программе у нее была функция отображения графика изменения нагрузки в классах по дням недели. Оказалось, что в программе «НИКА» подобная функция также присутствует (Рис.8).
Более того, имеется возможность задать предельные нагрузки классов для каждого дня недели, и программа будет их учитывать автоматически при расчете расписания в соответствии с выбранным профилем. Мы выбрали профиль перевернутой параболы, когда нагрузка должна иметь максимумы в середине недели. Потратив 15 минут на ввод значений графиков предельных нагрузок для каждого класса, запустили программу на расчет еще раз. Получили те же самые нерасписанные 12 часов, что и прежде. Плюс, к ним добавились еще три часа, которые явились объективным следствием нового достаточно серьезного ограничения в виде графиков предельной нагрузки. По итогам перерасчета на прежних условиях осталось четыре нерасписанных часа.
В параметрах перерасчета имеется возможность отменить ограничения на соблюдение графиков нагрузки. Но, в данном случае, мы решили это не применять и расставить четыре часа в режиме ручной редакции расписания.
Данный режим, хотя и называется «ручным», на самом деле представляет собой «полуавтомат». Пользователь имеет возможность зацепить мышкой нужный час и перенести его в то место, которое считает для него уместным. При этом, если в соответствующий день и час учитель уже задействован в другом классе, программа автоматически отработает перемещение его и других часов в расписании таким образом, чтобы, и образовавшееся в другом классе окно закрыть, и всевозможные условия с ограничениями не нарушить.
На расстановку четырех оставшихся часов «вручную» было потрачено еще около 15 минут. Затем расписание распечатали и изучили более пристально. Завуч обнаружила, что в двух случаях были неправильно заданы методические дни, что забыла директору запретить два последних урока в среду (она уезжает на совещание), а также ей не понравилось, что в младших классах очень много математики выпадает на последние уроки. Методдни исправили, директору поставили запретные часы. Для предмета Математика в пятых и шестых классах задали запрет расписываться на шестые уроки. Запустили расчет по новой. Результат, как нетрудно догадаться, оказался несколько иным. Всего насчитали 13 нерасписанных часов. С ними справились ранее отработанными приемами. Опять распечатали, стали изучать.
Тут, вошла другая завуч. Она также заинтересовалась расписанием. И выразила пожелание, чтобы при расписании ее часов (а она преподает химию) соблюдались, так называемые, «параллели». То есть, чтобы сначала она отвела часы, допустим, во всех 7-х классах, затем в 8-х, а на другой день таким же образом в 9-х и 10-х. Классической «лесенки» мы ей пообещать не смогли, но вот ограничить ее расписание двумя параллелями на один день, вполне уверенно пообещали. Задали соответствующее ограничение для предмета Химия и опять запустили расчет. Посмотрели, перерасчитали, довели «вручную», распечатали, проверили, остались, в целом, довольны. Завуч сказала, что есть еще некоторые шероховатости, но при наличии полуавтоматического редактора довести все до ума для нее не составит особого труда.
Когда сравнили основные показатели старого «ручного» расписания и рассчитанного с помощью программы «НИКА», то оказалось, что в новом расписании значительно меньше окон учителей и почти полностью удовлетворены условия непревышения уровней дневных нагрузок. В старом расписании последнее требование было удовлетворено только наполовину.
При расставании часы показывали 14.35. Около двух с половиной часов с перерывом на чай потребовалось на ввод с нуля всех данных по школе и на последующий расчет и доводку расписания, по которому школа может реально жить и работать.
Школа приобрела программу в тот же день.
Мы описали случай реального применения программы «НИКА» в одной типовой общеобразовательной школе. На самом деле, с момента выхода в свет новой версии программы, она была апробирована во многих школах, как с участием разработчиков, так и при самостоятельном освоении программы пользователями. Программа показала свою универсальность и эффективность в учебных заведениях самых разных типов и профилей. По результатам обобщения опыта эксплуатации мы планируем продолжить серию подобных публикаций, акцентируя внимание на применение программы в школах, гимназиях и лицеях, имеющих свою специфику и свои особые требования к расписанию занятий.