Какой тип бд использовать?

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

А конкретная СУБД может быть любой: от MS Access или SQLite, до MS SQL Server. Данные простые, данных немного. Можно вообще JSON или YAML со всеми данными в файле хранить.

Основную проблему создаст совсем не хранение данных, а скрипт, генерирующий варианты расписания.

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

Tarantool — платформа in-memory вычислений с гибкой схемой данных для эффективного создания высоконагруженных приложений. Включает в себя базу данных и сервер приложений на Lua.