●  How to use · Allocation & Packing

Assembly line balancing

Assign tasks to stations along a line so that precedence holds and no station exceeds the cycle time.

What it decides

For every task, the solver picks a station along the line.

Minimal example

from optimaru.assembly_line_balancing import solve
from optimaru.assembly_line_balancing.models import (
    AssemblyLineBalancingProblemModel, PrecedenceModel, TaskModel,
)

problem = AssemblyLineBalancingProblemModel(
    cycle_time=5,
    tasks=[TaskModel(id="A", duration=3), TaskModel(id="B", duration=3), TaskModel(id="C", duration=2)],
    precedences=[PrecedenceModel(before="A", after="B")],
)

solve(problem, time_limit_seconds=1.0, random_seed=42)  # solves in place
print({task.id: task.station for task in problem.tasks}, problem.stations_used, problem.station_loads)

The same use case as a Jupyter notebook, with charts and saved outputs: examples/assembly-line-balancing.ipynb ↗

Input parameters

TaskModel

Field Meaning
id required Task id. duration required Processing time. min_station Lowest station allowed. 0 by default. max_station Highest station allowed. fixed_station Station the task must use. forbidden_stations Stations the task must not use.

PrecedenceModel

Field Meaning
before required Task that comes first. after required Task that follows.

TaskGroupModel

Field Meaning
id required Group id. task_ids required Tasks that must share a station.

TaskPairModel

Field Meaning
first required Id of one task. second required Id of the task it must be apart from.

AssemblyLineBalancingProblemModel

Field Meaning
cycle_time required Maximum processing time on one station. tasks required Tasks. precedences Before and after arcs. max_stations Limit on the number of stations. same_station_groups Tasks that must share a station. different_station_pairs Task pairs that must be on different stations.

Solve parameters

What you pass to the solve call. Time limit, seed and parallel count are here.

Parameter Default Meaning
time_limit_seconds None Search budget in seconds, from 0 to 1e9. Left unset, it is the config's spent_limit_seconds, 30 by default.
random_seed None Seed for the search. Left unset, it is the config's value, 0 by default.
parallel_solver_count None Independent parallel starts. Each gets its own seed and the full budget, and the best result wins. Left unset, it is the config's value, 1 by default.
stop_at_first_feasible False Stop as soon as hard 0 is reached.
on_new_best None Callback run on each new best solution. If it raises, the solve stops and raises the same exception.
config None A SolverConfig as the base configuration. Keyword arguments here override it for this solve only; the object you pass is not changed.
constraints None Which constraints to score, and how. Left unset, the defaults apply.
All search options (26)

Set these on a SolverConfig and pass it as config=.

Parameter Default Meaning
best_score_limit — Stop early once the best score reaches this value. By default it never fires.
change_move_weight 0.75 Relative share of change moves. 0 disables them.
close_station_moves True Enable the move that empties one used station at once. It is the only way to cut the station count in one step.
custom_move_probability 1.0 Cap on how often a step may draw a use-case move. 1 means no cap.
descent_weight 0.0 Share of best-improvement descent. 0 turns it off.
full_assert False Check every incremental score against a full recompute. Slow; for debugging.
late_acceptance_size 0 Late-acceptance history length. 0 picks it from the instance size.
on_new_best None Callback run on each new best solution. If it raises, the solve stops and raises the same exception.
parallel_solver_count 1 Independent parallel starts, each with its own seed and the full budget. The best one wins.
random_seed 0 Seed for the search.
ruin_recreate True Run adaptive ruin-and-recreate kicks when the search stagnates.
ruin_recreate_as_move_max_ruin 12 Most entities that small ruin removes.
ruin_recreate_as_move_weight 0.0 Probability that a step is a small ruin and repair, judged like any other move. Negative picks it automatically where the use case supports that; 0 turns it off.
ruin_recreate_max_ruin_count 60 Absolute cap on entities removed per kick.
ruin_recreate_max_ruin_fraction 0.3 Largest share of the solution one kick removes.
ruin_recreate_min_ruin_fraction 0.1 Smallest share of the solution one kick removes.
ruin_recreate_operator_decay 0.8 How fast operator weights adapt.
ruin_recreate_polish_steps 5000 Hill-climbing moves that polish each kick. Not counted against step_count_limit.
ruin_recreate_rewards [33.0, 9.0, 3.0, 0.0] Operator rewards for a new best, a better, an accepted and a rejected result.
ruin_recreate_unimproved_step_trigger 5000 Steps without a new best before a kick.
spent_limit_seconds 30.0 Time budget in seconds, from 0 to 1e9.
step_count_limit 0 Stop after this many steps. 0 means no limit.
swap_move_weight 0.25 Relative share of swap moves. 0 disables them.
unimproved_spent_limit_seconds 0.0 Stop after this many seconds without a new best. 0 means no limit.
unimproved_step_count_limit 0 Stop after this many steps without a new best. 0 means no limit.
value_recommender_probability 0.5 Probability that a change move draws a task's new station from its precedence and station window instead of from every station. 0 means off.

What comes back

solve fills problem in place and returns the engine Score, with .hard and .soft. It also takes the engine object from problem.to_core().

TaskModel

Field Meaning
station Zero-based station. -1 means unsolved.

AssemblyLineBalancingProblemModel

Field Meaning
stations_used Non-empty stations. station_loads Processing-time load of each station. score_hard Hard score. 0 means feasible. score_soft Soft score.

Constraints

Pick them by calling their classes from optimaru.assembly_line_balancing.constraints, such as StationCapacityCost(). Only what you pass is scored; pass nothing to keep the defaults. A list may name a constraint more than once, and each pick is scored on its own. Each one takes these parameters:

Parameter Default Meaning
weight None Multiplier on the constraint's cost, in units of the level in effect. Left unset, the default weight below applies. A constraint whose default weight is 0 is off until you give it a weight.
level None "hard" makes the constraint a must and "soft" a preference, as do Level.HARD and Level.SOFT. Left unset, it keeps the level below. This use case has no medium level, so "medium" raises ValueError. A reward refuses "hard", and a fixed level refuses any change; both raise ValueError.
exponent 1.0 Sign-preserving power on the cost, above 0, taken after offset. 2.0 squares it, so concentrated violations cost much more. It applies per unit, such as a vehicle or a day, or to the total of a constraint scored as one sum.
offset 0.0 Subtracted from the cost x before the exponent, per unit or total like the exponent. It is in the cost's own measure: seconds, minutes, a count and so on. Any finite number of either sign, keyword only. clip decides what happens below it.
clip True True makes offset a threshold: only the part beyond it counts, max(0, x - offset) ** exponent, so a cost at or below it adds nothing. False takes the literal (x - offset) ** exponent, sign kept: a unit below the offset counts negative, as a reward, even one whose cost is 0. On a level that counts toward hard, clip=False with a non-zero offset raises ValueError, since hard 0 must mean no violation. Keyword only.

This continues the minimal example above.

from optimaru.assembly_line_balancing.constraints import (
    StationCapacityCost, TaskPrecedenceCost, UsedStationsCost, WorkloadImbalanceCost,
)

custom = problem.model_copy(deep=True)
print(solve(custom, time_limit_seconds=1.0, random_seed=42, constraints=[
    StationCapacityCost(), TaskPrecedenceCost(), UsedStationsCost(), WorkloadImbalanceCost(weight=1),
]))
Name Level Default weight What it does
station_capacity_cost Hard 1 Processing time above cycle_time, across stations.
task_precedence_cost Hard 1 Precedence arcs assigned in reverse station order.
max_stations_cost Hard 1 Station indices beyond max_stations.
task_station_bounds_cost Hard 1 Assignments outside a task's station bounds.
fixed_task_stations_cost Hard 1 Tasks not on their fixed_station.
forbidden_task_stations_cost Hard 1 Tasks on a forbidden station.
same_station_groups_cost Hard 1 Additional stations used by tasks that must share one.
different_station_pairs_cost Hard 1 Task pairs on the same station that must be apart.
used_stations_cost Soft 1 Number of non-empty stations.
workload_imbalance_cost Soft 0 Range between the most and least loaded used stations. Weight 0 by default, so give it a weight to use it.

How constraints work →

Starting from an existing solution

This needs the latest release: pip install -U optimaru.

with_initial_solution(problem, solution) returns a copy of problem whose search starts from solution, a solved model or the same thing as a JSON dict.

This continues the minimal example above.

from optimaru.assembly_line_balancing import with_initial_solution

warm = with_initial_solution(problem, problem.model_dump(mode="json"))
solve(warm, time_limit_seconds=1.0, random_seed=42)
print({task.id: task.station for task in warm.tasks}, warm.stations_used)
  • Tasks are matched by id. Tasks left out or at station -1 are placed by the normal construction, and a complete seed skips it. While a task is unassigned it costs nothing.
  • Any result of solve is accepted, feasible or not: max_stations, station domains and fixed_station stay hard penalties.
  • With time_limit_seconds=0 the solve stops at once, so a complete solution comes back as it went in. Use the time limit for this: step_count_limit = 0 means no limit.
  • Unknown ids, duplicates, stations below -1 and non-integer stations raise ValueError.

Exceptions and limits

  • workload_imbalance_cost is off until you give it a weight.