Solver framework¶
The registry, the search run-time every order-based solver uses, the shared schedule builder and evaluator, the vector encodings, the variation operators, and the priority attributes.
dispatchatlas.solvers
¶
Solvers, the solver registry, and the shared search machinery.
Look solvers up by id through default_registry(), or call solve()
directly:
from dispatchatlas.solvers import solve
result = solve(problem, "simulated-annealing", time_limit=5.0, seed=1)
Building blocks for new solvers: Decoder
(orders to schedules), Search (budget,
incumbent, trace), operators, and
encoding.
solve
¶
solve(problem: Problem, solver: str, *, time_limit: float | None = None, max_evaluations: int | None = None, max_iterations: int | None = None, target: float | None = None, patience: int | None = None, seed: int = 0, **parameters: Any) -> SolveResult
Solve a problem with a registered solver.
Parameters:
| Name | Type | Description | Default |
|---|---|---|---|
problem
|
Problem
|
The problem. |
required |
solver
|
str
|
Registered solver id, for example |
required |
time_limit
|
float | None
|
Wall-clock limit in seconds. |
None
|
max_evaluations
|
int | None
|
Limit on evaluated schedules. |
None
|
max_iterations
|
int | None
|
Limit on main-loop iterations. |
None
|
target
|
float | None
|
Stop once the primary objective reaches this value. |
None
|
patience
|
int | None
|
Stop after this many iterations without improvement. |
None
|
seed
|
int
|
Seed of the run. |
0
|
**parameters
|
Any
|
Solver parameters. |
{}
|
Returns:
| Type | Description |
|---|---|
SolveResult
|
The solver's result. |
dispatchatlas.solvers.registry
¶
The solver registry and plugin discovery.
Solvers register a class (or any factory) together with its
SolverInfo. The default registry holds every
built-in solver and, unless disabled, the solvers that installed packages
publish under the dispatchatlas.solvers entry-point group.
A plugin package declares, in its pyproject.toml:
where register(registry) calls SolverRegistry.register() for each of
its solvers.
PLUGIN_GROUP
module-attribute
¶
Entry-point group scanned for solver plugins.
BUILT_IN_MODULES
module-attribute
¶
BUILT_IN_MODULES: tuple[str, ...] = ('dispatchatlas.solvers.rules', 'dispatchatlas.solvers.constructive', 'dispatchatlas.solvers.trajectory', 'dispatchatlas.solvers.population', 'dispatchatlas.solvers.continuous', 'dispatchatlas.solvers.swarm', 'dispatchatlas.solvers.multiobjective', 'dispatchatlas.solvers.learning', 'dispatchatlas.solvers.exact', 'dispatchatlas.solvers.hybrid')
Modules whose register(registry) function adds the built-in solvers.
SolverRegistry
¶
A collection of solvers addressable by id.
register
¶
register(factory: SolverFactory, info: SolverInfo | None = None, *, replace_existing: bool = False) -> None
Add a solver.
Parameters:
| Name | Type | Description | Default |
|---|---|---|---|
factory
|
SolverFactory
|
Callable that builds the solver from keyword parameters. Usually the solver's dataclass. |
required |
info
|
SolverInfo | None
|
The solver's metadata. Defaults to |
None
|
replace_existing
|
bool
|
Allow replacing a solver with the same id. |
False
|
Raises:
| Type | Description |
|---|---|
ConfigError
|
If the id is taken and |
create
¶
create(solver_id: str, **parameters: Any) -> Solver
Build a solver by id with the given parameter values.
Raises:
| Type | Description |
|---|---|
ConfigError
|
If the id is unknown or a parameter is not accepted. |
load_plugins
¶
load_plugins(registry: SolverRegistry, *, group: str = PLUGIN_GROUP) -> list[str]
Register the solvers published by installed plugins.
Each entry point must load a callable that takes the registry. A plugin that fails to load is skipped with a warning and registers none of its solvers, so one broken package cannot disable or half-install the others.
Returns:
| Type | Description |
|---|---|
list[str]
|
Names of the entry points that loaded. |
default_registry
¶
default_registry(*, plugins: bool = True) -> SolverRegistry
Return a registry of the built-in solvers, plus plugins by default.
Each call returns a fresh copy, so callers may register more solvers without affecting others.
Parameters:
| Name | Type | Description | Default |
|---|---|---|---|
plugins
|
bool
|
Also load solvers from the |
True
|
dispatchatlas.solvers.search
¶
The run-time every order-based solver uses.
Search owns what all heuristics and metaheuristics share: the random
generator, the evaluator, the stop criteria, the incumbent, the convergence
trace, and the construction of the SolveResult.
Solvers only express their search logic, so every one honours every stop
criterion, counts evaluations exactly, and scores candidates with the same
schedule builder that produces the reported schedule.
Typical use inside a solver:
def solve(self, problem, stop, seed=0):
search = Search(problem, stop, seed, self.info)
with search:
order = list(range(problem.size))
search.evaluate(order)
while True:
search.next_iteration()
... # propose candidates and call search.evaluate(...)
return search.result()
evaluate and next_iteration raise Exhausted when a stop
criterion fires; leaving the with block swallows it. Constructive solvers
that build a schedule task by task hand it to Search.submit() instead of
decoding its order again, and schedules that change a parameter over the run
read Search.progress().
A search created inside listening() also reports every new incumbent to
a listener, as an Improvement. The campaign engine listens in this
way to keep what a run had found when the run is killed.
Exhausted
¶
Exhausted(reason: StopReason)
Candidate
¶
An evaluated order with its modes, decoded schedule, and score.
Improvement
¶
Improvement(search: Search, candidate: Candidate, point: TracePoint)
A new incumbent of a search, as a listener receives it.
Attributes:
| Name | Type | Description |
|---|---|---|
point |
The trace point the search records for the incumbent: when the search found it, its value of the primary objective, and whether it is feasible. |
objectives
¶
Return every problem objective of the incumbent, keyed by name.
The values are computed from the incumbent's decoded schedule when this is called, so a listener that drops an improvement pays nothing for them. The schedule of an evaluated candidate does not change, so the call is valid from another thread while the search goes on.
Search
¶
Search(problem: Problem, stop: StopCriteria, seed: int, info: SolverInfo, *, objective: str | None = None, archive: bool = False, insertion: bool = True)
Budget, incumbent, and trace of one solver run.
Parameters:
| Name | Type | Description | Default |
|---|---|---|---|
problem
|
Problem
|
The problem being solved. |
required |
stop
|
StopCriteria
|
Stop criteria. Must be bounded when |
required |
seed
|
int
|
Seed of the run's random generator. |
required |
info
|
SolverInfo
|
Metadata of the solver, used for the result and for feature checks. |
required |
objective
|
str | None
|
Primary objective. Defaults to the problem's first one. |
None
|
archive
|
bool
|
Keep the non-dominated set of feasible candidates over every problem objective, for multi-objective solvers. |
False
|
insertion
|
bool
|
Passed to the schedule builder. |
True
|
Raises:
| Type | Description |
|---|---|
UnsupportedProblemError
|
If the problem has features the solver does not
declare in |
SolverError
|
If an iterative solver receives unbounded stop criteria. |
elapsed
property
¶
Seconds since the origin of the run's clock.
The origin is the instant the search was created, or, inside
clock_origin(), the origin set there.
The time limit counts from the same instant.
remaining_time
¶
Seconds left before the time limit, or None without one.
progress
¶
Return the fraction of the binding budget used so far, in [0, 1].
Solvers whose parameters follow a schedule over the run, such as a
falling inertia weight, read it to place the current iteration on
that schedule. It is StopCriteria.progress of this run's
evaluations, started iterations, and elapsed time: the largest
fraction of a limit that the criteria's schedule counts.
A run that reads it records in the extras of its result which clock
its schedule followed, see result().
Parameters:
| Name | Type | Description | Default |
|---|---|---|---|
deterministic
|
bool | None
|
Overrides the criteria's |
None
|
check
¶
Raise Exhausted if the time limit has passed.
Call it inside expensive loops that evaluate nothing, so they cannot overrun the time limit.
next_iteration
¶
Start a new main-loop iteration.
Raises:
| Type | Description |
|---|---|
Exhausted
|
When the iteration limit, the patience, or the time limit is reached. |
evaluate
¶
evaluate(order: Sequence[int], modes: Sequence[int] | None = None) -> Score
Evaluate a candidate and update the incumbent.
Parameters:
| Name | Type | Description | Default |
|---|---|---|---|
order
|
Sequence[int]
|
Task indices in priority order. |
required |
modes
|
Sequence[int] | None
|
Mode index per task, or |
None
|
Returns:
| Type | Description |
|---|---|
Score
|
The candidate's score. |
Raises:
| Type | Description |
|---|---|
Exhausted
|
When the evaluation or time limit is reached before the evaluation, or the target is reached by it. |
assess
¶
assess(order: Sequence[int], modes: Sequence[int] | None = None) -> Candidate
Evaluate a candidate like evaluate() and return all its details.
submit
¶
submit(decoded: Decoded, order: Sequence[int] | None = None, modes: Sequence[int] | None = None) -> Candidate
Score a complete schedule the solver built itself, like assess().
Constructive solvers that place tasks one at a time with a builder of
this search's decoder (search.evaluator.decoder.builder()) submit
the result instead of decoding its order again. The schedule counts as
one evaluation and updates the incumbent, the trace, and the archive
exactly as assess() does. The builder keeps capacities,
precedence, and setup times; a solver that accepts permutation
problems must also place the tasks of each group together, as the
decoder does.
Parameters:
| Name | Type | Description | Default |
|---|---|---|---|
decoded
|
Decoded
|
The complete schedule, as |
required |
order
|
Sequence[int] | None
|
A priority list that yields the schedule, kept with the candidate for later variation. Defaults to the placement order. |
None
|
modes
|
Sequence[int] | None
|
Mode of every task. Defaults to the modes of the schedule. |
None
|
Returns:
| Type | Description |
|---|---|
Candidate
|
The candidate. |
Raises:
| Type | Description |
|---|---|
SolverError
|
If the schedule leaves a task unplaced. |
Exhausted
|
When the evaluation or time limit is reached before the schedule is scored, or the target is reached by it. |
probe
¶
Decode and score an order without letting it become the incumbent.
Constructive heuristics probe partial orders to compare insertion
positions. A probe counts as one evaluation and obeys the evaluation
and time limits like evaluate(), but it never changes the
incumbent, the trace, or the archive. Evaluate a complete candidate
before probing, so that a run stopped by a probe has a schedule to
report.
Parameters:
| Name | Type | Description | Default |
|---|---|---|---|
order
|
Sequence[int]
|
Task indices in priority order, possibly a predecessor-closed subset of the tasks. |
required |
modes
|
Sequence[int] | None
|
Mode index per task, negative or |
None
|
Returns:
| Type | Description |
|---|---|
tuple[Score, Decoded]
|
The score and the decoded, possibly partial, schedule. |
Raises:
| Type | Description |
|---|---|
Exhausted
|
When the evaluation or time limit is reached. |
vector
¶
vector(candidate: Candidate) -> tuple[float, ...]
Return a candidate's objective vector in minimisation form.
result
¶
result(extras: Mapping[str, Scalar] | None = None) -> SolveResult
Build the result of the run from the incumbent.
A run that read progress() records in its extras which clock
its parameter schedule followed: schedule_clock is
"evaluations", "iterations", or "time", the limit that
places the end of the run on the schedule, and schedule_progress
is that place, in [0, 1]. A value below 1 says that the schedule did
not reach its end.
Parameters:
| Name | Type | Description | Default |
|---|---|---|---|
extras
|
Mapping[str, Scalar] | None
|
Solver-specific facts to record, merged with |
None
|
Raises:
| Type | Description |
|---|---|
SolverError
|
If no candidate was ever evaluated. |
listening
¶
listening(listener: Listener) -> Iterator[None]
Report the new incumbents of the searches created inside the block.
A Search created inside the block, in the thread that entered
it, calls listener each time its incumbent improves, for as long as
the search runs. The call is made inside the search and its time counts
as the solver's, so a listener returns at once and leaves any work for
later, such as Improvement.objectives(). An exception it raises
ends the solver's run. A solver that does not run inside a
Search reports nothing.
Parameters:
| Name | Type | Description | Default |
|---|---|---|---|
listener
|
Listener
|
Called with every |
required |
dispatchatlas.solvers.scheduling
¶
The schedule builder shared by every order-based solver.
Most heuristics and metaheuristics search over task orders (priority lists)
and, for tasks with several modes, over mode choices. Decoder
turns an order into a schedule with the serial schedule-generation scheme
(Kolisch 1996, doi:10.1016/0377-2217(95)00357-6): it takes tasks one at a
time, in the order given as far as precedence allows, and starts each at the
earliest time its predecessors, data transfers, release time, and resources
permit.
Details that make every decoded schedule feasible for release times, precedence with lags and transfers, capacities, and setup times:
- Precedence repair. At each step the decoder takes the earliest-listed task whose predecessors are all scheduled, so any permutation decodes.
- Insertion. A task may fill an idle gap left earlier on its resources. Resources with setup times, and every resource of a permutation problem, append only, so their processing sequence equals the decoding sequence.
- Mode choice. Without explicit modes, or where a task's mode entry is negative, a task takes the mode that finishes it earliest, the lowest mode index on ties.
- Permutation problems. The group (job) sequence is the order in which groups first appear in the list, and each group's tasks are decoded together, which yields a permutation schedule.
- Zero-duration tasks occupy an instant that no task on an exclusive resource may run across, and hold nothing on other resources, as the data model defines. On append-only resources they also take their place in the sequence.
Hard deadlines are not enforced here. The evaluator prices their excess.
Decoded
dataclass
¶
Decoded(sequence: tuple[int, ...], modes: tuple[int, ...], starts: tuple[float, ...], ends: tuple[float, ...])
A decoded schedule in array form, indexed by task index.
Attributes:
| Name | Type | Description |
|---|---|---|
sequence |
tuple[int, ...]
|
Task indices in the order they were placed. |
modes |
tuple[int, ...]
|
Mode index of each task. |
starts |
tuple[float, ...]
|
Start time of each task. |
ends |
tuple[float, ...]
|
Finish time of each task. |
Decoder
¶
Decoder(problem: Problem, *, insertion: bool = True)
Builds schedules from task orders and optional mode choices.
A decoder precomputes everything that does not depend on the order, so
create one per problem and reuse it for every evaluation. Constructive
heuristics that place tasks one at a time use builder() instead.
Parameters:
| Name | Type | Description | Default |
|---|---|---|---|
problem
|
Problem
|
The problem to decode for. |
required |
insertion
|
bool
|
Let tasks fill idle gaps on their resources. Ignored on resources with setup times and in permutation problems. |
True
|
decode
¶
decode(order: Sequence[int], modes: Sequence[int] | None = None) -> Decoded
Decode a priority list into a schedule.
Parameters:
| Name | Type | Description | Default |
|---|---|---|---|
order
|
Sequence[int]
|
Task indices in priority order. Covering every task decodes the whole problem. A predecessor-closed subset decodes a partial schedule, as used by insertion heuristics. |
required |
modes
|
Sequence[int] | None
|
Mode index per task index. |
None
|
Returns:
| Type | Description |
|---|---|
Decoded
|
The decoded schedule. |
schedule
¶
schedule(order: Sequence[int], modes: Sequence[int] | None = None) -> Schedule
Decode order and return the result as a schedule.
group_major
¶
Reorder so each group's tasks follow the group's first appearance.
transfer
¶
Return the transfer time of dependency number between two resources.
Builder
¶
Builder(decoder: Decoder)
A partial schedule that grows one task at a time.
Obtain one from Decoder.builder(). A task can be placed once all of
its predecessors are placed.
eligible
¶
Return whether task is unplaced and all its predecessors are placed.
earliest
¶
Return the earliest (start, finish) of task in mode now.
Raises:
| Type | Description |
|---|---|
ModelError
|
If the mode is invalid or a predecessor is unplaced. |
best
¶
Return (start, finish, mode) of the mode that finishes task first.
Parameters:
| Name | Type | Description | Default |
|---|---|---|---|
task
|
int
|
Task index. |
required |
allowed
|
Sequence[int] | None
|
Candidate modes. Defaults to every mode. |
None
|
place
¶
Commit task in mode at start, or as early as possible.
Returns:
| Type | Description |
|---|---|
tuple[float, float]
|
The |
precedence_feasible
¶
precedence_feasible(problem: Problem, order: Sequence[int]) -> list[int]
Return the precedence-feasible sequence closest to a priority list.
At every step the earliest-listed task whose listed predecessors are all
placed comes next. Tasks absent from order are left out, so order
may cover a predecessor-closed subset of the tasks.
Parameters:
| Name | Type | Description | Default |
|---|---|---|---|
problem
|
Problem
|
The problem. |
required |
order
|
Sequence[int]
|
Task indices, each at most once. |
required |
Returns:
| Type | Description |
|---|---|
list[int]
|
The repaired sequence. |
Raises:
| Type | Description |
|---|---|
ModelError
|
If |
dispatchatlas.solvers.evaluation
¶
Scoring decoded schedules.
An Evaluator decodes orders with a Decoder
and scores the result. Scores compare lexicographically: first the total
hard-deadline overrun, then the primary objective in minimisation form. Every
search therefore prefers any schedule that meets all deadlines over one that
does not, and among equals prefers the better objective.
The evaluator computes every built-in objective directly from the decoded arrays, which is much faster than building a schedule object. Objectives registered by plugins fall back to their registered function. A partial schedule, as insertion heuristics decode, is scored over its placed tasks: jobs with no placed task, and transfers from or to unplaced tasks, count nothing.
Score
dataclass
¶
The quality of a schedule. Smaller is better.
Attributes:
| Name | Type | Description |
|---|---|---|
violation |
float
|
Total time by which tasks overrun their hard deadlines. Zero for a feasible schedule. |
value |
float
|
Primary objective in minimisation form. |
Evaluator
¶
Evaluator(problem: Problem, objective: str | None = None, *, insertion: bool = True)
Decodes orders and scores them for one problem.
Parameters:
| Name | Type | Description | Default |
|---|---|---|---|
problem
|
Problem
|
The problem. |
required |
objective
|
str | None
|
Primary objective. Defaults to the problem's first one. |
None
|
insertion
|
bool
|
Passed to the |
True
|
Attributes:
| Name | Type | Description |
|---|---|---|
problem |
The problem. |
|
decoder |
The shared schedule builder. |
|
objective |
Objective
|
The primary objective. |
evaluations |
Candidates scored so far: calls to |
evaluate
¶
Decode and score one candidate. Counts as one evaluation.
score
¶
Score an already decoded schedule. Does not count as an evaluation.
value
¶
Return one objective of a decoded schedule, as the registry defines it.
dispatchatlas.solvers.encoding
¶
Representations that map search vectors to task orders and mode choices.
Continuous optimisers (differential evolution, particle swarms, CMA-ES, and
the population methods in dispatchatlas.solvers.swarm) search over
real-valued vectors. These helpers turn a vector into a task order and mode
choices, which the shared schedule builder then decodes.
VectorEncoding
¶
VectorEncoding(problem: Problem, *, rule: Literal['random-key', 'largest-value'] = 'random-key', modes: Literal['keys', 'builder'] = 'keys')
Decodes real vectors into task orders and mode choices for one problem.
A vector holds one key per task, then, when modes come from keys, one key
per task with several modes. The task keys give the order: ascending
under the "random-key" rule (random_key_order()), descending
under the "largest-value" rule (largest_value_order()). Each mode
key selects its task's mode as modes_from_keys() does. With
modes="builder" the vector holds task keys only and the schedule
builder gives each task its earliest-finishing mode, which suits
time-based objectives but ignores modes that save energy or cost. Search
in the unit hypercube: every real vector decodes, because orders only
compare keys and mode keys wrap.
Parameters:
| Name | Type | Description | Default |
|---|---|---|---|
problem
|
Problem
|
The problem. |
required |
rule
|
Literal['random-key', 'largest-value']
|
How task keys become an order. |
'random-key'
|
modes
|
Literal['keys', 'builder']
|
|
'keys'
|
Attributes:
| Name | Type | Description |
|---|---|---|
problem |
The problem. |
|
rule |
The order rule. |
|
modes |
Where mode choices come from. |
|
dimension |
Length of the vectors. |
|
flexible |
tuple[int, ...]
|
Indices of the tasks whose mode a key selects, in key order. |
decode
¶
Return the task order and the modes, None when the builder chooses them.
Raises:
| Type | Description |
|---|---|
ValueError
|
If the vector length differs from |
encode
¶
Return a vector in the unit hypercube that decodes to order and modes.
Useful to seed a population with a heuristic solution. A task whose
mode is None or negative gets the key of mode 0. Modes are ignored
when the builder chooses them.
random_key_order
¶
Return task indices sorted by ascending key, ties by index.
This is the random-key representation of Bean (1994), doi:10.1287/ijoc.6.2.154, also called the smallest-position-value rule.
largest_value_order
¶
Return task indices sorted by descending key, ties by index.
This is the largest-order-value rule used by many swarm scheduling methods.
keys_from_order
¶
Return keys in [0, 1) whose ascending sort reproduces order.
Useful to seed a continuous population with a heuristic order.
dispatchatlas.solvers.operators
¶
Variation operators on task orders and mode vectors.
Every operator returns a new list and leaves its inputs untouched. Orders need not respect precedence: the schedule builder repairs them.
swap
¶
Return order with the elements at positions i and j exchanged.
insert
¶
Return order with the element at position i moved to position j.
reverse
¶
Return order with the segment between positions i and j reversed.
random_swap
¶
Exchange two distinct random positions.
random_insert
¶
Move a random element to a different random position.
random_order
¶
random_order(problem: Problem, rng: Random) -> list[int]
Return a uniformly random permutation of the task indices.
random_topological_order
¶
random_topological_order(problem: Problem, rng: Random) -> list[int]
Return a random precedence-feasible order.
At each step a task is drawn uniformly from those whose predecessors are all placed.
order_crossover
¶
Order crossover (OX) of Davis (1985).
A random slice is copied from first; the remaining positions receive
the missing elements in the order they appear in second, starting after
the slice and wrapping around.
partially_mapped_crossover
¶
Partially mapped crossover (PMX) of Goldberg and Lingle (1985).
random_modes
¶
random_modes(problem: Problem, rng: Random) -> list[int]
Return a uniformly random mode index for every task.
mutate_modes
¶
mutate_modes(problem: Problem, modes: Sequence[int], rng: Random, rate: float) -> list[int]
Redraw each task's mode with probability rate, among its other modes.
uniform_mode_crossover
¶
Take each task's mode from either parent with equal probability.
dispatchatlas.solvers.priorities
¶
Static task attributes that priority rules and list heuristics rank by.
Every function returns one value per task index. Durations of multi-mode tasks use a summary over the modes (shortest or mean), stated per function.
min_durations
¶
min_durations(problem: Problem) -> list[float]
Shortest duration of each task over its modes.
mean_durations
¶
mean_durations(problem: Problem) -> list[float]
Mean duration of each task over its modes.
effective_due_dates
¶
effective_due_dates(problem: Problem) -> list[float]
Due date of each task, inherited from its group when it has none.
A task without its own due date takes the earliest due date in its group. Tasks with neither get infinity.
longest_tails
¶
longest_tails(problem: Problem) -> list[float]
Length of the longest path from each task's start to the end of the problem.
The path length counts the shortest duration of every task on it and the lags between them, the classic critical-path bound.
remaining_group_work
¶
remaining_group_work(problem: Problem) -> list[float]
Work left in each task's group from that task on.
The work is the task's shortest duration plus those of the tasks of its group that it reaches through dependencies between tasks of that group. For a job made of a chain of operations this is the classic "most work remaining" quantity. A task without a group counts only itself.
upward_ranks
¶
upward_ranks(problem: Problem) -> list[float]
Upward rank of each task, as in HEFT (Topcuoglu, Hariri and Wu 2002).
rank(i) = w(i) + max over successors j of (c(i, j) + rank(j)), where
w is the mean duration over modes and c is the lag plus the mean
transfer time over every pair of modes of i and j.