Solver catalogue¶
Every solver of DispatchAtlas, generated from the solver registry when this
site is built. For each solver: what it does, the parameters it takes with
their defaults, the problem features it does not model, the extra it needs,
and the sources it implements. The same facts are available from the command
line with dispatchatlas solvers show ID, and in Python from
default_registry().info(id).
"Stochastic" solvers draw from the run's seed, "deterministic" ones ignore it. Solvers that run "until a stop criterion" need a time, evaluation, or iteration limit; the others finish on their own and still honour the limits they are given (see Solvers).
DispatchAtlas registers 72 solvers in 12 families. Every solver can be run by its id from Python, from the command line, and in campaign files.
| Solver | Family | Runs | Extra |
|---|---|---|---|
earliest-due-date |
dispatching-rule | deterministic, to completion | - |
input-order |
dispatching-rule | deterministic, to completion | - |
least-slack |
dispatching-rule | deterministic, to completion | - |
longest-processing-time |
dispatching-rule | deterministic, to completion | - |
longest-remaining-path |
dispatching-rule | deterministic, to completion | - |
most-work-remaining |
dispatching-rule | deterministic, to completion | - |
shortest-processing-time |
dispatching-rule | deterministic, to completion | - |
heft |
list-scheduling | deterministic, to completion | - |
max-min |
list-scheduling | deterministic, to completion | - |
min-min |
list-scheduling | deterministic, to completion | - |
sufferage |
list-scheduling | deterministic, to completion | - |
beam-search |
constructive | deterministic, to completion | - |
monte-carlo-tree-search |
constructive | stochastic, until a stop criterion | - |
neh |
constructive | deterministic, to completion | - |
squeaky-wheel-optimization |
constructive | stochastic, until a stop criterion | - |
alns |
local-search | stochastic, until a stop criterion | - |
grasp |
local-search | stochastic, until a stop criterion | - |
great-deluge |
local-search | stochastic, until a stop criterion | - |
guided-local-search |
local-search | stochastic, until a stop criterion | - |
hill-climbing |
local-search | stochastic, until a stop criterion | - |
iterated-greedy |
local-search | stochastic, until a stop criterion | - |
iterated-local-search |
local-search | stochastic, until a stop criterion | - |
late-acceptance-hill-climbing |
local-search | stochastic, until a stop criterion | - |
mode-assignment-tabu |
local-search | stochastic, until a stop criterion | - |
record-to-record-travel |
local-search | stochastic, until a stop criterion | - |
simulated-annealing |
local-search | stochastic, until a stop criterion | - |
tabu-search |
local-search | stochastic, until a stop criterion | - |
threshold-accepting |
local-search | stochastic, until a stop criterion | - |
variable-neighbourhood-search |
local-search | stochastic, until a stop criterion | - |
ant-colony-optimization |
population | stochastic, until a stop criterion | - |
brkga |
population | stochastic, until a stop criterion | - |
cma-es |
population | stochastic, until a stop criterion | - |
differential-evolution |
population | stochastic, until a stop criterion | - |
genetic-algorithm |
population | stochastic, until a stop criterion | - |
lshade |
population | stochastic, until a stop criterion | - |
memetic-algorithm |
population | stochastic, until a stop criterion | - |
scatter-search |
population | stochastic, until a stop criterion | - |
umda |
population | stochastic, until a stop criterion | - |
arithmetic-optimization-algorithm |
swarm | stochastic, until a stop criterion | - |
artificial-bee-colony |
swarm | stochastic, until a stop criterion | - |
clpso |
swarm | stochastic, until a stop criterion | - |
cuckoo-search |
swarm | stochastic, until a stop criterion | - |
firefly-algorithm |
swarm | stochastic, until a stop criterion | - |
gravitational-search-algorithm |
swarm | stochastic, until a stop criterion | - |
grey-wolf-optimizer |
swarm | stochastic, until a stop criterion | - |
harris-hawks-optimization |
swarm | stochastic, until a stop criterion | - |
jaya |
swarm | stochastic, until a stop criterion | - |
marine-predators-algorithm |
swarm | stochastic, until a stop criterion | - |
moth-flame-optimization |
swarm | stochastic, until a stop criterion | - |
particle-swarm-optimization |
swarm | stochastic, until a stop criterion | - |
salp-swarm-algorithm |
swarm | stochastic, until a stop criterion | - |
sine-cosine-algorithm |
swarm | stochastic, until a stop criterion | - |
teaching-learning-based-optimization |
swarm | stochastic, until a stop criterion | - |
whale-optimization-algorithm |
swarm | stochastic, until a stop criterion | - |
age-moea-ii |
multi-objective | stochastic, until a stop criterion, multi-objective | - |
ibea |
multi-objective | stochastic, until a stop criterion, multi-objective | - |
moea-d |
multi-objective | stochastic, until a stop criterion, multi-objective | - |
nsga-ii |
multi-objective | stochastic, until a stop criterion, multi-objective | - |
nsga-iii |
multi-objective | stochastic, until a stop criterion, multi-objective | - |
rvea |
multi-objective | stochastic, until a stop criterion, multi-objective | - |
sms-emoa |
multi-objective | stochastic, until a stop criterion, multi-objective | - |
spea2 |
multi-objective | stochastic, until a stop criterion, multi-objective | - |
cp-sat |
exact | deterministic, until a stop criterion | exact |
enumeration |
exact | deterministic, to completion | - |
milp |
exact | deterministic, to completion | exact |
restricted-neighbourhood-search |
matheuristic | stochastic, until a stop criterion | exact |
q-learning-dispatching |
learning | stochastic, until a stop criterion | - |
reinforce-priority-policy |
learning | stochastic, until a stop criterion | - |
sarsa-dispatching |
learning | stochastic, until a stop criterion | - |
gp-hyper-heuristic |
hyper-heuristic | stochastic, until a stop criterion | - |
selection-hyper-heuristic |
hyper-heuristic | stochastic, until a stop criterion | - |
random-search |
random-sampling | stochastic, until a stop criterion | - |
Dispatching rule¶
Builds one schedule from a fixed priority rule.
Earliest due date¶
Decodes tasks by increasing due date, inherited from the task's group when the task has none.
- Id:
earliest-due-date; implemented byEarliestDueDate - Runs: deterministic, to completion
- Parameters: none
- Models: every feature
- Sources: Panwalkar and Iskander (1977); Kolisch (1996)
Input order¶
Decodes tasks by release time, then in their listed order, a first-come first-served baseline.
- Id:
input-order; implemented byInputOrder - Runs: deterministic, to completion
- Parameters: none
- Models: every feature
- Sources: Kolisch (1996)
Least slack¶
Decodes tasks by increasing slack, the due date minus the longest remaining path, which approximates the latest start time.
- Id:
least-slack; implemented byLeastSlack - Runs: deterministic, to completion
- Parameters: none
- Models: every feature
- Sources: Panwalkar and Iskander (1977); Kolisch (1996)
Longest processing time¶
Decodes tasks in decreasing order of their shortest duration, which balances load on parallel resources.
- Id:
longest-processing-time; implemented byLongestProcessingTime - Runs: deterministic, to completion
- Parameters: none
- Models: every feature
- Sources: Panwalkar and Iskander (1977); Kolisch (1996)
Longest remaining path¶
Decodes tasks by decreasing length of the longest dependency path from their start to the end of the problem, the critical-path rule.
- Id:
longest-remaining-path; implemented byLongestRemainingPath - Runs: deterministic, to completion
- Parameters: none
- Models: every feature
- Sources: Kolisch (1996)
Most work remaining¶
Decodes tasks by decreasing work left in their group from the task on.
- Id:
most-work-remaining; implemented byMostWorkRemaining - Runs: deterministic, to completion
- Parameters: none
- Models: every feature
- Sources: Panwalkar and Iskander (1977); Kolisch (1996)
Shortest processing time¶
Decodes tasks in increasing order of their shortest duration.
- Id:
shortest-processing-time; implemented byShortestProcessingTime - Runs: deterministic, to completion
- Parameters: none
- Models: every feature
- Sources: Smith (1956); Panwalkar and Iskander (1977)
List scheduling¶
Ranks tasks, then maps each to the resource that finishes it first.
Heterogeneous earliest finish time¶
Ranks tasks by upward rank, the mean duration plus the longest mean-communication path to the end, then places each on the mode that finishes it earliest, filling idle gaps.
- Id:
heft; implemented byHeft - Runs: deterministic, to completion
- Parameters: none
- Models: every feature
- Sources: Topcuoglu et al. (2002)
Max-min¶
Repeatedly places, among the eligible tasks, the one whose earliest completion time over its modes is largest, in the mode that achieves it.
- Id:
max-min; implemented byMaxMin - Runs: deterministic, to completion
- Parameters: none
- Does not model: permutation
- Sources: Braun et al. (2001); Ibarra and Kim (1977)
Min-min¶
Repeatedly places, among the eligible tasks, the one whose earliest completion time over its modes is smallest, in the mode that achieves it.
- Id:
min-min; implemented byMinMin - Runs: deterministic, to completion
- Parameters: none
- Does not model: permutation
- Sources: Braun et al. (2001); Ibarra and Kim (1977)
Sufferage¶
Maps tasks in passes where each resource goes to the claiming task that would lose the most, second-best minus best completion time, without its best mode.
- Id:
sufferage; implemented bySufferage - Runs: deterministic, to completion
- Parameters: none
- Does not model: permutation
- Sources: Maheswaran et al. (1999)
Constructive¶
Builds a schedule step by step with look-ahead or insertion.
Filtered beam search¶
Keeps the best partial schedules, extends each by its highest-priority eligible items, and ranks the extensions by the score of their completion under the upward-rank rule.
- Id:
beam-search; implemented byBeamSearch - Runs: deterministic, to completion
- Parameters:
width=3,filter_width=5 - Models: every feature
- Sources: Ow and Morton (1988); Sabuncuoglu and Bayiz (1999); Topcuoglu et al. (2002)
Monte Carlo tree search¶
Grows a tree of sequence prefixes by UCB1 selection and expansion of one eligible task per playout, completes each playout with random eligible tasks, and backs up rank-normalised rewards.
- Id:
monte-carlo-tree-search; implemented byMonteCarloTreeSearch - Runs: stochastic, until a stop criterion
- Parameters:
exploration=0.3 - Models: every feature
- Sources: Kocsis and Szepesvári (2006); Auer et al. (2002)
NEH insertion¶
Takes tasks, or whole jobs, in decreasing order of total work and inserts each at the position of the growing sequence whose partial schedule scores best.
- Id:
neh; implemented byNeh - Runs: deterministic, to completion
- Parameters: none
- Models: every feature
- Sources: Nawaz et al. (1983)
Squeaky wheel optimization¶
Repeatedly decodes a priority sequence, blames each task for its cost beyond the least it could incur, and moves blamed tasks forward by distances that grow with their blame.
- Id:
squeaky-wheel-optimization; implemented bySqueakyWheel - Runs: stochastic, until a stop criterion
- Parameters:
step=0.5,jitter=1.0,restart_after=50 - Models: every feature
- Sources: Joslin and Clements (1999)
Local search¶
Improves one solution through neighbourhood moves.
Adaptive large neighbourhood search¶
Removes and greedily reinserts groups of tasks with destroy and repair operators drawn by adaptive roulette weights, accepting results by simulated annealing.
- Id:
alns; implemented byAlns - Runs: stochastic, until a stop criterion
- Parameters:
min_removed=1,max_removed=4,segment=100,reaction=0.1,sigma1=33.0,sigma2=9.0,sigma3=13.0,start_worsening=0.05,cooling=0.99975,determinism=6.0 - Models: every feature
- Sources: Ropke and Pisinger (2006); Shaw (1998)
GRASP¶
Builds schedules by drawing each next task from those whose earliest completion time is within a fraction of the best, then improves each by a first-improvement climb.
- Id:
grasp; implemented byGrasp - Runs: stochastic, until a stop criterion
- Parameters:
alpha=0.3,max_failures=100 - Models: every feature
- Sources: Feo and Resende (1995)
Great deluge¶
Accepts any random neighbour whose cost is below a water level that drops by a fixed amount at each accepted move.
- Id:
great-deluge; implemented byGreatDeluge - Runs: stochastic, until a stop criterion
- Parameters:
initial_margin=1.0,rain_speed=0.01 - Models: every feature
- Sources: Dueck (1993)
Guided local search¶
Descends on the objective plus penalties on solution features, items at positions and tasks in modes, and at each local optimum penalises the features whose cost over one plus their penalty is highest.
- Id:
guided-local-search; implemented byGuidedLocalSearch - Runs: stochastic, until a stop criterion
- Parameters:
alpha=0.3 - Models: every feature
- Sources: Voudouris and Tsang (1999)
Hill climbing¶
Moves to each sampled insert, swap, or mode neighbour that improves the current solution and restarts from a random sequence after a run of non-improving samples.
- Id:
hill-climbing; implemented byHillClimbing - Runs: stochastic, until a stop criterion
- Parameters:
restart_after=100 - Models: every feature
- Sources: Hoos and Stützle (2004)
Iterated greedy¶
Removes a few random tasks or jobs from the current sequence, reinserts each at its best position, and accepts the result at a constant temperature, starting from NEH.
- Id:
iterated-greedy; implemented byIteratedGreedy - Runs: stochastic, until a stop criterion
- Parameters:
destruction=4,temperature=0.4,local_search=True - Models: every feature
- Sources: Ruiz and Stützle (2007); Nawaz et al. (1983)
Iterated local search¶
Perturbs the current local optimum with a few random moves, climbs to a new local optimum by first improvement, and keeps it when it is no worse.
- Id:
iterated-local-search; implemented byIteratedLocalSearch - Runs: stochastic, until a stop criterion
- Parameters:
strength=3,max_failures=100 - Models: every feature
- Sources: Lourenço et al. (2003)
Late acceptance hill climbing¶
Accepts a random neighbour that is no worse than the current solution or than the current solution a fixed number of iterations earlier.
- Id:
late-acceptance-hill-climbing; implemented byLateAcceptanceHillClimbing - Runs: stochastic, until a stop criterion
- Parameters:
history=50 - Models: every feature
- Sources: Burke and Bykov (2017)
Mode-assignment tabu search¶
Moves each iteration to the best admissible mode vector that changes one task's mode, decoding a fixed priority list, with a tabu list of recently vacated modes, aspiration by objective, and frequency-based diversification.
- Id:
mode-assignment-tabu; implemented byModeAssignmentTabu - Runs: stochastic, until a stop criterion
- Parameters:
adjust_after=10,diversification=0.5 - Models: every feature
- Sources: De Reyck and Herroelen (1999)
Record-to-record travel¶
Accepts any random neighbour whose cost is below the best cost the walk has reached plus a fixed deviation.
- Id:
record-to-record-travel; implemented byRecordToRecordTravel - Runs: stochastic, until a stop criterion
- Parameters:
deviation=0.2 - Models: every feature
- Sources: Dueck (1993)
Simulated annealing¶
Accepts a worse random neighbour with probability exp(-Δ/T), where T starts at a target acceptance rate of sampled worsening moves and cools geometrically.
- Id:
simulated-annealing; implemented bySimulatedAnnealing - Runs: stochastic, until a stop criterion
- Parameters:
initial_acceptance=0.5,cooling=0.95,epoch=None - Models: every feature
- Sources: Kirkpatrick et al. (1983); Johnson et al. (1989)
Tabu search¶
Moves to the best of a sample of neighbours while forbidding, for a fixed tenure, moves that restore recently removed item positions or task modes, unless they beat the best solution found.
- Id:
tabu-search; implemented byTabuSearch - Runs: stochastic, until a stop criterion
- Parameters:
tenure=7,candidates=20 - Models: every feature
- Sources: Glover (1986); Glover (1989)
Threshold accepting¶
Accepts any random neighbour less than a threshold worse than the current solution and lowers the threshold geometrically.
- Id:
threshold-accepting; implemented byThresholdAccepting - Runs: stochastic, until a stop criterion
- Parameters:
initial_threshold=1.0,cooling=0.95,epoch=None - Models: every feature
- Sources: Dueck and Scheuer (1990)
Variable neighbourhood search¶
Shakes the current local optimum by k random moves, climbs by first improvement, and moves on improvement with k reset to 1, otherwise tries the next larger k.
- Id:
variable-neighbourhood-search; implemented byVariableNeighbourhoodSearch - Runs: stochastic, until a stop criterion
- Parameters:
max_neighbourhood=5,max_failures=100 - Models: every feature
- Sources: Mladenović and Hansen (1997)
Population¶
Evolves a population of solutions through variation and selection.
MAX-MIN Ant System¶
Builds task sequences position by position from bounded pheromone trails on (task, position) pairs and a priority-rule desirability, and lets the best solution reinforce its trails.
- Id:
ant-colony-optimization; implemented byAntColonyOptimization - Runs: stochastic, until a stop criterion
- Parameters:
ants=10,alpha=1.0,beta=1.0,heuristic='auto',evaporation=0.1,best_probability=0.05,deposit='iteration-best',modes='builder' - Models: every feature
- Sources: Stützle and Hoos (2000); Dorigo et al. (1996); Merkle et al. (2002); Topcuoglu et al. (2002)
Biased random-key genetic algorithm¶
Keeps the elite random-key chromosomes, adds random mutants, and fills the population with crossings of an elite and a non-elite parent that favour the elite parent's keys.
- Id:
brkga; implemented byBrkga - Runs: stochastic, until a stop criterion
- Parameters:
seeded=False,modes='keys',population_size=None,elite_fraction=0.2,mutant_fraction=0.15,inheritance=0.7 - Models: every feature
- Sources: Gonçalves and Resende (2011); Bean (1994)
CMA-ES¶
Samples random-key vectors from a multivariate normal distribution, moves its mean to the weighted mean of the best samples, and adapts its step size and covariance matrix from evolution paths and the selected steps.
- Id:
cma-es; implemented byCmaEs - Runs: stochastic, until a stop criterion
- Parameters:
seeded=False,modes='keys',population_size=None,step_size=0.3 - Models: every feature
- Sources: Hansen and Ostermeier (2001); Hansen et al. (2003); Hansen (2016); Bean (1994)
Differential evolution¶
Adds a scaled difference of two random members to a third, crosses the result with each member coordinate by coordinate, and keeps the trial when it is no worse, over random-key vectors.
- Id:
differential-evolution; implemented byDifferentialEvolution - Runs: stochastic, until a stop criterion
- Parameters:
seeded=False,modes='keys',population_size=None,scale_factor=0.5,crossover_rate=0.1 - Models: every feature
- Sources: Storn and Price (1997); Bean (1994); Zhang and Sanderson (2009)
Genetic algorithm¶
Evolves task sequences and mode settings by tournament selection, order crossover, uniform mode crossover, and insert, swap, or mode mutation, keeping the best members from one generation to the next.
- Id:
genetic-algorithm; implemented byGeneticAlgorithm - Runs: stochastic, until a stop criterion
- Parameters:
population_size=30,crossover_rate=0.9,mutation_rate=0.2,tournament_size=2,elites=2 - Models: every feature
- Sources: Holland (1992); Davis (1985); Hartmann (1998)
L-SHADE¶
Evolves random-key vectors by current-to-pbest differential mutation with an archive, draws each trial's crossover rate and scale factor from a memory of successful values, and shrinks the population linearly over the budget.
- Id:
lshade; implemented byLShade - Runs: stochastic, until a stop criterion
- Parameters:
seeded=False,modes='keys',population_size=None,min_population=4,memory_size=6,best_fraction=0.11,archive_rate=2.6 - Models: every feature
- Sources: Tanabe and Fukunaga (2014); Tanabe and Fukunaga (2013); Zhang and Sanderson (2009); Bean (1994)
Memetic algorithm¶
Evolves task sequences and mode settings like the genetic algorithm and improves every child by an insertion local search, so that the population holds local optima.
- Id:
memetic-algorithm; implemented byMemeticAlgorithm - Runs: stochastic, until a stop criterion
- Parameters:
population_size=20,crossover_rate=0.9,mutation_rate=0.2,tournament_size=2,elites=2,local_search_rate=1.0 - Models: every feature
- Sources: Moscato (1989); Davis (1985); Ruiz and Stützle (2007)
Scatter search¶
Keeps a reference set of good and mutually distant task sequences, combines pairs of them by averaging item positions, improves each combination by local search, and rebuilds the set from new diverse solutions when it stops changing.
- Id:
scatter-search; implemented byScatterSearch - Runs: stochastic, until a stop criterion
- Parameters:
population_size=20,reference_size=8,quality_size=4,max_failures=50 - Models: every feature
- Sources: Glover (1998); Martí et al. (2006)
Univariate marginal distribution algorithm¶
Fits an independent normal distribution per random key to the best members and samples the next population from their product.
- Id:
umda; implemented byUmda - Runs: stochastic, until a stop criterion
- Parameters:
seeded=False,modes='keys',population_size=100,selection_fraction=0.5,elites=1 - Models: every feature
- Sources: Mühlenbein and Paaß (1996); Larrañaga and Lozano (2002); Bean (1994)
Swarm¶
Moves a population of real-valued priority vectors by update rules.
Arithmetic Optimization Algorithm¶
Resamples each vector component around the best vector by multiplying or dividing early and by adding or subtracting late, with a step that shrinks over the budget.
- Id:
arithmetic-optimization-algorithm; implemented byArithmeticOptimizationAlgorithm - Runs: stochastic, until a stop criterion
- Parameters:
population_size=20,rule='random-key',modes='keys',moa_min=0.2,moa_max=0.9,alpha=5.0,mu=0.5 - Models: every feature
- Sources: Abualigah et al. (2021); Bean (1994)
Artificial Bee Colony¶
Moves one random component of each vector towards or away from a random member, repeats this for members drawn in proportion to their quality, keeps only improvements, and restarts the vector that failed to improve longest.
- Id:
artificial-bee-colony; implemented byArtificialBeeColony - Runs: stochastic, until a stop criterion
- Parameters:
population_size=20,rule='random-key',modes='keys',limit=None - Models: every feature
- Sources: Karaboga and Basturk (2007); Deb (2000); Bean (1994)
Comprehensive learning particle swarm optimizer¶
Moves random-key vectors toward exemplars whose coordinates come from different particles' best positions, drawing new exemplars for a particle that stops improving.
- Id:
clpso; implemented byClpso - Runs: stochastic, until a stop criterion
- Parameters:
seeded=False,modes='keys',population_size=40,inertia_start=0.9,inertia_end=0.4,acceleration=1.49445,refresh_gap=7,velocity_limit=0.2 - Models: every feature
- Sources: Liang et al. (2006); Bean (1994)
Cuckoo Search¶
Perturbs each vector with Lévy steps scaled by its offset from the best vector, keeps every move that is not worse, and replaces a fixed fraction of the worst vectors with random ones.
- Id:
cuckoo-search; implemented byCuckooSearch - Runs: stochastic, until a stop criterion
- Parameters:
population_size=20,rule='random-key',modes='keys',step_size=0.01,replaced_fraction=0.25 - Models: every feature
- Sources: Yang and Deb (2009); Mantegna (1994); Bean (1994)
Firefly Algorithm¶
Pulls each vector towards every better vector of the previous iteration with a strength that decays exponentially with the squared distance, adding uniform noise that shrinks geometrically.
- Id:
firefly-algorithm; implemented byFireflyAlgorithm - Runs: stochastic, until a stop criterion
- Parameters:
population_size=20,rule='random-key',modes='keys',attraction=1.0,attraction_decay=1.0,noise=0.25,noise_decay=0.97 - Models: every feature
- Sources: Yang (2009); Yang (2014); Bean (1994)
Gravitational Search Algorithm¶
Accelerates each vector towards the members of highest quality, weighted by quality over distance, with a gain that decays exponentially, a number of attracting members that shrinks to one, and random momentum.
- Id:
gravitational-search-algorithm; implemented byGravitationalSearchAlgorithm - Runs: stochastic, until a stop criterion
- Parameters:
population_size=20,rule='random-key',modes='keys',gain=100.0,gain_decay=20.0 - Models: every feature
- Sources: Rashedi et al. (2009); Deb (2000); Bean (1994)
Grey Wolf Optimizer¶
Moves every vector to the mean of three random points drawn around the three best vectors found so far, with a spread that shrinks linearly to zero over the budget.
- Id:
grey-wolf-optimizer; implemented byGreyWolfOptimizer - Runs: stochastic, until a stop criterion
- Parameters:
population_size=20,rule='random-key',modes='keys' - Models: every feature
- Sources: Mirjalili et al. (2014); Bean (1994)
Harris Hawks Optimization¶
Moves each vector by a rule chosen with a random coefficient whose range shrinks over the budget: jumps relative to random members and the population mean while it is large, contractions towards the best vector and greedy trials with Lévy perturbations while it is small.
- Id:
harris-hawks-optimization; implemented byHarrisHawksOptimization - Runs: stochastic, until a stop criterion
- Parameters:
population_size=20,rule='random-key',modes='keys' - Models: every feature
- Sources: Heidari et al. (2019); Mantegna (1994); Bean (1994)
Jaya¶
Moves each vector towards the best and away from the worst member of the population by random amounts per component, keeping the move only if it improves the vector.
- Id:
jaya; implemented byJaya - Runs: stochastic, until a stop criterion
- Parameters:
population_size=20,rule='random-key',modes='keys' - Models: every feature
- Sources: Rao (2016); Bean (1994)
Marine Predators Algorithm¶
Moves vectors relative to the best vector with Gaussian steps early, Lévy steps late and a mix of both in between, then applies masked random jumps or scaled member differences, keeping every change that is not worse.
- Id:
marine-predators-algorithm; implemented byMarinePredatorsAlgorithm - Runs: stochastic, until a stop criterion
- Parameters:
population_size=20,rule='random-key',modes='keys',step_scale=0.5,jump_probability=0.2 - Models: every feature
- Sources: Faramarzi et al. (2020); Mantegna (1994); Bean (1994)
Moth-Flame Optimization¶
Moves each vector along a logarithmic spiral around one of the best vectors found so far, sharing a number of those vectors that shrinks to one over the budget.
- Id:
moth-flame-optimization; implemented byMothFlameOptimization - Runs: stochastic, until a stop criterion
- Parameters:
population_size=20,rule='random-key',modes='keys',spiral_shape=1.0 - Models: every feature
- Sources: Mirjalili (2015); Bean (1994)
Particle swarm optimization¶
Moves random-key vectors with velocities that combine inertia, a pull toward each particle's best position, and a pull toward the swarm's best, with the inertia weight decreasing over the budget.
- Id:
particle-swarm-optimization; implemented byParticleSwarmOptimization - Runs: stochastic, until a stop criterion
- Parameters:
seeded=False,modes='keys',population_size=30,inertia_start=0.9,inertia_end=0.4,cognitive=2.0,social=2.0,velocity_limit=1.0 - Models: every feature
- Sources: Kennedy and Eberhart (1995); Shi and Eberhart (1998); Shi and Eberhart (1999); Bean (1994)
Salp Swarm Algorithm¶
Resamples the first vector of a chain around the best vector with a spread that shrinks over the budget, then moves every other vector halfway to the one ahead of it.
- Id:
salp-swarm-algorithm; implemented bySalpSwarmAlgorithm - Runs: stochastic, until a stop criterion
- Parameters:
population_size=20,rule='random-key',modes='keys' - Models: every feature
- Sources: Mirjalili et al. (2017); Bean (1994)
Sine Cosine Algorithm¶
Moves each vector component by a sine- or cosine-weighted random multiple of its distance to a random rescaling of the best vector, with an amplitude that shrinks linearly.
- Id:
sine-cosine-algorithm; implemented bySineCosineAlgorithm - Runs: stochastic, until a stop criterion
- Parameters:
population_size=20,rule='random-key',modes='keys',amplitude=2.0 - Models: every feature
- Sources: Mirjalili (2016); Bean (1994)
Teaching-Learning-Based Optimization¶
Moves each vector towards the best member and away from the population mean, then towards a better or away from a worse random member, keeping each move only if it improves the vector.
- Id:
teaching-learning-based-optimization; implemented byTeachingLearningBasedOptimization - Runs: stochastic, until a stop criterion
- Parameters:
population_size=20,rule='random-key',modes='keys' - Models: every feature
- Sources: Rao et al. (2011); Bean (1994)
Whale Optimization Algorithm¶
Moves each vector by a shrinking random multiple of its distance to the best vector or to a random member, or along a logarithmic spiral around the best vector, choosing between the two by a fair coin.
- Id:
whale-optimization-algorithm; implemented byWhaleOptimizationAlgorithm - Runs: stochastic, until a stop criterion
- Parameters:
population_size=20,rule='random-key',modes='keys',spiral_shape=1.0 - Models: every feature
- Sources: Mirjalili and Lewis (2016); Bean (1994)
Multi objective¶
Approximates the Pareto front of several objectives.
AGE-MOEA-II¶
Breeds task sequences and modes by binary tournaments on rank and survival score, fits the curvature of the first non-dominated front by Newton's method, and keeps members by their geodesic spread on the fitted surface and, in later fronts, by proximity to the ideal point.
- Id:
age-moea-ii; implemented byAgeMoea2 - Runs: stochastic, until a stop criterion, multi-objective
- Parameters:
population_size=40,crossover_rate=0.9,mutation_rate=0.2,mode_mutation=1.0 - Models: every feature
- Sources: Panichella (2022); Panichella (2019); Deb et al. (2002); Davis (1985)
IBEA¶
Breeds task sequences and modes by binary tournaments on fitness from the additive epsilon indicator between members, and removes the least fit member one at a time, updating the others' fitness, until the population fits.
- Id:
ibea; implemented byIbea - Runs: stochastic, until a stop criterion, multi-objective
- Parameters:
population_size=40,crossover_rate=0.9,mutation_rate=0.2,mode_mutation=1.0,kappa=0.05 - Models: every feature
- Sources: Zitzler and Künzli (2004); Deb et al. (2002); Davis (1985)
MOEA/D¶
Decomposes the objectives into Tchebycheff subproblems along Das and Dennis weight vectors, each holding one schedule, and lets a child bred from a subproblem's neighbourhood replace every neighbour that it scalarises no worse.
- Id:
moea-d; implemented byMoeaD - Runs: stochastic, until a stop criterion, multi-objective
- Parameters:
population_size=40,crossover_rate=0.9,mutation_rate=0.2,mode_mutation=1.0,neighbourhood_size=20 - Models: every feature
- Sources: Zhang and Li (2007); Das and Dennis (1998); Deb et al. (2002); Davis (1985)
NSGA-II¶
Breeds task sequences and modes by crowded binary tournaments, order crossover, and insert, swap, and mode mutation, then keeps the parents and children of lowest non-dominated rank and, in the last front, of largest crowding distance.
- Id:
nsga-ii; implemented byNsga2 - Runs: stochastic, until a stop criterion, multi-objective
- Parameters:
population_size=40,crossover_rate=0.9,mutation_rate=0.2,mode_mutation=1.0 - Models: every feature
- Sources: Deb et al. (2002); Davis (1985)
NSGA-III¶
Breeds task sequences and modes from random parents by order crossover and insert, swap, and mode mutation, then keeps whole non-dominated fronts and fills the last one by niching normalised objective vectors around Das and Dennis reference points.
- Id:
nsga-iii; implemented byNsga3 - Runs: stochastic, until a stop criterion, multi-objective
- Parameters:
population_size=40,crossover_rate=0.9,mutation_rate=0.2,mode_mutation=1.0 - Models: every feature
- Sources: Deb and Jain (2014); Das and Dennis (1998); Deb et al. (2002); Davis (1985)
RVEA¶
Breeds task sequences and modes from random parents and keeps, for each reference vector, the member of smallest angle-penalised distance, a penalty that shifts selection from convergence to spread as the budget is used, rescaling the vectors to the objectives' ranges at fixed budget fractions.
- Id:
rvea; implemented byRvea - Runs: stochastic, until a stop criterion, multi-objective
- Parameters:
population_size=40,crossover_rate=0.9,mutation_rate=0.2,mode_mutation=1.0,alpha=2.0,adaptation_frequency=0.1 - Models: every feature
- Sources: Cheng et al. (2016); Das and Dennis (1998); Davis (1985)
SMS-EMOA¶
Breeds one child at a time from random parents by order crossover and insert, swap, and mode mutation, then removes the member of the last non-dominated front with the smallest exact hypervolume contribution, keeping the front's best member in each objective.
- Id:
sms-emoa; implemented bySmsEmoa - Runs: stochastic, until a stop criterion, multi-objective
- Parameters:
population_size=40,crossover_rate=0.9,mutation_rate=0.2,mode_mutation=1.0 - Models: every feature
- Sources: Beume et al. (2007); Emmerich et al. (2005); Deb et al. (2002); Davis (1985)
SPEA2¶
Breeds task sequences and modes by binary tournaments on strength fitness, the summed strengths of dominating members plus a nearest-neighbour density, and keeps an archive of the non-dominated members, truncated by distance to the nearest neighbours.
- Id:
spea2; implemented bySpea2 - Runs: stochastic, until a stop criterion, multi-objective
- Parameters:
population_size=40,crossover_rate=0.9,mutation_rate=0.2,mode_mutation=1.0 - Models: every feature
- Sources: Zitzler et al. (2001); Deb et al. (2002); Davis (1985)
Exact¶
Proves optimality or infeasibility with a mathematical model.
CP-SAT interval model¶
States each task as optional intervals, one per mode with exactly one present, under no-overlap, cumulative, precedence, and circuit constraints, and proves optimality with the OR-Tools CP-SAT solver, which combines clause learning with linear relaxations.
- Id:
cp-sat; implemented byCpSat - Runs: deterministic, until a stop criterion
- Parameters:
threads=1,relative_gap=0.0,log=False - Models: every feature
- Needs: the
exactextra - Sources: Perron and Furnon (2026); Perron et al. (2023)
Exhaustive enumeration¶
Decodes every precedence-feasible task order under every mode vector with the serial schedule builder, expanding each distinct partial schedule once, and returns the best schedule, which is optimal for regular objectives.
- Id:
enumeration; implemented byEnumeration - Runs: deterministic, to completion
- Parameters:
max_tasks=8 - Does not model: setups
- Sources: Kolisch (1996); Sprecher et al. (1995)
Time-indexed MILP¶
Formulates the problem as a 0-1 program with one binary per task, mode, and start period, capacity rows per resource and period, and precedence rows on start times, and solves it by branch and bound with CBC, HiGHS, Gurobi, or SCIP.
- Id:
milp; implemented byTimeIndexedMilp - Runs: deterministic, to completion
- Parameters:
backend='cbc',threads=1,relative_gap=0.0,max_variables=200000 - Does not model: network, permutation, setups
- Needs: the
exactextra - Sources: Pritsker et al. (1969); Talbot (1982); Mitchell et al. (2011); Forrest and Lougee-Heimer (2005); Huangfu and Hall (2018)
Matheuristic¶
Improves a solution by solving restricted subproblems exactly.
Restricted neighbourhood search¶
Frees the tasks that start in a random window of the incumbent schedule, keeps every other task's mode and resource order, solves the restricted problem exactly with the CP-SAT interval model, and keeps the result when it is no worse.
- Id:
restricted-neighbourhood-search; implemented byRestrictedNeighbourhoodSearch - Runs: stochastic, until a stop criterion
- Parameters:
window=8,call_limit=1.0 - Models: every feature
- Needs: the
exactextra - Sources: Shaw (1998); Pisinger and Ropke (2010)
Learning¶
Learns a scheduling policy from experience gathered while solving.
Q-learning dispatching¶
Learns which of four dispatching rules should pick the next task in each coarse state of the construction by one-step Q-learning, bootstrapping from the best action value of the next state, and builds schedules with epsilon-greedy rule choices.
- Id:
q-learning-dispatching; implemented byTemporalDifferenceDispatching - Runs: stochastic, until a stop criterion
- Parameters:
learning_rate=0.5,discount=0.9,exploration=0.3,stage_buckets=4 - Does not model: permutation
- Sources: Watkins and Dayan (1992); Aydin and Öztemel (2000); Panwalkar and Iskander (1977)
REINFORCE priority policy¶
Draws task orders from a softmax over linear priorities of five task features and moves the weights along the REINFORCE gradient of each order's log-probability, scaled by its schedule's reward minus the running mean reward.
- Id:
reinforce-priority-policy; implemented byReinforcePriorityPolicy - Runs: stochastic, until a stop criterion
- Parameters:
learning_rate=0.2,temperature=1.0 - Models: every feature
- Sources: Williams (1992); Kolisch (1996)
SARSA dispatching¶
Learns which of four dispatching rules should pick the next task in each coarse state of the construction by SARSA, bootstrapping from the value of the rule chosen in the next state, and builds schedules with epsilon-greedy rule choices.
- Id:
sarsa-dispatching; implemented byTemporalDifferenceDispatching - Runs: stochastic, until a stop criterion
- Parameters:
learning_rate=0.5,discount=0.9,exploration=0.3,stage_buckets=4 - Does not model: permutation
- Sources: Rummery and Niranjan (1994); Sutton and Barto (2018); Aydin and Öztemel (2000); Zhang et al. (2011); Panwalkar and Iskander (1977)
Hyper heuristic¶
Searches over heuristics rather than over schedules.
Genetic programming hyper-heuristic¶
Evolves priority-rule expression trees over task attributes by tournament selection, subtree crossover, and subtree mutation, evaluating only the bred rules that a nearest-neighbour surrogate over their decisions in sample situations ranks best, each by the list schedule it builds.
- Id:
gp-hyper-heuristic; implemented byGpHyperHeuristic - Runs: stochastic, until a stop criterion
- Parameters:
population=24,max_depth=6,crossover_rate=0.8,mutation_rate=0.15,tournament_size=5,elites=2,offspring_multiplier=2,neighbours=1,situations=12,situation_size=7 - Models: every feature
- Sources: Koza (1992); Hildebrandt and Branke (2015); Zhang et al. (2021); Zaki et al. (2024); Burke et al. (2013)
Selection hyper-heuristic¶
Applies the low-level heuristic with the highest reinforcement score, raised by one when it improves the current solution and lowered by one otherwise, and keeps its result by late acceptance.
- Id:
selection-hyper-heuristic; implemented bySelectionHyperHeuristic - Runs: stochastic, until a stop criterion
- Parameters:
history=5,max_score=10,removed=2 - Models: every feature
- Sources: Burke et al. (2013); Nareyek (2003); Özcan et al. (2009); Burke and Bykov (2017)
Random sampling¶
Draws random solutions and keeps the best, as a baseline.
Random search¶
Decodes uniformly random precedence-feasible orders until the budget runs out and returns the best, the baseline any search must beat.
- Id:
random-search; implemented byRandomSearch - Runs: stochastic, until a stop criterion
- Parameters:
random_modes=False - Models: every feature
- Sources: Kolisch (1996)