Learning methods¶
Solvers that learn a way of building schedules while they solve: temporal-difference agents, a policy gradient, and a genetic-programming hyper-heuristic.
dispatchatlas.solvers.learning
¶
Solvers that learn how to build schedules while they solve.
Each learner starts from scratch on the problem it is given, spends the run's budget on learning, and returns the best schedule it evaluated. What it learns is a way of building schedules, which is itself evaluated as it improves:
temporal_difference:q-learning-dispatchingandsarsa-dispatching, tabular agents that learn which of four dispatching rules picks the next task in each state of the construction.policy_gradient:reinforce-priority-policy, a softmax policy over linear priorities of task features, trained by the REINFORCE policy gradient.hyper_heuristic:gp-hyper-heuristic, genetic programming of priority-rule expression trees (trees) with a surrogate that chooses which bred rules to evaluate.
All of them use only the standard library and NumPy.
register
¶
register(registry: SolverRegistry) -> None
Add the learning solvers and the genetic-programming hyper-heuristic to registry.
dispatchatlas.solvers.learning.common
¶
Pieces the learning solvers share: due dates, rewards, and policy values.
Improvement
dataclass
¶
The reward of a schedule: its improvement over a reference schedule, without units.
The reward of a schedule with objective v, in minimisation form, and
total deadline overrun o is (v0 - v) / max(|v0|, 1) + (o0 - o) /
max(m0, 1), where v0, o0, and m0 are the objective, overrun,
and makespan of the reference. The first term is the relative gain in the
objective, the second the overrun removed, counted in reference makespans.
The reference itself scores zero.
Attributes:
| Name | Type | Description |
|---|---|---|
value |
float
|
Objective of the reference, in minimisation form. |
overrun |
float
|
Total deadline overrun of the reference. |
value_scale |
float
|
Divisor of objective differences, |
time_scale |
float
|
Divisor of overrun differences, |
over
classmethod
¶
over(reference: Candidate) -> Improvement
Return the reward that measures schedules against an evaluated reference.
horizon
¶
horizon(problem: Problem) -> float
Return the latest release time plus the sum of the shortest task durations.
Running every task in its shortest mode one after another from the last release, ignoring lags and transfers, ends at this time. The learners use it as the due date of tasks that have none.
due_dates
¶
due_dates(problem: Problem) -> list[float]
Return the due date that the learners rank each task by.
A task's due date is the earlier of its soft due date, inherited from its
group when it has none (see
effective_due_dates()), and its hard
deadline. A task with neither gets the problem's horizon(), so that
its slack stays finite and large.
policy_value
¶
Return the objective of the latest greedy-policy schedule a learner evaluated.
The learners evaluate the greedy policy of their untrained start first. When that evaluation reached the target and ended the run before returning, the incumbent is that schedule.
Parameters:
| Name | Type | Description | Default |
|---|---|---|---|
search
|
Search
|
The run. |
required |
latest
|
Candidate | None
|
The latest greedy-policy schedule whose evaluation returned. |
required |
Returns:
| Type | Description |
|---|---|
float
|
The objective with its natural sign, or NaN when nothing was evaluated. |
dispatchatlas.solvers.learning.temporal_difference
¶
Tabular temporal-difference agents that learn which dispatching rule to apply.
Aydin and Oztemel (2000) train an agent that chooses, at each scheduling decision, the priority rule that suits the current state of the shop, and Zhang et al. (2011) learn choices among rule-based actions with SARSA. The agents here learn such a choice on the problem being solved, by tabular temporal-difference control:
- Construction. An episode builds one schedule a task at a time with the
shared
Builder. At each step the agent observes a state and chooses a rule, the rule picks the next task among the eligible ones, whose predecessors are all placed, and the builder places it at its earliest start in its earliest-finishing mode. The placement order and modes are then evaluated, which rebuilds the same schedule. - Rules (
RULES, in action order): shortest processing time, longest processing time, earliest due date, and minimum slack. Durations are the shortest over a task's modes and due dates come fromdue_dates(). The slack of an eligible task is its due date minus its earliest finish time in the partial schedule minus the longest path after it, so the slack rule reacts to the schedule built so far. Every rule breaks ties by the lowest task index. - States (
observe()): the fraction of tasks already placed, cut intostage_bucketsequal bins, and the number of eligible tasks: one, two, or three or more. - Learning. The agent chooses rules epsilon-greedily: a uniformly random
rule with probability
epsilon, else the rule of largest action value, the first among ties. A decision followed by another earns no reward, and its value moves bylearning_ratetoward the discounted value of the next state: the largest action value there for Q-learning (Watkins and Dayan 1992), the value of the rule the agent chooses there for SARSA (Rummery and Niranjan 1994; Sutton and Barto 2018). The last decision of an episode moves toward the episode's reward, theImprovementof its schedule over the reference schedule. - Budget. Action values start at zero, so the untrained greedy policy
applies the first rule in every state. Its schedule is evaluated first and is
the reference. The exploration rate falls linearly from
explorationto zero as the budget is spent. After an episode that changes the greedy rule of some state, the greedy policy's schedule is evaluated too, unless it equals the last one evaluated. One episode is one iteration.
The rules interleave jobs freely, which a permutation problem forbids, so the agents do not accept permutation problems.
RULES
module-attribute
¶
RULES: tuple[str, ...] = ('shortest-processing-time', 'longest-processing-time', 'earliest-due-date', 'minimum-slack')
The dispatching rules the agents choose among, in action order.
READY_BUCKETS
module-attribute
¶
Number of eligible-set buckets of a state: one, two, and three or more tasks.
INFOS
module-attribute
¶
INFOS: dict[Target, SolverInfo] = {'q-learning': SolverInfo(id='q-learning-dispatching', name='Q-learning dispatching', family='learning', summary='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.', references=('watkins1992qlearning', 'aydin2000dynamic', 'panwalkar1977survey'), supports=_SUPPORTS, parameters=_PARAMETERS), 'sarsa': SolverInfo(id='sarsa-dispatching', name='SARSA dispatching', family='learning', summary='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.', references=('rummery1994online', 'sutton2018reinforcement', 'aydin2000dynamic', 'zhang2011semiconductor', 'panwalkar1977survey'), supports=_SUPPORTS, parameters=_PARAMETERS)}
Metadata of the two registered agents, by target.
ActionValues
¶
DispatchRules
¶
DispatchRules(problem: Problem)
Episode
dataclass
¶
One schedule built by an agent.
Attributes:
| Name | Type | Description |
|---|---|---|
schedule |
Decoded
|
The schedule, as the agent's builder placed it. |
decisions |
tuple[tuple[State, int], ...]
|
The state and the chosen rule of every construction step. |
changed |
bool
|
Whether a value update during the construction changed the greedy rule of some state. |
Agent
¶
Agent(problem: Problem, decoder: Decoder, *, target: Target, learning_rate: float, discount: float, stage_buckets: int, check: Callable[[], None] | None = None)
The action values, the rules, and the construction loop of one run.
Parameters:
| Name | Type | Description | Default |
|---|---|---|---|
problem
|
Problem
|
The problem. |
required |
decoder
|
Decoder
|
The decoder of the run, whose builder places the tasks. |
required |
target
|
Target
|
The bootstrap target of the value updates. |
required |
learning_rate
|
float
|
Step size of the value updates. |
required |
discount
|
float
|
Discount of the next state's value. |
required |
stage_buckets
|
int
|
Number of progress bins of a state. |
required |
check
|
Callable[[], None] | None
|
Called before every construction step. The solver passes
|
None
|
Attributes:
| Name | Type | Description |
|---|---|---|
values |
The learned action values. |
episode
¶
episode(rng: Random, epsilon: float) -> Episode
Build a schedule with epsilon-greedy rule choices, updating values on the way.
At every step the agent draws one uniform number, and a rule index when
it explores. The value of the last decision is left for finish(),
since the episode's reward is known only once its schedule is evaluated.
TemporalDifferenceDispatching
dataclass
¶
TemporalDifferenceDispatching(target: Target = 'q-learning', learning_rate: float = 0.5, discount: float = 0.9, exploration: float = 0.3, stage_buckets: int = 4)
A tabular temporal-difference agent that learns which dispatching rule to apply.
Episodes build schedules in which one of four dispatching rules picks each
next task, and the rewards of those schedules teach the agent which rule to
apply in each construction state. target selects the registered solver:
q-learning-dispatching or sarsa-dispatching. The module docstring
gives the details.
Attributes:
| Name | Type | Description |
|---|---|---|
target |
Target
|
|
learning_rate |
float
|
Step size of the value updates, in |
discount |
float
|
Discount of the next state's value, in |
exploration |
float
|
Exploration rate at the start of the run, in |
stage_buckets |
int
|
Number of equal bins of the placed fraction in a state, at least 1. |
solve
¶
solve(problem: Problem, stop: StopCriteria, seed: int = 0) -> SolveResult
Learn rule choices within the stop criteria and return the best schedule built.
The result extras hold states, the number of states visited, and
policy_value, the objective of the latest greedy-policy schedule
evaluated.
observe
¶
observe(placed: int, total: int, eligible: int, stage_buckets: int) -> State
Return the state before a construction step.
Parameters:
| Name | Type | Description | Default |
|---|---|---|---|
placed
|
int
|
Tasks already placed. |
required |
total
|
int
|
Tasks of the problem, at least one. |
required |
eligible
|
int
|
Tasks eligible now, at least one. |
required |
stage_buckets
|
int
|
Number of equal bins of the placed fraction. |
required |
Returns:
| Type | Description |
|---|---|
State
|
``(min(placed * stage_buckets // total, stage_buckets - 1), |
State
|
min(eligible - 1, READY_BUCKETS - 1))``. |
greedy_action
¶
Return the action of largest value, the lowest index among ties.
td_target
¶
td_target(target: Target, values: Sequence[float], action: int, discount: float) -> float
Return the discounted value that a zero-reward transition moves toward.
Parameters:
| Name | Type | Description | Default |
|---|---|---|---|
target
|
Target
|
|
required |
values
|
Sequence[float]
|
Action values of the next state. |
required |
action
|
int
|
The action the agent takes in the next state. |
required |
discount
|
float
|
Discount factor. |
required |
Returns:
| Type | Description |
|---|---|
float
|
|
register
¶
register(registry: SolverRegistry) -> None
Add q-learning-dispatching and sarsa-dispatching to registry.
dispatchatlas.solvers.learning.policy_gradient
¶
A linear softmax priority policy trained with REINFORCE.
Instead of applying a fixed priority rule, this solver learns one. A task's
priority is a weighted sum of five features, and the policy builds a task order
by drawing, at each step, one eligible task (all its predecessors already
drawn) with probability given by the softmax of the eligible tasks' priorities
divided by temperature. The weights are trained with the REINFORCE
estimator of Williams (1992):
- Features (
task_features()): a constant 1, the shortest duration over the task's modes, the release time, the slack, and the number of direct successors. The slack is the due date fromdue_dates()minus the release time minus the shortest duration; tasks without a due date use the problem's horizon, the latest release plus the sum of the shortest durations. Every column except the constant is divided by its largest absolute value over the tasks, so the weights are comparable. The constant shifts every priority by the same amount, so it changes neither the probabilities nor the greedy order, and its gradient is zero. - Rollout. An episode draws one order with one uniform number per step
(inverse-transform sampling) and sums, over the steps, the gradient of the
log-probability of each choice with respect to the weights,
(phi(chosen) - E[phi]) / temperature, whereE[phi]is the mean feature vector of the eligible tasks under the policy. - Update. The order is evaluated. Its reward is the
Improvementof its schedule over the reference schedule, and the weights move bylearning_rate * (reward - baseline)times the summed gradient. The baseline is the mean reward of the earlier episodes, zero before the first, the reinforcement comparison that Williams (1992) discusses. - Greedy policy. The greedy policy takes the eligible task of highest priority, the lowest index on ties. With the initial all-zero weights it yields the problem's topological order, whose schedule is evaluated first and is the reference. After every update the greedy order is evaluated when it differs from the last one evaluated.
Orders are evaluated as they are drawn: the schedule builder places each task at its earliest start in its earliest-finishing mode, and in a permutation problem it keeps each job's tasks together, jobs in the order they first appear. One episode is one iteration.
FEATURES
module-attribute
¶
Names of the policy's features, in weight order.
LinearPolicy
¶
LinearPolicy(problem: Problem, temperature: float)
A softmax policy over eligible tasks with linear priorities.
Parameters:
| Name | Type | Description | Default |
|---|---|---|---|
problem
|
Problem
|
The problem. |
required |
temperature
|
float
|
Divisor of the priorities inside the softmax. |
required |
Attributes:
| Name | Type | Description |
|---|---|---|
features |
Feature vector of every task, from |
|
weights |
One weight per feature, initially zero. |
priorities
¶
Return the priority of every task, its weighted feature sum rounded once.
rollout
¶
Draw a precedence-feasible order and the gradient of its log-probability.
Parameters:
| Name | Type | Description | Default |
|---|---|---|---|
rng
|
Random
|
Source of the one uniform number drawn per step. |
required |
check
|
Callable[[], None] | None
|
Called before every step, to stop at the time limit. |
None
|
Returns:
| Type | Description |
|---|---|
list[int]
|
The order and, per weight, the sum over the steps of |
list[float]
|
|
greedy
¶
Return the order of the greedy policy: highest priority first, lowest index on ties.
step
¶
Add scale times gradient to the weights.
ReinforcePriorityPolicy
dataclass
¶
A linear priority rule learned by the REINFORCE policy gradient (Williams 1992).
The policy draws task orders from a softmax over linear priorities of five task features, and each schedule's reward moves the weights along the gradient of the drawn order's log-probability. The module docstring gives the details.
Attributes:
| Name | Type | Description |
|---|---|---|
learning_rate |
float
|
Step size of the weight updates, positive. |
temperature |
float
|
Divisor of the priorities inside the softmax, positive. Larger values make the draws more uniform. |
solve
¶
solve(problem: Problem, stop: StopCriteria, seed: int = 0) -> SolveResult
Train the policy within the stop criteria and return the best schedule built.
The result extras hold policy_value, the objective of the latest
greedy-policy schedule evaluated, and the final weights, as
weight_<feature>.
task_features
¶
task_features(problem: Problem) -> list[tuple[float, ...]]
Return the feature vector of every task, in the order of FEATURES.
Every column except the constant is divided by its largest absolute value over the tasks. A column of zeros stays zero.
softmax
¶
Return the softmax of scores, computed after subtracting the largest one.
sample
¶
Return an index drawn with the given probabilities, from one uniform number.
The first index whose cumulative probability exceeds the uniform draw is returned, the last one when rounding leaves the total below the draw.
dispatchatlas.solvers.learning.hyper_heuristic
¶
A genetic-programming hyper-heuristic that evolves priority rules.
A hyper-heuristic searches a space of heuristics instead of a space of
schedules (Burke et al. 2013). This one evolves priority rules, the expression
trees of trees, by genetic programming
(Koza 1992), and scores each rule by the schedule it builds on the problem:
- Decoding. A rule gives every task a priority; a priority that is not a
number counts as minus infinity. The list schedule takes, at each step, the
eligible task of highest priority (
pick()): priorities withinTIE_TOLERANCEof the highest tie, and ties go to the shortest task, then the lowest index. The schedule builder places each task at its earliest start in its earliest-finishing mode. Every rule applied to the problem is one evaluation. - Initialisation.
populationrules by ramped half-and-half. - Breeding. A generation breeds
offspring_multiplier * populationchildren, each from winners of tournaments oftournament_sizemembers: subtree crossover of two winners with probabilitycrossover_rate, subtree mutation of one with probabilitymutation_rate, otherwise a copy of one. A child deeper thanmax_depthis replaced by a new ramped half-and-half tree. - Surrogate screening (Hildebrandt and Branke 2015). A rule's phenotypic
characterisation lists its decision in each of
situationsdecision situations: sets of 2 tosituation_sizetasks, drawn uniformly once at the start of the run. The decision is the rank, by shortest duration then lowest index, of the task that the rule picks in the situation. Rules with equal characterisations count as equivalent, so a child whose characterisation occurs in the population or in an earlier child is dropped. The others are ranked by their estimated score, the mean score of theneighboursmembers of the current population whose characterisations are nearest in Euclidean distance, and evaluated in that order until, together with theelitesbest members carried over unchanged, they fill the next population. New random rules fill any remaining places. Zhang et al. (2021) screen offspring of scheduling rules with this surrogate as well.
One generation is one iteration. The result extras hold the rule of the best schedule as text.
TIE_TOLERANCE
module-attribute
¶
Priorities this close to the highest one count as ties.
Rule
dataclass
¶
Rule(tree: Tree, priorities: tuple[float, ...], characterisation: tuple[int, ...])
A rule with its priorities and phenotypic characterisation.
Attributes:
| Name | Type | Description |
|---|---|---|
tree |
Tree
|
The expression tree. |
priorities |
tuple[float, ...]
|
Priority of every task. |
characterisation |
tuple[int, ...]
|
Rank decisions in the run's decision situations. |
Member
dataclass
¶
GpHyperHeuristic
dataclass
¶
GpHyperHeuristic(population: int = 24, max_depth: int = 6, crossover_rate: float = 0.8, mutation_rate: float = 0.15, tournament_size: int = 5, elites: int = 2, offspring_multiplier: int = 2, neighbours: int = 1, situations: int = 12, situation_size: int = 7)
Genetic programming of priority rules with surrogate screening of the offspring.
A population of priority-rule trees evolves by tournament selection, subtree crossover, and subtree mutation. Every generation breeds a surplus of children, and a nearest-neighbour surrogate over the rules' decisions in sample situations chooses which of them to evaluate. The module docstring gives the details.
Attributes:
| Name | Type | Description |
|---|---|---|
population |
int
|
Rules per generation, at least 1. |
max_depth |
int
|
Largest depth of a bred tree, at least the largest initial depth, 3. |
crossover_rate |
float
|
Probability that a child is a subtree crossover. |
mutation_rate |
float
|
Probability that a child is a subtree mutation. With
|
tournament_size |
int
|
Members drawn, with replacement, per tournament. |
elites |
int
|
Best members carried into the next generation, fewer than
|
offspring_multiplier |
int
|
Children bred per generation, as a multiple of
|
neighbours |
int
|
Nearest population members whose mean score estimates a child's score. |
situations |
int
|
Decision situations of the phenotypic characterisation. |
situation_size |
int
|
Largest number of tasks in a decision situation, at least 2. |
solve
¶
solve(problem: Problem, stop: StopCriteria, seed: int = 0) -> SolveResult
Evolve rules within the stop criteria and return the best schedule built.
The result extras hold rule, the rule of the best schedule as text.
pick
¶
Return the candidate of highest priority.
Candidates within TIE_TOLERANCE of the highest priority tie, and
ties go to the shortest duration, then the lowest index.
list_order
¶
list_order(problem: Problem, priorities: Sequence[float], durations: Sequence[float]) -> list[int]
Return the list-scheduling order of a rule's priorities.
At each step the eligible task (all its predecessors already listed) that
pick() chooses comes next.
decision_situations
¶
Draw the decision situations of the phenotypic characterisation.
Each situation is a sorted set of distinct tasks whose size is drawn
uniformly from 2 to min(largest, tasks). A single-task problem has
only the situation made of its task.
Parameters:
| Name | Type | Description | Default |
|---|---|---|---|
tasks
|
int
|
Number of tasks of the problem. |
required |
count
|
int
|
Number of situations. |
required |
largest
|
int
|
Largest number of tasks in a situation, at least 2. |
required |
rng
|
Random
|
Random generator. |
required |
characterise
¶
characterise(priorities: Sequence[float], situations: Sequence[tuple[int, ...]], durations: Sequence[float]) -> tuple[int, ...]
Return the phenotypic characterisation of a rule given by its priorities.
Entry i is the rank, by shortest duration then lowest index, of the
task that pick() chooses in situation i.
dispatchatlas.solvers.learning.trees
¶
Priority rules as expression trees: the primitive set and the variation operators.
A rule is an expression tree whose leaves are terminals, attributes of a task, and whose inner nodes are binary functions. Evaluated on a task, it gives the task's priority. The function set, including the protected division, follows the task-scheduling rules that Zaki et al. (2024) evolve, as do the duration and successor-count terminals:
DUR: the shortest duration over the task's modes.SUCC: the number of the task's direct successors.REL: the task's release time.SLACK: the due date fromdue_dates()minus the release time minus the shortest duration.DEPTH: the number of dependencies on the longest chain of dependencies that ends at the task (task_depths()).ADD,SUB,MUL,MAX,MIN, andDIV, the protected division, whose value is 1 wherever the divisor is 0.
Trees are evaluated on every task at once, over NumPy columns. The operators are those of Koza (1992): ramped half-and-half initialisation, subtree crossover, and subtree mutation. Nodes are addressed by their pre-order index.
TERMINALS
module-attribute
¶
Terminal names, in the order random draws index them.
FUNCTIONS
module-attribute
¶
Function names, in the order random draws index them.
INITIAL_DEPTHS
module-attribute
¶
Depths of the trees that ramped half-and-half draws from.
GROW_TERMINAL_RATE
module-attribute
¶
Probability that the grow method ends a branch above the depth limit.
OPERATIONS
module-attribute
¶
OPERATIONS: Mapping[str, Callable[[Column, Column], Column]] = MappingProxyType({'ADD': np.add, 'SUB': np.subtract, 'MUL': np.multiply, 'DIV': protected_division, 'MAX': lambda first, second: np.where(first >= second, first, second), 'MIN': lambda first, second: np.where(first <= second, first, second)})
The element-wise operation of every function.
Tree
¶
A terminal name, or a function name with its two argument trees.
protected_division
¶
Divide element-wise, giving 1 wherever the divisor is 0.
task_depths
¶
task_depths(problem: Problem) -> list[int]
Return, per task, the number of dependencies on the longest chain ending at it.
One pass over the tasks in topological order relaxes every dependency, so each task's depth is one more than the largest depth of its predecessors, and zero without predecessors.
terminal_columns
¶
Return the value of every terminal for every task, keyed by terminal name.
evaluate
¶
Return the value of tree for every task, from the terminal columns.
Overflow gives infinities and undefined operations give NaN, without warnings.
grow
¶
grow(limit: int, full: bool, rng: Random) -> Tree
Return a random tree of depth at most limit.
With full, every branch reaches limit. Otherwise a branch above the
limit ends in a terminal with probability GROW_TERMINAL_RATE.
Terminals and functions are drawn uniformly.
ramped_half_and_half
¶
ramped_half_and_half(rng: Random) -> Tree
Return a tree of a depth drawn from INITIAL_DEPTHS, full or grown with equal odds.
subtree
¶
Return the subtree rooted at the node of pre-order index position.
replace
¶
Return a copy of tree with the subtree at pre-order index position replaced.
crossover
¶
Return parent with a random subtree replaced by a random subtree of donor.
mutate
¶
Return tree with a random subtree replaced by a new grown tree.
The new tree has at most the smallest depth of INITIAL_DEPTHS.