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: the data model, objectives, feasibility checking, seeds, serialization, and the solver contract.dispatchatlas.benchmarks: instance generators, published benchmark suites, and file-format readers.dispatchatlas.solvers: the solver registry and its heuristics, metaheuristics, exact methods, and learning methods.dispatchatlas.processes: pinned child processes for caller-defined calls, a resumable rows file, and process tools.dispatchatlas.campaigns: reproducible, resumable experiments.dispatchatlas.analysis: statistics, tables, figures, and reports.
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
Networkderives 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 |
tier |
str | None
|
Network endpoint group, for example |
idle_power |
float
|
Power drawn while powered on, in watts. |
busy_power |
float
|
Power drawn at full utilisation, in watts. A task holding
|
cost_rate |
float
|
Monetary cost per second of full utilisation. A task holding
|
metadata |
Metadata
|
Free-form annotations. Never read by solvers. |
Mode
dataclass
¶
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 |
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. |
on
classmethod
¶
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 |
{}
|
Returns:
| Type | Description |
|---|---|
Self
|
The task. |
Dependency
dataclass
¶
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 |
Link
dataclass
¶
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
¶
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
|
|
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.
SetupTimes
dataclass
¶
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.
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
|
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
¶
Map from task id to its position in tasks.
resource_index
cached
property
¶
Map from resource id to its position in resources.
exclusive_resources
cached
property
¶
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
¶
Indices of each task's direct predecessors.
successors
cached
property
¶
Indices of each task's direct successors.
topological_order
cached
property
¶
Task indices in a precedence-feasible order, lowest index first on ties.
groups
cached
property
¶
Task indices of each named group, in task order.
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 |
required |
target
|
str | None
|
Resource id where the successor runs, or |
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
¶
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 |
sense |
Literal['min', 'max']
|
|
unit |
str
|
Unit of the value, for example |
description |
str
|
One sentence stating what is measured. |
function |
Callable[[Problem, Schedule], float]
|
Computes the value of a schedule for a problem. |
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 |
unregister_objective
¶
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
¶
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
¶
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
¶
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 |
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.
dispatchatlas.core.schedule
¶
Schedules: when each task runs and in which mode.
Assignment
dataclass
¶
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 |
start |
float
|
Start time. |
end |
float
|
Finish time. Equals |
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. |
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
¶
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
¶
Status
¶
Bases: StrEnum
What is known about the returned schedule.
OPTIMAL
class-attribute
instance-attribute
¶
Feasible and proven optimal for the primary objective.
FEASIBLE
class-attribute
instance-attribute
¶
Feasible, optimality not proven.
VIOLATED
class-attribute
instance-attribute
¶
A schedule was built but it misses a hard deadline.
INFEASIBLE
class-attribute
instance-attribute
¶
Proven that no feasible schedule exists.
UNKNOWN
class-attribute
instance-attribute
¶
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
|
bounded
property
¶
Whether a time, evaluation, or iteration limit guarantees termination.
schedule_timed
property
¶
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 |
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
|
|
str | None
|
whose fraction is the largest among those |
str | None
|
counts, the first in that order among equals. |
str | None
|
limit. |
to_dict
¶
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
¶
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 |
objectives |
Mapping[str, float]
|
Values of every problem objective for |
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. |
gap
property
¶
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 |
name |
str
|
Human-readable name. |
family |
str
|
A key of |
summary |
str
|
One sentence describing what the solver does, in mechanism terms. |
references |
tuple[str, ...]
|
Bibliography keys (see |
stochastic |
bool
|
Whether results depend on the seed. |
iterative |
bool
|
Whether the solver runs until a stop criterion fires.
Iterative solvers require bounded |
multi_objective |
bool
|
Whether the solver optimises every problem objective and returns a Pareto front. |
supports |
frozenset[str]
|
Problem features the solver models. See
|
requires |
tuple[str, ...]
|
Optional-dependency extras the solver needs, for example
|
parameters |
Mapping[str, Any]
|
Default values of the solver's parameters. |
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.
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
¶
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 |
None
|
Yields:
| Type | Description |
|---|---|
float
|
The origin. |
Raises:
| Type | Description |
|---|---|
ValueError
|
If |
clock_start
¶
Return the instant a solver clock created now starts at.
Returns:
| Type | Description |
|---|---|
float
|
The origin set by |
float
|
|
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
¶
Domain separator mixed into every derivation.
derive_seed
¶
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 |
Raises:
| Type | Description |
|---|---|
ValueError
|
If |
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
¶
Serialise value to canonical JSON: sorted keys, no spaces, ASCII only.
Raises:
| Type | Description |
|---|---|
SerializationError
|
If |
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.
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.
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. |
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 |
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 |
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
¶
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
¶
Return the indices of the points no other point dominates.
Duplicates of a non-dominated point are all kept.
fast_non_dominated_sort
¶
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
¶
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
¶
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
¶
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
¶
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
¶
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
¶
Write UTF-8 text with LF line endings atomically. Returns the path.
atomic_write_json
¶
Write a JSON document atomically with sorted keys. Returns the path.
Raises:
| Type | Description |
|---|---|
SerializationError
|
If |
read_json
¶
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 |
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
¶
Format of a line of a SessionLog file; the time is in UTC.
LOG_FILE_LIMIT
module-attribute
¶
Most characters a SessionLog writes to its file by default.
Lowered
¶
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 |
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 |
()
|
limit
|
int
|
Most characters written to the file. |
LOG_FILE_LIMIT
|
open
¶
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
¶
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
¶
Return the library logger for a module.
Parameters:
| Name | Type | Description | Default |
|---|---|---|---|
name
|
str
|
Module name, usually |
required |
Returns:
| Type | Description |
|---|---|
Logger
|
A logger in the |
configure_logging
¶
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 |
INFO
|