Skip to content

Core

The data model, objectives, feasibility checking, seeds, serialization, and the solver contract. The core depends on nothing outside the standard library.

dispatchatlas

DispatchAtlas: reproducible benchmarking of scheduling algorithms.

The package is organised in layers:

dispatchatlas.core

Core data model and contracts shared by every DispatchAtlas package.

The core has no third-party dependencies. It defines problems (Problem, Task, Mode, Resource, Dependency), schedules, objectives, feasibility checking, seeds, serialization, and the solver contract.

dispatchatlas.core.model

The scheduling data model: resources, tasks, modes, dependencies, and problems.

One model covers classic machine scheduling, project scheduling, and task placement across a computing continuum:

  • A resource has a capacity. A machine is a resource of capacity 1. A compute node with eight cores is a resource of capacity 8.
  • A task runs in exactly one of its modes. A mode fixes the duration and the amount of each resource the task holds while it runs. Alternative machines (flexible job shops, unrelated parallel machines, placement on heterogeneous nodes) are alternative modes.
  • A dependency forces a task to start after another one finishes, plus an optional time lag and an optional data transfer whose duration a Network derives from where the two tasks run.
  • A problem bundles tasks, resources, dependencies, the objectives to optimise, and optional setup times, network, and permutation constraint.

A mode of zero duration occupies an instant. On an exclusive resource, one where every demand takes the whole capacity (a machine, typically), no other task may run across that instant, as in the disjunctive graph of shop scheduling. On other resources a zero-duration task holds nothing, as in project scheduling. In a permutation problem it also takes its place in each machine's group order, which reproduces the completion-time recurrence of the permutation flow shop for instances with zero processing times. Zero-duration modes may not use machines with setup times.

Every object is immutable. A Problem validates its whole structure when it is built, so code that receives one can rely on it being consistent.

FEATURES module-attribute

FEATURES: Mapping[str, str] = FrozenMap({'precedence': 'Some tasks must wait for others to finish.', 'lags': 'Some dependencies carry a minimum time lag.', 'modes': 'Some tasks can run in more than one mode.', 'multi-resource': 'Some modes hold more than one resource at once.', 'cumulative': 'Some resources can run several tasks at once.', 'release': 'Some tasks cannot start before a release time.', 'due': 'Some tasks carry a soft due date.', 'deadline': 'Some tasks carry a hard deadline.', 'setups': 'Some resources need sequence-dependent setup times.', 'network': 'Some dependencies transfer data across a network.', 'permutation': 'Every resource must process the task groups in one order.', 'groups': 'Tasks are grouped into jobs or applications.'})

Names of the structural features a problem can exhibit, with their meaning.

Solvers declare the features they model in SolverInfo.supports, and campaigns refuse to pair a solver with a problem that has an unsupported one.

Resource dataclass

Resource(id: str, capacity: float = 1.0, kind: str = 'machine', tier: str | None = None, idle_power: float = 0.0, busy_power: float = 0.0, cost_rate: float = 0.0, metadata: Metadata = dict())

A renewable resource that tasks hold while they run.

Attributes:

Name Type Description
id str

Unique identifier within the problem.

capacity float

Units available at any instant. 1 models a machine that runs one task at a time. Larger values model pools such as the cores of a compute node.

kind str

Free-form label such as "machine", "node", or "device".

tier str | None

Network endpoint group, for example "edge", "fog", or "cloud". Links of a Network join tiers. When absent, the resource is its own endpoint.

idle_power float

Power drawn while powered on, in watts.

busy_power float

Power drawn at full utilisation, in watts. A task holding u of capacity units adds (busy_power - idle_power) * u / capacity watts while it runs.

cost_rate float

Monetary cost per second of full utilisation. A task holding u units for d seconds costs cost_rate * d * u / capacity.

metadata Metadata

Free-form annotations. Never read by solvers.

endpoint property

endpoint: str

The network endpoint of this resource: its tier, or its own id.

unary property

unary: bool

Whether the resource runs at most one unit-demand task at a time.

Mode dataclass

Mode(duration: float, demands: Mapping[str, float] = dict(), location: str | None = None)

One way of executing a task.

Attributes:

Name Type Description
duration float

Processing time, in seconds or any consistent time unit.

demands Mapping[str, float]

Units of each resource held for the whole duration, keyed by resource id. Empty for a task that holds nothing, such as a dummy start or end task.

location str | None

Resource whose network endpoint is the task's location when a dependency transfers data. Defaults to the demanded resource when the mode demands exactly one.

Task dataclass

Task(id: str, modes: tuple[Mode, ...], release: float = 0.0, due: float | None = None, deadline: float | None = None, weight: float = 1.0, group: str | None = None, metadata: Metadata = dict())

A unit of work that runs once, in one of its modes.

Attributes:

Name Type Description
id str

Unique identifier within the problem.

modes tuple[Mode, ...]

Alternative ways of running the task. At least one.

release float

Earliest start time.

due float | None

Soft due date. Finishing later adds tardiness, which objectives such as total_tardiness penalise.

deadline float | None

Hard deadline. A schedule that finishes the task later is infeasible.

weight float

Importance used by weighted objectives. Tasks in one group must share a weight.

group str | None

Job, application, or tenant the task belongs to. Completion-time objectives are computed per group.

metadata Metadata

Free-form annotations. Never read by solvers.

min_duration property

min_duration: float

The shortest duration over the task's modes.

on classmethod

on(task_id: str, resource: str, duration: float, *, demand: float = 1.0, **attributes: Any) -> Self

Build a single-mode task that holds demand units of one resource.

Parameters:

Name Type Description Default
task_id str

Task identifier.

required
resource str

Identifier of the resource the task runs on.

required
duration float

Processing time.

required
demand float

Units of the resource held while running.

1.0
**attributes Any

Further Task fields, such as release.

{}

Returns:

Type Description
Self

The task.

Dependency dataclass

Dependency(before: str, after: str, lag: float = 0.0, data: float = 0.0)

A finish-to-start precedence between two tasks.

The after task may start once the before task has finished, the lag has elapsed, and data units have crossed the network between the two tasks' locations.

Attributes:

Name Type Description
before str

Id of the predecessor.

after str

Id of the successor.

lag float

Minimum time between the predecessor's finish and the successor's start.

data float

Volume the predecessor sends to the successor. Transfer time is derived from the problem's Network. Ignored without one.

Link(a: str, b: str, bandwidth: float = inf, latency: float = 0.0, energy_per_unit: float = 0.0, cost_per_unit: float = 0.0)

A symmetric network link between two endpoints.

Endpoints are resource tiers, or resource ids for resources without a tier. A link from an endpoint to itself describes transfers between two different resources of the same tier.

Attributes:

Name Type Description
a str

First endpoint.

b str

Second endpoint.

bandwidth float

Data units per second. Infinite bandwidth leaves only latency.

latency float

Fixed delay added to every transfer, in seconds.

energy_per_unit float

Energy spent per data unit transferred, in joules.

cost_per_unit float

Monetary cost per data unit transferred.

transfer_time

transfer_time(data: float) -> float

Return the time to move data units across this link.

Parameters:

Name Type Description Default
data float

Volume to transfer. Zero means nothing is sent.

required

Returns:

Type Description
float

latency + data / bandwidth, or zero when data is zero.

Network dataclass

Network(links: tuple[Link, ...] = ())

The links that carry data between task locations.

Two tasks placed on the same resource exchange data instantly. Otherwise the transfer uses the link between the endpoints of the two resources.

endpoints property

endpoints: frozenset[str]

Every endpoint named by a link.

link(a: str, b: str) -> Link | None

Return the link joining endpoints a and b, if one exists.

SetupTimes dataclass

SetupTimes(times: Mapping[tuple[str, str | None, str], float] = dict())

Sequence-dependent setup times on machines.

times[(resource, previous, following)] is the idle time resource needs after finishing previous before it can start following. A previous of None gives the setup before the first task on the resource. Missing entries mean no setup. Setups apply to resources of capacity 1 only.

resources cached property

resources: frozenset[str]

Resources that have at least one non-zero setup time.

get

get(resource: str, previous: str | None, following: str) -> float

Return the setup time for following after previous on resource.

Problem dataclass

Problem(id: str, tasks: tuple[Task, ...], resources: tuple[Resource, ...], dependencies: tuple[Dependency, ...] = (), objectives: tuple[str, ...] = ('makespan',), network: Network | None = None, setups: SetupTimes | None = None, permutation: bool = False, family: str | None = None, metadata: Metadata = dict())

A complete scheduling problem.

Building a problem validates its whole structure. Invalid input raises ModelError listing every defect.

Attributes:

Name Type Description
id str

Problem identifier, used in file names and result records.

tasks tuple[Task, ...]

The tasks to schedule. Their order is the task index order that solvers use.

resources tuple[Resource, ...]

The resources tasks hold.

dependencies tuple[Dependency, ...]

Finish-to-start precedences. Must form an acyclic graph.

objectives tuple[str, ...]

Names of the objectives to optimise, primary first. See dispatchatlas.core.objectives for the registry.

network Network | None

Links used to price data transfers along dependencies.

setups SetupTimes | None

Sequence-dependent setup times on machines.

permutation bool

Whether every resource must process the task groups in one common order, as in the permutation flow shop. A task without a group forms a group of its own. Permutation problems use capacity-1 machines held whole, and each group uses a machine in at most one of its tasks.

family str | None

Id of the benchmark family that generated the problem, if any.

metadata Metadata

Free-form annotations such as generator parameters. Never read by solvers.

task_index cached property

task_index: Mapping[str, int]

Map from task id to its position in tasks.

resource_index cached property

resource_index: Mapping[str, int]

Map from resource id to its position in resources.

exclusive_resources cached property

exclusive_resources: frozenset[str]

Ids of the demanded resources where every demand takes the whole capacity.

Tasks never overlap on such a resource, and a zero-duration task occupies an instant that no other task on it may run across.

incoming cached property

incoming: tuple[tuple[Dependency, ...], ...]

Dependencies ending at each task, indexed like tasks.

predecessors cached property

predecessors: tuple[tuple[int, ...], ...]

Indices of each task's direct predecessors.

successors cached property

successors: tuple[tuple[int, ...], ...]

Indices of each task's direct successors.

topological_order cached property

topological_order: tuple[int, ...]

Task indices in a precedence-feasible order, lowest index first on ties.

groups cached property

groups: Mapping[str, tuple[int, ...]]

Task indices of each named group, in task order.

features cached property

features: frozenset[str]

The structural features the problem exhibits. See FEATURES.

size property

size: int

Number of tasks.

task

task(task_id: str) -> Task

Return the task with the given id.

resource

resource(resource_id: str) -> Resource

Return the resource with the given id.

transfer_time

transfer_time(dependency: Dependency, source: str | None, target: str | None) -> float

Return the data-transfer time of a dependency between two locations.

Parameters:

Name Type Description Default
dependency Dependency

The dependency whose data moves.

required
source str | None

Resource id where the predecessor ran, or None.

required
target str | None

Resource id where the successor runs, or None.

required

Returns:

Type Description
float

Zero when there is no network, no data, no known location, or both

float

tasks share a resource. Otherwise the link's transfer time.

with_objectives

with_objectives(*objectives: str) -> Problem

Return a copy that optimises the given objectives, primary first.

renamed

renamed(problem_id: str) -> Problem

Return a copy with another id.

The structure is unchanged, so the copy skips validation, which matters for large generated problems.

summary

summary() -> dict[str, Any]

Return headline counts that describe the problem's size and shape.

dispatchatlas.core.objectives

Objective functions and their registry.

Every objective maps a problem and a schedule to one number. Solvers, campaigns, and analyses look objectives up by name, so a plugin can add one with register_objective() and use it everywhere.

Completion-time objectives are computed per job: the tasks that share a group, or a single task without one. Due-date objectives are computed per task, so a job's due date belongs on its final task.

Objective dataclass

Objective(name: str, sense: Literal['min', 'max'], unit: str, description: str, function: Callable[[Problem, Schedule], float])

A named objective function.

Attributes:

Name Type Description
name str

Registry key, for example "makespan".

sense Literal['min', 'max']

"min" to minimise or "max" to maximise.

unit str

Unit of the value, for example "time".

description str

One sentence stating what is measured.

function Callable[[Problem, Schedule], float]

Computes the value of a schedule for a problem.

minimized

minimized(value: float) -> float

Return value oriented so that smaller is better.

register_objective

register_objective(objective: Objective, *, replace: bool = False) -> None

Add an objective to the registry.

Parameters:

Name Type Description Default
objective Objective

The objective to add.

required
replace bool

Allow replacing an objective registered under the same name.

False

Raises:

Type Description
ModelError

If the name is taken and replace is false, or the sense is not "min" or "max".

unregister_objective

unregister_objective(name: str) -> None

Remove an objective that a plugin registered.

Removing a plugin's replacement of a built-in objective restores the library's definition. The library's own definitions cannot be removed.

Raises:

Type Description
ModelError

If no objective of that name is registered, or it is a built-in objective with the library's definition.

is_registered

is_registered(name: str) -> bool

Return whether an objective of that name is registered.

get_objective

get_objective(name: str) -> Objective

Return the registered objective called name.

Raises:

Type Description
ModelError

If no such objective is registered.

registered_objectives

registered_objectives() -> tuple[Objective, ...]

Return every registered objective, sorted by name.

is_built_in

is_built_in(name: str) -> bool

Return whether name is registered with the library's own definition.

evaluate

evaluate(problem: Problem, schedule: Schedule, names: Iterable[str] | None = None) -> dict[str, float]

Compute objective values of a schedule.

Parameters:

Name Type Description Default
problem Problem

The problem the schedule solves.

required
schedule Schedule

The schedule to evaluate.

required
names Iterable[str] | None

Objectives to compute. Defaults to the problem's objectives.

None

Returns:

Type Description
dict[str, float]

Objective values keyed by name, in the requested order.

dispatchatlas.core.validation

Feasibility checking of schedules against problems.

check_schedule() reports every constraint a schedule breaks. It is independent of the schedule builders in dispatchatlas.solvers, so tests use it as an oracle for them.

DEFAULT_TOLERANCE module-attribute

DEFAULT_TOLERANCE = 1e-06

Absolute slack allowed in time and capacity comparisons.

Violation dataclass

Violation(code: str, message: str, task: str | None = None, resource: str | None = None, amount: float = 0.0)

One broken constraint.

Attributes:

Name Type Description
code str

Machine-readable kind, for example "precedence".

message str

Human-readable description.

task str | None

Id of the task involved, when there is one.

resource str | None

Id of the resource involved, when there is one.

amount float

Size of the violation in the constraint's unit.

check_schedule

check_schedule(problem: Problem, schedule: Schedule, *, tolerance: float = DEFAULT_TOLERANCE) -> tuple[Violation, ...]

Return every constraint of problem that schedule violates.

Checked constraints: every task assigned exactly once in a valid mode, the mode's duration respected, release times, dependencies with lags and transfer times, resource capacities (including the instants zero-duration tasks occupy on exclusive resources), setup times, hard deadlines, and the permutation constraint.

Parameters:

Name Type Description Default
problem Problem

The problem.

required
schedule Schedule

The schedule to check.

required
tolerance float

Absolute slack for time and capacity comparisons.

DEFAULT_TOLERANCE

Returns:

Type Description
tuple[Violation, ...]

The violations, empty when the schedule is feasible.

is_feasible

is_feasible(problem: Problem, schedule: Schedule, *, tolerance: float = DEFAULT_TOLERANCE) -> bool

Return whether schedule violates no constraint of problem.

deadline_excess

deadline_excess(problem: Problem, schedule: Schedule) -> float

Return the total time by which tasks overrun their hard deadlines.

dispatchatlas.core.schedule

Schedules: when each task runs and in which mode.

Assignment dataclass

Assignment(task: str, mode: int, start: float, end: float)

The execution of one task.

Attributes:

Name Type Description
task str

Id of the task.

mode int

Index of the mode the task runs in, within Task.modes.

start float

Start time.

end float

Finish time. Equals start plus the mode's duration in a valid schedule.

duration property

duration: float

Time between start and finish.

Schedule dataclass

Schedule(assignments: tuple[Assignment, ...])

A set of task assignments, ordered by start time and then task id.

A schedule records decisions only. Whether it respects a problem's constraints is checked by dispatchatlas.core.validation.check_schedule().

by_task cached property

by_task: Mapping[str, Assignment]

Assignments keyed by task id.

Raises:

Type Description
ModelError

If a task is assigned more than once.

makespan property

makespan: float

Latest finish time, or zero for an empty schedule.

of classmethod

of(assignments: Iterable[Assignment]) -> Schedule

Build a schedule from any iterable of assignments.

dispatchatlas.core.solver

The solver contract: stop criteria, results, metadata, and the protocol.

A solver is any object with an info attribute and a solve() method. The library's own solvers and third-party plugins implement the same contract, so campaigns and analyses treat them alike.

SOLVER_FAMILIES module-attribute

SOLVER_FAMILIES: Mapping[str, str] = FrozenMap({'dispatching-rule': 'Builds one schedule from a fixed priority rule.', 'list-scheduling': 'Ranks tasks, then maps each to the resource that finishes it first.', 'constructive': 'Builds a schedule step by step with look-ahead or insertion.', 'local-search': 'Improves one solution through neighbourhood moves.', 'population': 'Evolves a population of solutions through variation and selection.', 'swarm': 'Moves a population of real-valued priority vectors by update rules.', 'multi-objective': 'Approximates the Pareto front of several objectives.', 'exact': 'Proves optimality or infeasibility with a mathematical model.', 'matheuristic': 'Improves a solution by solving restricted subproblems exactly.', 'learning': 'Learns a scheduling policy from experience gathered while solving.', 'hyper-heuristic': 'Searches over heuristics rather than over schedules.', 'random-sampling': 'Draws random solutions and keeps the best, as a baseline.'})

Standard solver families. Plugins may use other kebab-case family names.

SCHEDULES module-attribute

SCHEDULES = ('deterministic', 'binding')

The clocks a parameter schedule can follow, the default first.

"deterministic" places a run on its schedule by its evaluations and iterations whenever an evaluation or iteration limit is set, and by the elapsed time only when the time limit is the only limit. "binding" counts every limit that is set, so the schedule follows whichever of them is nearest.

StopReason

Bases: StrEnum

Why a solver stopped.

COMPLETED class-attribute instance-attribute

COMPLETED = 'completed'

The algorithm finished on its own, for example a constructive heuristic.

STAGNATION class-attribute instance-attribute

STAGNATION = 'stagnation'

No improvement for patience iterations.

Status

Bases: StrEnum

What is known about the returned schedule.

OPTIMAL class-attribute instance-attribute

OPTIMAL = 'optimal'

Feasible and proven optimal for the primary objective.

FEASIBLE class-attribute instance-attribute

FEASIBLE = 'feasible'

Feasible, optimality not proven.

VIOLATED class-attribute instance-attribute

VIOLATED = 'violated'

A schedule was built but it misses a hard deadline.

INFEASIBLE class-attribute instance-attribute

INFEASIBLE = 'infeasible'

Proven that no feasible schedule exists.

UNKNOWN class-attribute instance-attribute

UNKNOWN = 'unknown'

No schedule found and infeasibility not proven.

StopCriteria dataclass

StopCriteria(time_limit: float | None = None, max_evaluations: int | None = None, max_iterations: int | None = None, target: float | None = None, patience: int | None = None, schedule: Literal['deterministic', 'binding'] = 'deterministic')

When an iterative solver must stop. The first criterion met ends the run.

Attributes:

Name Type Description
time_limit float | None

Wall-clock seconds.

max_evaluations int | None

Schedules built and scored.

max_iterations int | None

Main-loop iterations, as each solver defines them.

target float | None

Stop once the primary objective reaches this value or better.

patience int | None

Stop after this many iterations without improvement.

schedule Literal['deterministic', 'binding']

Which clock a parameter schedule follows, one of SCHEDULES. It ends no run: it decides how progress() places a run on a schedule such as a falling exploration rate. With "deterministic", a run under an evaluation or iteration limit follows the same schedule on every machine, and the schedule stops short of its end when the time limit ends the run first. With "binding", the schedule reaches its end at whichever limit ends the run, and where it is at a given evaluation depends on the speed and load of the machine whenever a time limit is set.

bounded property

bounded: bool

Whether a time, evaluation, or iteration limit guarantees termination.

schedule_timed property

schedule_timed: bool

Whether a parameter schedule reads the elapsed time under these criteria.

It does when a time limit is set and schedule is "binding" or no evaluation or iteration limit is set. What a solver that follows a schedule does before it stops then depends on the speed and load of the machine.

progress

progress(evaluations: int, iterations: int, elapsed: float, *, deterministic: bool | None = None) -> float

Return the fraction of the binding budget a run has used, in [0, 1].

The fraction is the largest of evaluations over the evaluation limit, iterations over the iteration limit, and elapsed seconds over the time limit, among the limits schedule counts, so with "binding" it reaches 1 when the first of them ends the run. The target and the patience end runs at points no one can predict and play no part. Without a limit the fraction is 0.

Parameters:

Name Type Description Default
evaluations int

Evaluations so far.

required
iterations int

Iterations started so far.

required
elapsed float

Seconds since the run started.

required
deterministic bool | None

Overrides schedule for this reading: True counts the time limit only when neither an evaluation nor an iteration limit is set, and False counts every set limit. None, the default, follows schedule.

None

schedule_clock

schedule_clock(evaluations: int, iterations: int, elapsed: float, *, deterministic: bool | None = None) -> str | None

Return which clock gives progress() its value at this point of a run.

Takes the arguments of progress().

Returns:

Type Description
str | None

"evaluations", "iterations", or "time": the limit

str | None

whose fraction is the largest among those schedule

str | None

counts, the first in that order among equals. None without a

str | None

limit.

to_dict

to_dict() -> dict[str, Any]

Return the criteria that are set, as a JSON-ready dictionary.

schedule is written only when it is not the default, so it enters the identity of a campaign only when a protocol sets it.

from_dict classmethod

from_dict(values: Mapping[str, Any]) -> StopCriteria

Build criteria from a dictionary such as to_dict() returns.

TracePoint dataclass

TracePoint(elapsed: float, evaluations: int, iteration: int, value: float, feasible: bool = True)

The best solution found so far, sampled when it improves.

Attributes:

Name Type Description
elapsed float

Seconds since the run started.

evaluations int

Schedules evaluated so far.

iteration int

Main-loop iteration.

value float

Primary objective of the best schedule so far.

feasible bool

Whether that schedule meets every hard deadline.

FrontPoint dataclass

FrontPoint(values: tuple[float, ...], schedule: Schedule | None = None)

One non-dominated solution of a multi-objective run.

Attributes:

Name Type Description
values tuple[float, ...]

Objective values in the problem's objective order.

schedule Schedule | None

The schedule that achieves them.

SolveResult dataclass

SolveResult(solver: str, problem: str, objective: str, status: Status, schedule: Schedule | None, objectives: Mapping[str, float], stop_reason: StopReason, elapsed: float, evaluations: int = 0, iterations: int = 0, bound: float | None = None, trace: tuple[TracePoint, ...] = (), front: tuple[FrontPoint, ...] = (), extras: Mapping[str, Scalar] = dict())

The outcome of one solver run.

Attributes:

Name Type Description
solver str

Id of the solver.

problem str

Id of the problem.

objective str

Name of the primary objective.

status Status

What is known about the schedule.

schedule Schedule | None

The best schedule found, or None.

objectives Mapping[str, float]

Values of every problem objective for schedule.

stop_reason StopReason

Why the run ended.

elapsed float

Wall-clock seconds of the run.

evaluations int

Schedules evaluated.

iterations int

Main-loop iterations.

bound float | None

Proven bound on the primary objective, for exact solvers.

trace tuple[TracePoint, ...]

Improvements of the best solution over time.

front tuple[FrontPoint, ...]

Non-dominated solutions, for multi-objective solvers.

extras Mapping[str, Scalar]

Solver-specific facts, such as a backend's raw status.

feasible property

feasible: bool

Whether the schedule meets every constraint.

value property

value: float | None

Primary objective value, or None without a schedule.

gap property

gap: float | None

Relative distance between the value and the bound, when both exist.

Computed as |value - bound| / max(|value|, 1e-9), the convention of MILP solvers.

SolverInfo dataclass

SolverInfo(id: str, name: str, family: str, summary: str, references: tuple[str, ...] = (), stochastic: bool = True, iterative: bool = True, multi_objective: bool = False, supports: frozenset[str] = frozenset(FEATURES), requires: tuple[str, ...] = (), parameters: Mapping[str, Any] = dict())

Metadata describing a solver.

Attributes:

Name Type Description
id str

Registry key in kebab case, for example "simulated-annealing".

name str

Human-readable name.

family str

A key of SOLVER_FAMILIES, or another kebab-case family.

summary str

One sentence describing what the solver does, in mechanism terms.

references tuple[str, ...]

Bibliography keys (see dispatchatlas.references), DOIs, or URLs of the sources the solver implements.

stochastic bool

Whether results depend on the seed.

iterative bool

Whether the solver runs until a stop criterion fires. Iterative solvers require bounded StopCriteria.

multi_objective bool

Whether the solver optimises every problem objective and returns a Pareto front.

supports frozenset[str]

Problem features the solver models. See FEATURES.

requires tuple[str, ...]

Optional-dependency extras the solver needs, for example ("exact",).

parameters Mapping[str, Any]

Default values of the solver's parameters.

unsupported

unsupported(problem: Problem) -> frozenset[str]

Return the features of problem this solver does not model.

accepts

accepts(problem: Problem) -> bool

Return whether this solver models every feature of problem.

Solver

Bases: Protocol

The interface every solver implements.

A solver may also define warm_up(), a method without arguments that returns nothing and does what the solver does once in a process before it can solve, such as importing a backend. A caller that times a run calls it before the clock of the run starts, as the campaign engine does, so that this work is inside the time limit of no run. solve works whether or not warm_up was called.

info property

info: SolverInfo

Metadata of the solver.

solve

solve(problem: Problem, stop: StopCriteria, seed: int = 0) -> SolveResult

Solve problem within stop using randomness derived from seed.

dispatchatlas.core.clock

The instant from which a solver run counts its time.

A solver measures its elapsed time, and checks its time limit, on a clock it creates during the run: the one of Search, of the exact solvers, or of the continuous optimisers. Each such clock starts at clock_start(). Called on its own, a solver therefore counts from the instant it creates its clock, and what it does before, such as importing a backend, is outside its elapsed time and its time limit.

Code that calls a solver can fix the origin first, with clock_origin(). Every clock created inside the block then starts at that origin, so the same time limit covers the same work for every solver: everything the solver does from the origin on. The campaign engine sets the origin when an attempt of a run starts.

clock_origin

clock_origin(origin: float | None = None) -> Iterator[float]

Start the solver clocks created inside the block at one instant.

The origin holds for the clocks created in the thread that entered the block, until the block ends. A block inside another one replaces the origin for its own duration.

A clock created inside the block counts from the origin, not from its own creation, and so does its time limit. A solver that runs several searches in turn, or gives one a share of its time limit, therefore opens a block of its own around each: with clock_origin(): starts the clocks created inside it at the instant it is entered.

Parameters:

Name Type Description Default
origin float | None

The instant, as time.perf_counter() counts. Defaults to the instant the block is entered.

None

Yields:

Type Description
float

The origin.

Raises:

Type Description
ValueError

If origin is not a finite number, or is later than the current reading of time.perf_counter(), as a reading of another clock would be.

clock_start

clock_start() -> float

Return the instant a solver clock created now starts at.

Returns:

Type Description
float

The origin set by clock_origin(), or the current reading of

float

time.perf_counter() when none is set.

dispatchatlas.core.seeds

Deterministic seed derivation.

Experiments draw every random stream from a single root seed. A stream is addressed by a namespace, such as "run:flow-shop-3:simulated-annealing", and an index, such as a repetition number. Equal coordinates always give the same seed on every platform, and different coordinates give independent seeds, so adding a solver to an experiment never shifts another solver's randomness.

SEED_DOMAIN module-attribute

SEED_DOMAIN = 'dispatchatlas.seed.v1'

Domain separator mixed into every derivation.

MAX_SEED module-attribute

MAX_SEED = 2 ** 63 - 1

Largest seed value derive_seed() returns.

derive_seed

derive_seed(root: int, namespace: str, index: int = 0) -> int

Derive a seed from a root seed, a namespace, and an index.

The seed is the first eight bytes, read big-endian, of the SHA-256 digest of "dispatchatlas.seed.v1\0{root}\0{namespace}\0{index}", reduced modulo 2**63.

Parameters:

Name Type Description Default
root int

Non-negative root seed of the experiment.

required
namespace str

Non-empty name of the stream. Surrounding whitespace is ignored.

required
index int

Non-negative position within the stream.

0

Returns:

Type Description
int

A seed in [0, 2**63 - 1].

Raises:

Type Description
ValueError

If root or index is negative or not an integer, or namespace is empty.

dispatchatlas.core.serialization

JSON formats for problems, schedules, and solver results, and canonical hashing.

Problem documents are the interchange format of DispatchAtlas: generators write them, campaigns store them, and every solver reads them. Fields equal to their default are omitted, so small problems stay readable.

Example document:

{
  "format": "dispatchatlas.problem",
  "version": 1,
  "id": "two-jobs",
  "objectives": ["makespan"],
  "resources": [{"id": "m1"}],
  "tasks": [
    {"id": "a", "modes": [{"duration": 3.0, "demands": {"m1": 1.0}}]},
    {"id": "b", "modes": [{"duration": 2.0, "demands": {"m1": 1.0}}]}
  ],
  "dependencies": [{"before": "a", "after": "b"}]
}

A schedule document lists [task, mode, start, end] rows. A result document holds every field of a SolveResult, its schedules as schedule documents and its trace as [elapsed, evaluations, iteration, value, feasible] rows, and, when the writer knows them, how the run was made: the digest of the problem, the stop criteria, the seed, and the solver's parameters.

canonical_json

canonical_json(value: Any) -> str

Serialise value to canonical JSON: sorted keys, no spaces, ASCII only.

Raises:

Type Description
SerializationError

If value holds NaN, infinity, or a type JSON cannot represent.

digest

digest(value: Any) -> str

Return the SHA-256 hex digest of value's canonical JSON.

problem_to_dict

problem_to_dict(problem: Problem) -> dict[str, Any]

Convert a problem to a JSON-ready dictionary.

problem_from_dict

problem_from_dict(document: Mapping[str, Any]) -> Problem

Build a problem from a dictionary produced by problem_to_dict().

Raises:

Type Description
SerializationError

If the document is not a problem document of a supported version, or its content is invalid.

dumps_problem

dumps_problem(problem: Problem, *, indent: int | None = 2) -> str

Serialise a problem to a JSON string.

loads_problem

loads_problem(text: str) -> Problem

Parse a problem from a JSON string.

save_problem

save_problem(problem: Problem, path: str | Path, *, indent: int | None = 2) -> Path

Write a problem to a JSON file and return its path.

load_problem

load_problem(path: str | Path) -> Problem

Read a problem from a JSON file.

problem_digest

problem_digest(problem: Problem) -> str

Return the SHA-256 digest of a problem's canonical JSON form.

schedule_to_dict

schedule_to_dict(schedule: Schedule, problem_id: str | None = None) -> dict[str, Any]

Convert a schedule to a JSON-ready dictionary of compact rows.

schedule_from_dict

schedule_from_dict(document: Mapping[str, Any]) -> Schedule

Build a schedule from a dictionary produced by schedule_to_dict().

save_schedule

save_schedule(schedule: Schedule, path: str | Path, problem_id: str | None = None) -> Path

Write a schedule to a JSON file and return its path.

Raises:

Type Description
SerializationError

If the schedule holds a value JSON cannot represent, such as a non-finite time.

load_schedule

load_schedule(path: str | Path) -> Schedule

Read a schedule from a JSON file.

result_to_dict

result_to_dict(result: SolveResult, *, problem: Problem | None = None, stop: StopCriteria | None = None, seed: int | None = None, parameters: Mapping[str, Any] | None = None) -> dict[str, Any]

Convert a solver result to a JSON-ready dictionary.

Every field of the result is written. The keyword arguments record how the run was made, which the result itself does not say; each is written only when given, as problem_digest, stop, seed, and parameters.

Parameters:

Name Type Description Default
result SolveResult

The result.

required
problem Problem | None

The problem solved, whose digest identifies it beyond its id.

None
stop StopCriteria | None

The stop criteria of the run.

None
seed int | None

The seed of the run.

None
parameters Mapping[str, Any] | None

The solver's parameters.

None

Raises:

Type Description
SerializationError

If problem is not the problem the result names.

result_from_dict

result_from_dict(document: Mapping[str, Any]) -> SolveResult

Build a solver result from a dictionary produced by result_to_dict().

How the run was made (problem_digest, stop, seed, and parameters) is not part of a result; read it from the document.

Raises:

Type Description
SerializationError

If the document is not a result document of a supported version, or a field is missing or holds a value of the wrong type.

save_result

save_result(result: SolveResult, path: str | Path, *, problem: Problem | None = None, stop: StopCriteria | None = None, seed: int | None = None, parameters: Mapping[str, Any] | None = None) -> Path

Write a solver result to a JSON file and return its path.

The keyword arguments are those of result_to_dict().

Raises:

Type Description
SerializationError

If the result holds a value JSON cannot represent, such as a number that is not finite, or problem does not match.

load_result

load_result(path: str | Path) -> SolveResult

Read a solver result from a JSON file.

dispatchatlas.core.pareto

Pareto dominance on minimisation vectors.

Every function here assumes that smaller is better in every coordinate. Use dispatchatlas.core.objectives.Objective.minimized() to orient values of maximised objectives first.

dominates

dominates(a: Vector, b: Vector) -> bool

Return whether a Pareto-dominates b.

a dominates b when it is no worse in every coordinate and strictly better in at least one.

non_dominated

non_dominated(points: Sequence[Vector]) -> list[int]

Return the indices of the points no other point dominates.

Duplicates of a non-dominated point are all kept.

fast_non_dominated_sort

fast_non_dominated_sort(points: Sequence[Vector]) -> list[list[int]]

Partition point indices into successive non-dominated fronts.

Implements the sorting procedure of Deb, Pratap, Agarwal and Meyarivan (2002), NSGA-II, doi:10.1109/4235.996017.

Returns:

Type Description
list[list[int]]

Fronts in rank order. The first front holds the non-dominated points.

crowding_distance

crowding_distance(points: Sequence[Vector]) -> list[float]

Return the NSGA-II crowding distance of every point in one front.

Boundary points in any coordinate get infinite distance. Coordinates with zero spread contribute nothing.

hypervolume

hypervolume(points: Sequence[Vector], reference: Vector) -> float

Return the volume that points dominate, bounded by reference.

Points that are not strictly below the reference in every coordinate add nothing. The result is exact in any dimension: two coordinates use a sweep over the staircase, more coordinates slice along the last one (While, Hingston, Barone and Huband 2006, doi:10.1109/TEVC.2005.851275). The cost grows as n ** (d - 1), which suits the front sizes of scheduling experiments.

Parameters:

Name Type Description Default
points Sequence[Vector]

Objective vectors in minimisation form.

required
reference Vector

A point that every counted vector must dominate.

required

Returns:

Type Description
float

The hypervolume, zero for an empty set.

dispatchatlas.core.errors

Exception hierarchy shared by every DispatchAtlas package.

Every error raised on purpose by the library derives from DispatchAtlasError, so callers can catch the whole family with one clause. The concrete classes also derive from the matching built-in exception (ValueError, RuntimeError, ImportError), so generic handlers keep working.

DispatchAtlasError

Bases: Exception

Base class of every error raised on purpose by DispatchAtlas.

ModelError

ModelError(message: str, issues: tuple[str, ...] = ())

Bases: DispatchAtlasError, ValueError

A problem, task, resource, or schedule violates the data model.

Attributes:

Name Type Description
issues

One human-readable line per detected defect. A problem that fails several checks reports all of them at once.

SerializationError

Bases: DispatchAtlasError, ValueError

A document cannot be read or written in a DispatchAtlas format.

ConfigError

Bases: DispatchAtlasError, ValueError

A configuration file or parameter set is invalid.

SolverError

Bases: DispatchAtlasError, RuntimeError

A solver cannot run as requested, for example with unbounded stop criteria.

UnsupportedProblemError

Bases: SolverError

A solver was asked to solve a problem with features it does not model.

MissingDependencyError

MissingDependencyError(package: str, extra: str, feature: str)

Bases: DispatchAtlasError, ImportError

An optional third-party package required by a feature is not installed.

The message names the package and the extra of DispatchAtlas that provides it, for example exact for OR-Tools.

dispatchatlas.core.io

File helpers: atomic writes and JSON documents.

atomic_write_bytes

atomic_write_bytes(path: Path, data: bytes) -> Path

Write data to path so readers never see a partial file.

The data goes to a temporary file in the same directory, is flushed to disk, and then replaces path in one step.

Returns:

Type Description
Path

The path written.

atomic_write_text

atomic_write_text(path: Path, text: str) -> Path

Write UTF-8 text with LF line endings atomically. Returns the path.

atomic_write_json

atomic_write_json(path: Path, value: Any, *, indent: int | None = 2) -> Path

Write a JSON document atomically with sorted keys. Returns the path.

Raises:

Type Description
SerializationError

If value cannot be represented in JSON.

read_json

read_json(path: Path) -> Any

Read a JSON document.

Raises:

Type Description
SerializationError

If the file is not UTF-8 text or not valid JSON.

OSError

If the file cannot be opened or read. The error names the file in its filename, also when the operating system refuses the read of an open file and names none.

dispatchatlas.core.logs

Logging helpers.

The library logs through the standard logging module under the dispatchatlas logger and sends nothing to a stream of its own accord, so applications decide what is shown. configure_logging() is a convenience for scripts and the command line. SessionLog writes what is logged during one piece of work, such as a campaign session, to a file with UTC time stamps, and Lowered lets chosen loggers record from a lower level meanwhile. Neither changes what the other handlers show.

LOG_FORMAT module-attribute

LOG_FORMAT = '%(asctime)s %(levelname)s %(name)s: %(message)s'

Format of a line of a SessionLog file; the time is in UTC.

LOG_FILE_LIMIT module-attribute

LOG_FILE_LIMIT = 1 << 26

Most characters a SessionLog writes to its file by default.

Lowered

Lowered(names: Sequence[str], level: int)

Lets loggers record from a lower level while a with block runs, and shows no more.

Each logger of names that lets fewer records through than level asks for gets that level for the block; a logger that lets them through already is left alone. Every handler the records of such a logger can reach, on the logger, on the loggers above it as far as its records propagate, and on the loggers below it, gets a filter for the block. The filter holds back what the lowering added and nothing else: a record of a lowered logger, or of a logger below one, passes when its logger let it through before the block, and a record of any other logger passes always. Those handlers therefore show inside the block what they show outside it, and the block leaves the levels and the filters as it found them. A handler that is added inside the block is not filtered.

Parameters:

Name Type Description Default
names Sequence[str]

Names of the loggers to lower.

required
level int

The level they are lowered to.

required

apply

apply() -> None

Lower the loggers and filter the handlers their records reach.

undo

undo() -> None

Give the loggers the levels they had and take the filter off the handlers.

SessionLog

SessionLog(level: int = INFO, *, lowered: Sequence[str] = (), limit: int = LOG_FILE_LIMIT)

A file that receives what the library logs while a with block runs.

Inside the block every record of level or higher that reaches the dispatchatlas logger is kept, and open() names the file: the records kept so far are written to it, and every later one as it arrives. Each line states the UTC time of its record to the millisecond, the level, the logger, and the message (LOG_FORMAT). The file is appended to, never replaced. A block that ends before open() writes nothing.

The loggers of lowered record from level inside the block, as Lowered arranges it, so what the other handlers show stays as it was. Every other logger of the library keeps its level, and the file receives from it what it lets through anyway: a record that is not made costs the code that would log it next to nothing, and one that is made costs its making and one buffered write.

The file is written through a buffer. A record of the level WARNING or higher is on disk when it is written, and so is a record that arrives a second or more after the last one that was; the records of a burst below WARNING reach the disk with the next such record or at the end of the block. At most limit characters are written: later records are counted, and the last line of the file states how many were left out.

Parameters:

Name Type Description Default
level int

Lowest level of the records the file receives.

INFO
lowered Sequence[str]

Names of the loggers that record from level inside the block.

()
limit int

Most characters written to the file.

LOG_FILE_LIMIT

open

open(path: str | Path) -> Path

Write the records kept so far, and every later one, to path.

Parameters:

Name Type Description Default
path str | Path

The log file. Its directory is created when missing.

required

Returns:

Type Description
Path

The path.

write

write(created: float, level: int, name: str, message: str) -> None

Add a record that did not reach the loggers of this process.

The record goes to the file only, with its own time, so a worker process can hand over what it logged.

Parameters:

Name Type Description Default
created float

When the record was made, in seconds since the epoch.

required
level int

Level of the record.

required
name str

Name of its logger.

required
message str

Its message.

required

get_logger

get_logger(name: str) -> Logger

Return the library logger for a module.

Parameters:

Name Type Description Default
name str

Module name, usually __name__. Names outside the dispatchatlas package are nested under it.

required

Returns:

Type Description
Logger

A logger in the dispatchatlas hierarchy.

configure_logging

configure_logging(level: int | str = INFO) -> None

Send library log records to standard error with a compact format.

Calling it more than once replaces the handler it installed before.

Parameters:

Name Type Description Default
level int | str

Minimum level to show, as a number or a name such as "DEBUG".

INFO