Расписание

Расписа́ние — вид календаря (то есть, упорядоченность по времени), для которого указана информация о предстоящих (планируемых или потом произошедших) событиях.

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

Расписание для курсирующих по постоянному маршруту повозок появилось в Великобритании в 1784 году, но лишь для времени отправления, а не прибытия. Расписание с временем прибытия появилось уже во времена паровозов в 1840 году.
С расписанием связано и Среднее время по Гринвичу: в 1847 году британские паровозные компании объединились, и для всебританского расписания было определено единое время по времени Гринвичской обсерватории.

По расписанию ходят рейсы многих маршрутов общественного транспорта. Особенно это относится к междугороднему и международному транспорту.

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

На железнодорожных станциях, в аэропортах и т. д. информация о рейсах может обновляться и отображаться на табло.

Боевое расписание — (фр. ordre de bataille, нем. Schlachtordnung) — термин существовавший в XVII, XVIII и даже в начале XIX века, который обозначал распределение войсковых частей в боевом порядке армии^[1]. Боевые расписания на флоте представляют свод обязанностей каждого чина на корабле во время боевых действий^[2].

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

Оптимизация расписания занятий является одним из основных факторов, способных существенно оптимизировать учебный процесс

Расписание для вузов весьма отличается от расписания для школ: так как в школах учатся несовершеннолетние и во время учёбы за них отвечают учителя, то по школьному расписанию учащиеся должны быть полностью заняты (без «окон»), в то время как для университетского это обязательство отсутствует. Также есть отличия в вычислительных ресурсах для составлении расписания (см. en:Constraint satisfaction problem)

en:University timetable

en:School timetable

Расписание (называемое графиком) работы (Schedule, rota) имеющихся в нём работников указывает, кто из них в какой промежуток времени должен работать. Применяется при сменной работе — график дежурств, уборка территорий (помещений и т. п.). Имеет периодичность в несколько суток.

Теоретическими разработками в области составления расписания занимается математический раздел исследование операций

В основе составления расписания занятий лежит теория расписания. Теория расписания является хорошо изученной и описанной во многих работах, начиная с 1960-х годов. Она широко используется как при организации работы предприятий, так и применима для учебных заведений^[3][4][5].

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

Исходными составляющими данного процесса являются:

• P — потоки обучения, которые включают в свой состав от одной до нескольких групп обучения, или подгруппы, которые образуются за счет деления одной или нескольких групп (поток) на отдельные подразделения.
• T — преподаватели, являющиеся основным механизмом воздействия на потоки обучения. В отличие от классических подходов в теории расписания (один механизм - одна операция) в данной ситуации могут быть ситуации, когда несколько преподавателей могут объединяться в один «механизм» для проведения занятия.
• D – дисциплины обучения, основой которой является тематический план обучения, включающий различные типы занятий.
• А — аудитории, являющиеся местом для проведения занятий (выполнения операции). Во многих существующих теориях и системах, реализующих  составление расписания, данный участник выносится из общей задачи с целью упрощения системы.

Постановка задачи на планирование

Во многих работах она формулируется, как перебор всевозможных вариантов для всех исходных данных процесса планирования (декартово множество R = {P*T*D*A*z}, где z – периоды проведения занятия (дата и пара) с нахождением оптимума по критерию соответствия заданным требованиям к расписанию. При таком подходе делается вывод о сложности составления расписания, так как при её решении появляется экспоненциальный рост количества сочетаний, что делает задачу NP-полной.^[3]

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

Если рассматривать планирование в данном случае как процесс определения временного отрезка для конкретного занятия, то задача становится классической с точки зрения теории расписаний. То есть, для заданного числа работ (дисциплин) и операций (занятие дисциплины) определить такие временные отрезки, чтобы составленное расписание соответствовало заданным критериям оптимальности и предъявляемым требованиям.

При этом для составления расписания должны быть определены:

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

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

Для данного подхода можно использовать следующий критерий^[6]:

Kopt(i,j)=Wrd(i)/Wmo(j), где

i — номер преподавателя (машины), лежащее в диапазоне от 1 до M;

i — номер дисциплины (работы), лежащее в диапазоне от 1 до N;

Wrd — количество занятий (операций), которое необходимо провести по выбранной  дисциплине (работе);

Wmo — количество занятий (операций), которые может провести преподаватель (машина) по планируемому периоду времени с учётом наложенных ограничений на выполнение занятий по данной дисциплине и преподавателю.

Ранжирование дисциплин для составления расписания выполняется в порядке уменьшения полученного критерия.

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

${\displaystyle Kj=Sum(Kopt(i,j);N)<1}$

, где N — количество дисциплин по данному преподавлю.

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

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

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

При возникновении ситуации, когда по выбранной очередной дисциплине планирование является невозможным, выполняется перепланирование. В качестве перепланируемой дисциплины выбирается та, у которой наименьшее значение показателя Kopt(i,j).

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