ЗАДАЧА СОСТАВЛЕНИЯ ШКОЛЬНОГО РАСПИСАНИЯ

(Кодекс о школьном расписании с короткими
комментариями и пояснениями)

Вот уже на протяжении нескольких десятилетий людям так или иначе связанным с образовательным процессом не дает покоя вопрос применения компьютеров (раньше ЭВМ) при составлении расписания занятий в учебном заведении. Имеются описания работ по автоматизации процесса составления расписания, которые проводились у нас в стране еще на больших ЭВМ и для которых в качестве носителей данных использовались картонные перфокарты. Особой популярностью эта задача пользуется у начинающих программистов - школьников и студентов. Однако серьезные ученые постоянно их предупреждают об имеющихся трудностях на выбранном пути. Так, на странице 171 в учебнике для будущих математиков - (Романовский И.В. Дискретный анализ. Учебное пособие для студентов, специализирующихся по прикладной математике и информатике. - СПб.: Невский диалект, 2000.) автор язвительно пишет:

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

Довольно сильно интерес юных программистов подогревает к этой задаче и легенда о том как, теперь самый богатый человек на планете, а тогда юный (шестнадцати летний) Билл Гейтс вместе со своим старшим другом Полом Алленом "решили" эту задачу, взамен получили за программирование машинное время и заработали 2400 долларов карманных денег. С этой историей можно ознакомиться, например, на страницах 22-24 книжки: Ичбана Д., Кнеппер С. Бил Гейтс и сотворение Microsoft. Ростов-на-Дону: Издательство "Феникс", 1997.

Достаточно характерным высказыванием разработчиков программ по составлению школьного расписания, начинавших свою работу у нас в стране еще каких-нибудь лет восемь - девять назад, является примерно такое: 

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

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

ПРИМЕЧАНИЕ: Думаю, что не сильно ошибусь, если скажу, что соотношение источников информации по рассматриваемой теме, на русском языке и на английском составляет примерно 1:100. В принципе эта цифра вполне соответствует отношению доли экономики нашей страны в мировой экономике. А если еще и учесть, что основным богатством нашей страны является необработанное сырье, а не высоко технологичная продукция, тем более в сфере информатизации, то цифра может измениться и в худшею для нас сторону. Так  например, объем продаж не без известной корпорации Microsoft на российском рынке в 2006 ф. г., составил около 0.67% (ноль целых шестьдесят сем сотых процента) от общемировых продаж (общего объема продаж в мире).  Но ничего, зато у нас есть свобода слова. Ежедневно по телевизору можно посмотреть один а то и два фильма о том как менты борются с бандитами и как бандиты шикарно живут оставаясь не уязвимыми для ментов.

Лет шесть назад отечественные разработчики программ составления расписания уже начали делать, а теперь (точнее два года назад в 2004 г.) и заявлять примерно следующее:

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

Приведем еще одно поучительное заявление:

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

Таким образом, появилась возможность изучения опыта работы коллег по цеху, не приставая в течение двух лет к живым людям (завучам) с просьбой "на благо родины" поделиться "секретными технологиями" их работы, а блуждая по закоулкам и перемещаясь по магистралям Всемирной Паутины, почти бесплатно черпать нужную информацию. Что называется, помню по себе, как еще в каком-нибудь 1993 году попытка просто сформулировать на содержательном уровне задачу составления расписания школьных занятий закончилась для меня полным провалом. Думаю, да в общем-то уверен, что с такой бедой столкнулся не только я один. На взгляд автора, последовательное и систематическое (упорядоченное) обсуждение рассматриваемой задачи может пригодиться (будет интересно) не только начинающим программистам но и пользователям программных систем составления расписания занятий в школе.

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

Следует отметить, что автор предпринял все усилия на которые только был способен, а сделать это не так просто, в том числе и по объективным причинам, что бы найти ту "золотую середину" (тот компромисс) между математическим текстом, доступным только профессионалу - математику, с одной стороны, текстом понятным человеку с гуманитарным образованием, с другой стороны, и, что называется, "литературой для слабоумных", с третьей. 

ПРИМЕЧАНИЕ: К "литературе для слабоумных" автор отнес бы следующее заявление:

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

Или следующее:

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

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

Больше всего автору в "литературе для слабоумных" нравятся примерно такие обороты:

1) Если у учителей маленькие зарплаты, то невозможно придумать (его не существует) алгоритм составления школьного расписания; 2) Если наша программа не расставляет в сетку часов всю учебную нагрузку, то в этом виновато правительство Российской Федерации и гадкие чиновники со своими омерзительными инструкциями; 3) В последние годы ситуация кардинально изменилась - с повсеместным распространением персональных компьютеров и прикладного программирования выяснилось, что задача составления расписания является задачей нематематической; 4) Невозможно составить приемлемое расписание, не зная взаимоотношений между учителями, не предугадывая возможную реакцию родительских комитетов отдельных классов; 5) Подводя итог, отметим, что несмотря на использование математического моделирования в столь тонком деле, как составление расписание для средней школы, ожидание стопроцентного результата - утопия. Качественный результат можно получить лишь при комбинированном методе, при совмещении искусственного интеллекта и человеческого знания; 6) Получение наилучшего решения поставленной задачи возможно только перебором всех возможных вариантов решения, что ставит задачу в ряд задач комбинаторики. Но полный перебор нецелесообразен из-за большого количества вариантов; 7) Работа по составлению расписаний - крайне нервная и напряженная, а условия экстремальные. Нужно уметь сдерживать эмоции и осваивать правильные компьютерные приемы и методы работы. Тогда вы получите хороший результат; 8) Ручной режим составления Расписания предназначен для опытных преподавателей, у которых сложились свои технологии составления расписания и которым нужен лишь удобный инструмент; 9) Так как не существует строгих алгоритмов составления расписания, в этом режиме предлагаются лишь возможные варианты автоматического расчета; 10) Задача решается автоматически до нахождения оптимального варианта решения; если автоматическое решение затруднено, оператору выдаются рекомендации по изменению исходных данных с целью успешного решения; 11) Каждый добросовестный завуч вкладывает в расписание душу и сердце, почти в прямом смысле; 12) Поскольку программа составления расписания работает с большой базой данных, в которой содержатся сведения о школе, учебных планах, учителях, предметах и т.п., она предоставляет пользователю дополнительные возможности; 13) Программа поддержки расписаний написана на языке Delphi с использованием собственных программных разработок специалистов компании, что значительно повышает производительность системы; 14) С помощью нашей программы пользователь может практически неограниченное число раз искать лучший вариант заполнения сетки расписания, наиболее полно удовлетворяющий огромному объему требований; 15) Во всех этих проблемах, как правило, винят завуча (или другого человека, составляющего расписание), не справляющегося со своими обязанностями. Но, как показывает анализ, проблема гораздо серьезнее: следует говорить о принципиальной неразрешимости задачи составления школьного расписания в результате противоречивости (как правило) условий, налагаемых на данное расписание. Причем чем большее количество условий накладывается на расписание, тем более очевидна неразрешимость этой задачи. ... Поэтому завуч ищет не идеальное решение, а решение, которое удовлетворяло бы обязательным условиям (и наибольшему их количеству), получая приемлемое расписание; 16) Решением задач, подобных проблеме составления школьного расписания, занимается теория расписаний. В ней можно встретить и сложные задачи, тем не менее довольно легко поддающиеся алгоритмизации, и, казалось бы, легкие, решить которые нельзя иначе, как перебором. Проблему составления школьного расписания, к сожалению, можно отнести к последней группе — определенного алгоритма для ее решения (кроме перебора) не существует (впрочем, как было оговорено выше, он и не может существовать).

Этот список можно было бы продолжать чуть ли не ограничено. Кстати говоря, автор собирает коллекцию подобных глупостей.

На этом мы заканчиваем, что называется, краткое введение в тему, включая обзор различных глупостей, и переходим к реализации той скромной цели, которую поставил перед собой автор - попытка разработки первого (эскизного) варианта кодекса школьного расписания. Следует отметить, что чтение любого кодекса, что уголовного, что трудового, что школьного расписания,  задача не простая и до чертиков скучная. Автор в меру своих способностей попытался "разбавить" текст различными примечаниями, но тем не менее, от читателя понадобится известное мужество, что бы до конца дочитать весь предлагаемый текст. Итак, уменьшим скорость чтения, по меньшей мере, раз в пять.

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

  1. Перечень результатов формирования (построения, составления) расписания;
  2. Стратегию (общие принципы, политику, общие правила) составления школьного расписания;
  3. Общие требования ко всему расписанию в целом;
  4. Необходимые условия существования расписания (потенциальной возможности его построения);
  5. Базовое требование формирования (построения, составления) расписания;
  6. Безусловные требования формирования (построения, составления) расписания;
  7. Жесткие требования (для классов и учителей) формирования (построения, составления) расписания;
  8. Мягкие требования (для классов и учителей) формирования (построения, составления) расписания;
  9. Общие требования к программе (алгоритму) решения задачи составления расписания школьных занятий и последовательность работы по составлению расписания;
  10. Требования к коррекции расписания во время использования его в учебном процессе;
  11. Дополнительные задачи (функции), решаемые (обеспечиваемые) параллельно с составлением расписания занятий;
  12. Перечень исходных данных для формирования (построения, составления) расписания.

ПРИМЕЧАНИЕ 1: Смысл каждого из приведенных пунктов будет, с большей или меньшей степенью подробности, разъяснен далее по тексту. Однако здесь необходимо сразу же пояснить такие понятия как - базовое требование, безусловное требование, жесткое требование, мягкое требование.

ПРИМЕЧАНИЕ 2: Везде в данном тексте употребляется термин - школьное расписание. Следует иметь ввиду, что под школьным расписанием понимается расписание не только для средних общеобразовательных школ. Под школьным расписанием понимается расписание для достаточно широкого круга учебных заведений - колледжей, училищ, лицеев и т.п. Основным признаком школьного расписания в отличии, например, от расписания для высшего учебного заведения, является то, что в расчете участвует единый учительский (преподавательский, педагогический) коллектив, в то время как, педагогический (профессорско-преподавательский) коллектив высшего учебного заведения разделен на отдельные кафедры, задействованные для преподавания на разных факультетах.

ПРИМЕЧАНИЕ 3: Говоря о термине - школьное расписание, следует так же отметить, что под школьным расписанием не имеется в виду расписание для начальной школы. Это объясняется тем, что такое расписание по существу является весьма тривиальным случаем. Действительно, что здесь рассчитывать (составлять)? Один учитель (учитель младших классов) учит детей всем предметам, все время, в одном помещении. Единственная тонкость состоит в том, что некоторые учителя, обучающие специфическим предметам, например, физическое воспитание или иностранный язык, которые обучают школьников 2-й и 3-й ступени (средних и старших классов) могут быть задействованы и в начальной школе. Вопрос о посещении (преподавании) начальной школы решается весьма просто - в свободное от "основной" работы время (во время не занятое преподаванием в старших классах).

ПРИМЕЧАНИЕ 4: Любой качественный законодательный текст всегда структурирован. То есть, разделен на главы, главы разделены на статьи, статьи на пункты или части. Поскольку нашей целью является написание хоть и "игрушечного", но все же  текста напоминающего некий кодекс, мы так же для удобства ссылок на этот текст будем его делить (структурировать). Делить текст на главы, было бы в известной степени перебором, поэтому мы предпримем попытку деления его на параграфы в соответствии с выше указанными пунктами постановки содержательной задачи составления школьного расписания. Таким образом, ссылаться на отдельные положения текста, можно будет указывав через точку набор цифр. Например 7.2.4 будет означать - параграф 7, пункт 2, часть 4.

 § 1

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

  1. Ученики (классы);
  2. Учителя;
  3. Администрация школы (директор, завуч, охрана, другие заинтересованные лица);
  4. Сторонние потребители (в том числе проверяющие и контролирующие организации).

ПРИМЕЧАНИЕ 1: Сторонних потребителей, по всей видимости, может интересовать вопрос о качестве расписания по которому работает общеобразовательное учреждение. Может интересовать соответствие составленного расписания санитарным правилам и нормам. В частности, например, соблюдение дневных и недельных кривых умственной работоспособности обучающихся. Однако это не помешает и администрации школы, и родителям, пользоваться построенными соответствующими таблицами в различных целях. Содержание и форма таких таблиц, должна быть приспособлена (соответствовать пожеланиям) для простого и ясного восприятия соответствующими потребителями, содержащейся в них информации.

ПРИМЕЧАНИЕ 2: Наиболее интересным вопросом, если в данном контексте вообще уместно употребление слова интересный, является то, каким образом в расписании следует отражать различные объединения / разъединения классов, о которых речь пойдет далее.

 § 2

Стратегия (общие принципы, политика, общие правила) составления расписания школьных занятий (школьного расписания) заключается в том, что:

  1. Каждое требование к расписанию должно быть обоснованным. Обоснование может быть логическим, математическим, юридическим, подтвержденным многолетней практикой (здравым смыслом). Недопустимы требования к школьному расписанию, являющиеся плодом бесплодных фантазий, обличенные в наукообразную или эмоциональную форму. Каждое требование должно быть ясным и конкретным;
  2. При составлении расписания уроков в образовательном учреждении, а так же при распределении учебной нагрузки между преподавателями, недопустимо учитывать не столько интересы учащихся, сколько интересы учителей. То есть, интересы учащихся следует считать более приоритетными по сравнению с интересами учителей если они противоречат друг другу (не совпадают);
  3. Кроме того, интересы учителей, работающих по совместительству, имеют больший приоритет чем интересы учителей являющихся штатными работниками школы. То есть, в первую очередь следует заботиться о совместителях, при условии, что их интересы не противоречат и интересам учеников;
  4. Недопустимо стимулирование или поощрение работы педагогов (учителей), путем установления кому либо из них, наиболее удобного графика работы (удобного расписания) по сравнению с другими педагогами (учителями);
  5. Недопустимо стимулирование или поощрение работы педагогов (учителей), возможностью выбора учебной нагрузки (обучаемых классов), при этом каждый педагог (учитель) проводит занятия по тому предмету, по которому имеет соответствующую подготовку (квалификацию);
  6. Недопустимо стимулирование или поощрение работы педагогов (учителей), предоставляя им привилегии по сравнению с другими педагогами, с помощью каких-либо других способов (приемов), относящихся к составлению расписания, в том числе и на заслуженных (справедливых) основаниях;
  7. Недопустимо улучшать (выделять, в первую очередь заботиться) условия преподавания по какому-либо одному или нескольким предметам, за счет ухудшения условий преподавания по другим предметам, в том числе, если такая ситуация возникает и по объективным обстоятельствам (причинам), например, из-за нехватки учебных помещений или отсутствия нужного педагога (преподавателя, учителя), в том числе штатного;
  8. Следует признать то обстоятельство (согласиться с тем), что расчет расписания с помощью компьютера позволит, с одной стороны, исключить субъективные оценки и личные симпатии завуча по отношению к учителю (части учителей), при составления расписания, в том числе и при распределении педагогической нагрузки, а с другой стороны, позволит полностью исключить незаслуженные обвинения в адрес завуча со стороны учителей, в таких субъективных оценках и симпатиях, поскольку очевидно, что компьютер "лицо не заинтересованное" (во всем "виноват" компьютер). Тем самым, расчет расписания на компьютере, может улучшить психологический климат в учительском коллективе (соблюсти принципы справедливости и равноправия).

ПРИМЕЧАНИЕ 1: Принято считать, что задача составления расписания школьных занятий является, так называемой, целочисленной задачей многокритериальной оптимизации. В связи с этим актуален вопрос не только о формальном (математическом) подходе, но и о "политическом", отражающим накопленный опыт, отвечающий здравому смыслу и интуиции. Это и вынуждает решать некоторые не математические вопросы, которые можно было бы назвать "политические" (стратегические, общие), что называется "на берегу" ("до ухода в плавание", до начала составления расписания). Не подлежит сомнению тот факт, что стратегия составления школьного расписания является наиболее дискуссионной частью задуманного кодекса. 

ПРИМЕЧАНИЕ 2: Рассуждая по поводу ясности и конкретности, а так же наукообразия, приведем в качестве примера, следующий текст:

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

Какую функцию имеет в виду автор? Я этот текст, понять не могу, кроме того, что ни одна программа такой функции не имеет.

 § 3

Общие требования ко всему расписанию в целом, можно, как один из вариантов, представить следующим образом:

  1. Относящиеся к работе всей школы (образовательного учреждения):
    1. Формируемое расписание создается на одну учебную неделю или две учебные недели, с совершенно разными расписаниями для каждой из этих двух недель. Может быть создано расписание на одну неделю, но с указанием в некоторых местах расписания (уроках) сведений о четности недели. Например, в среду, четверным уроком, по четным неделям - история театра, по нечетным - история религии. Далее полученное расписание используется необходимый период времени в работе всей школы (четверть, полугодие, семестр и т.п.);
    2. Длительность учебной недели для всех классов (для всей школы) составляет 5 или 6 учебных дней. Допустимы так же различные сочетания, например, когда старшая школа задействована 6 рабочих дней, а основная и младшая - 5. Для некоторых учебных заведений (организаций) может быть предусмотрена 7-ми или 4-х (3-х, 2-х) дневная учебная неделя;
    3. Работа школы организована в одну или более (до трех) смен;
    4. Временной единицей (моментом времени) при составлении расписания является урок или пара.
  2. Относящиеся к учителям:
    1. За учителями могут быть закреплены кабинеты (один учитель ответственный за один кабинет);
    2. На учителя может быть возложено классное руководство (один учитель - один класс);
    3. Преподавательский (учительский) состав может быть разделен (а может быть и не разделен) различными способами, например, на преподающих для второй ступени обучения и третьей ступени обучения, на преподавателей дневной и вечерней форм обучения и т.п.
  3. Относящиеся к ученикам:
    1. Объем образовательной максимально допустимой нагрузки для учеников должен соответствовать гигиеническим требованиям. Часы факультативных, групповых и индивидуальных занятий должны входить в объем максимально допустимой нагрузки;
    2. Перерывы между уроками (занятиями) и длительность занятий (уроков) устанавливается в соответствии с гигиеническими требованиями;
  4. Относящиеся к факультативным занятиям:
    1. Расписание уроков составляется отдельно для обязательных и факультативных занятий;
    2. Факультативные занятия проводятся после обязательных;
    3. Факультативные занятия следует планировать на дни с наименьшим количеством обязательных уроков;
  5. Относящиеся к формам обучения:
    1. Расписание должно быть построено с учетом разнообразных форм обучения (специфики расписания): средние (дневные и верчение) общеобразовательные школы, лицеи, гимназии, училища, колледжи, интернаты, курсы повышения квалификации и т.п.
  6. Относящиеся к распределению педагогической нагрузки:
    1. Распределение педагогической нагрузки, т.е. общее количество часов оплачиваемой педагогической (преподавательской) работы в неделю (две недели), между работниками школы на новый учебный год, осуществляется в соответствии с действующим законодательством (правовыми нормами), при этом:
      1. Такое распределение должно существовать;
      2. Такое распределение не должно нарушать требований, предъявляемых к расписанию.
    2. Основой распределения педагогической нагрузки, а тем самым и школьного расписания, является учебный план школы, общепринятой (утвержденной) формы и содержания.
    3. По общему правилу у педагогов при распределении учебной нагрузки на новый учебный год должна сохраняться преемственность классов и объем учебной нагрузки, установленные в предыдущем учебном году.

ПРИМЕЧАНИЕ: Пожалуй, что самым "туманным" местом во сем этом списке являются требования, относящиеся к распределению педагогической нагрузки. Основной причиной такого "тумана" является ссылка нашего "игрушечного" кодекса о школьном расписании на настоящий Трудовой Кодекс РФ. Безусловно, вопрос распределения педагогической нагрузки требует тщательного и подробного рассмотрения. Тем более, что, так называемая, таблица распределения педагогической нагрузки, является основной структурой данных, при решении задачи составления школьного расписания. Подробное обсуждение данного вопроса будет предпринято в разделе статьи, посвященной перечню исходных данных для формирования расписания.

 § 4

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

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

ПРИМЕЧАНИЕ: В связи с отсутствием в настоящее время удовлетворительно построенной математической теории решаемой задачи, вопрос о полноте данного списка остается открытым. Однако руководствуясь здравым смыслом, интуицией и правдоподобными рассуждениями можно с уверенностью утверждать, что представленный список является далеко не полным.

 § 5

Базовое требование относится ко всему расписанию в целом (ко всем его "участникам") и формулируется следующим образом:

Другими словами, базовое требование представляет из себя одновременное выполнение трех условий, с учетом одного исключения (случаев объединения / разъединения классов, перечисленных (описанных) ниже):

  1. Ни один класс, в одно и тоже время, не может находится более чем на одном уроке, с одним учителем, в одном кабинете;
  2. Ни один учитель, в одно и тоже время, не может проводить какой-либо урок более чем у одного класса, в одном кабинете; 
  3. Ни в одном учебном помещении (учебной аудитории, кабинете) не может проводиться более одного урока для одного класса с одним учителем.

ПРИМЕЧАНИЕ 1: Базовое требование является пожалуй единственной частью содержательной постановки задачи, которая не вызывает дискуссий и споров, как среди математиков (программистов), занимающихся данной задачей, так и среди потенциальных пользователей соответствующих программ (систем составления расписания школьных занятий). Объясняется это по видимому тем, что это требование, в общем-то и требованием можно назвать с некоторой натяжкой, поскольку представляет из себя, не что иное как собственно задачу (ее фундамент, суть задачи) составления школьного расписания, правда с дополнительными ограничениями (условиями, требованиями) к основной задаче.

ПРИМЕЧАНИЕ 2: Введение исключения в общее правило - один учитель, один класс, один кабинет, несколько "затуманивает" довольно понятное и простое базовое требование. Чуть-чуть подробнее об этом будет сказано в следующем параграфе.

 § 6

Безусловные требования состоят из:

  1. Относящихся ко всему расписанию в целом (ко всем "участникам" расписания).
    1. Все ученики (учащиеся, обучаемые) делятся в зависимости от года обучения на параллели. Параллели делятся на классы. Классы могут делиться на группы.
    2. В ходе процесса обучения допускаются все возможные виды объединений (слияний) и разделения (разбиений) классов:
      1. В один и тот же момент времени (в один и тот же урок);
        1. Для обучения по некоторым предметам классы могут делится на группы, при этом в каждой группе урок (занятие), в разных кабинетах, проводит один (свой) учитель;
        2. Из нескольких классов, может быть сформировано несколько (другое количество) групп, в каждой из которых занятие, в разных кабинетах, ведет свой (один) учитель. Например, из двух классов может быть "вперемешку" сформировано три группы для изучения профильных дисциплин;
        3. Для обучения по некоторым предметам классы могут объединятся в потоки, при этом один учитель проводит урок (занятие) для всего потока, в одном помещении (аудитории). Примером для средних общеобразовательных школ данной ситуации может служить - коллективное посещение плавательного бассейна;
        4. Класс может быть разделен на группы для изучения какого-либо предмета, в одном кабинете (помещении) с несколькими учителями (каждому учителю - своя группа).
      2. В разные моменты времени (в разные уроки);
        1. Для проведения некоторых предметов классы могут делиться на группы, при этом в каждой группе преподает один (свой) учитель (возможно один и тот же учитель, возможно в разных кабинетах, возможно в том же кабинете).
    3. Для некоторых классов может быть предусмотрен день для обучения в другом месте (в учебно-производственном комбинате - в УПК).
  2. Относящихся к классам.
    1. Занятия во всех классах школы, обучающихся в первую смену, начинаются с первого урока;
    2. Если работа школы организована более чем в одну смену, то выпускные (9-е и 11-е) классы занимаются только в первую смену, при этом уроки 1-й и 2-й смен максимально сближаются;
    3. У классов в расписании не может быть пустых (не занятых полезными действиями) уроков, стоящих в расписании между какими-либо занятиями (уроками) этих классов. Другими словами, не может быть, так называемых, "окон" в расписании занятий;
    4. У классов в течение дня может быть заранее запланированный общий или скользящий (для каждого класса свой, т.е. определенный в индивидуальное время) перерыв в обучении, например, для обеда или перехода в другое здание.
  3. Относящиеся к программе.
    1. Все случаи объединения / разъединения классов и назначения плановых перерывов в занятиях учащихся, должны быть заранее "указаны" (поставлены в сетку расписания) программе, т.е. фактически являться исходными данными к расчету школьного расписания.

ПРИМЕЧАНИЕ: На первый взгляд может показаться, что требование 6.1.2, относящееся ко всему расписанию в целом, плохо (непонятно) согласуется с базовым требованием. Действительно, основой базового требования является "единственность триады" - один класс, один учитель, одна аудитория. Не хотелось бы здесь углубляться в математические (алгоритмические, логические, построения внутренних структур данных) тонкости данного вопроса, отметим лишь только то, что данное противоречие ("туман") разрешается на достаточно глубоком (скрытым от глаз пользователя) уровне. Для того, что бы чуть-чуть развеять завесу таинственности приведем только лишь одни пример, пользуясь методом "правдоподобных рассуждений". 

Предположим, что нам нужно реализовать требование 6.1.2.3, т.е. провести для некоторого количества классов, например, параллели, лекционное занятие с одним учителем в одной аудитории, в среду, третьим уроком. Для этого мы, а точнее программа (пользователь об этом даже и не узнает), поступит следующим образом. Сначала программа назначит в среду, третьим уроком, для каждого класса (всей параллели) - "окно", и составит расписание с такими "окнами". При этом программа для данного момента времени (данного урока) исключит из рассмотрения нужного учителя (нет его в школе).  Сделать ей это (составить расписание с "окнами" для всех классов параллели, и исключить из расчета учителя), проще "пареной репы". Причем сделает она это (составит расписание) в точном соответствии с концепцией - один класс, один учитель, одна аудитория. Далее, после получения расписания, программа "скажет": - "Вот в это "окно" вся параллель (все классы) и соберутся в такой-то аудитории, с таким-то (ранее исключенным из рассмотрения) учителем". Таким образом, нам удалось при помощи не хитрого приемчика "обмануть" глупую программу ("главный вычислитель"), которая тупо воспринимает задачу только для исходных данных соответствующих концепции - одни класс, один учитель, одна аудитория. Другими словами, речь идет о преобразовании на внутреннем уровне, скрытом от глаз пользователя, "неправильных" исходных данных в "правильные". Ясно, что исходные данные кажутся "неправильными" для программы (алгоритма, "главного решателя"), а для пользователя, они-то как раз наоборот, являются "правильными". Ну и наконец отметим то, что конечному пользователю знать о таких "не хитрых" приемчиках, в общем-то не обязательно. Хотя и вреда, от такого знания, никакого не будет, разве что немножко ухудшится сон, поскольку меньше знаешь - лучше спишь.

 § 7

Жесткие требования определены:

  1. Для классов.
    1. У каждого класса не может быть в какой-либо день двух одинаковых уроков, не считая сдвоенных (специально заданных, отмеченных, выделенных);
    2. Занятия у классов по любому предмету, должны проходить в специально оборудованных для проведения этого предмета учебных помещениях или местах (кабинетах, мастерских, залах, площадках и т.п.).
  2. Для учителей.
    1. У каждого учителя, являющегося штатным работником школы для которой создается расписание, в неделю должен быть хотя бы один свободный (выходной) день, не считая воскресенья, который не задается (определяется, назначается) учителем, а вычисляется (определяется, рассчитывается) внутренним алгоритмом программы формирования расписания;
    2. В течение рабочего (учебного) дня у учителя должен быть перерыв для отдыха и питания, время наступления и длительность которого определяется программным путем (внутренним алгоритмом);
    3. Учитель, для проведении урока в закрепленном за ним учебном помещении, имеет приоритет по сравнению с другими учителями. 

ПРИМЕЧАНИЕ: В том случае, если у какого-либо класса недельная учебная нагрузка превышает количество учебных дней по которой работает школа, то тогда с целью "обхода" жесткого требования о не повторяемости урока в любой из учебных дней, следует указать разбиение (разложение на части) данной учебной нагрузки. Например, нагрузку в 8 часов можно представить как 6+2, или 5+3, или 4+4. При этом программа (для себя, с точки зрения ее внутренних структур данных) будет воспринимать данную нагрузку как два разных предмета с тем же учителем. Пользователь же об этом, даже и не  узнает, не считая того, что в расписании в какие-то дни появятся повторяющиеся уроки, и будет воспринимать данную нагрузку как один предмет. В данном случае, речь так же идет об "умелом" преобразовании "неправильных" исходных данных в "правильные".

 § 8

Мягкие требования, так же определены:

  1. Для классов.
    1. Предметы (уроки) естественно-математического и гуманитарного циклов должны чередоваться в течение дня;
    2. Проведение каждого предмета (урока) должно быть равномерно (разумно) распределено в течение недели;
    3. Расписание уроков строится с учетом хода дневной и недельной кривой умственной работоспособности обучающихся.
  2. Для учителей.
    1. В расписании учителей количество "окон" должно быть минимальным;
    2. Рабочая неделя учителя (совокупность рабочих дней в неделе) должна быть равномерно загружена проводимыми уроками;
    3. Нельзя составлять расписание по которому в какой-либо день учитель должен провести только один урок (занятие), за исключением тех экзотических случаев когда, например, совместитель (лектор) имеет всего один час в неделю или два часа, которые не должны проводиться в одни день;
    4. Учителям с небольшой учебной нагрузкой, являющихся штатными работниками школы для которой создается расписание, может быть предоставлено более одного свободного (выходного) дня  в неделю, не считая воскресенья, которые так же определяются программно, тем самым не создавая препятствий для заработков "на стороне" (совместительству);
    5. Для учителей работающих (преподающих) по совместительству в школе, для которой создается расписание занятий, рабочие (учебные) дни могут быть жестко назначены (указаны), при составлении расписания занятий этой школы;
    6. Некоторым учителям, по уважительной причине, может быть предоставлена возможность начинать занятия (являться на работу) со второго урока. (Хрестоматийный случай - нужно успеть отвести ребенка в детский сад).

ПРИМЕЧАНИЕ 1: Мягкие требования являются пожалуй самой "зыбкой" (неопределенной, подверженной дискуссиям) частью содержательной постановки задачи составления школьного расписания. Нет ни одного автора, который бы не изложил свою точку зрения (свое мнение) по данному вопросу, далее непременно отмечая, что по данному вопросу нет единства суждений, и более того, такие требования могут быть изменены в силу "специфики" отдельно взятого общеобразовательного учреждения. Что ж, автор тоже "держит нос по ветру". Пожалуйте-ка вам, еще один вариантик (будьте так любезны).

ПРИМЕЧАНИЕ 2: Достаточно распространенным требованием к школьному расписанию, которое можно было бы отнести к мягким требованиям является, так называемое - выдерживание параллелей. Имеется ввиду расписание в соответствии с которым какому-либо учителю (учителям), в некоторый день (дни) приходится вести уроки в одной параллеле. Например, первым уроком идет 5-А, вторым 5-Б, третьим 5-В и так далее. Как свидетельствует практика, данное требование является весьма распространенным и довольно настойчиво проводится в жизнь. Более того, в одной из программ по составлению школьного расписания, требование - выдерживать параллели, появилось в виде следующей (усовершенствованной, более продвинутой) версии. Следовательно на разработчика было оказано, если уместно такое выражение, определенное давление (сформулирована задача с пожеланиями ее незамедлительной реализации). По мнению автора, обсуждаемое требование является не чем иным, как подсознательным или совершенно сознательным (умышленным) желанием учителя обеспечить себе отсутствие "окон" в расписании, увеличить для себя количество свободных (выходных) дней, а так же облегчить домашнюю подготовку к рабочему (учебному) дню под видом методико-педагогической целесообразности. На сегодняшний момент достаточно трудно доказать математически, но на интуитивном уровне, человеку хорошо знакомому с математическими методами составления школьного расписания, вполне очевидно, что выполнение такого требования для одного учителя, можно обеспечить только лишь за счет ухудшения расписания (условий труда) другого учителя (коллеги). А именно - увеличение "окон" в расписании, отсутствие свободных (выходных) дней и т.п. Для учеников же, никакой пользы от выдерживания параллелей не видно. Поэтому, по мнению автора, требование - выдерживать параллели не может быть включено в постановку (реализацию) задачи о составлении школьного расписания, как вредное, ухудшающее расписание и создающее напряженную обстановку в школьном коллективе (между учителями).

Справедливости ради, следует отметить, что такой вывод вызывает бурную реакцию негодования у учителей. Они предлагают поставить вопрос по другому - а хуже будет ученикам, если для преподавателей будет соблюдаться правило выдерживания параллелей? Так почему же при отсутствии вреда для учеников не позаботиться о пользе для учителя, хотя бы на столько на сколько это возможно не ухудшая условий работы коллег. Таким образом данный вопрос можно считать "открытым" для дискуссии. Учителя голосуют за правило выдерживания параллелей.

ПРИМЕЧАНИЕ 3: Еще одно требование, которое встречается в большинстве работ (статей, руководств пользователя, рекламных материалов) посвященных сравнению программ по составлению школьного расписания и которое можно было бы отнести к мягким требованиям, это, так называемое, закрепление уроков. Имеется в виду, что пользователь может "указать программе", например, провести урок русского языка в 7-В классе, четвертым уроком, в среду. Таким образом, закрепление урока фактически является частью исходных данных к расчету расписания. Что интересно, наличие такой функции выдается за достоинство программы. То есть, программы которые не могут обеспечить такого закрепления (таких закреплений) это плохие программы, а которые могут - хорошие (продвинутые) программы. У автора данного текста, который вы сейчас читаете, проще говоря у меня, не хватило собственной фантазии, что бы придумать ситуацию при которой может понадобиться такое закрепление. Иными словами, зачем закреплять? После долгих и мучительных поисков в различных источниках посвященных рассматриваемой задаче, все же удалось найти несколько мнений на этот счет.

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

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

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

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

Следует обратить внимание на то, что в этом отрывке ничего не сказано о том, что с вероятностью 99.9% программа в ходе описанного алгоритма должна выдавать сообщение: - "Не могу расставить всю учебную нагрузку. Оставшиеся 3-5% не расставленных уроков, расставьте сами. Измените исходные данные и повторите расчет заново". Или что-нибудь в этом роде. Не сказано так же и то, что программа настолько хороша, что можно повторять эту процедуру (созерцать на экране: - "Не могу расставить всю учебную нагрузку ...") совершенно не ограниченное число раз, вплоть до полного морального или физического износа компьютера. Но для нас сейчас, это не важно! Важно то, что необходимость закрепления уроков выдается за возможность такого закрепления. Не нужно быть очень умным, что бы понять - закрепление уроков в данном (выше приведенном) случае является частью технологического (алгоритмического) процесса составления школьного расписания.

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

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

Вот еще одно мнение, высказанное правда, в ходе дискуссии.

Более серьезное возражение состоит в том, что расписание это не плод решения математической задачи. Расписание - это управленческое решение, а решение математической задачи - лишь этап в формировании этого решения. Поэтому принимающий это решение руководитель должен иметь полный контроль над расписанием, вплоть до полностью ручного его составления. Это его решение, а не программы. Он за него отвечает. Никакие отмазки "так копм сосчитал" не проходят. Каким способом получено решение не имеет ни какого значения. Важно каково оно. А ручное составление, это и есть, по существу, цепочка последовательных закреплений. Директор сказал: - "Поставь мои уроки туда и туда". Что будете делать без закрепления?

Ну то, что ученики ходят в школу для того что бы директору хорошо работалось, а так же для того, что бы ему хорошо елось и пилося, хотелось и моглося, всем известно. Что же касается того, что цепочка последовательных закреплений по существу и есть - ручное составление расписания, тут я согласен на все сто процентов. А действительно, зачем программы то применять? Составляли ведь расписание без этих компьютеров, и нечего. Какое поколение вырастили! Может действительно - ну их к Лешиму?

И на конец, приведем еще одно мнение:

... которые прибавят комфортность работе программы ...

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

Как-то еще в студенческие годы, мне довелось прочитать в одной переводной книжке, посвященной проектированию технических систем, теперь уже не помню, ни названия, ни автора довольно интересное высказывание. Высказывание это примерно такое (не дословно, по памяти). Разные люди обладают разным кругозором. У некоторых людей кругозор чрезвычайно широкий и его можно представить в виде линии горизонта. У других он достаточно узкий и их кругозор можно представить в виде отрезка горизонта. У третьих он совсем маленький и стягивается в точку. Тогда человек говорит: - "Это моя точка зрения".

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

 § 9

Общие требования к программе (алгоритму) решения задачи составления расписания школьных занятий и последовательность работы по составлению расписания сводятся к следующему:

  1. Требования носящие принципиальный характер:
    1. Программа (алгоритм) должна представлять из себя полностью автоматизированную систему составления расписания, позволяющую без участия человека (пользователя) строить готовое для применения в учебном процессе расписание;
    2. Программа должна в автоматическом режиме устранять (обходить, игнорировать) ограничения введенные пользователем, только в том случае, если они приводят к не существованию решения задачи, информируя о таких устранениях пользователя после завершения расчета (составления) расписания, например, выдавая список произведенных обходов;
    3. Готовое расписание с целью его локального улучшения, но не переделки заново, может быть отредактировано в ручном режиме. При этом программа во время редактирования расписания должна обеспечивать в автоматическом режиме проверку на допустимость (соблюдение всех требований) отредактированного расписания;
    4. Отдельной функцией (возможностью) программы должно быть - планирование педагогических советов, методических объединений и т.п., поскольку в школе с большим количеством педагогов, не так то просто выбрать день или какие-либо дни, в которые все педагоги находились бы (присутствовали) в школе.
  2. Требования носящие технический характер:
    1. Программа должна обеспечивать поиск ошибок в исходных данных введенных пользователем, которые возможно найти до начала решения задачи, по типу компилятора;
    2. Программа должна иметь встроенную контекстную справочную систему, но, что более важно, программа должна иметь хорошее, на сколько позволят творческие силы ее авторов (создателей, проектировщиков), руководство пользователя (учебник), изданный (изготовленный) в виде печатного (бумажного или с возможностью получения твердой копии) текста с иллюстрациями (картинками, графиками, диаграммами и т.п.);
    3. Программа должна поддерживать архив, в котором могут храниться, как готовые расписания за предыдущее время использования со своими исходными данными, так и варианты решения текущей задачи.

ПРИМЕЧАНИЕ 1: Удовлетворительная реализация всех без исключения перечисленных требований является далеко не тривиальным вопросом. Прежде всего это связано с отсутствуем в настоящий момент удовлетворительно построенной (достаточно полной и точной) математической теории задачи о составлении расписания школьных занятий. В частности остается открытым вопрос о необходимых и достаточных условиях существования решения задачи, вопрос полноты исходных данных. Требует так же своей глубокой проработки вопрос о понятии - редактирования расписания. Какие именно действия (операции) можно признать редактирующими расписание? Соблюдение каких условий обеспечивает сохранение допустимости расписания при его редактировании? И этот, далеко не полный список вопросов, можно было бы продолжать достаточно долго. Будем надеяться, что в недалеком будущем поставленные вопросы будут успешно разрешены. В настоящий же момент приходится довольствоваться вычислительным экспериментом и правдоподобными рассуждениями, что вообще говоря не помешает пользователям решать стоящие перед ними задачи. Известно, что чистые математики работают над вопросами которыми можно заниматься и делают это как нужно, а прикладные, вопросами которыми нужно заниматься и делают это как можно.

ПРИМЕЧАНИЕ 2: На первый взгляд может показаться, что требования 9.1.1 и 9.1.3 (общих требований, предъявляемых к программе) противоречат друг другу. Действительно, если программа полностью в автоматическом режиме составляет школьное расписание, причем без всякого участия человека (пользователя), и составленное таким образом расписание годится для использования в учебном процессе, то зачем полученное расписание редактировать в ручном режиме. Не ужели, завучу при его колоссальной загруженности методической работой больше не чем заняться? Собственно говоря, вся "затея" с автоматизацией составления школьного расписания и нацелена на то, что бы завуча полностью избавить от "ручного комбинирования" (другими словами - исключить такое "комбинирование"). Безусловно, некоторая "логика" в данном рассуждении имеется. Однако, как представляется, сколь бы подробно мы не ставили задачу, учесть все ограничения (требования, пожелания), абсолютно в полном объеме, не представляется возможным. Тем более, что часть требований, вполне разумных, содержательных и наполненных здравым смыслом, очень трудно формализовать или предвидеть заранее. Эти требования не будут (не могут быть) "известны" программе. То есть, программа не будет (не может) их учитывать.

Представим себе такую ситуацию. Завуч в автоматическом режиме составил расписание. Начинает его изучать (оценивать). И вдруг обнаруживает, что составленное расписание содержит "видимый не вооруженным глазом" дефект. Причем, что самое интересное, этот дефект, с формальной точки зрения, дефектом не является. Абсолютно все требования, которые "известны" программе, выполнены. Однако не смотря на формальное выполнение всех требований к расписанию, завуч уверен (убежден), что имеет дело с дефектом. Что делать? Здесь возможны, как говорят в Одессе: - "Две большие разницы". Первая заключается в том, что пользователь (наш завуч) не знает как имеющийся дефект исправить. Напрашивается вариант - пусть исправит компьютер. Но для этого как минимум, нужно сообщить компьютеру о имеющемся дефекте. А как это сделать? Думаю, что пытаясь ответить на этот вопрос, можно написать не одну толстенную книжку, чего сейчас мы делать не будем. Так что в реальности, скорее всего, полученное расписание будет использоваться с имеющимся дефектом. Вторая же "разница" заключается в том, что решение обнаруженной проблемы лежит на  поверхности. "Это" с "этим" переставить, а "то" отодвинуть, и нет дефекта. Так почему же нашему завучу, не предоставить такую возможность? А вот ответ на этот вопрос, представляется чрезвычайно простым и легким - такую возможность нужно предоставить.

Другое дело, что под предлогом неизбежного возникновения подобных ситуаций, нельзя (просто неприлично и стыдно) объявлять имеющуюся возможность составления расписания в полностью автоматическом режиме, пусть даже не имеющую строгого теоретического обоснования - абсурдом. Что называется, переворачивать вопрос с ног на голову. Выплескивать ребенка... И все такое... Что там еще, писал старик Маркс по этому поводу в письмах старику Энгельсу. Таким образом, выше указанные требования к программе (системе составления школьного расписания), не противоречат друг другу, а взаимно дополняют друг друга.

ПРИМЕЧАНИЕ 3: Полностью автоматизированный расчет школьного расписания без участия человека (пользователя), важное необходимое условие использования программы для организации учебного процесса, но не достаточное. Немаловажное значение для продуктивного использования программы, является разумное (незначительное) время расчета (составления) расписания. Действительно, трудно себе представить, что программа составляющая даже идеальное расписание, но при этом составляющая его в течение месяца будет практически пригодна. Сомнения в возможности расчета расписания за разумное время порождает то обстоятельство, что даже быстрые алгоритмы имеют, так называемую, полиномиальную временную сложность. Другими словами при увеличении размерности задачи (для разных алгоритмов размерность задачи определяет разная величина, в нашем же случае это количество классов) в два раза, время расчета может увеличиваться в десять и более раз.

Последние три с половиной года, в круг интересов автора данного текста входили задачи весьма похожие (близкие) на задачу составления школьного расписания. Как правило, это задачи из области расчета расписаний для промышленных предприятий занимающихся различными видами деятельности. Среди них можно назвать, например, такие как: расчет графиков персонала поточной линии, при организации работы в многосменном режиме;  расчет расписания выхода на работу кассиров в крупном гипермаркете; расчет расписания выхода на работу сотрудников различных центров обслуживания, имеющих ярко выраженные суточные, недельные и сезонные колебания потока заявок на обслуживание; расчет скользящего графика выхода на работу локомотивных бригад. Задача расчета школьного расписания, безусловно представляет интерес для любого любознательного человека, однако в связи с низким платежеспособным спросом у нас в стране, до этой задачи (программы, системы), все как-то, не доходили руки. Но август месяц, как известно - месяц отпусков. И автор данного текста, решив воспользоваться данным обстоятельством, задался целью (любопытство одолело): во-первых "померить" имеющуюся библиотеку алгоритмов на задачу расчета школьного расписания, и во-вторых определить каким образом время расчета задачи будет изменяться с увеличением ее размерности. Не могу сказать, что задача расчета школьного расписания оказалась решаемой за одни день, не даром некоторые ее называют весьма "крепким орешком", но тем не менее, имеющуюся библиотеку алгоритмов, не без некоторых усилий, удалось приспособить для ее решения. Естественно, что в результате решения задачи удовлетворялось базовое требование, все жесткие требования и абсолютное большинство мягких требований, перечисленных в данной статье. Некоторые мягкие требования не были приняты во внимание поскольку было совершенно очевидным то, что их удовлетворение является не более чем техническом вопросом и не оказывает никакого влияния на время расчета расписания.

Поскольку речь идет о вычислительном эксперименте, нужно было написать генератор исходных (тестовых) данных. Для этого в программу был "зашит" типовой учебный план школы. Далее для каждой задачи (экземпляра исходных данных) выбиралось некоторое количество классов с вариацией, определяемой случайным образом, по количеству классов в каждой параллели. Например, для каждой параллели количество классов выбиралось от 1 до 3, итого общее количество классов от 7 до 21 (брались классы с 5-го по 11-й). Далее количество классов в параллеле от 2 до 4, итого общее количество от 14 до 28. Следующая размерность: в параллеле от 3 до 5, общее количество от 21 до 35. И так далее. При этом, в каждом случае, на основе имеющегося ("зашитого") типового учебного плана и полученного количества классов, по вполне правдоподобному алгоритму, имитирующему действия директора школы по найму на работу учителей, задавалось их количество и специализация, из расчета 18-ти часовой недельной нагрузки для каждого учителя. Кроме того, так же по вполне правдоподобному алгоритму, имитирующему действия завуча, распределялась педагогическая нагрузка среди имеющихся учителей. На этом генерация исходных данных для каждой задачи заканчивалась. Всего каждая типовая размерность имеет 2187 вариантов (это три в седьмой степени). Поскольку генерируемое число классов подчиняется нормальному (в смысле теории вероятностей) распределению, то для полной уверенности, что было построено расписание для любого варианта (всех возможных комбинаций) тестовой задачи, вычислительный эксперимент (расчет) прекращался тогда, когда число решенных задач превышало примерно 22 тысячи.

Полученные результаты представлены в следующей таблице.

Количество классов в параллеле Число решенных задач Время расчета Среднее время на одну задачу
1 - 3 22116 9 м. 40 сек. 0.026 сек.
2 - 4 22030  19 м. 49 сек. 0.054 сек.
3 - 5 28851 1 ч. 09 мин. 0.14 сек.
4 - 6 26640 1 ч. 30 мин. 0.20 сек.1
5 - 7 16884 1 ч. 39 мин.  0.35 сек.
6 - 8 20196 2 ч. 57 мин. 0.53 сек.
7 - 9 33792  10 ч. 49 мин. 1.15 сек.
8 - 10 27261  18 ч. 10 мин. 2.4 сек.
9 - 11 29383 16 ч. 44 мин. 2.05 сек.2
10 - 12 31375  34 ч. 29 мин. 3.96 сек.
11 - 13 10057  55 ч. 16 мин. 19.8 сек.
12 - 14 2917 116 ч.16 мин. 2 м. 23 сек.3
  1. максимальное время счета задач такой размерности, может отличаться от минимального, до одного порядка, т.е. в 10 раз;  
  2. максимальное время счета задач такой размерности, может отличаться от минимального (не среднего!), до двух порядков, т.е. в 100 раз;
  3. максимальное время счета задач такой размерности, может отличаться от минимального (не среднего!), до трех порядков, т.е. в 1000 раз.

Как видно из представленной таблицы и сносок к этой таблице, все волнения (опасения) по поводу решения задачи построения школьного расписания за разумное время счета, оказались напрасными. Компьютер для экспериментов использовался самый, что ни на есть простенький: Intel Celeron 3 Ггц., RAM DDR-400. Задачи превышающие размерность по количеству классов в параллеле от 4 до 6, решались только ради спортивного интереса, поскольку реальных школ с таким количеством классов не бывает. Правда последнее утверждение может оказаться несколько наивным (упрощающем ситуацию). Некоторые специализированные средние учебные заведения (типа школы) не проводят обучение в начальной школе и за счет этого количество классов второй и третьей ступеней обучения является довольно значительным. Некоторые такие средние учебные заведения располагают даже несколькими зданиями, что конечно характерно в первую очередь для высшей школы (ВУЗов, университетов). Кроме того не следует забывать о средних специальных учебных заведениях (колледжах), не говоря уже о ВУЗах, количество учебных групп в которых может измеряться несколькими сотнями.

Пессимисты скажут, что от работающего алгоритма до программного обеспечения, отвечающего всем общепринятым требованиям, как "до Луны". Оптимисты скажут, что на то они и средства быстрой разработки программ (RAD - Rapid Application Development), что бы лепить программные системы, готовые к практическому использованию, как горячие пирожки. Автор данной статьи придерживается реалистической точки зрения - доработка системы построения школьного расписания потребует значительных, как финансовых, так и человеческих (временных) ресурсов, но принципиальная возможность создания такой системы продемонстрирована.

ПРИМЕЧАНИЕ 4: Следует отметить, что вопрос о разумном времени счета программы по составлению расписания не является столь очевидным и однозначным. Некоторые склонны не драматизировать ситуацию по поводу необходимости "мгновенного" расчета расписания. Аргументы здесь следующие. Некоторые завучи начинают составлять расписание на следующее полугодие с самого начала текущего полугодия, постепенно и не спеша согласовывая его ("утрясая") со всеми заинтересованными лицами. Таким образом, вяло текущий процесс окончательного составления расписания может растягиваться на долгие месяцы. И собственно, почему бы работая в таком не не спешном, другими словами "между делом" темпе не оставлять на ночь работающий компьютер перебирающий многие и многие миллиарды различных комбинаций. В конце концов, компьютер он же, как и паровоз - "железный", хлеба не просит, на усталость не жалуется.

Можно привести и другой аргумент в защиту "долго думающих" программ. Не так давно, в одном из Российских ВУЗов, прошла защита кандидатской диссертации, предметом которой являлись: 1) Структурные модели представления исходной информации для составления расписания; 2) Агрегированный алгоритм генетической оптимизации; 3) Интеллектуальный алгоритм определения коэффициентов важности частных критериев оптимальности расписания в условиях неопределенности. В качестве практической ценности диссертации, в частности было заявлено - разработанное программное обеспечение, реализующие предлагаемые алгоритмы генетической оптимизации применительно к решению задачи составления расписания в образовательных системах массового обучения. От себя заметим, что под образовательными системами массового обучения имеются в виду крупные ВУЗы. Так вот, в качестве достоинства предлагаемых алгоритмов было указано на существенное сокращение времени счета при составлении расписания по сравнению с программой уже используемой в том же ВУЗе. При этом важно то, что время расчета расписания было сокращено с 14 часов до 7 часов непрерывной работы современного (Pentium IY) компьютера. Одновременно было указано, что время ввода исходных данных для осуществления расчета расписания составляет около 7 рабочих дней "без отрывной" работы оператора. Таким образом, по сравнению с семью рабочими днями ручной работы по вводу исходных данных для начала осуществления расчета, время семь часов работы компьютера в автоматическом (без участия человека) режиме, не представляется таким уж длительным. Возражать против данного аргумента трудно, естественно при условии, что полученное таким образом расписание пригодно для непосредственного использования. Можно так же предположить, что время анализа (оценки человеком) и дальнейшее утверждение (в данном случае ректоратом) полученного расписания, составляет тоже весьма продолжительный период, по сравнению со временем его расчета.

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

ПРИМЕЧАНИЕ: Не нужно быть обладателем неистовой фантазии или располагать какими-либо выдающимися творческими способностями, что бы догадаться - после анализа полученного расписания (программа 3), можно в случае необходимости вернуться снова к программе ввода исходных данных (программа 1) и заняться коррекцией таких данных, например, изменить некоторые ограничения (требования отдельных участников расписания) или скорректировать таблицу распределения педагогической нагрузки. Однако результаты ручного редактирования расписания при этом пропадут, поскольку по убеждению автора (в силу его знаний и представлений о работе алгоритма составления расписания) программа не может (не должна) пользоваться какими-либо "черновыми" вариантами предварительно составленного расписания занятий "ручным" способом.

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

 § 10

Требования к коррекции расписания во время использования его в учебном процессе заключаются в том, что;

ПРИМЕЧАНИЕ 1: Вопрос по поводу условий существования замен и условий не нарушения требований, предъявляемых к расписанию, при таких заменах нуждается в подробном и достаточно глубоком изучении. Осложняет дело - отсутствие в настоящее время удовлетворительно построенной математической теории рассматриваемой задачи. 

ПРИМЕЧАНИЕ 2: Следует отметить, что задача коррекции расписания во время его использования хотя и является, вообще говоря, не сложной с алгоритмической точки зрения, но тем не менее является достаточно объемной с содержательной точки зрения и требующей подробного обсуждения. Неспроста некоторые разработчики программ по составлению школьного расписания выделяют подобную коррекцию в самостоятельный продукт имеющий свою (отдельную) цену.  Кроме того, не следует забывать о достаточно распространенной практике когда ученики при отсутствии заболевшего учителя приходят в школу, например, к третьему уроку, а покидают ее после пятого. Короче говоря, подробное обсуждение темы коррекции расписания или как часто ее называют - замен, выходит за рамки данной статьи и требует отдельного обсуждения. 

 § 11

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

  1. Формирование (составление) расписания различных консультаций и экзаменов в период их проведения;
  2. Программную поддержку разработки учебных планов;
  3. Разумно автоматизировать заполнение таблицы тарификации в ходе подготовки исходных данных для составления расписания;
  4. Можно в программе замен, предусмотреть функцию ведения табеля для расчета зарплаты учителям;
  5. В базу данных программы могут быть внесены статистические данные об учителях (возраст, адрес, стаж работы и т.п.);
  6. Кроме того, в базу данных программы могут быть внесены сведения о классах, например, количество учеников, а так же некоторые индивидуальные данные об учениках;
  7. В программу могут быть внесены сведения о времени проведения школьных звонков;
  8. Программа может иметь функцию авторизации пользователей, работающих с программой с дифференциацией прав доступа;
  9. Программа должна обеспечивать удобный способ пересылки сформированных исходных данных по сети Интернет с целью их удаленной коррекции, для проведения консультаций, оказания помощи и т.п.;
  10. В программе может быть реализована функция оперативного оповещения преподавателей об изменениях в их расписании посредством электронной почты или рассылки sms-сообщений.
  11. Следует предусмотреть такую возможность, что бы после составления расписания, оно могло бы быть опубликовано в виде html-страниц в локальной сети учебного заведения или на его Web-сайте;
  12. В программе может быть предусмотрена функция экспорта данных в различные популярные форматы - Excel, Word, XML, текстовый и т.п.;
  13. В программе может быть реализован многоязычный интерфейс пользователя.

ПРИМЕЧАНИЕ: Поскольку для реализации задач входящих в этот список кроме умения "немножко программировать" ничего не требуется, другими словами эти задачи чрезвычайно просты (или скажем так - задачи для грамотного инженера), а так же то, что перечисленные задачи, вообще говоря, к составлению школьного расписания занятий не относятся (не оказывают на него никакого влияния), мы ограничимся простым перечнем таких задач. Их подробное обсуждение, явно выходит за рамки рассматриваемой в этой статье темы.

 § 12

Итак, из двенадцати пунктов, относящихся к описанию задачи составления школьного расписания нами были освещены, с большей или меньшей степенью подробности, одиннадцать. Остался последний - перечень исходных данных для формирования (построения, составления) расписания. Однако немножко поразмыслив над данным вопросом, автор пришел к убеждению, что освещение последнего пункта (вопроса) может занять не меньше времени и места (страниц печатного текста) чем все выше изложенное в данной статье. Связано это прежде всего с тем, что центральное место в структуре данных для решения задачи составления школьного расписания, занимает, так называемая, таблица распределения педагогической нагрузка. Скажу больше. По мнению автора, составление (построение, формирование) такой таблицы представляет из себя, пусть и не сложную, как сама задача составления школьного расписания, но все же отдельную (самостоятельную) задачу. И не случайно, что это единственное место в содержательной постановке задачи о школьном расписании, которое регулируется действующим Федеральным законодательством. Простые вопросы на законодательном уровне не регулируются. Так что, придется отложить этот вопрос до следующей статьи. Надеюсь, что это произойдет в ближайшем будущем.

Осталось только завершить, уже написанную статью, финальным аккордом. Ну что ж. Автор наполнен, как говорили раньше (еще каких-нибудь лет двадцать пять назад) чувством глубокого удовлетворения. А что? Действительно - чувством глубокого удовлетворения. Переработаны горы словесной руды - не один десяток статей, несколько руководств пользователя, несколько книжек близких к рассматриваемой теме. Удалось более или менее внимательно ознакомиться с дюжиной демонстрационных программ. А вот, удалось ли автору воплотить на бумаге, цель поставленную до начала работы - краткое и компактное изложение в систематизированной форме требований к школьному расписанию (разработка "игрушечного" кодекса школьного расписания), судить не мене.

Как-то давным-давно, еще на заре нового российского капитализма, мне удалось услышать одно не бесспорное, но тем не менее, интересное суждение. Несколько лет я тогда работал, что называется "на пару" с одним, как мне кажется, очень талантливым программистом. Сейчас, вот уже две пятилетки, он трудится на благо, как вы уже наверное догадались, Соединенных Штатов Америки. Но это не важно. Важно то, что как-то прочитав очередную книжку по теории проектирования программного обеспечения я обратился к нему с претензией. И говорю: - "Дима. Крупные ученые рекомендуют "это" делать "так"". На что он мне ответил: - "Ни один крупный ученый в своей жизни не написал ни одной реально работающей программы". Должно быть, в этом есть какое-то преувеличение. Хотя бы взять, как не без справедливости считают многие, самого великого программиста всех времен и народов - Дональда Э. Кнута. Снискав себе великий почет и уважение, издавши трехтомник - "Искусство программирования", он однако разработал (написал "собственноручно"), как считают многие, лучшую в мире систему верстки математических текстов - Tex. Однако и высказывание великого английского драматурга Бернарда Шоу, тоже не стоит сбрасывать со счетов. Любил старик говаривать: - "Кто умеет делает, кто не умеет учит". На практике с подобным явлением, автору статьи приходилось сталкиваться многократно.

К чему я это собственно все рассказываю. А вот к чему. У некоторых читателей, должно быть закралось подозрение или, по меньшей мене, неустранимое сомнение: - "А автор данной статьи составил ли в своей жизни хоть одно расписание школьных занятий, по которому проработала бы реальная школа хоть одну четверть?". Столь проницательных читателей должен обрадовать. Нет, не составил. Автор к школе, а тем более к составлению расписания уроков для школы, не имеет никакого отношения. И вот именно по этому, хотелось бы завершить статью призывом ко всем шестидесяти семи тысячам российских (да и не только российских) завучей. Если каждый завуч, напишет хотя бы одно предложение, содержащее интересную мысль по поводу составления школьного расписания, то получиться книга по круче Библии или Корана. Так что, пишите ваши замечания к предложенному первому варианту кодекса школьного расписания! В простейшем случае можно только ответить на два вопроса - 1) Что не понятно? и 2) Что не правильно? Ну что же мы, все плюемся и плюемся в поганую Рашку, погрязшую за последние пятнадцать лет во взятках, пьянстве, наркотиках, воровстве, разбоях и тому подобном. Родина все-таки. Уж какая ни есть, а родину не выбирают.

ПРИМЕЧАНИЕ: Ни для кого не секрет, что Сеть Интернет представляет из себя огромную, до селе не виданную, мусорно-информационную (мусорно-рекламную) свалку отходов, и что особенно не приятно - источник различной заразы в виде разводного кидалова, финансовых пирамид, вредоносных программ (именуемых вирусами), порнографии и т.п. Однако в этой свалке отходов и прочей гадости, попадаются настоящие "золотые монеты" и настоящие "жемчужные россыпи". Что бы найти эти "золотые" монеты и "жемчужные россыпи" нужно изрядно потрудиться перерывая кучи навоза. Буду очень признателен всем тем, кто пришлет в мой адрес интересные ссылки по теме обсуждаемой в данной статье. Сеть постоянно обновляется (живет своей независимой жизнью), так что за всем не уследишь. Заранее признателен всем тем, кто не полениться оказать мне, а значит и всему цеху разработчиков ПО школьного расписания, такую услугу. Здесь же привожу ссылки, которые известны мне, но могут быть не известны читателю.

Сайты на русском языке:

Некоторые сайты на английском языке:

* На этих сайтах можно найти каталог зарубежных программ составления школьного расписания.

Адрес электронной почты автора всегда можно увидеть на главной странице сайта: www.mnogosmenka.ru .

С глубоким уважением к каждому, кто дочитал этот текст до конца!

А еще с большим уважением, к тому, кто выскажется, в виде электронного письма, на данную тему или пришлет интересную ссылку на ресурс в сети!

Август 2006 г.    Пиликов Николай Петрович.