Skip to content

Heuristics and local search

Priority rules, constructive heuristics, tree search, and trajectory metaheuristics.

dispatchatlas.solvers.rules

Priority rules and random sampling.

A priority rule ranks the tasks by one static attribute and decodes that order once with the shared schedule builder, which also picks each task's earliest-finishing mode. Rules are fast, deterministic baselines. Surveys of the classic rules: Panwalkar and Iskander (1977).

random-search is the stochastic baseline every metaheuristic should beat: it decodes random precedence-feasible orders until the budget runs out.

InputOrder dataclass

InputOrder()

Schedule tasks by release time, then in the order the problem lists them.

solve

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

Decode the input order.

ShortestProcessingTime dataclass

ShortestProcessingTime()

Schedule shorter tasks first.

solve

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

Decode tasks by increasing duration.

LongestProcessingTime dataclass

LongestProcessingTime()

Schedule longer tasks first.

solve

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

Decode tasks by decreasing duration.

EarliestDueDate dataclass

EarliestDueDate()

Schedule tasks with earlier due dates first.

solve

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

Decode tasks by due date.

MostWorkRemaining dataclass

MostWorkRemaining()

Schedule tasks whose job has the most work left first.

solve

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

Decode tasks by decreasing remaining group work.

LongestRemainingPath dataclass

LongestRemainingPath()

Schedule tasks with the longest path to the end of the problem first.

solve

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

Decode tasks by decreasing tail length.

LeastSlack dataclass

LeastSlack()

Schedule tasks with the latest start before their due date first.

solve

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

Decode tasks by increasing slack.

Heft dataclass

Heft()

Heterogeneous earliest finish time list scheduling.

solve

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

Decode tasks by decreasing upward rank with earliest-finish mode choice.

RandomSearch dataclass

RandomSearch(random_modes: bool = False)

Decode random precedence-feasible orders and keep the best.

Attributes:

Name Type Description
random_modes bool

Draw every task's mode at random too, instead of letting the builder pick the earliest-finishing mode.

solve

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

Sample random orders within the stop criteria.

register

register(registry: SolverRegistry) -> None

Add the rules and the random-search baseline to registry.

dispatchatlas.solvers.constructive

Constructive heuristics: insertion, beam and tree search, batch mapping, and SWO.

The first five build one schedule step by step and finish on their own, so none needs a stop criterion, yet each honours the criteria it is given:

  • neh (Nawaz, Enscore and Ham 1983) takes items in decreasing order of total work and inserts each at the position of the growing sequence whose partial schedule scores best.
  • beam-search (Ow and Morton 1988) keeps the best few partial schedules, extends each by one eligible item, and ranks the extensions by a look-ahead: the score of the complete schedule a priority rule makes of each.
  • min-min and max-min (Ibarra and Kim 1977; Braun et al. 2001) place, among the eligible tasks, the one whose earliest completion time is smallest, resp. largest, in the mode that achieves it.
  • sufferage (Maheswaran et al. 1999) gives each resource, in passes, to the eligible task that would lose the most by not getting its best mode.

Two more repeat their construction until a stop criterion fires:

  • squeaky-wheel-optimization (Joslin and Clements 1999) decodes a priority sequence, blames each item for its excess cost in the schedule, and moves blamed items forward before the next construction.
  • monte-carlo-tree-search (Kocsis and Szepesvári 2006), in tree_search, grows a search tree over sequence prefixes and completes each new prefix at random.

Insertion heuristics order items: single tasks, or whole jobs (the tasks of a group) when the problem is grouped. Items expands an item sequence into a task order and keeps every sequence precedence-feasible. A partial sequence decodes into a partial schedule, which score_sequence() scores with probe(): one evaluation that never becomes the run's incumbent, since it does not schedule every task.

Candidates carry mode settings: one per task, either a mode index or AUTO, which lets the builder give the task its earliest-finishing mode when the task is placed.

AUTO module-attribute

AUTO = -1

Mode setting that lets the builder choose the task's earliest-finishing mode.

The decoder treats every negative mode entry this way.

Items

Items(problem: Problem, *, jobs: bool)

Tasks or whole jobs: the elements that sequence heuristics order.

An item sequence expands to a task order by listing each item's tasks in topological order. Item a precedes item b when some task of a precedes some task of b. Every sequence built through this class keeps each item after its ancestors, so its expansion is precedence-feasible and any prefix of it decodes as a partial schedule.

Parameters:

Name Type Description Default
problem Problem

The problem.

required
jobs bool

Order whole jobs rather than single tasks. Tasks without a group stay single items. Ignored when the problem has no groups, or when dependencies between groups form a cycle, since jobs then cannot be sequenced as wholes.

required

Attributes:

Name Type Description
problem

The problem.

jobs

Whether the items are jobs.

members

Task indices of each item, in topological order.

item_of

Item index of each task.

predecessors

Direct predecessor items of each item.

successors

Direct successor items of each item.

topological

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

work

Total mean duration of each item's tasks.

fixed

Whether precedence admits a single item sequence.

count property

count: int

Number of items.

tasks

tasks(sequence: Sequence[int]) -> list[int]

Expand an item sequence into the task order it stands for.

closed_tasks

closed_tasks(sequence: Sequence[int]) -> list[int]

Expand the items of sequence whose ancestors are all in it.

A partial sequence may hold an item whose ancestor was removed. Its tasks cannot be decoded before that ancestor returns, so they are left out.

insertion_range

insertion_range(sequence: Sequence[int], item: int) -> range

Return the positions where item can enter sequence.

The item must follow every ancestor and precede every descendant in the sequence, including relations that run through items not in it. sequence must itself respect those relations, as every sequence built from a feasible one by removals and feasible insertions does.

feasible

feasible(priority: Sequence[int]) -> list[int]

Return the feasible order of the given items closest to their priority.

At each step the earliest-listed item whose listed ancestors are all placed comes next.

Parameters:

Name Type Description Default
priority Sequence[int]

Distinct item indices, highest priority first.

required

sequence_of

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

Return the item sequence of a task order: items by first appearance, repaired.

random_sequence

random_sequence(rng: Random) -> list[int]

Return a random feasible sequence, drawing uniformly among ready items.

is_ancestor

is_ancestor(before: int, after: int) -> bool

Return whether item before must precede item after.

Neh dataclass

Neh()

The NEH insertion heuristic of Nawaz, Enscore and Ham (1983).

Grouped problems insert whole jobs, as in the permutation flow shop the heuristic was designed for; other problems insert single tasks. The builder picks each task's earliest-finishing mode.

solve

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

Build the NEH sequence and return its schedule.

BeamSearch dataclass

BeamSearch(width: int = 3, filter_width: int = 5)

Filtered beam search over partial schedules (Ow and Morton 1988).

Level k holds up to width partial schedules of k items. Each is extended by its filter_width eligible items of highest priority, the upward rank of HEFT (for a job, its highest task rank). Every extension is scored by a look-ahead: the complete schedule obtained by appending the remaining items in priority order. The width best extensions form the next level; extensions that yield an identical partial schedule count once. One level is one iteration, so iteration and evaluation limits truncate the search, which then returns the best look-ahead found. The root look-ahead is the priority rule's own schedule, so the result is never worse than it. Permutation problems extend whole jobs.

Attributes:

Name Type Description
width int

Partial schedules kept at each level.

filter_width int

Extensions scored per partial schedule.

solve

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

Run the beam from the empty schedule to complete ones.

MinMin dataclass

MinMin()

The min-min mapping heuristic (Ibarra and Kim 1977; Braun et al. 2001).

Among the eligible tasks, whose predecessors are all placed, each step places the task with the smallest earliest completion time over its modes, in the mode that achieves it. Ties go to the lowest task, then the lowest mode.

solve

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

Map every task and return the schedule.

MaxMin dataclass

MaxMin()

The max-min mapping heuristic (Ibarra and Kim 1977; Braun et al. 2001).

Like MinMin, but each step places the eligible task whose earliest completion time is largest, so long tasks claim their best resources before short ones fill in around them.

solve

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

Map every task and return the schedule.

Sufferage dataclass

Sufferage()

The sufferage mapping heuristic of Maheswaran et al. (1999).

Tasks are mapped in passes. In a pass, the eligible tasks are visited in index order. A task's sufferage is its second-best completion time over its modes minus its best, or zero with a single mode. The task tentatively claims the resources of its best mode; if another task of the pass already holds one of them, the newcomer takes them over only when its sufferage is larger than every holder's, and the displaced tasks wait for the next pass. At the end of the pass the claims are placed. Resources play the role of the machines of the original meta-task mapping.

solve

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

Map every task and return the schedule.

SqueakyWheel dataclass

SqueakyWheel(step: float = 0.5, jitter: float = 1.0, restart_after: int = 50)

Squeaky wheel optimization (Joslin and Clements 1999).

Each iteration is one construct, analyse, prioritise cycle:

  1. construct: decode the priority sequence of items, each task in its earliest-finishing mode;
  2. analyse: blame every item for its excess cost in that schedule (see task_blame(); an item's blame is its highest task blame);
  3. prioritise: move every blamed item forward by step times the number of items times its blame over the highest blame, less a random jitter of up to jitter positions, and repair precedence.

An item thus needs high blame over several cycles to travel from the back of the sequence to the front, the published "sticky sort", and items that stop receiving blame sink as others overtake them. The first sequence ranks items by upward rank. After restart_after cycles without a new best schedule the cycle restarts from a random sequence, as the authors restart periodically. Items are jobs in permutation problems and tasks otherwise.

Attributes:

Name Type Description
step float

Largest forward move per cycle, as a fraction of the sequence length.

jitter float

Largest random forward shift, in positions, that breaks cycles.

restart_after int

Cycles without a new best schedule before a restart.

solve

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

Construct, analyse, and prioritise until a stop criterion fires.

prioritise

prioritise(items: Items, sequence: Sequence[int], blame: Sequence[float], rng: Random) -> list[int]

Move blamed items forward and return the repaired sequence.

Parameters:

Name Type Description Default
items Items

The items.

required
sequence Sequence[int]

The current priority sequence.

required
blame Sequence[float]

Blame of every item.

required
rng Random

Source of the jitter.

required

score_sequence

score_sequence(search: Search, items: Items, sequence: Sequence[int], modes: Sequence[int] | None = None, *, complete: bool) -> tuple[Score, Decoded]

Score an item sequence: as a candidate when complete, as a probe otherwise.

A probe scores the partial schedule of the items whose ancestors are all in the sequence (see Items.closed_tasks()). It counts as an evaluation but never becomes the incumbent, so evaluate a complete candidate first.

Parameters:

Name Type Description Default
search Search

The run that pays for the evaluation.

required
items Items

The items.

required
sequence Sequence[int]

The item sequence.

required
modes Sequence[int] | None

Mode setting of every task, or None for AUTO everywhere.

None
complete bool

Whether sequence holds every item.

required

Returns:

Type Description
tuple[Score, Decoded]

The score and the decoded schedule.

insert_best

insert_best(search: Search, items: Items, sequence: Sequence[int], item: int, modes: Sequence[int] | None = None, *, complete: bool = False) -> tuple[list[int], tuple[Score, Decoded] | None]

Insert item at the feasible position whose schedule scores best.

The earliest of equally good positions wins. A partial insertion with a single feasible position is made without scoring it.

Parameters:

Name Type Description Default
search Search

The run that pays for the evaluations.

required
items Items

The items.

required
sequence Sequence[int]

The sequence to insert into. It does not contain item.

required
item int

The item to insert.

required
modes Sequence[int] | None

Mode setting of every task, or None for AUTO everywhere.

None
complete bool

Whether the result holds every item, so that each candidate is a complete schedule evaluated by the search.

False

Returns:

Type Description
tuple[list[int], tuple[Score, Decoded] | None]

The new sequence and, when scored, its score and decoded schedule.

neh

neh(search: Search, items: Items, modes: Sequence[int] | None = None) -> tuple[list[int], Score, Decoded]

Build a sequence with the NEH insertion procedure of Nawaz, Enscore and Ham (1983).

Items are taken in decreasing order of total work, ties by index, repaired so that each follows its ancestors. The first is the initial sequence; each further item is inserted at the best feasible position of the sequence built so far, judged on the partial schedule. The priority order itself is first evaluated as a complete candidate, so a run stopped during the insertions still returns a schedule.

Parameters:

Name Type Description Default
search Search

The run that pays for the evaluations.

required
items Items

The items to sequence.

required
modes Sequence[int] | None

Mode setting of every task, or None for AUTO everywhere.

None

Returns:

Type Description
tuple[list[int], Score, Decoded]

The final sequence, its score, and its decoded schedule.

neh_order

neh_order(problem: Problem) -> list[int]

Return the task order the NEH heuristic builds for problem.

Useful to seed a metaheuristic. Runs without a budget, and scores partial schedules on the problem's primary objective.

task_blame

task_blame(problem: Problem, objective: str) -> Callable[[Sequence[float]], list[float]]

Return the analyser of squeaky wheel optimization for problem.

The blame of a task is its excess cost, the cost it incurs in a schedule minus the least cost it could incur, where the cost follows the objective:

  • for makespan and energy, whose time-dependent part is the makespan, the end of schedule that the task's finish forces, its finish plus the shortest chain of successors after it; the least cost is the critical-path lower bound of the makespan, so tasks with slack get none;
  • for the due-date objectives, the task's weighted tardiness against its due date, or its group's; the least cost is the tardiness of its earliest possible finish;
  • for any other objective, the task's weighted completion time; the least cost is its earliest possible finish.

Earliest finishes and successor chains use each task's shortest mode, its release, and the lags, and ignore resources.

Parameters:

Name Type Description Default
problem Problem

The problem.

required
objective str

Name of the objective the run minimises.

required

Returns:

Type Description
Callable[[Sequence[float]], list[float]]

A function from the tasks' finish times to their blame.

register

register(registry: SolverRegistry) -> None

Add the constructive heuristics to registry.

Monte Carlo tree search over sequence prefixes.

The tree's root is the empty sequence, and each node is a sequence prefix whose children append one more eligible item: a task, or a job in permutation problems. Each iteration is one playout of UCT (Kocsis and Szepesvári 2006):

  1. selection: from the root, while the node has no untried item, descend to the child with the highest UCB1 value (Auer, Cesa-Bianchi and Fischer 2002), mean reward + c · sqrt(ln N / n) for a node visited N times and a child visited n times;
  2. expansion: append one untried eligible item, drawn uniformly, as a new child;
  3. simulation: complete the sequence by drawing each next item uniformly among the eligible ones, and evaluate it, each multi-mode task in its earliest-finishing mode;
  4. backpropagation: add the reward to every node on the path.

UCB1 needs rewards in [0, 1]. The reward of a playout is the fraction of the earlier playouts whose schedule it beats, ties counting half, which maps any objective and deadline overrun to that interval. A node whose whole subtree has been enumerated is closed and never selected again, so on a small problem the search ends by itself once every sequence has been evaluated, and the best of them is optimal for the schedule builder.

RankReward

RankReward()

Rewards a score by the fraction of the earlier scores it beats, ties counting half.

__call__

__call__(score: Score) -> float

Return the reward of score and remember it.

MonteCarloTreeSearch dataclass

MonteCarloTreeSearch(exploration: float = 0.3)

UCT over sequence prefixes with uniformly random rollouts.

Attributes:

Name Type Description
exploration float

The constant c of the UCB1 bound. UCB1 itself uses √2; rank rewards cluster around one half, so the mean rewards of siblings differ little and a smaller constant lets them count.

solve

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

Play out until a stop criterion fires or the tree is enumerated.

dispatchatlas.solvers.trajectory

Trajectory metaheuristics: methods that improve one solution at a time.

All of them search item sequences and, for multi-mode tasks, explicit mode choices, through the moves and the local search of SequenceSpace. They differ in how they move and what they accept:

  • acceptance: one random neighbour per iteration, accepted by a rule. hill-climbing, simulated-annealing, threshold-accepting, great-deluge, record-to-record-travel, and late-acceptance-hill-climbing.
  • tabu: the best admissible neighbour of a sample, with a tabu list. tabu-search.
  • iterated: perturbation plus local search. iterated-local-search and variable-neighbourhood-search.
  • greedy: greedy construction plus local search. iterated-greedy and grasp.
  • alns: adaptive destroy and repair. alns.
  • guided: descent on an objective augmented with feature penalties. guided-local-search.
  • hyper: learned choice among low-level heuristics with late acceptance. selection-hyper-heuristic.
  • mode_tabu: tabu search over mode vectors alone. mode-assignment-tabu.

register

register(registry: SolverRegistry) -> None

Add the trajectory metaheuristics to registry.

dispatchatlas.solvers.trajectory.space

The solution space the trajectory methods move through.

A solution is an item sequence (see Items) and, when some task has several modes, a mode setting for every task: a fixed mode, or AUTO, which lets the builder give the task its earliest-finishing mode when it is placed. Items are jobs in permutation problems, whose schedules depend only on the job sequence, and single tasks otherwise. Searches start with every multi-mode task on AUTO, the greedy mapping of list scheduling, and fix modes only where that pays. Three moves change a solution, each keeping the sequence precedence-feasible:

  • insert moves one item to another position between its predecessors and successors;
  • swap exchanges two items whose exchange keeps precedence;
  • mode changes one multi-mode task's setting: an AUTO task gets a fixed mode other than the one it runs in, a fixed task gets AUTO or another fixed mode, drawn uniformly.

A random neighbour draws the move kind uniformly among the kinds the problem allows. Solutions compare by Score: deadline overrun first, then the objective. Rules that weigh how much worse a candidate is use worsening(), which is infinite when the overruns differ, so a walk always accepts a smaller overrun and never a larger one.

Solution dataclass

Solution(sequence: tuple[int, ...], modes: tuple[int, ...] | None, score: Score, decoded: Decoded)

An evaluated point of the space.

Attributes:

Name Type Description
sequence tuple[int, ...]

Item indices in sequence order.

modes tuple[int, ...] | None

Mode setting of every task, or None when no task has several modes.

score Score

The score of the decoded schedule.

decoded Decoded

The decoded schedule, whose modes are the modes the tasks run in.

key property

key: tuple[tuple[int, ...], tuple[int, ...] | None]

A hashable identity of the solution's decisions.

Move dataclass

Move(kind: MoveKind, first: int, second: int)

A change to a solution.

Attributes:

Name Type Description
kind MoveKind

"insert", "swap", or "mode".

first int

The source position (insert), the lower position (swap), or the task (mode).

second int

The target position (insert), the upper position (swap), or the new setting (mode).

SequenceSpace

SequenceSpace(search: Search, items: Items | None = None)

Solutions, moves, and local search for one run.

Every evaluation goes through the run's Search, so it counts against the budget and updates the incumbent.

Parameters:

Name Type Description Default
search Search

The run.

required
items Items | None

The items to sequence. Defaults to jobs in permutation problems and tasks otherwise.

None

Attributes:

Name Type Description
search

The run.

items

The items the sequences order.

flexible

Indices of the tasks with more than one mode.

movable property

movable: bool

Whether any move exists, that is, whether the space holds more than one solution.

kinds property

kinds: tuple[MoveKind, ...]

The move kinds this problem allows.

Insert and swap, unless precedence fixes the sequence, and mode when some task has several modes.

automatic property

automatic: tuple[int, ...] | None

The starting mode settings: AUTO for multi-mode tasks, mode 0 for the others.

evaluate

evaluate(sequence: Sequence[int], modes: Sequence[int] | None) -> Solution

Decode and score a sequence under the given mode settings.

start

start(sequence: Sequence[int]) -> Solution

Evaluate a sequence with every multi-mode task on AUTO.

random_start

random_start() -> Solution

Evaluate a random precedence-feasible sequence with AUTO modes.

settings

settings(task: int, current: int, running: int) -> list[int]

Return the settings a mode move or a mode descent may give task.

Parameters:

Name Type Description Default
task int

The task.

required
current int

Its current setting.

required
running int

The mode it runs in now.

required

Returns:

Type Description
list[int]

For an AUTO task, every mode but the one it runs in; for a fixed

list[int]

task, AUTO and every other mode.

sample

sample(sequence: Sequence[int], modes: Sequence[int] | None, running: Sequence[int] | None = None) -> Move | None

Draw a random move, or return None when no move exists.

Parameters:

Name Type Description Default
sequence Sequence[int]

The item sequence.

required
modes Sequence[int] | None

The mode settings.

required
running Sequence[int] | None

The modes the tasks run in, when known, so that a mode move never picks the mode an AUTO task already runs in.

None

sample_kind

sample_kind(kind: MoveKind, sequence: Sequence[int], modes: Sequence[int] | None, running: Sequence[int] | None = None) -> Move

Draw a random move of the given kind, which must be one of kinds.

Parameters:

Name Type Description Default
kind MoveKind

"insert", "swap", or "mode".

required
sequence Sequence[int]

The item sequence.

required
modes Sequence[int] | None

The mode settings.

required
running Sequence[int] | None

The modes the tasks run in, as for sample().

None

swaps

swaps(sequence: Sequence[int], index: int) -> list[int]

Return every position whose item can exchange places with the one at index.

An exchange is allowed when both items stay between their direct predecessors and successors, which keeps the sequence precedence-feasible.

apply staticmethod

apply(sequence: Sequence[int], modes: Sequence[int] | None, move: Move) -> tuple[tuple[int, ...], tuple[int, ...] | None]

Return the sequence and mode settings that move produces.

neighbour

neighbour(solution: Solution) -> tuple[Solution, Move] | None

Evaluate a random neighbour of solution, with the move that made it.

perturb

perturb(solution: Solution, moves: int) -> Solution

Apply moves random moves in a row and evaluate the result once.

deltas

deltas(solution: Solution, samples: int) -> list[float]

Evaluate random neighbours and return how much worse each is than solution.

climb

climb(solution: Solution, failures: int) -> Solution

Improve solution by first-improvement over random neighbours.

Random neighbours are evaluated one at a time and each strictly better one becomes the current solution. The climb ends after failures consecutive neighbours fail to improve, a sampled test of local optimality whose cost does not grow with the neighbourhood.

descend

descend(solution: Solution) -> Solution

Improve solution to a local optimum of the insertion and mode moves.

The iterative-improvement insertion search of Ruiz and Stützle (2007), extended to modes: items are visited in random order, and each is removed and reinserted at the feasible position that scores best, then each of its multi-mode tasks tries every other setting. A change is kept only when it strictly improves the solution. Passes repeat until one changes nothing.

reinsert

reinsert(current: Solution, item: int) -> Solution | None

Move item to its best feasible position, if that improves current.

Every other feasible position is evaluated. Returns the best of them when it is strictly better than current, and None otherwise.

worsening

worsening(candidate: Score, current: Score) -> float

Return how much worse candidate is than current, in objective units.

Returns:

Type Description
float

The objective difference when both overrun their deadlines by the same

float

amount, minus infinity when the candidate's overrun is smaller, and

float

plus infinity when it is larger.

move_scale

move_scale(deltas: Sequence[float]) -> float

Return the typical size of a worsening move among sampled deltas.

The mean of the finite positive deltas, or, when no sampled move worsens the solution, the mean size of the finite negative ones, or zero when no move changed the objective.

dispatchatlas.solvers.trajectory.acceptance

Single-solution walks that differ only in their acceptance rule.

Each method here repeats one step: draw a random neighbour of the current solution (an insert, swap, or mode move, see space), evaluate it, and let the rule decide whether it becomes the current solution. One iteration is one step. Every walk starts from a random precedence-feasible sequence.

=============================  =======================================================
Method                         A candidate becomes the current solution when
=============================  =======================================================
hill climbing                  it is strictly better (a restart ends a run of failures)
simulated annealing            it is no worse, or with probability ``exp(-Δ/T)``
threshold accepting            it is less than ``T`` worse
great deluge                   its cost is below the water level
record-to-record travel        its cost is below the best cost found plus a deviation
late acceptance hill climbing  it is no worse than the current solution, or than the
                               current solution ``L`` steps earlier
=============================  =======================================================

Δ is how much worse the candidate is (see worsening()), so no rule accepts a larger deadline overrun and every rule accepts a smaller one. Simulated annealing, threshold accepting, the great deluge, and record-to-record travel measure their tolerances in units of the move scale: the mean worsening of CALIBRATION_SAMPLES random neighbours of the starting solution. That makes their defaults independent of the objective's units.

CALIBRATION_SAMPLES module-attribute

CALIBRATION_SAMPLES = 20

Random neighbours of the starting solution evaluated to measure the move scale.

AcceptanceRule

Bases: Protocol

Decides whether a candidate replaces the current solution of a walk.

accept

accept(candidate: Score, current: Score, rng: Random) -> bool

Return whether candidate replaces current.

update

update(current: Score, *, accepted: bool) -> None

Advance the rule's state after one decision.

Parameters:

Name Type Description Default
current Score

The current solution's score after the decision.

required
accepted bool

Whether the candidate was accepted.

required

Improvement dataclass

Improvement()

Accept strictly better candidates only.

accept

accept(candidate: Score, current: Score, rng: Random) -> bool

Return whether candidate is strictly better.

update

update(current: Score, *, accepted: bool) -> None

Keep no state.

Metropolis dataclass

Metropolis(temperature: float, cooling: float, epoch: int, decisions: int = 0)

The Metropolis rule of simulated annealing with geometric cooling.

A candidate Δ worse is accepted with probability exp(-Δ/T), a candidate no worse always. After every epoch decisions the temperature is multiplied by cooling.

Attributes:

Name Type Description
temperature float

The temperature T.

cooling float

Factor applied to T after each epoch.

epoch int

Decisions per temperature.

decisions int

Decisions taken so far.

accept

accept(candidate: Score, current: Score, rng: Random) -> bool

Apply the Metropolis test.

update

update(current: Score, *, accepted: bool) -> None

Count the decision and cool at the end of an epoch.

Threshold dataclass

Threshold(threshold: float, cooling: float, epoch: int, decisions: int = 0)

The threshold-accepting rule of Dueck and Scheuer (1990).

A candidate is accepted when it is less than threshold worse. After every epoch decisions the threshold is multiplied by cooling.

Attributes:

Name Type Description
threshold float

The threshold T.

cooling float

Factor applied to T after each epoch.

epoch int

Decisions per threshold value.

decisions int

Decisions taken so far.

accept

accept(candidate: Score, current: Score, rng: Random) -> bool

Accept a candidate less than the threshold worse.

update

update(current: Score, *, accepted: bool) -> None

Count the decision and lower the threshold at the end of an epoch.

WaterLevel dataclass

WaterLevel(level: float, rain: float)

The great-deluge rule of Dueck (1993), for minimisation.

A candidate is accepted when its objective is below the water level, and the level drops by rain every time a candidate is accepted. Between candidates with different deadline overruns the smaller overrun wins.

Attributes:

Name Type Description
level float

The water level.

rain float

Drop of the level per accepted candidate.

accept

accept(candidate: Score, current: Score, rng: Random) -> bool

Accept a candidate below the level.

update

update(current: Score, *, accepted: bool) -> None

Lower the level after an acceptance.

RecordDeviation dataclass

RecordDeviation(record: Score, deviation: float)

The record-to-record travel rule of Dueck (1993), for minimisation.

A candidate is accepted when its objective is below the record, the best objective the walk has reached, plus a fixed deviation. Between candidates with different deadline overruns the smaller overrun wins.

Attributes:

Name Type Description
record Score

The best score the walk has reached.

deviation float

The allowed excess over the record.

accept

accept(candidate: Score, current: Score, rng: Random) -> bool

Accept a candidate within the deviation of the record.

update

update(current: Score, *, accepted: bool) -> None

Raise the record when the current solution beats it.

LateAcceptance dataclass

LateAcceptance(history: list[Score], iteration: int = 0)

The late-acceptance rule of Burke and Bykov (2017).

At iteration i a candidate is accepted when it is no worse than the current solution or than entry i mod L of a history of L costs. That entry then records the current solution's cost. The history starts filled with the starting cost.

Attributes:

Name Type Description
history list[Score]

The last L current costs.

iteration int

Decisions taken so far.

accept

accept(candidate: Score, current: Score, rng: Random) -> bool

Compare with the current cost and the cost L steps back.

update

update(current: Score, *, accepted: bool) -> None

Record the current cost in the history.

HillClimbing dataclass

HillClimbing(restart_after: int = 100)

First-improvement hill climbing with random restarts.

Each iteration evaluates one random neighbour and moves to it when it is strictly better. After restart_after consecutive neighbours fail to improve, the current solution is treated as a local optimum and the climb restarts from a new random sequence, which takes one iteration.

Attributes:

Name Type Description
restart_after int

Consecutive non-improving neighbours before a restart.

solve

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

Climb and restart until a stop criterion fires.

SimulatedAnnealing dataclass

SimulatedAnnealing(initial_acceptance: float = 0.5, cooling: float = 0.95, epoch: int | None = None)

Simulated annealing (Kirkpatrick, Gelatt and Vecchi 1983).

A random neighbour Δ worse than the current solution is accepted with probability exp(-Δ/T). The starting temperature makes a move of the move scale acceptable with probability initial_acceptance, that is T0 = scale / ln(1 / initial_acceptance), calibrating the start on the instance as in the experimental study of Johnson et al. (1989). The temperature is multiplied by cooling after every epoch moves.

Attributes:

Name Type Description
initial_acceptance float

Probability of accepting a move of the move scale at the start.

cooling float

Geometric cooling factor per epoch.

epoch int | None

Moves per temperature. Defaults to the number of sequence items.

solve

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

Anneal until a stop criterion fires.

ThresholdAccepting dataclass

ThresholdAccepting(initial_threshold: float = 1.0, cooling: float = 0.95, epoch: int | None = None)

Threshold accepting (Dueck and Scheuer 1990).

A random neighbour is accepted when it is less than the threshold worse than the current solution. The threshold starts at initial_threshold move scales and is multiplied by cooling after every epoch moves.

Attributes:

Name Type Description
initial_threshold float

Starting threshold, in move scales.

cooling float

Geometric lowering factor per epoch.

epoch int | None

Moves per threshold value. Defaults to the number of sequence items.

solve

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

Walk under a falling threshold until a stop criterion fires.

GreatDeluge dataclass

GreatDeluge(initial_margin: float = 1.0, rain_speed: float = 0.01)

The great deluge algorithm (Dueck 1993).

A random neighbour is accepted when its objective is below the water level. The level starts initial_margin move scales above the starting objective and drops by rain_speed move scales at every acceptance, so the walk is squeezed towards ever better solutions.

Attributes:

Name Type Description
initial_margin float

Starting level above the starting objective, in move scales.

rain_speed float

Drop of the level per accepted move, in move scales.

solve

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

Walk under a falling water level until a stop criterion fires.

RecordToRecordTravel dataclass

RecordToRecordTravel(deviation: float = 0.2)

Record-to-record travel (Dueck 1993).

A random neighbour is accepted when its objective is below the record, the best objective the walk has reached, plus a fixed deviation of deviation move scales.

Attributes:

Name Type Description
deviation float

Allowed excess over the record, in move scales.

solve

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

Travel within the deviation of the record until a stop criterion fires.

LateAcceptanceHillClimbing dataclass

LateAcceptanceHillClimbing(history: int = 50)

Late acceptance hill climbing (Burke and Bykov 2017).

A random neighbour is accepted when it is no worse than the current solution or than the current solution history iterations earlier.

Attributes:

Name Type Description
history int

Length L of the cost history.

solve

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

Walk with a delayed acceptance test until a stop criterion fires.

walk

walk(space: SequenceSpace, current: Solution, rule: AcceptanceRule) -> None

Move from current through random neighbours until a stop criterion fires.

Returns only when the space has no move; otherwise the search's Exhausted ends the walk.

dispatchatlas.solvers.trajectory.tabu

Tabu search over sampled insert, swap, and mode moves.

Tabu search (Glover 1986, 1989) moves every iteration to the best admissible neighbour, even when it is worse than the current solution, and forbids moves that would undo recent ones. Here the neighbourhood is a sample of candidates random moves (a candidate-list strategy). A move's attributes record where it puts things: an insert or swap puts an item at a position, a mode move puts a task in a mode. After a move, the attributes it removed (the item's old position, the task's old mode) are tabu for tenure iterations: a candidate that would restore one is inadmissible, unless it beats the best score found before the iteration (aspiration by objective). When every sampled candidate is inadmissible, the best of them is taken anyway.

TabuSearch dataclass

TabuSearch(tenure: int = 7, candidates: int = 20)

Tabu search with a sampled neighbourhood and aspiration by objective.

One iteration evaluates candidates random neighbours and moves to the best admissible one. The search starts from a random precedence-feasible sequence.

Attributes:

Name Type Description
tenure int

Iterations during which a removed attribute stays tabu.

candidates int

Neighbours sampled per iteration.

solve

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

Search until a stop criterion fires.

attributes

attributes(solution: Solution, move: Move) -> tuple[list[Attribute], list[Attribute]]

Return the attributes a move adds to and removes from solution.

Returns:

Type Description
tuple[list[Attribute], list[Attribute]]

The attributes the neighbour gains, and those the current solution loses.

dispatchatlas.solvers.trajectory.iterated

Perturbation and local search: iterated local search and variable neighbourhood search.

Both methods alternate a random perturbation of a local optimum with the local search climb(), a first-improvement descent over random insert, swap, and mode neighbours that ends after max_failures consecutive neighbours fail to improve. A perturbation of strength k applies k random moves in a row. One iteration is one perturbation followed by its local search. Both start from the local optimum of a random precedence-feasible sequence.

IteratedLocalSearch dataclass

IteratedLocalSearch(strength: int = 3, max_failures: int = 100)

Iterated local search (Lourenço, Martin and Stützle 2003).

Each iteration perturbs the current local optimum with strength random moves, climbs to a new local optimum, and keeps it when it is no worse than the current one: the better acceptance criterion, with ties accepted so that the walk can cross plateaus of equal cost.

Attributes:

Name Type Description
strength int

Random moves per perturbation.

max_failures int

Consecutive non-improving neighbours that end a local search.

solve

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

Perturb and climb until a stop criterion fires.

VariableNeighbourhoodSearch dataclass

VariableNeighbourhoodSearch(max_neighbourhood: int = 5, max_failures: int = 100)

Basic variable neighbourhood search (Mladenović and Hansen 1997).

Neighbourhood N_k holds the solutions k random moves away. Each iteration shakes the current local optimum to a random point of N_k, climbs from it, and moves there when the result is strictly better, returning to k = 1; otherwise k grows by one, wrapping to 1 after max_neighbourhood.

Attributes:

Name Type Description
max_neighbourhood int

The largest neighbourhood index k_max.

max_failures int

Consecutive non-improving neighbours that end a local search.

solve

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

Shake, climb, and change neighbourhoods until a stop criterion fires.

dispatchatlas.solvers.trajectory.greedy

Greedy construction inside a search: iterated greedy and GRASP.

Iterated greedy (Ruiz and Stützle 2007) repeatedly removes a few items from the current sequence and reinserts them greedily, NEH style. GRASP (Feo and Resende 1995) repeatedly builds a schedule with a randomised greedy rule and improves it by local search, the first-improvement climb of climb() for GRASP and the insertion search of descend() for iterated greedy.

IteratedGreedy dataclass

IteratedGreedy(destruction: int = 4, temperature: float = 0.4, local_search: bool = True)

Iterated greedy (Ruiz and Stützle 2007), from an NEH start.

The search starts from the NEH sequence (see neh()), improved by local search when local_search is set. Each iteration then:

  1. destroys: removes destruction items drawn at random;
  2. constructs: reinserts them, in the order drawn, each at the position whose partial schedule scores best; an item whose removed ancestor has not been reinserted yet waits for it;
  3. improves the result by local search, when local_search is set;
  4. accepts it when it is better than the current solution, and otherwise with probability exp(-Δ/temperature), where the constant temperature is temperature * mean task duration / 10, the published T · Σp / (n · m · 10) with each task as one operation.

NEH inserts whole jobs in grouped problems. The search then keeps moving whole jobs in permutation problems, whose schedules depend only on the job sequence, and single tasks otherwise. The temperature is in time units, as calibrated for makespan.

Attributes:

Name Type Description
destruction int

Items removed per iteration, the published d.

temperature float

The published temperature factor T.

local_search bool

Apply the insertion and mode local search after NEH and after every construction.

acceptance_temperature

acceptance_temperature(problem: Problem) -> float

Return the constant acceptance temperature for problem.

temperature times the mean task duration over ten; a task's duration is the mean over its modes.

solve

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

Destroy, reconstruct, and accept until a stop criterion fires.

Grasp dataclass

Grasp(alpha: float = 0.3, max_failures: int = 100)

Greedy randomised adaptive search procedure (Feo and Resende 1995).

Each iteration builds a schedule task by task. The greedy value of an eligible task is its earliest completion time over its modes, recomputed after every placement. The restricted candidate list holds the eligible tasks whose value is at most min + alpha · (max - min); one is drawn uniformly and placed in its best mode. The schedule is then improved by a first-improvement climb over random insert, swap, and mode neighbours. The best schedule over all iterations is returned.

Attributes:

Name Type Description
alpha float

Greediness of the candidate list, from 0 (pure greedy) to 1 (uniformly random among eligible tasks).

max_failures int

Consecutive non-improving neighbours that end a local search.

solve

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

Construct and improve until a stop criterion fires.

rebuild

rebuild(space: SequenceSpace, current: Solution, count: int) -> Solution

Remove count random items and reinsert each at its best position.

The destruction and construction phases of iterated greedy (Ruiz and Stützle 2007): the items are drawn uniformly, then reinserted one at a time, ancestors first and otherwise in the order drawn, each at the position whose partial schedule scores best. The mode settings are kept.

Parameters:

Name Type Description Default
space SequenceSpace

The space of the run.

required
current Solution

The solution to rebuild.

required
count int

Items to remove, at least 1 and fewer than the number of items.

required

dispatchatlas.solvers.trajectory.alns

Adaptive large neighbourhood search (Ropke and Pisinger 2006).

Each iteration removes q items from the current solution with a destroy operator and reinserts them with a repair operator; q is drawn uniformly between min_removed and max_removed. The operators are drawn by roulette wheel in proportion to their weights, destroy and repair independently.

Destroy operators, on the current decoded schedule:

  • random: q items drawn uniformly;
  • worst: items whose tasks waited longest after they were ready, the waiting time standing in for the cost an item adds;
  • related: the relatedness removal of Shaw (1998): a random item, then items related to a random already-removed one, relatedness being closeness of start times plus a unit penalty when the two items share no resource.

Worst and related removal draw from their ranked candidate list with the randomised rule of Ropke and Pisinger: position floor(y^p · |L|) for a uniform y in [0, 1) and determinism p.

Repair operators insert the removed items into the partial sequence one at a time. A removed task with several modes loses its mode setting, as a removed request loses its route: every feasible position is scored with the task on AUTO, and at the best position each other mode is scored too. The operators differ in which item goes next:

  • greedy: the item whose best insertion scores best goes first;
  • regret-2: the item that would lose most by missing its best insertion, the gap between its second-best and best insertion scores, goes first.

A new solution is accepted by the simulated-annealing test with a temperature that starts where a solution start_worsening (as a fraction) worse than the initial one is accepted with probability 0.5, and is multiplied by cooling every iteration. Every segment iterations each operator's weight becomes w (1 - reaction) + reaction · π / θ, where θ counts its uses in the segment and π sums its rewards: sigma1 for a new best solution, sigma2 for a better solution not accepted before, sigma3 for a worse one not accepted before but accepted now. The defaults of those parameters are the published ones.

Alns dataclass

Alns(min_removed: int = 1, max_removed: int = 4, segment: int = 100, reaction: float = 0.1, sigma1: float = 33.0, sigma2: float = 9.0, sigma3: float = 13.0, start_worsening: float = 0.05, cooling: float = 0.99975, determinism: float = 6.0)

Adaptive large neighbourhood search (Ropke and Pisinger 2006).

The search starts from a random precedence-feasible sequence. One iteration is one destroy, repair, and acceptance step. Removal sizes are smaller than the published 4 to 40 percent of the requests because every insertion probe decodes a schedule.

Attributes:

Name Type Description
min_removed int

Fewest items removed per iteration.

max_removed int

Most items removed per iteration.

segment int

Iterations between weight updates.

reaction float

Reaction factor r of the weight update.

sigma1 float

Reward for a new best solution.

sigma2 float

Reward for a better solution not accepted before.

sigma3 float

Reward for an accepted worse solution not accepted before.

start_worsening float

A solution this fraction worse than the initial one is accepted with probability 0.5 at the start.

cooling float

Temperature factor per iteration.

determinism float

Exponent p of the randomised choice in worst and related removal.

solve

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

Destroy, repair, and adapt until a stop criterion fires.

dispatchatlas.solvers.trajectory.guided

Guided local search (Voudouris and Tsang 1999).

Guided local search escapes local optima by changing the objective the local search minimises. A solution exhibits features, each with a fixed cost:

  • an item (a task, or a job in permutation problems) at a sequence position, whose cost is the item's mean work;
  • a multi-mode task running in a mode, whose cost is that mode's duration.

The local search minimises the augmented objective f + λ · Σ p_i over the features i present in the solution, where p_i counts how often feature i has been penalised. At each local optimum the features present with the highest utility cost / (1 + p_i) gain one penalty unit, so costly features that keep appearing in local optima are driven out, and each new penalty on a feature matters less than the last. The best solution under the true objective is what the run reports.

The local search is the fast local search of the same authors: the neighbourhood is split into one sub-neighbourhood per item, the exchanges of the item with every other item it may swap with plus the other mode settings of its tasks, each with an activation bit. Active items are scanned in index order. The moves of an item's sub-neighbourhood are tried in random order, and the first that improves the augmented objective is made and activates the items it involves; an item whose moves all fail is deactivated. The descent ends when no item is active. After a penalty update, only the items of the penalised features are activated.

Feature

Feature = tuple[int, int, int]

(0, item, position) for an item at a position, (1, task, mode) for a task in a mode.

Penalties

Penalties(space: SequenceSpace)

Feature penalties and the augmented objective of one run.

Parameters:

Name Type Description Default
space SequenceSpace

The space the features describe.

required

Attributes:

Name Type Description
weight

The penalty weight λ.

counts dict[Feature, int]

Penalty count of every penalised feature.

size property

size: int

Number of features present in every solution.

features

features(solution: Solution) -> list[tuple[Feature, float]]

Return the features present in solution with their costs.

total

total(solution: Solution) -> int

Return the sum of the penalties of the features present in solution.

augmented

augmented(solution: Solution) -> Score

Return the score whose objective carries λ times the solution's penalties.

penalise

penalise(solution: Solution) -> list[int]

Penalise the features of maximum utility in solution.

Returns:

Type Description
list[int]

The items the penalised features belong to, in index order.

GuidedLocalSearch dataclass

GuidedLocalSearch(alpha: float = 0.3)

Guided local search (Voudouris and Tsang 1999) with fast local search.

The search starts from a random precedence-feasible sequence and descends with every item active and no penalty. The penalty weight is then fixed at λ = alpha · |f(s*)| / F, where s* is that first local optimum and F the number of features present in a solution, so one penalty unit is worth alpha times the objective per feature. Each iteration penalises the features of maximum utility in the current local optimum and descends again from it.

Attributes:

Name Type Description
alpha float

Coefficient of the penalty weight.

solve

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

Descend, penalise, and descend again until a stop criterion fires.

dispatchatlas.solvers.trajectory.hyper

A selection hyper-heuristic: learned heuristic choice with late acceptance.

A selection hyper-heuristic searches over heuristics rather than directly over solutions (Burke et al. 2013). At each step it chooses one of several low-level heuristics, applies it to the current solution, and lets a move-acceptance rule decide whether the result becomes the current solution. Here:

  • The low-level heuristics are insert, swap, and mode, each one random move of that kind (see SequenceSpace); ruin_recreate, which removes a few random items and reinserts each at its best position (see rebuild()); and reinsert, which moves one random item to its best position when that improves the solution. Only those the problem allows take part.
  • The heuristic is chosen by reinforcement learning with bounded scores (Nareyek 2003), in the form the survey describes: every heuristic starts at score 0, one whose result improves the current solution gains 1, any other loses 1, scores stay within [0, max_score], and the heuristic with the highest score is applied, ties broken uniformly at random.
  • The result is accepted by late acceptance (Burke and Bykov 2017), the combination studied by Özcan et al. (2009): a result no worse than the current solution, or than the current solution history steps earlier, is kept.

One iteration is one application of one heuristic, whatever it costs in evaluations. The run starts from a random precedence-feasible sequence.

Heuristic

Heuristic = Callable[[SequenceSpace, Solution], Solution]

A low-level heuristic: evaluates and returns a new solution made from the current one.

HeuristicScores

HeuristicScores(count: int, maximum: int)

Bounded reinforcement scores and the max strategy that reads them.

Parameters:

Name Type Description Default
count int

Number of heuristics.

required
maximum int

Upper bound of a score. The lower bound is 0, where scores start.

required

Attributes:

Name Type Description
values

The score of every heuristic.

choose

choose(rng: Random) -> int

Return a heuristic of highest score, drawn uniformly among ties.

update

update(index: int, *, improved: bool) -> None

Raise a heuristic's score by one after an improvement, else lower it by one.

SelectionHyperHeuristic dataclass

SelectionHyperHeuristic(history: int = 5, max_score: int = 10, removed: int = 2)

Reinforcement-learning heuristic selection with late acceptance.

Attributes:

Name Type Description
history int

Length of the late-acceptance cost history, in heuristic applications. They cost several evaluations each, so the default is shorter than that of late-acceptance-hill-climbing.

max_score int

Upper bound of a heuristic's score.

removed int

Items the ruin_recreate heuristic removes.

solve

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

Choose, apply, and accept heuristics until a stop criterion fires.

low_level_heuristics

low_level_heuristics(space: SequenceSpace, removed: int) -> dict[str, Heuristic]

Return the low-level heuristics the problem allows, by name.

Parameters:

Name Type Description Default
space SequenceSpace

The space of the run.

required
removed int

Items the ruin_recreate heuristic removes.

required

dispatchatlas.solvers.trajectory.mode_tabu

Tabu search over mode assignments (De Reyck and Herroelen 1999).

The search space is the mode vector: one mode for every task that has more than one. The schedule of a mode vector is the serial decoding of one fixed priority list, the tasks in decreasing upward rank (see upward_ranks()), so the search changes durations and resource demands and never the priority order. The published method solves this inner fixed-mode problem with a truncated branch and bound.

Following the published tabu search:

  • The search starts with every task in its shortest mode, the published start when no nonrenewable resource constrains the modes.
  • The neighbourhood holds every mode vector in which exactly one task has another mode. Every neighbour is evaluated and the best admissible one is taken, even when it is worse (steepest descent, mildest ascent).
  • After a move from mode x to mode y of a task, moves that give that task mode x again are tabu. The tabu list keeps the attributes of the last L moves. L starts at 2√m for m multi-mode tasks and, after every adjust_after iterations without a new best solution, grows or shrinks by one, or stays, with equal probability, within [√m, 3√m].
  • A tabu move aspires, globally, when it beats the best solution found and, regionally, when it beats the best evaluated solution with that task in that mode. Aspiring moves have a pending status: they are admissible only when no non-tabu move improves the current solution.
  • When no admissible move improves the current solution, the choice is diversified by transition frequencies: a move on a task that has changed mode often is penalised in proportion to its count relative to the highest one. The penalty is diversification times the mean worsening of the evaluated neighbours, so it is measured in the units of the moves themselves.

The published phases of intensification and diversification by residence frequencies, and the aspiration by influence, by search direction, and by strong admissibility are not implemented.

Neighbour dataclass

Neighbour(task: int, mode: int, candidate: Candidate)

An evaluated mode vector one move away from the current one.

Attributes:

Name Type Description
task int

The task whose mode changes.

mode int

Its new mode.

candidate Candidate

The evaluated schedule.

score property

score: Score

The neighbour's score.

rank property

rank: tuple[Score, int, int]

Sort key: score, then task, then mode.

ModeAssignmentTabu dataclass

ModeAssignmentTabu(adjust_after: int = 10, diversification: float = 0.5)

Tabu search over the mode vector of a multi-mode problem.

One iteration evaluates the whole neighbourhood, one evaluation per neighbour, and makes one move. A problem without multi-mode tasks has a single mode vector, which the run evaluates once.

Attributes:

Name Type Description
adjust_after int

Iterations without a new best solution between two random changes of the tabu list length.

diversification float

Weight of the transition-frequency penalty, in mean worsenings of the neighbourhood.

solve

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

Search mode vectors until a stop criterion fires.

tabu_length_bounds

tabu_length_bounds(flexible: int) -> tuple[int, int, int]

Return the lowest, starting, and highest tabu list length for flexible tasks.

The published bounds √m and 3√m and start 2√m, rounded, and at least 1.