ЗАДАЧА СОСТАВЛЕНИЯ ШКОЛЬНОГО РАСПИСАНИЯ (Кодекс о школьном расписании с короткими комментариями и пояснениями) Вот уже на протяжении нескольких десятилетий людям так или иначе связанным с образовательным процессом не дает покоя вопрос применения компьютеров (раньше ЭВМ) при составлении расписания занятий в учебном заведении. Имеются описания работ по автоматизации процесса составления расписания, которые проводились у нас в стране еще на больших ЭВМ и для которых в качестве носителей данных использовались картонные перфокарты. Особой популярностью эта задача пользуется у начинающих программистов - школьников и студентов. Однако серьезные ученые постоянно их предупреждают об имеющихся трудностях на выбранном пути. Так, на странице 171 в учебнике для будущих математиков - (Романовский И.В.
Дискретный анализ. Учебное пособие для студентов, специализирующихся по прикладной математике и информатике. СПб.: Невский диалект, 2000.) автор язвительно пишет. Так как задача составления расписаний хорошо всем известна по школьному быту, то на каждом курсе находится один или несколько студентов, обуреваемых идеей алгоритмизации составления расписания занятий. Поэтому я вынужден предупредить, что это очень сложная задача. Существует особая наука - теория расписаний, изучающая и систематизирующая задачи такого рода, а так же различные приближенные методы их решения (на точные методы надежды почти нет).
Программа составления расписания 'Ректор' предназначена для составления расписания уроков для обычных школ и школ с углубленным изучением иностранных языков. Предусмотрен учет пожеланий учителей, включая выходные дни, время работы по дням, планирование работы в 2-3 смены, деление классов на две или три группы для занятий иностранными языками, физкультурой и т.д. При работе с программой возможно применение трех методов составления расписания: ручной подбор расписания, основанный на опыте и интуиции; автоматический подбор расписания с применением эффективного алгоритма поиска; комбинир. Программа для составления и сервис для публикации расписания Составитель.
Особое место среди них занимают эвристические методы, в которых делаются попытки описать логику и технику действий диспетчера. Довольно сильно интерес юных программистов подогревает к этой задаче и легенда о том как, теперь самый богатый человек на планете, а тогда юный (шестнадцати летний) Билл Гейтс вместе со своим старшим другом Полом Алленом 'решили' эту задачу, взамен получили за программирование машинное время и заработали 2400 долларов карманных денег.
С этой историей можно ознакомиться, например, на страницах 22-24 книжки: Ичбана Д., Кнеппер С. Бил Гейтс и сотворение Microsoft. Ростов-на-Дону: Издательство 'Феникс', 1997.
Достаточно характерным высказыванием разработчиков программ по составлению школьного расписания, начинавших свою работу у нас в стране еще каких-нибудь лет восемь - девять назад, является примерно такое: В течение двух лет разработки и в течение полугода после первой продажи мы не были знакомы с аналогами, предлагаемыми другими разработчиками. В этом утверждении нет ни маркетингового лукавства, ни традиционного в среде творческих людей кокетства. Во-первых, рынок подобного рода программ в нашей стране еще не оформился, поэтому конкуренты могут на нем подолгу работать, не подозревая о существовании друг друга.
Во-вторых, изначально продукт предназначался чуть ли не для домашнего использования. В-третьих, некоторые сведения о состоянии дел в области автоматизации процессов в образовании до нас все-таки доходили и свидетельствовали, что ничего по настоящему толкового для решения проблем с расписанием никем еще не предложено. В силу этих причин разработка программы велась с нуля и без благоговейного трепета перед теми, кто шел по этой дороге раньше, да простят нас уважаемые первопроходцы за такую дерзость. В настоящее же время, ситуация изменилась. Можно прочитать на русском языке пару десятков статей на данную тему. Можно, опять же на русском языке, прочитать несколько толстых руководств пользователя, можно несколько тонких.
Можно посмотреть полтора десятка демонстрационных версий отечественных программ составления расписания. По крайней мере несколько десятков зарубежных. Можно прочитать несколько русских книжек по своей теме, достаточно близких к обсуждаемому вопросу.
ПРИМЕЧАНИЕ: Думаю, что не сильно ошибусь, если скажу, что соотношение источников информации по рассматриваемой теме, на русском языке и на английском составляет примерно 1:100. В принципе эта цифра вполне соответствует отношению доли экономики нашей страны в мировой экономике. А если еще и учесть, что основным богатством нашей страны является необработанное сырье, а не высоко технологичная продукция, тем более в сфере информатизации, то цифра может измениться и в худшею для нас сторону. Так например, объем продаж не без известной корпорации Microsoft на российском рынке в 2006 ф.
Г., составил около 0.67% (ноль целых шестьдесят сем сотых процента) от общемировых продаж (общего объема продаж в мире). Но ничего, зато у нас есть свобода слова. Ежедневно по телевизору можно посмотреть один а то и два фильма о том как менты борются с бандитами и как бандиты шикарно живут оставаясь не уязвимыми для ментов.
Лет шесть назад отечественные разработчики программ составления расписания уже начали делать, а теперь (точнее два года назад в 2004 г.) и заявлять примерно следующее: Руководство компании проанализировало ошибки, которые вновь и вновь допускали различные разработчики программ, пытаясь создать полностью автоматизированную систему составления расписания, и пришли к выводу, что для достижения поставленной ими цели необходимо учесть следующие ключевые моменты. Приведем еще одно поучительное заявление: По итогам почти двух летней работы на рынке мы обнаружили, что во многих продвинутых учебных заведениях большинство предметов ведется с делением класса на две группы, причем часто в обеих группах предмет ведет один и тот же учитель. У большинства наших пользователей есть проблема, когда по какому-либо предмету класс нужно делить на группы, а преподаватель только один. Таким образом, появилась возможность изучения опыта работы коллег по цеху, не приставая в течение двух лет к живым людям (завучам) с просьбой 'на благо родины' поделиться 'секретными технологиями' их работы, а блуждая по закоулкам и перемещаясь по магистралям Всемирной Паутины, почти бесплатно черпать нужную информацию.
Что называется, помню по себе, как еще в каком-нибудь 1993 году попытка просто сформулировать на содержательном уровне задачу составления расписания школьных занятий закончилась для меня полным провалом. Думаю, да в общем-то уверен, что с такой бедой столкнулся не только я один.
На взгляд автора, последовательное и систематическое (упорядоченное) обсуждение рассматриваемой задачи может пригодиться (будет интересно) не только начинающим программистам но и пользователям программных систем составления расписания занятий в школе. В данной статье в конспективной форме, если угодно в форме кодекса (уголовного или трудового), изложено описание, или как принято говорить - интуитивная (содержательная) простановка задачи составления расписания школьных занятий. В следующих статьях будет проведено подробное обсуждение каждого из положений, здесь лишь только кратко обозначенных. На взгляд автора, такие приемы (такой подход) позволят сформировать у читателя целостную картину обсуждаемого вопроса. Следует отметить, что автор предпринял все усилия на которые только был способен, а сделать это не так просто, в том числе и по объективным причинам, что бы найти ту 'золотую середину' (тот компромисс) между математическим текстом, доступным только профессионалу - математику, с одной стороны, текстом понятным человеку с гуманитарным образованием, с другой стороны, и, что называется, 'литературой для слабоумных', с третьей.
ПРИМЕЧАНИЕ: К 'литературе для слабоумных' автор отнес бы следующее заявление. Таким образом, при составлении расписания необходим учет степени профессионального мастерства учителя, стиля и методов его работы, микроклимата, складывающегося на каждом уроке, 'направленности' конкретного класса на предметы гуманитарного или естественно-математического цикла.
Или следующее. Такие факторы, как разумность методического насыщения каждого дня недели, эффективность расположения того или иного урока в сетке учебного дня и взаимного расположения уроков, учет возрастных особенностей учащихся, требований санитарно-гигиенических норм и т.п., оказывает чуть ли не решающее влияние на процесс усвоения знаний.
В то же время, реальный учет специфики сегодняшнего дня общеобразовательных учреждений не позволяет игнорировать такие факторы, как: дефицит педагогических кадров, мизерную зарплату учителей, нехватку учебных площадей, реальную потребность в экспериментальной педагогической работе, не подкрепленную ни нормативным, ни материальным обеспечением и многие другие. Исходя из этого, мы не только считаем несколько 'наивными' попытки создания программ 'полностью автоматизированного составления расписания', но и продолжаем реализовывать создание компьютерных инструментов-помощников, освобождающих человека от бремени рутинной работы, оберегающих его от ошибок, работающих с ним в постоянном диалоге и при этом оставляющих за человеком решающее слово в деле создания столь сложного организационно-методического документа, как расписание. Количество классов в параллеле Число решенных задач Время расчета Среднее время на одну задачу 1 - 3 22116 9 м. 2 - 4 22030 19 м. 3 - 5 28851 1 ч.
4 - 6 26640 1 ч. 1 5 - 7 16884 1 ч. 6 - 8 20196 2 ч. 7 - 9 33792 10 ч.
8 - 10 27261 18 ч. 9 - 11 29383 16 ч. 2 10 - 12 31375 34 ч. 11 - 13 10057 55 ч.
12 - 14 2917 116 ч.16 мин. 3. максимальное время счета задач такой размерности, может отличаться от минимального, до одного порядка, т.е. В 10 раз; максимальное время счета задач такой размерности, может отличаться от минимального (не среднего!), до двух порядков, т.е.
В 100 раз;. максимальное время счета задач такой размерности, может отличаться от минимального (не среднего!), до трех порядков, т.е.
Как видно из представленной таблицы и сносок к этой таблице, все волнения (опасения) по поводу решения задачи построения школьного расписания за разумное время счета, оказались напрасными. Компьютер для экспериментов использовался самый, что ни на есть простенький: 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: Следует отметить, что задача коррекции расписания во время его использования хотя и является, вообще говоря, не сложной с алгоритмической точки зрения, но тем не менее является достаточно объемной с содержательной точки зрения и требующей подробного обсуждения. Неспроста некоторые разработчики программ по составлению школьного расписания выделяют подобную коррекцию в самостоятельный продукт имеющий свою (отдельную) цену. Кроме того, не следует забывать о достаточно распространенной практике когда ученики при отсутствии заболевшего учителя приходят в школу, например, к третьему уроку, а покидают ее после пятого. Короче говоря, подробное обсуждение темы коррекции расписания или как часто ее называют - замен, выходит за рамки данной статьи и требует отдельного обсуждения.