●  How to use · Timetabling

School timetabling

Assign every lesson to a period and a room with no teacher, class or room conflicts, then polish for gaps, consecutive lessons and teacher wishes.

What it decides

For every weekly period of every course, the solver picks a day and a period. Special rooms are assigned afterwards by a greedy pass.

Minimal example

from optimaru import school_timetabling as st

problem = {
    "calendar": {"periods_per_day": {"0": 4, "1": 4, "2": 4}},
    "subjects": [
        {"id": "MATH", "name": "Math", "required_room_type": None,
         "preferred_periods": [1, 2], "avoided_periods": []},
        {"id": "ART", "name": "Art", "required_room_type": None,
         "preferred_periods": [], "avoided_periods": []},
    ],
    "teachers": [
        {"id": "T1", "name": "Kim", "subject_ids": ["MATH"], "unavailable": [{"day": 0, "period": 1}],
         "max_periods_per_week": 20, "max_periods_per_day": 4, "max_consecutive_periods": 3,
         "preferred_free_days": [], "homeroom_class_id": None},
        {"id": "T2", "name": "Lee", "subject_ids": ["ART"], "unavailable": [],
         "max_periods_per_week": 20, "max_periods_per_day": 4, "max_consecutive_periods": 3,
         "preferred_free_days": [], "homeroom_class_id": None},
    ],
    "class_groups": [{"id": "C1", "name": "Class 1", "grade": 1, "unavailable": []}],
    "rooms": [],
    "courses": [
        {"id": "C1-MATH", "class_group_id": "C1", "subject_id": "MATH", "teacher_ids": ["T1"],
         "periods_per_week": 3, "block_periods": 0, "max_periods_per_day": 1,
         "fixed_slots": [], "forbidden_slots": [], "parallel_group": None},
        {"id": "C1-ART", "class_group_id": "C1", "subject_id": "ART", "teacher_ids": ["T2"],
         "periods_per_week": 2, "block_periods": 2, "max_periods_per_day": 2,
         "fixed_slots": [], "forbidden_slots": [], "parallel_group": None},
    ],
}

timetable = st.solve(problem, time_limit_seconds=2.0, random_seed=42)  # returns a dict
print(timetable["status"], timetable["objective_value"], timetable["penalties"])
for lesson in timetable["lessons"]:
    print(lesson["course_id"], lesson["slot"], lesson["room_id"])

The same use case as a Jupyter notebook, with charts and saved outputs: examples/school-timetabling.ipynb ↗

Input parameters

problem["calendar"]

Field Meaning
periods_per_day Periods per weekday, as {"0": 7, "1": 7, ...}. 0 is Monday.

problem["subjects"][i]

Field Meaning
id Subject id. required_room_type Room type the subject needs, or None for the class's own room. preferred_periods Periods to aim for. avoided_periods Periods to stay away from.

problem["teachers"][i]

Field Meaning
id Teacher id. unavailable Slots the teacher cannot teach, as {"day": 0, "period": 1}. max_periods_per_week Weekly period cap. max_periods_per_day Daily period cap. 6 if left out. max_consecutive_periods Consecutive-lesson cap. 4 if left out. preferred_free_days Weekdays the teacher would like off.

problem["class_groups"][i]

Field Meaning
id Class id. unavailable Slots the class cannot use.

problem["rooms"][i]

Field Meaning
id Room id. room_type Room type, matched against required_room_type.

problem["courses"][i]

Field Meaning
id Course id. class_group_id The class. subject_id The subject. teacher_ids Teachers. Two or more means team teaching. periods_per_week Weekly periods to place. block_periods 2 or more joins that many periods into one consecutive block per week. max_periods_per_day Daily cap for this course. 1 if left out. fixed_slots Slots that are pinned. The engine never moves them. forbidden_slots Slots this course may not use. parallel_group Courses sharing this value are parallel sections: always at the same time, taking one class cell.

Solve parameters

What you pass to the solve call. Time limit, seed and parallel count are here.

Parameter Default Meaning
mode 'canonical' canonical honours every constraint below. quickstart is an approximate conversion to a smaller model, and its limits are listed in notes.
time_limit_seconds None Search budget in seconds, from 0 to 1e9. Left unset, it is the config's spent_limit_seconds, 30 by default.
random_seed None Seed for the search. Left unset, it is the config's value, 0 by default.
parallel_solver_count None Independent parallel starts. Each gets its own seed and the full budget, and the best result wins. Left unset, it is the config's value, 1 by default.
stop_at_first_feasible False Stop as soon as hard 0 is reached.
weights None Soft weights by constraint name, such as {"teacher_gap_cost": 40}. Omitted names keep their default. canonical mode only, and not together with constraints=.
constraints None Which constraints to score, and how. Left unset, the defaults apply.
on_new_best None Callback run on each new best solution. If it raises, the solve stops and raises the same exception.
config None A SolverConfig as the base configuration. Keyword arguments here override it for this solve only; the object you pass is not changed.
initial_solution None An earlier Timetable dict to start from.
All search options (31)

Set these on canon.SolverConfig and pass it as config=. The top-level SolverConfig is refused in the default canonical mode.

Parameter Default Meaning
best_score_limit — Stop early once the best score reaches this value. By default it never fires.
change_move_weight 0.75 Relative share of change moves. 0 disables them.
descent_max_sweeps 4 Improving passes before giving up on a neighbourhood.
descent_weight 0.0 Share of best-improvement descent. 0 turns it off.
full_assert False Check every incremental score against a full recompute. Slow; for debugging.
hot_lesson_probability 0.7 Probability of moving a lesson that carries a hard violation. 0 disables it.
late_acceptance_size 0 Late-acceptance history length. 0 picks it from the instance size.
on_new_best None Callback run on each new best solution. If it raises, the solve stops and raises the same exception.
parallel_solver_count 1 Independent parallel starts, each with its own seed and the full budget. The best one wins.
random_seed 0 Seed for the search.
reassign_candidates 32 Slots tried by the reassign move, used only when unassigned lessons are allowed.
ruin_recreate True Run adaptive ruin-and-recreate kicks when the search stagnates.
ruin_recreate_as_move_max_ruin 12 Most entities that small ruin removes.
ruin_recreate_as_move_weight 0.0 Probability that a step is a small ruin and repair, judged like any other move. Negative picks it automatically where the use case supports that; 0 turns it off.
ruin_recreate_max_ruin_count 60 Absolute cap on entities removed per kick.
ruin_recreate_max_ruin_fraction 0.3 Largest share of the solution one kick removes.
ruin_recreate_min_ruin_fraction 0.1 Smallest share of the solution one kick removes.
ruin_recreate_operator_decay 0.8 How fast operator weights adapt.
ruin_recreate_polish_steps 5000 Hill-climbing moves that polish each kick. Not counted against step_count_limit.
ruin_recreate_rewards [33.0, 9.0, 3.0, 0.0] Operator rewards for a new best, a better, an accepted and a rejected result.
ruin_recreate_unimproved_step_trigger 5000 Steps without a new best before a kick.
same_class_nearby True Treat lessons of one class as neighbours.
same_class_nearby_probability 0.5 Probability of drawing a swap partner from those neighbours.
smart_class_swap_candidates 8 Swaps tried per such move.
smart_class_swap_moves True Try several swaps between lessons of one class and keep the best.
spent_limit_seconds 30.0 Time budget in seconds, from 0 to 1e9.
step_count_limit 0 Stop after this many steps. 0 means no limit.
swap_move_weight 0.25 Relative share of swap moves. 0 disables them.
unimproved_spent_limit_seconds 0.0 Stop after this many seconds without a new best. 0 means no limit.
unimproved_step_count_limit 0 Stop after this many steps without a new best. 0 means no limit.
weights ObjectiveWeights() The six soft weights, as canon.ObjectiveWeights: teacher_gap_cost 20, teacher_workday_cost 3, teacher_free_day_cost 30, class_gap_cost 10, avoided_period_cost 5 and non_preferred_period_cost 1.

What comes back

School timetabling takes a dict and returns a dict, so there is no model to convert. The decisions are in lessons.

timetable

Field Meaning
status FEASIBLE with no hard violation left, INFEASIBLE otherwise. lessons One entry per placed period. objective_value Weighted sum of penalties. penalties Raw soft counts, by constraint name. notes Explains violations left in an INFEASIBLE result. wall_time_seconds Solve time. best_objective_bound Always None: local search proves no bound.

timetable["lessons"][i]

Field Meaning
course_id The course. class_group_id The class. subject_id The subject. teacher_ids The teachers. slot The chosen time, as {"day": 0, "period": 1}. room_id Filled only for lessons that need a special room. Otherwise None: the class's own room.

Constraints

Pick them by calling their classes from optimaru.school_timetabling.constraints, such as UnassignedLessonsCost(). Only what you pass is scored; pass nothing to keep the defaults. A list may name a constraint more than once, and each pick is scored on its own. Each one takes these parameters:

Parameter Default Meaning
weight None Multiplier on the constraint's cost, in units of the level in effect. Left unset, the default weight below applies. A constraint whose default weight is 0 is off until you give it a weight.
level None "hard" makes the constraint a must and "soft" a preference, as do Level.HARD and Level.SOFT. Left unset, it keeps the level below. This use case has no medium level, so "medium" raises ValueError. A reward refuses "hard", and a fixed level refuses any change; both raise ValueError.
exponent 1.0 Sign-preserving power on the cost, above 0, taken after offset. 2.0 squares it, so concentrated violations cost much more. It applies per unit, such as a vehicle or a day, or to the total of a constraint scored as one sum.
offset 0.0 Subtracted from the cost x before the exponent, per unit or total like the exponent. It is in the cost's own measure: seconds, minutes, a count and so on. Any finite number of either sign, keyword only. clip decides what happens below it.
clip True True makes offset a threshold: only the part beyond it counts, max(0, x - offset) ** exponent, so a cost at or below it adds nothing. False takes the literal (x - offset) ** exponent, sign kept: a unit below the offset counts negative, as a reward, even one whose cost is 0. On a level that counts toward hard, clip=False with a non-zero offset raises ValueError, since hard 0 must mean no violation. Keyword only.

Pass weights={"teacher_gap_cost": 40} to change soft weights, or constraints=Assembly()... to pick, drop or flip constraints. Assembly keeps one entry per name: add() on a name already there replaces it. A plain constraints=[...] list may pick a name several times, each pick scored on its own. Without constraints=, the solve keeps its fast path and can run workers in parallel; with it, the search is single-start.

This continues the minimal example above.

from optimaru.school_timetabling.constraints import Assembly

# start from all 17, change one, drop one
custom = st.solve(
    problem, time_limit_seconds=2.0, random_seed=42,
    constraints=Assembly().add("teacher_gap_cost", weight=40).drop("teacher_workday_cost"),
)
print(custom["status"], custom["penalties"])
Name Level Default weight What it does
unassigned_lessons_cost Hard 1 One point per unassigned lesson. Demoted with level="soft", unfilled periods become a result instead of a violation; see below.
class_conflict_cost Hard 1 One point per pair of same-class lessons at the same time.
teacher_conflict_cost Hard 1 One point per teacher shared by a pair of lessons at the same time, team teaching included.
disallowed_slot_cost Hard 1 One point per lesson outside its allowed slots: forbidden times and teacher or class unavailability.
room_capacity_cost Hard 1 Per special-room type and time, demand above the rooms there are.
course_max_periods_per_day_cost Hard 1 Per course and weekday, periods above the daily cap.
block_adjacency_cost Hard 1 How far a block's periods are from being consecutive on one day.
teacher_max_periods_cost Hard 1 Each teacher's excess over the daily and weekly caps.
teacher_max_consecutive_periods_cost Hard 1 Each teacher's excess over the consecutive-lesson cap.
teacher_gap_cost Soft 20 Idle periods inside a teacher's day.
teacher_workday_cost Soft 3 One point per teacher and weekday with lessons.
teacher_free_day_cost Soft 30 One point per teacher and weekday with lessons on a requested free day.
class_gap_cost Soft 10 Idle periods inside a class's day.
avoided_period_cost Soft 5 One point per lesson in an avoided period.
non_preferred_period_cost Soft 1 One point per lesson outside its preferred periods, when it has some.
fixed_slots_cost Hard Fixed level 1 Lessons off their course's fixed_slots. The engine pins every fixed lesson, so this is always 0, and level="soft" raises ValueError.
parallel_groups_cost Hard Fixed level 1 Sections of one parallel_group at different times. The engine merges each group into one lesson, so this is always 0, and level="soft" raises ValueError.

How constraints work →

Starting from an existing solution

This needs the latest release: pip install -U optimaru.

Problems here are dicts, so there is no with_initial_solution. Pass the earlier timetable to solve with initial_solution=.

This continues the minimal example above.

better = st.solve(problem, time_limit_seconds=2.0, random_seed=42, initial_solution=timetable)
print(better["status"], better["objective_value"])
  • Lessons are matched by course_id.
  • A complete solution skips construction: the search starts exactly from it. A partial one keeps what it gives, and only the periods it leaves out are constructed.
  • With time_limit_seconds=0 the solve stops at once, so a complete solution comes back as it went in. Use the time limit for this: step_count_limit = 0 means no limit.
  • room_id is ignored, since it is recomputed from the result.
  • fixed_slots are kept, and a course's other slots must fit its free periods, so a complete solution that moves a fixed lesson is rejected.
  • An unknown course, a course given twice at one time, more slots than a course has free periods, or parallel sections at different times raise ValueError.
  • A time a course may not use is accepted and scores as a hard violation, so an INFEASIBLE result can be resumed.

Exceptions and limits

  • Local search cannot prove optimality or infeasibility. INFEASIBLE means hard violations were left at the time limit, not that no timetable exists.
  • A calendar is limited to 16 periods and to weekday indices below 8. A larger one raises ValueError.
  • To leave unfillable periods out instead of getting INFEASIBLE, demote the first constraint: Assembly().add("unassigned_lessons_cost", level="soft", weight=10_000). One unassigned period costs that weight, so keep it above the sum of the other soft terms.
  • Do not combine that assembly with stop_at_first_feasible: a timetable that drops every lesson is hard 0 too, and the search would stop there.