Interval assignment

Assign tasks with fixed start/end times to a minimum-cost set of resources, with a minimum gap between consecutive tasks on the same resource and — optionally — a location-connection rule (a resource can only take a task that starts where its previous task ended). Real instances: aircraft rotations (gap = turnaround), crew lines of flying, gate allocation, vehicle/driver duty chaining, machine reservations.

One function; optional columns opt into complexity across four regimes:

#

locations

resources

example

model

1

no

no

single fleet, single base

pairwise conflict CP-SAT

2

yes

no

single fleet, no base

min path cover on a DAG

3

no

yes

mixed fleet, single base

pairwise + typed used-vars

4

yes

yes

mixed fleet, free network

per-type flow on a DAG

The connection condition subsumes the interval condition: task i can precede j on one resource iff end(i) + min_gap <= start(j) and (no locations or end_location(i) == start_location(j)). Regime 1 is regime 2 where every location is identical, so a single compatibility-arc builder drives all four models.

ortidy.scheduling.interval_assignment.interval_assignment(tasks, *, task_column='taskId', start_column='start', end_column='end', start_location_column=None, end_location_column=None, resources=None, eligibility=None, min_gap=0, time_limit=None, random_seed=0)[source]

Assign fixed-time tasks to a minimum-cost set of resources.

Parameters:

  • tasks (Any) – One row per task, with id, start, and end columns.

  • task_column (str) – Task column names.

  • start_column (str) – Task column names.

  • end_column (str) – Task column names.

  • start_location_column (str | None) – Opt in to location chaining — a resource can only take a task that starts where its previous task ended. Both must be set together (or neither).

  • end_location_column (str | None) – Opt in to location chaining — a resource can only take a task that starts where its previous task ended. Both must be set together (or neither).

  • resources (Any | None) – Opt in to a typed fleet — a frame with resourceType, count (>= 1), and fixed_cost columns. The objective becomes total fixed cost.

  • eligibility (Any | None) – Opt in to restrictions — a (taskId, resourceType) frame listing the allowed types for a task. Tasks absent from it may use any type.

  • min_gap (int) – Minimum gap between consecutive tasks on the same resource.

  • time_limit (float | None) – Optional wall-clock limit in seconds.

  • random_seed (int) – Solver seed for determinism.

Returns:

SolveResult whose frame is the input frame (same backend) plus a resourceId column (dense, numbered 0..k-1 by earliest task start) and — when resources is given — a resourceType column. Objective is the number of resources used, or total fixed_cost when typed. Regimes 3/4 can be INFEASIBLE when count caps bind.

Return type:

SolveResult