Как реализовать оптимальную расстановку расписания занятий в уч. заведении?

Универсального алгоритма такого как решение квадратного уравнения не существует (иначе вы даже и не искали его). Это так называемая NP полная задача которая в общем случае решается полным перебором. Оптимального решения может и не существовать в силу множества параметров и переменных.

Но есть различные алгоритмы и методики которые могут дать приемлемый (компромиссный) результат.

1. Метод ветвей и границ

2. Жадные алгоритмы

3. Генетические алгоритмы

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

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

Так вот, после генерации массива комбинаций, каждому варианту нужно будет присвоить оценку скажем в 10к и дальше у каждого варианта уменьшать эту оценку, если он не соответствует какому-то требованию.

Итог - ТОП-3 лучших варианта расписания

P.S. за реализацию не брался, возможно когда нибудь попробую на досуге

Успешность человеческих начинаний, как правило, обратно пропорциональна предсказуемости их результата. (с) Насим Талеб

Я довольно долго занимался составлением расписания в университете и мне есть что сказать на эту тему.

Первое, к сожалению, программы, которая составляет расписание в полностью автоматическом режим нет. С этим нужно просто смириться. Её нет не потому что это супер-мега сложная задача, а потому что это как раз рутина, которой никому не интересно заниматься, поскольку она не несёт больших экономических выгод. Тех, кого пугает перебор 51! вариантов (1.5511e+66) могут попробовать запустить такой цикл. У меня на (Xeon e5 2678 v3 + GTX 2060) весь процесс занимает 30 минут, поэтому говорить о вычислительной сложности, сейчас, при всём уважении, это просто смешно.

Второе, если Вам необходимо реальное расписание, а не решение теоретической задачи, то нужно иметь ввиду следующее - математически идеальное расписание на практике НЕ будет идеальным. Несколько раз на протяжении 7 лет мне удавалось составить идеальное расписание (в математическом смысле), но ни разу оно не оказалось практически идеальным. Объясню почему, преподавателю внезапно нужно отвести дочку на секцию не в 9 утра, а в 17:00 после школы, вот так изменились обстоятельства, другой сорвал спину на даче, теперь он ходит на процедуры и надо изменить время, третьему перестало быть удобно это время просто потому что... Кроме того, часто бывает такое, что нескольким людям удобно одно и тоже время, а это коллизия, которую можно разрешить только вручную.

Третье, Вы знаете, как преподаватель скажу, провести 3 пары + 2 пары с одним окном, это не тоже самое, что провести 5 пар подряд. То есть, конечно, я не за всех говорю, может кому-то и легче, но наличие окон иногда очень упрощает жизнь и снижает общую нагрузку.

чтобы не было такого, что у препода всего 1 пара в день

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

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

Самый крутой завуч (в ВУЗе обычно эту тему курирует зам. декана) сделает любой алгоритм в лёгкую. Люди, которые занимаются составлением расписаний по 15-20 лет делают за пару дней расписание, которое всех устраивает с минимальным числом правок, а из 10к вариантов он сразу видит какие есть смысл рассматривать, а какие нет, потом за пару правок всё становится на свои места.

В сухом остатке у нас критерии идеального расписания следующие:

1. Делается итеративным методом, то есть в первоначальный вариант вносятся правки;
2. Нужен удобный способ внесения изменений, которые всегда возникают;
3. Желательно быстро получить нулевую итерацию, которая не идеальна, но которую уже можно править;
4. Критерий того, что расписание идеальное - те, кто по нему занимается довольны или одинаковы недовольны, чтобы не было ни кому обидно (это самый важный момент).

Теперь двигаемся дальше. Часто бывает, что в силу разных обстоятельств получается удачное расписание, все довольны, всем удобно. Вот старались-старались использовали Nvidia Grid и получилось расписание просто супер. С тех пор прошло время, допустим два года, и вот было бы не плохо его снова использовать, но... Никто не знает где файл расписания или какой из вариантов тех файлов, которые есть правильный... Знающие товарищи меня поправят, что всё можно найти и восстановить, но расписание настолько "важная" и нудная штука, что на практике после того как расписание готово, обычно все делают вздох облегчения, а память стирает травмирующие воспоминания.

В итоге имеем ещё два пункта:

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

Из написанного выше напрашивается вывод, что лучше всего использовать нейросеть для решения данной задачи, а расписание хранить в XML-файле.

Открытым остаётся вопрос - какую сеть использовать?

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

Ещё один момент, если Вы, в отличие от меня, доведёте эту тему до конца и получите готовый продукт. Есть две наиболее популярные программы для составления расписаний. У нас это АВТОРасписание, а у них это aSc TimeTables. С ними имеет смысл ознакомится в любом случае, чтобы посмотреть на их "фишки" и недостатки.

Вот как-то так. Если будут вопросы - спрашивайте.

Удачи Вам в составлении расписаний!

Google Or tools имеет модуль CP-SAT. Я использую последнее время его на работе. Это оптимизатор для подобных задач, да и в целом constraint programming.

https://developers.google.com/optimization/scheduling/employee_scheduling