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
¶
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
¶
Schedule shorter tasks first.
solve
¶
solve(problem: Problem, stop: StopCriteria, seed: int = 0) -> SolveResult
Decode tasks by increasing duration.
LongestProcessingTime
dataclass
¶
Schedule longer tasks first.
solve
¶
solve(problem: Problem, stop: StopCriteria, seed: int = 0) -> SolveResult
Decode tasks by decreasing duration.
EarliestDueDate
dataclass
¶
Schedule tasks with earlier due dates first.
solve
¶
solve(problem: Problem, stop: StopCriteria, seed: int = 0) -> SolveResult
Decode tasks by due date.
MostWorkRemaining
dataclass
¶
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
¶
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
¶
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
¶
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
¶
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-minandmax-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), intree_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
¶
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. |
tasks
¶
Expand an item sequence into the task order it stands for.
closed_tasks
¶
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
¶
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
¶
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
¶
Return the item sequence of a task order: items by first appearance, repaired.
random_sequence
¶
Return a random feasible sequence, drawing uniformly among ready items.
is_ancestor
¶
Return whether item before must precede item after.
Neh
dataclass
¶
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
¶
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
¶
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
¶
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
¶
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
¶
Squeaky wheel optimization (Joslin and Clements 1999).
Each iteration is one construct, analyse, prioritise cycle:
- construct: decode the priority sequence of items, each task in its earliest-finishing mode;
- analyse: blame every item for its excess cost in that schedule (see
task_blame(); an item's blame is its highest task blame); - prioritise: move every blamed item forward by
steptimes the number of items times its blame over the highest blame, less a random jitter of up tojitterpositions, 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
|
complete
|
bool
|
Whether |
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 |
required |
item
|
int
|
The item to insert. |
required |
modes
|
Sequence[int] | None
|
Mode setting of every task, or |
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
|
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. |
dispatchatlas.solvers.tree_search
¶
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):
- 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 visitedNtimes and a child visitedntimes; - expansion: append one untried eligible item, drawn uniformly, as a new child;
- 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;
- 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
¶
MonteCarloTreeSearch
dataclass
¶
UCT over sequence prefixes with uniformly random rollouts.
Attributes:
| Name | Type | Description |
|---|---|---|
exploration |
float
|
The constant |
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, andlate-acceptance-hill-climbing.tabu: the best admissible neighbour of a sample, with a tabu list.tabu-search.iterated: perturbation plus local search.iterated-local-searchandvariable-neighbourhood-search.greedy: greedy construction plus local search.iterated-greedyandgrasp.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
AUTOtask gets a fixed mode other than the one it runs in, a fixed task getsAUTOor 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
¶
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 |
score |
Score
|
The score of the decoded schedule. |
decoded |
Decoded
|
The decoded schedule, whose |
key
property
¶
A hashable identity of the solution's decisions.
Move
dataclass
¶
A change to a solution.
Attributes:
| Name | Type | Description |
|---|---|---|
kind |
MoveKind
|
|
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
¶
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
¶
Whether any move exists, that is, whether the space holds more than one solution.
kinds
property
¶
The move kinds this problem allows.
Insert and swap, unless precedence fixes the sequence, and mode when some task has several modes.
automatic
property
¶
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
¶
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 |
list[int]
|
task, |
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 |
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
|
|
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 |
None
|
swaps
¶
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
¶
Evaluate a random neighbour of solution, with the move that made it.
perturb
¶
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
¶
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
¶
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.
worsening
¶
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
¶
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
¶
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
¶
Return whether candidate replaces current.
Improvement
dataclass
¶
Metropolis
dataclass
¶
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 |
cooling |
float
|
Factor applied to |
epoch |
int
|
Decisions per temperature. |
decisions |
int
|
Decisions taken so far. |
Threshold
dataclass
¶
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 |
cooling |
float
|
Factor applied to |
epoch |
int
|
Decisions per threshold value. |
decisions |
int
|
Decisions taken so far. |
WaterLevel
dataclass
¶
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. |
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. |
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 |
iteration |
int
|
Decisions taken so far. |
HillClimbing
dataclass
¶
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
¶
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
¶
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
¶
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
¶
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 |
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
¶
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
¶
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
¶
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
¶
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 |
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
¶
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:
- destroys: removes
destructionitems drawn at random; - 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;
- improves the result by local search, when
local_searchis set; - accepts it when it is better than the current solution, and
otherwise with probability
exp(-Δ/temperature), where the constant temperature istemperature * mean task duration / 10, the publishedT · Σ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 |
temperature |
float
|
The published temperature factor |
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
¶
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:
qitems 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 |
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 |
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
¶
(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. |
GuidedLocalSearch
dataclass
¶
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, andmode, each one random move of that kind (seeSequenceSpace);ruin_recreate, which removes a few random items and reinserts each at its best position (seerebuild()); andreinsert, 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
historysteps 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
¶
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. |
SelectionHyperHeuristic
dataclass
¶
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 |
max_score |
int
|
Upper bound of a heuristic's score. |
removed |
int
|
Items the |
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 |
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
xto modeyof a task, moves that give that task modexagain are tabu. The tabu list keeps the attributes of the lastLmoves.Lstarts at2√mformmulti-mode tasks and, after everyadjust_afteriterations 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
diversificationtimes 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. |
ModeAssignmentTabu
dataclass
¶
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
¶
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.