Building a cinema scheduling engine with OR-Tools CP-SAT, staged relaxation and an occupancy forecast

A multiplex's daily schedule decides which film plays on which screen, how many times and at what minute — and with it attendance, occupancy, concession sales and how well prime time is used. It is also bound by more than thirty business rules: a minimum interval between starts of the same film, spacing between different films for entry, exit and the concession queue, popular films in prime time, dubbed children's films at child-friendly hours, and a target share of the day for every film. A rule-of-thumb plan quietly breaks some of them. A binary for every screen, film and start minute grows too fast to solve while a scheduler waits. And a strict model that treats every rule as hard returns nothing on exactly the days that need help — when a pre-sold session sits in an awkward place, or the film mix does not fit.

In this post we walk through the engine we built instead. It maps each request onto typed inputs, models every screen as a chain of optional show slots on a five-minute grid in OR-Tools CP-SAT, writes each film's target as a seat-weighted share whose reachable values are pre-computed by dynamic programming, adds redundant cuts and symmetry breaking so the solver can prune early, and solves in stages that relax rules into priced penalties only when the strict model has no answer. An independent validator re-checks every rule, and the engine runs as an asynchronous FastAPI service on Kubernetes. Alongside it, an occupancy forecast built with LightGBM and a Temporal Fusion Transformer estimates how well a film will do by site and time slot.

Solution overview

The engine is one Python service. A request carries a day's films, screens, opening hours, pre-sold sessions and rule settings as JSON. The service maps it to typed objects, builds a CP-SAT model, solves it in stages inside one time budget, validates the result and posts it back through a callback. The occupancy forecast is a separate track that learns from past attendance; it is not on the request path.

The numbered steps in the diagram:

1. The request's films, screens, windows, pre-sold sessions and rule switches are parsed into Python dataclasses; ineligible screens and films with no target are dropped, and a film-group ↔ screen eligibility map is built.
2. Each screen becomes a fixed number of optional slots in OR-Tools CP-SAT — film choice, start on a five-minute grid, end and cleaning gap — tied together as a time chain with optional intervals and NoOverlap.
3. Each film's seats must land within a tolerance of its target share of all seats; reachable seat totals are pre-computed by dynamic programming and passed to the solver as exact variable domains.
4. Redundant cuts, conservation identities, slot-order symmetry breaking, element tables and decision strategies shrink the search without changing the optimum.
5. Hard rules, then hard + soft; if no schedule exists, rules become priced penalty variables and a final stage caps the penalty at the previous value. Each stage is hinted with the last solution.
6. An independent validator re-checks every rule and names the ones that gave way; the result goes back through an httpx callback from a FastAPI service running in a Kubernetes pod.
7. A week-ahead forecast by site, film and day compares LightGBM with a Tweedie objective, a log-target LightGBM baseline and a Temporal Fusion Transformer, and selects or blends them.

Technology stack

Step 1: Map the request onto typed inputs

A request describes one operating day: the screen inventory (seats, format, floor, cleaning-time limits and special flags), the films (runtime, target share, priority, format, and flags such as dubbed or domestic), opening hours with the main-time and dubbing windows, sessions already on sale, and a set of rule switches and thresholds. Rules arrive as settings, not as code.

The first job is to make the problem smaller before any variable exists. Screens that cannot show anything are dropped, films with a zero target are removed, and the remaining films are grouped — a title's format variants share a group — with an eligibility map that records which groups each screen may play. Every later step iterates over this map instead of over all screen–film pairs.

from dataclasses import dataclass

@dataclass(frozen=True)
class Screen:
    id: str
    seats: int
    fmt: str                     # projection / sound format
    clean_min: int               # minutes between shows
    clean_max: int

@dataclass(frozen=True)
class Film:
    id: str
    group: str                   # one title; its format variants share a group
    fmt: str
    runtime: int                 # minutes, ads added later
    share: float                 # target share of the day's seats
    priority: int = 0

def eligibility(screens, films):
    """Keep films with a target; map each screen to the film groups it may play."""
    films = [f for f in films if f.share > 0]
    elig = {s.id: sorted({f.group for f in films if f.fmt == s.fmt}) for s in screens}
    return {s: groups for s, groups in elig.items() if groups}, films

Simplified. Real eligibility also depends on special screen flags and rule switches.

Step 2: Model each screen as a chain of optional shows

A binary for every screen × film × start minute is the obvious formulation and the wrong one: most of those variables can never be true, and the solver learns little from them. Instead each screen gets a fixed number of slots. A slot is either active or not; if active it plays exactly one film group (and one format variant within it), starts on a five-minute grid, and ends after the ads and the runtime. The next slot starts after a cleaning gap that is bounded on both sides — long enough to clean, short enough not to leave the screen idle.

y[s,k,g] ∈ {0,1}     slot k of screen s plays film group g
z[s,k,v] ∈ {0,1}     format variant v of that group,     Σ_{v∈g} z[s,k,v] = y[s,k,g]
active[s,k] = Σ_g y[s,k,g]

start[s,k]   = open + 5 · idx[s,k]                                  five-minute grid
end[s,k]     = start[s,k] + Σ_g y[s,k,g] · (ads + runtime_g)        if active[s,k]
start[s,k+1] = end[s,k] + gap[s,k],      clean_min(s) ≤ gap[s,k] ≤ clean_max(s)
end[s,k]     ≤ close

Each slot is also an optional interval whose presence literal is the slot's active flag. That makes the timetable structure explicit: add_no_overlap on a screen's intervals gets a dedicated scheduling propagator, and an inactive slot drops out of every constraint that uses it. Most rules then become one-line constraints on start, end or gap.

from ortools.sat.python import cp_model

GRID = 5  # minutes

def add_screen(m, scr, groups, length, K, t_open, t_close):
    """K optional show slots on screen scr; length[g] = ads + runtime of group g."""
    n_grid = (t_close - t_open) // GRID
    slots, prev = [], None
    for k in range(K):
        act = m.new_bool_var(f"act[{scr.id},{k}]")
        y = {g: m.new_bool_var(f"y[{scr.id},{k},{g}]") for g in groups}
        m.add(sum(y.values()) == act)                   # one film group iff active
        idx = m.new_int_var(0, n_grid, f"idx[{scr.id},{k}]")
        start = m.new_int_var(t_open, t_close, f"start[{scr.id},{k}]")
        m.add(start == t_open + GRID * idx)             # five-minute grid
        size = m.new_int_var(0, max(length.values()), f"len[{scr.id},{k}]")
        m.add(size == sum(length[g] * y[g] for g in groups))
        end = m.new_int_var(t_open, t_close, f"end[{scr.id},{k}]")   # ends before closing
        iv = m.new_optional_interval_var(start, size, end, act, f"show[{scr.id},{k}]")
        if prev is not None:
            m.add(act <= prev["act"])                   # fill slots from the front
            gap = m.new_int_var(scr.clean_min, scr.clean_max, f"gap[{scr.id},{k}]")
            m.add(start == prev["end"] + gap).only_enforce_if(act)
        prev = dict(act=act, y=y, idx=idx, start=start, end=end, iv=iv)
        slots.append(prev)
    m.add_no_overlap([sl["iv"] for sl in slots])
    return slots

Simplified. Format variants (the z layer), pre-sold sessions and rule switches are omitted.

Why CP-SAT? The model is an integer program, but a timetable also needs scheduling primitives. CP-SAT combines linear integer constraints with optional intervals, NoOverlap and element constraints, runs a parallel search portfolio, and accepts solution hints — which the staged solve in Step 5 relies on.

Step 3: Express target share in seats, with exact domains

Every film has a target share of the day. Counting shows would let a film meet its target on the smallest screen, so share is measured in seats: each show contributes the seat count of its screen. Dividing by the day's total seats would make the constraint non-linear, so both sides are multiplied through and the solver never divides. The tolerance around the target can be asymmetric, and it depends on the film's format.

seats_g = Σ_{s,k} seats_s · y[s,k,g]                      seats given to film group g
SEATS   = Σ_g seats_g                                      all seats of the day

(share_g − δ⁻_f) · SEATS  ≤  seats_g  ≤  (share_g + δ⁺_f) · SEATS          f = format of g

The bounds alone are loose. A film's seat total can only take values that are sums of its eligible screens' seat counts, and most integers in between are unreachable. A small dynamic program — a bounded subset sum over eligible screens, with each screen's maximum number of shows — enumerates the reachable totals, and the result becomes the variable's domain. The solver then rejects an impossible total immediately instead of discovering it deep in the search. The same idea is available as a linear-in-domain constraint on the sum itself.

from ortools.sat.python import cp_model

def reachable_seat_totals(eligible_seats, max_shows):
    """Bounded subset sum: every total Σ n_s · seats_s with 0 ≤ n_s ≤ max_shows[s]."""
    reach = {0}
    for s, seats in eligible_seats.items():
        reach = {r + n * seats for r in reach for n in range(max_shows[s] + 1)}
    return sorted(reach)

def add_share(m, g, slots_by_screen, eligible_seats, max_shows, total_seats,
              lo_pm, hi_pm):
    """lo_pm, hi_pm: target minus / plus tolerance in per-mille, so all terms are integers."""
    dom = cp_model.Domain.from_values(reachable_seat_totals(eligible_seats, max_shows))
    seats_g = m.new_int_var_from_domain(dom, f"seats[{g}]")     # exact reachable values
    m.add(seats_g == sum(eligible_seats[s] * sl["y"][g]
                         for s, slots in slots_by_screen.items() if s in eligible_seats
                         for sl in slots))
    m.add(1000 * seats_g >= lo_pm * total_seats)            # linear: no division
    m.add(1000 * seats_g <= hi_pm * total_seats)
    return seats_g

Simplified. total_seats is an integer variable equal to the sum of all seats_g; tolerances are passed in and not shown.

Step 4: Add redundant structure the solver can use

With a correct model, most of the remaining work went into speed: sharing variables between rules, choosing which structures to model explicitly, and stating constraints the solver could derive but in practice does not. None of the following changes the set of optimal schedules.

• Symmetry removal. Active slots fill from the front (active[s,k+1] ≤ active[s,k]), so a screen with four shows has one representation instead of one per choice of four slots out of K.
• Minimum-cycle cut. n shows on a screen occupy at least n of the shortest shows plus n − 1 of the shortest cleanings. Stated explicitly, this bounds the number of shows per screen before a single show is placed.
• Conservation identities. Shows summed over films equal shows summed over screens, and film seat totals add up to the day's seats. Both are implied, but the linear relaxation only uses them when they are written down.
• Element tables and map-domain. Element constraints look attributes up from a slot's index variable — below, whether a slot starts in the main window — and map-domain links an integer such as the show count to one literal per value.
• Search order and tie-break. Decision strategies tell the search what to branch on first, and a deterministic tie-break makes identical requests return identical schedules.

n_s = Σ_k active[s,k]                                                    shows on screen s
n_s · (len_min + clean_min(s)) − clean_min(s)  ≤  close − open           minimum-cycle cut
Σ_g shows_g = Σ_s n_s,          Σ_g seats_g = SEATS                       conservation identities

from ortools.sat.python import cp_model

GRID = 5

def tighten(m, scr, slots, length, t_open, t_close, main_window):
    """Redundant structure: same optimum, smaller search."""
    acts = [sl["act"] for sl in slots]
    n = m.new_int_var(0, len(slots), f"n[{scr.id}]")
    m.add(n == sum(acts))
    is_n = [m.new_bool_var(f"n[{scr.id}]=={i}") for i in range(len(slots) + 1)]
    m.add_map_domain(n, is_n)                           # is_n[i] <=> n == i

    # Minimum-cycle cut: n shows need n shortest shows and n-1 shortest cleanings.
    shortest = min(length.values())
    m.add(n * (shortest + scr.clean_min) - scr.clean_min <= t_close - t_open)

    # Element table: does the slot start inside the main window?
    n_grid = (t_close - t_open) // GRID
    table = [int(main_window[0] <= t_open + GRID * i < main_window[1])
             for i in range(n_grid + 1)]
    for k, sl in enumerate(slots):
        sl["in_main"] = m.new_bool_var(f"main[{scr.id},{k}]")
        m.add_element(sl["idx"], table, sl["in_main"])

    # Search order: which slots are active first, then start times, earliest first.
    m.add_decision_strategy(acts, cp_model.CHOOSE_FIRST, cp_model.SELECT_MAX_VALUE)
    m.add_decision_strategy([sl["idx"] for sl in slots], cp_model.CHOOSE_FIRST,
                          cp_model.SELECT_MIN_VALUE)
    return n, is_n

Simplified. Times are minutes since midnight; main_window is a (from, to) pair.

These constraints earned their place the hard way: removing a redundant cut made solves several times slower. "Redundant" describes the model, not the solver.

Step 5: Solve in stages so a schedule always comes back

Some days have no schedule that satisfies every rule. Rather than return nothing, the engine walks down a fixed sequence of stages inside one total time budget, giving each stage a share of it:

• Hard only. Find any schedule that satisfies every rule.
• Hard + soft. Keep every rule and optimise the soft objective: few empty slots, few screens that mix films, and priority films inside the main window, with weights w₁, w₂, w₃.
• Relaxed hard. If the strict model has no solution, first diagnose the sessions already on sale — held exactly, then loosened to a bound, and only then ignored — and then turn relaxable rules into penalty variables with tiered prices and minimise the total penalty.
• Relaxed hard + soft. Cap the total penalty at the value the previous stage reached and optimise the soft objective under that cap, so a better-looking schedule can never buy back a broken rule.

soft(x)    = w₁ · empty_slots + w₂ · mixed_screens + w₃ · priority_outside_main

stage 1    find x                               s.t. all rules
stage 2    min soft(x)                          s.t. all rules
stage 3    min P(x) = Σ_r π_tier(r) · v_r       s.t. a_r(x) ≤ b_r + v_r,  v_r ≥ 0     relaxable rules r
stage 4    min soft(x)                          s.t. P(x) ≤ P*₃,  unrelaxable rules hard

Every stage starts from the previous stage's solution, and the hint is expanded to every variable — not only the decisions — so CP-SAT begins from a complete, consistent point instead of repairing a partial one. A schedule always comes back unless the input itself breaks a rule that may never be relaxed. Tier prices and weights encode business judgement and are written here as symbols.

from ortools.sat.python import cp_model

def run(built, seconds, workers, hint=None):
    model, vars_, penalty = built
    for name, value in (hint or {}).items():
        if name in vars_:
            model.add_hint(vars_[name], value)            # hint every variable
    solver = cp_model.CpSolver()
    solver.parameters.max_time_in_seconds = seconds
    solver.parameters.num_workers = workers
    if solver.solve(model) not in (cp_model.OPTIMAL, cp_model.FEASIBLE):
        return None
    sol = {name: solver.value(v) for name, v in vars_.items()}
    sol["__penalty"] = solver.value(penalty) if penalty is not None else 0
    return sol

def staged_solve(build, budget, workers):
    """build(stage, cap) -> (model, vars_by_name, penalty_expr or None)."""
    sol = run(build("hard", None), 0.2 * budget, workers)
    if sol is not None:                                  # every rule can hold
        better = run(build("hard+soft", None), 0.8 * budget, workers, hint=sol)
        return (better or sol), "hard+soft" if better else "hard"
    sol = run(build("relaxed", None), 0.4 * budget, workers)       # min penalty
    if sol is None:
        raise ValueError("the input breaks a rule that may never be relaxed")
    better = run(build("relaxed+soft", sol["__penalty"]), 0.6 * budget, workers,
                 hint=sol)                               # penalty <= previous value
    return (better or sol), "relaxed+soft" if better else "relaxed"

Simplified. build(stage, cap) returns a fresh model, its variables by name and the penalty expression; the pre-sold-session diagnosis lives inside build and is not shown. Time shares are illustrative.

Step 6: Validate independently and serve as an asynchronous job

The model is not trusted to grade itself. A validator, written separately from the model builder, re-checks every rule on the final timetable — gaps, windows, spacing, shares — and reports any rule that was given up during relaxation. It catches modelling mistakes that an OPTIMAL status would hide, and it tells the scheduler exactly which rule gave way on a hard day.

CHECKS = {}

def rule(name):
    def register(fn):
        CHECKS[name] = fn
        return fn
    return register

@rule("cleaning_gap")
def cleaning_gap(day):
    for screen, shows in day.shows_by_screen():
        for a, b in zip(shows, shows[1:]):
            if not screen.clean_min <= b.start - a.end <= screen.clean_max:
                yield screen.id, b.start

@rule("seat_share")
def seat_share(day):
    for group, lo, hi in day.share_bounds():
        if not lo <= day.seats(group) <= hi:
            yield group, day.seats(group)

def validate(day):
    """Run every registered rule on the final timetable, independently of the model."""
    found = {name: list(check(day)) for name, check in CHECKS.items()}
    return {name: hits for name, hits in found.items() if hits}

Simplified. Two of the rule checks; the real validator registers one check per business rule.

The engine runs as a FastAPI / uvicorn application in a Docker image (Python 3.11) inside a Kubernetes pod, with Redis alongside it. A request is accepted immediately, the solve runs in the background, and the schedule with its validation report is posted back to the caller with httpx.

import os
import httpx
from fastapi import BackgroundTasks, FastAPI

app = FastAPI()

def cpu_limit():
    """CPU quota of this container (cgroup v2), used as the CP-SAT worker count."""
    try:
        quota, period = open("/sys/fs/cgroup/cpu.max").read().split()
        return max(1, int(quota) // int(period)) if quota != "max" else os.cpu_count()
    except OSError:
        return 1

WORKERS = cpu_limit()

@app.post("/schedules", status_code=202)
def submit(req: ScheduleRequest, background: BackgroundTasks):
    job_id = jobs.create(req)                           # job state
    background.add_task(solve_job, job_id, req)
    return {"job_id": job_id}

def solve_job(job_id, req):
    day = to_inputs(req)                                # step 1
    sol, stage = staged_solve(make_builder(day), req.time_budget_s, WORKERS)
    timetable = decode(day, sol)
    result = {"stage": stage, "schedule": timetable, "violations": validate(timetable)}
    jobs.finish(job_id, result)
    httpx.post(req.callback_url, json={"job_id": job_id, **result}, timeout=30)

Simplified. Authentication, request schema, the job store and error handling are omitted; endpoint and field names are generic.

One operational finding mattered more than any search parameter: fewer CP-SAT workers cut peak memory sharply with no loss in schedule quality. The worker count therefore follows the container's CPU limit rather than the solver's default, which keeps memory per request predictable.

Step 7: Forecast occupancy alongside the scheduler

Obeying every rule is not the same as maximising revenue; that needs an estimate of how well each film will do where and when it plays, which is what the forecasting track provides. Its inputs follow what drives occupancy — film performance, site characteristics, time of day, show sequence and the number of daily screenings — and its pipeline forecasts a week ahead (D+7) for every site, film and day. Three candidates are compared:

• LightGBM with a Tweedie objective. Audience counts are non-negative, right-skewed and full of small values; the Tweedie loss models that directly and predicts on the original scale.
• LightGBM on log audience. The simple baseline: regress log(1 + y) and transform back. It is easy to fit, but back-transformed predictions underestimate the mean, which is why it serves as the reference rather than the answer.
• Temporal Fusion Transformer. An attention-based sequence model that combines static covariates such as the site, past observations and inputs known in advance, and forecasts several horizons at once.

The final forecast is chosen automatically on a held-out window — the best single model or a blend. The occupancy model reached about 10% MAE.

import numpy as np
import lightgbm as lgb
from sklearn.metrics import mean_absolute_error as mae

def fit_lgbm(X, y, Xv, yv, objective, transform=None):
    yt, yvt = (transform(y), transform(yv)) if transform else (y, yv)
    model = lgb.LGBMRegressor(objective=objective, n_estimators=3000, learning_rate=0.03)
    model.fit(X, yt, eval_set=[(Xv, yvt)],
              callbacks=[lgb.early_stopping(200, verbose=False)])
    return model

def choose_forecast(X, y, Xv, yv, tft_pred_v):
    """Compare candidates on a held-out window; keep the best model or 2-way blend."""
    tweedie = fit_lgbm(X, y, Xv, yv, "tweedie")
    log_base = fit_lgbm(X, y, Xv, yv, "regression", transform=np.log1p)
    preds = {"tweedie": tweedie.predict(Xv),
             "log_baseline": np.expm1(log_base.predict(Xv)),
             "tft": tft_pred_v}
    best = min((mae(yv, p), (name,)) for name, p in preds.items())
    names = list(preds)
    for i, a in enumerate(names):
        for b in names[i + 1:]:
            for w in np.linspace(0.1, 0.9, 9):
                score = mae(yv, w * preds[a] + (1 - w) * preds[b])
                best = min(best, (score, (a, b, round(w, 1))))
    return best                                         # (validation MAE, recipe)

Simplified. Feature building and the TFT training loop are omitted; tft_pred_v is its forecast for the validation window.

Results

The engine generates schedules that respect more than thirty business rules — something very hard to achieve by hand — and when a day cannot satisfy all of them, it still returns a schedule and says which rules gave way. The occupancy model, at about 10% MAE, gives the next step a measure of demand.

The larger shift was in the process: cinema scheduling moved from a manual, experience-driven task to a structured decision problem built from data, rules, constraints, prediction and optimization — the foundation for end-to-end, revenue-oriented scheduling.

Lessons learned

• Model the structure the rules talk about. Rules speak of shows, gaps and windows, not of minutes. A chain of optional slots made most rules one-line constraints and kept the model small.
• State what the solver cannot see. Exact domains from a dynamic program, a minimum-cycle cut and conservation identities change nothing about the optimum and a great deal about solve time.
• Design for infeasibility on day one. Real days conflict. Staged relaxation with tiered penalties, a penalty cap and full-variable hints means the scheduler always gets a schedule and a list of what was given up.
• Check the answer outside the model. An independent validator catches modelling mistakes that a solver status hides.
• More workers is not always better. Fewer CP-SAT workers cut peak memory sharply without hurting quality; matching workers to the container's CPU limit made runs predictable.

Conclusion

Cinema scheduling is a constraint problem with a revenue question inside it. Treating each screen as a chain of optional shows, measuring share in seats with exact domains, adding the redundant structure a solver needs and stepping down through relaxation stages produced an engine that writes schedules people could not write by hand — and explains itself when the rules collide.

The pattern — a slot-based CP-SAT model, staged relaxation with a penalty cap, and an independent validator — carries over to other timetabling problems with many rules and a deadline for the answer, such as shift rosters or production sequencing.

Limitations

• Penalised stages trade rules against each other through tier prices; those prices encode business judgement and have to be agreed with the people who own the rules.
• Within a fixed time budget, large days return good feasible schedules rather than proven optima.
• The occupancy forecast ran as a separate track; the revenue effect of using it inside the objective is not reported here.
• The live model encodes ten rule checks on a generated multiplex, uses a synthetic attendance curve in place of the forecast and a greedy fallback in place of the staged relaxation; its rule-of-thumb baseline is a stand-in for manual scheduling, not a record of any real theatre.

About the demo and confidentiality

Screens, seat counts, films, runtimes, targets and the attendance curve in the embedded model are generated from a seed. No theatre, layout, rule-code mapping, interface field, penalty price, objective weight, target share, attendance figure or backtest result from the real project appears in this post — prices and weights are written as symbols. Code is simplified and written for illustration; it is not the production engine.