Skip to content

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 "heft".

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:

[project.entry-points."dispatchatlas.solvers"]
my_solvers = "my_package.solvers:register"

where register(registry) calls SolverRegistry.register() for each of its solvers.

PLUGIN_GROUP module-attribute

PLUGIN_GROUP = 'dispatchatlas.solvers'

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

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 factory.info. When the factory is a dataclass and info.parameters is empty, the parameters and their defaults are read from its fields.

None
replace_existing bool

Allow replacing a solver with the same id.

False

Raises:

Type Description
ConfigError

If the id is taken and replace_existing is false, or no metadata is available.

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.

info

info(solver_id: str) -> SolverInfo

Return the metadata of a registered solver.

infos

infos() -> tuple[SolverInfo, ...]

Return the metadata of every solver, sorted by id.

ids

ids() -> tuple[str, ...]

Return every registered id, sorted.

copy

copy() -> SolverRegistry

Return an independent copy of this registry.

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 dispatchatlas.solvers entry-point group.

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.

Listener

Listener = Callable[[Improvement], None]

What a search calls with each new incumbent.

Exhausted

Exhausted(reason: StopReason)

Bases: Exception

Raised by Search when a stop criterion fires.

Candidate

Candidate(order: list[int], modes: list[int] | None, score: Score, decoded: Decoded)

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.

objective property

objective: str

Name of the objective the search optimises.

objectives

objectives() -> dict[str, float]

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 info.iterative is true.

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 info.supports.

SolverError

If an iterative solver receives unbounded stop criteria.

evaluations property

evaluations: int

Candidates evaluated so far.

elapsed property

elapsed: float

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.

numpy_rng

numpy_rng() -> Generator

Return a NumPy generator seeded from the run seed.

remaining_time

remaining_time() -> float | None

Seconds left before the time limit, or None without one.

progress

progress(*, deterministic: bool | None = None) -> float

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 schedule for this reading: True counts the time limit only when neither an evaluation nor an iteration limit is set, so the schedule replays exactly on any machine, and False counts every set limit. None, the default, follows the criteria.

None

check

check() -> None

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

next_iteration() -> None

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 to let the builder choose.

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 builder.decoded() returns it.

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

probe(order: Sequence[int], modes: Sequence[int] | None = None) -> tuple[Score, Decoded]

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 to let the builder choose.

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.

front

front() -> list[Candidate]

Return the current non-dominated feasible candidates.

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 extras.

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 Improvement.

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. -1 for tasks not decoded.

starts tuple[float, ...]

Start time of each task.

ends tuple[float, ...]

Finish time of each task.

makespan property

makespan: float

Latest finish time over the decoded tasks.

schedule

schedule(problem: Problem) -> Schedule

Return the decoded tasks as a Schedule.

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

builder

builder() -> Builder

Return an empty partial schedule to place tasks into one by one.

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, or a negative entry for a task, picks the mode that finishes the task earliest when it is placed.

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

group_major(order: Sequence[int]) -> list[int]

Reorder so each group's tasks follow the group's first appearance.

transfer

transfer(number: int, source: int, target: int) -> float

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.

makespan property

makespan: float

Latest finish time of the placed tasks.

placed

placed(task: int) -> bool

Return whether task has been placed.

eligible

eligible(task: int) -> bool

Return whether task is unplaced and all its predecessors are placed.

earliest

earliest(task: int, mode: int) -> tuple[float, float]

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

best(task: int, allowed: Sequence[int] | None = None) -> tuple[float, float, int]

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

place(task: int, mode: int, start: float | None = None) -> tuple[float, float]

Commit task in mode at start, or as early as possible.

Returns:

Type Description
tuple[float, float]

The (start, finish) of the placed task.

copy

copy() -> Builder

Return an independent copy, for look-ahead heuristics.

decoded

decoded() -> Decoded

Return the placed tasks as a Decoded schedule.

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 order repeats a task, names an unknown index, or lists a task without one of its predecessors.

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

Score(violation: float, value: float)

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.

feasible property

feasible: bool

Whether every hard deadline is met.

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 Decoder.

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(), and schedules a Search received through submit.

evaluate

evaluate(order: Sequence[int], modes: Sequence[int] | None = None) -> tuple[Score, Decoded]

Decode and score one candidate. Counts as one evaluation.

score

score(decoded: Decoded) -> Score

Score an already decoded schedule. Does not count as an evaluation.

value

value(decoded: Decoded, objective: Objective) -> float

Return one objective of a decoded schedule, as the registry defines it.

values

values(decoded: Decoded) -> dict[str, float]

Return every problem objective of a decoded schedule, keyed by name.

vector

vector(decoded: Decoded) -> tuple[float, ...]

Return every problem objective in minimisation form, in problem order.

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" to search mode choices, "builder" to leave them to the schedule 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

decode(vector: Sequence[float]) -> tuple[list[int], list[int] | None]

Return the task order and the modes, None when the builder chooses them.

Raises:

Type Description
ValueError

If the vector length differs from dimension.

encode

encode(order: Sequence[int], modes: Sequence[int] | None = None) -> list[float]

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

random_key_order(keys: Sequence[float]) -> list[int]

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

largest_value_order(keys: Sequence[float]) -> list[int]

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

keys_from_order(order: Sequence[int]) -> list[float]

Return keys in [0, 1) whose ascending sort reproduces order.

Useful to seed a continuous population with a heuristic order.

modes_from_keys

modes_from_keys(problem: Problem, keys: Sequence[float]) -> list[int]

Map one key in [0, 1) per task to a mode index.

Key k selects mode floor(k * m) of a task with m modes. Keys outside [0, 1) are wrapped into it first, so any real vector is valid.

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

swap(order: Sequence[int], i: int, j: int) -> list[int]

Return order with the elements at positions i and j exchanged.

insert

insert(order: Sequence[int], i: int, j: int) -> list[int]

Return order with the element at position i moved to position j.

reverse

reverse(order: Sequence[int], i: int, j: int) -> list[int]

Return order with the segment between positions i and j reversed.

random_swap

random_swap(order: Sequence[int], rng: Random) -> list[int]

Exchange two distinct random positions.

random_insert

random_insert(order: Sequence[int], rng: Random) -> list[int]

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(first: Sequence[int], second: Sequence[int], rng: Random) -> list[int]

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(first: Sequence[int], second: Sequence[int], rng: Random) -> list[int]

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

uniform_mode_crossover(first: Sequence[int], second: Sequence[int], rng: Random) -> list[int]

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.