Одной из распространенных задач целочисленного программирования является задача составления расписания. Она относится к классу NP-полных. Решение задач этого типа предусматривает различные подходы. В последнее время они стали весьма актуальными в связи с полной автоматизацией процессов управления объектами различного назначения: транспорт, логистика, сборочное производство, проектирование, организация учебного процесса в образовательных заведениях всех уровней [1]. Автор предлагает математическую модель такой задачи на примере целочисленной задачи без потоков, характерной для технических вузов.

Для простоты изложения предлагаемой оригинальной процедуры составления расписания приведем постановку задачи для учебного процесса, характерного при дневном обучении: M – количество обобщенных групп; i – номер обобщенной группы; Р – количество обобщенных преподавателей; j – номер обобщенного преподавателя; T – общее число обобщенных занятий в неделю; Q – количество учебных дней в неделю; q – номер учебного дня недели; H – количество обобщенных занятий в день; h – номер обобщенного занятия в течение дня.

Очевидно, что для составления сквозного недельного расписания T=QH, где t – номер обобщенного занятия (сквозной за неделю); S=SL+SС – общее количество обобщенных аудиторий; C – количество групповых занятий (ГЗ) согласно тематическому плану; c – номер конкретного ГЗ (1,…,C) согласно тематическому плану; SC – число аудиторий для ГЗ.

Приведем блок понятий, реализующих общие для групп потоковые лекционные занятия [1, 2]: L – количество лекций согласно тематическому плану; l – номер конкретной лекции (1,…,L) согласно тематическому плану; SL – число аудиторий для лекций; k – номер обобщенной ауди- тории.

Следует учесть, что потоковые занятия необязательны для всех групп, поскольку существует разделение на специальности, направления и т.п. Тогда R – количество потоков; r – номер потока (1,…,R); kr – номер учебной группы в потоке r; Qkr – множество номеров рабочих дней группы kr; Lr – количество лекций в потоке r согласно тематическому плану; lr – номер конкретной лекции, 1,…,Lr.

При этом необходимо повториться по номенклатуре ГЗ по потокам: Cr – количество ГЗ в потоке r согласно тематическому плану; cr – номер конкретного ГЗ, 1,…,Cr; i – номер обобщенной группы (1–М); j – номер обобщенного преподавателя (1–Р); t – номер обобщенного занятия, сквозной за неделю (1–Т); q – номер учебного дня недели (1–Q); h – номер обобщенного занятия в течение дня (1–H); k – номер обобщенной аудитории (1–S).

Примем за критерий оптимальности максимизацию свободных дней преподавателей. Тогда задача будет сформулирована следующим образом: найти , где ξp – весовой коэффициент, определяемый статусом преподавателя; zqp – булева переменная, равная 0, если преподаватель имеет занятия в данный день, и равная 1 в противном случае, при ограничениях .

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

.

Равенство указывает, что для каждой группы ir должен выполняться установленный тематический план на неделю, где Yqhl=1, если в день q на паре h читается лекция l, 0 – в противном случае; Xqihcr=1, если в день q в группе ir на паре h проводится практическое занятие c, 0 – в противном случае.

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

Приведем ограничения в задаче составления расписания: Jqihr – 1, если в q-й день группа ir начинает занятия с h-й пары; Zqijr – 1, если в q-й день группа ir заканчивает занятия на h-й паре; Yqhl – 1, если в q-й день на h-й паре читается лекция l; Xqihcr – 1, если в q-й день в группе ir на h-й паре проводится ГЗ c; Dpl – 1, если преподаватель p читает лекцию l; dpiсr – 1, если преподаватель p в группе ir проводит ГЗ с; Np – нагрузка преподавателя p в неделю; Wir – тематический план на неделю для группы ir.

Тогда можно ввести следующие ограничения:

1)  – любое занятие не начинается раньше пары Jqih и не оканчивается позже пары Zqih;

2)  – все виды занятий заполняют интервал между первой Jqih и последней Zqih парами;

3)  – в q-й день на каждой h-й паре группа ir может иметь не более одного вида занятий (ГЗ c или лекция l);

4)  – ГЗ с и лекция l для

всех и всех групп ir могут проводиться не более одного раза на какой-либо h-й паре;

5)  – в q-й день на каждой h-й паре преподаватель p может вести не более одного занятия (ГЗ с в одной группе i или лекцию l);

6)  – каждый преподаватель в течение надели должен выполнить свою аудиторную нагрузку;

7)  – с группой ir должны быть проведены все занятия, запланированные на неделю;

8) ,  – в каждый день q и в каждой паре h число лекций и число ГЗ не должно превышать общего числа лекционных залов и аудиторий для ГЗ.

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

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

Найти ,

где ξp – весовой коэффициент, определяемый статусом преподавателя; zqp – булева переменная, равная 0, если преподаватель имеет занятия в данный день, и равная 1 в противном случае, при ограничениях:  – в каждый день q на каждой паре h для каждой группы i может проводиться не более одного занятия;

.

Для каждой группы i должен выполняться тематический план на неделю: Yqhl=1, если в день q на паре h читается лекция l, 0 в противном случае; Xqihc=1, если в день q в группе i на паре h проводится практическое занятие c, 0 в противном случае.

Ограничения в задаче составления расписания:

1)  – лю-

бое занятие не начинается раньше пары Jqih и не оканчивается позже пары Zqih;

2)  – все виды занятий заполняют интервал между первой Jqih и последней Zqih парами;

3)  – в q-й день на каждой h-й паре группа i может иметь не более одного вида занятий (ГЗ c или лекция l);

4)  – ГЗ с и лекция l для всех и всех групп i могут проводиться не более одного раза на какой-либо h-й паре;

5)  – в q-й день на каждой h-й паре преподаватель p может вести не более одного занятия (ГЗ с в одной группе i или лекцию l);

6)  – каждый преподаватель в течение надели должен выполнить свою аудиторную нагрузку;

7)  – с группой i должны быть проведены все занятия, запланированные на неделю;

8) ,  – в каждый день q и в каждой паре h число лекций и число ГЗ не должны превышать общего числа лекционных залов и аудиторий для ГЗ.

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

Литература

1.   Арефьев И.Б., Шевелев С.Б. Актуальные задачи формирования моделей графиков распределения по маршрутам грузовых автомобилей СПбТУ // Автотранспортное предприятие. № 9. 2007. С. 32–34.

2.   Арефьев И.Б., Северов А.А. Принципы разработки тестов. СПб: СЗТУ, AПСП, 2005. С. 133–138.

3.   Арефьев И.Б., Кивалов А.Н., Мартыщенко Л.А. Аналитическая логистика. Эконометрия логистических систем. 2-е изд. СПб: СЗТУ, 2008. 91 с.