Semiconductor fab scheduling

What it decides

For every operation of every lot, the solver picks an eligible machine, a start time and, on batch tools, the batch it runs in.

Minimal example

from optimaru.semiconductor_scheduling import solve
from optimaru.semiconductor_scheduling.models import (
    LotModel, MachineModel, MachineOptionModel, OperationModel, SemiconductorScheduleModel,
)

def step(id, family, *machines):
    return OperationModel(id=id, family=family,
                          eligible_machines=[MachineOptionModel(machine_id=m, duration=30) for m in machines])

problem = SemiconductorScheduleModel(
    machines=[
        MachineModel(id="LITHO-1", group="LITHO"),
        MachineModel(id="LITHO-2", group="LITHO"),
        MachineModel(id="ETCH-1", group="ETCH"),
    ],
    lots=[
        LotModel(id="L1", product="A", due_time=240, operations=[
            step("L1-1", "M1", "LITHO-1", "LITHO-2"), step("L1-2", "E1", "ETCH-1"),
            step("L1-3", "M2", "LITHO-1", "LITHO-2"),  # re-entrant: back to lithography
        ]),
        LotModel(id="L2", product="B", due_time=200, priority=2, operations=[
            step("L2-1", "M1", "LITHO-1", "LITHO-2"), step("L2-2", "E1", "ETCH-1"),
        ]),
    ],
)

print(solve(problem, time_limit_seconds=2.0, random_seed=42))  # a Score; fills problem.assignments
print([(a.lot_id, a.operation_id, a.machine_id, a.start, a.end) for a in problem.assignments])
print(problem.makespan, problem.total_weighted_tardiness)

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

Input parameters

MachineModel

id required Machine id. group required Equipment group, for example LITHO or ETCH. batch_capacity Lots it can run at once. 1 means a unary tool. minimum_batch_size Preferred minimum lots in one batch run. unavailable Maintenance and other downtime windows, as start and end.

OperationModel

id required Operation id, unique inside its lot. family required Recipe family, used for batching and setups. eligible_machines required Options, each with machine_id, duration and preference_cost. required_resources Ids of operators, reticles or fixtures it holds while running. min_queue_time Minimum wait after this operation before the next step. max_queue_time Maximum wait after this operation before the next step starts.

LotModel

id required Lot id. product required Product name. release_time Earliest start. due_time required Due time. priority Weight of the lot's tardiness. max_cycle_time Maximum time from release to completion. operations required The route, in order. It may return to an equipment group, which is what makes it re-entrant.

AuxiliaryResourceModel

id required Resource id. capacity How many operations can hold it at once. unavailable Windows when it cannot be used.

SetupTimeModel

machine_group required Equipment group the setup applies to. from_family required Previous recipe family. to_family required Next recipe family. duration required Setup time.

TransportTimeModel

from_group required Equipment group the lot leaves. to_group required Equipment group it goes to. duration required Minimum transport time.

SemiconductorScheduleModel

machines required Machines. lots required Lots. auxiliary_resources Operators, reticles, fixtures and similar. setup_times Sequence-dependent recipe setups. transport_times Transport times between equipment groups. pinned_assignments Operations frozen for replanning.

Solve parameters

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

All search options (26)

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

Parameter	Default	Meaning
acceptor_type	SIMULATED_ANNEALING	Which rule accepts or rejects a move.
best_score_limit	—	Stop early once the best score reaches this value. By default it never fires.
change_move_weight	1.0	Relative share of change moves. 0 disables them.
custom_move_probability	0.45	Cap on how often a step may draw a use-case move. 1 means no cap.
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.
machine_move_probability	0.55	Share of change moves that switch an operation's machine. The rest shift its priority.
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.
priority_swap_moves	True	Enable the move that swaps the priorities of two operations, keeping their machines.
random_seed	0	Seed for the search.
ruin_recreate	False	Run adaptive ruin-and-recreate kicks when the search stagnates.
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.
simulated_annealing_starting_temperature	(0, 0.0)	Starting temperature of the SIMULATED_ANNEALING acceptor, as (hard, soft). (0, 0.0) derives it from the start: hard 0, and soft simulated_annealing_temperature_fraction times the start's soft score in absolute value, and at least 1. It cools to 0 over the time limit, or over step_count_limit when that is further along.
simulated_annealing_temperature_fraction	0.01	Fraction of the start's soft score, in absolute value, that becomes the automatic starting temperature. It must be above 0.
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.0	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.

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().

AssignmentModel

lot_id required Lot. operation_id required Operation. machine_id required Chosen machine. start required Start time. end required End time. batch_id Batch, on batch tools.

SemiconductorScheduleModel

assignments One AssignmentModel per operation. makespan Completion time of the last operation. total_weighted_tardiness Lot tardiness times priority, summed. total_cycle_time Elapsed time from release to completion, summed. score_hard Hard score. 0 means feasible. score_soft Soft score.

Constraints

Pick them by calling their classes from optimaru.semiconductor_scheduling.constraints, such as MachineEligibilityCost(). 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:

This continues the minimal example above.

from optimaru.semiconductor_scheduling.constraints import (
    LotRoutePrecedenceCost, MachineCapacityCost, MachineEligibilityCost, WeightedTardinessCost,
)

custom = problem.model_copy(deep=True)
print(solve(custom, time_limit_seconds=2.0, random_seed=42, constraints=[
    MachineEligibilityCost(), LotRoutePrecedenceCost(), MachineCapacityCost(),
    WeightedTardinessCost(weight=5),
]))

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.semiconductor_scheduling import with_initial_solution

warm = with_initial_solution(problem, problem.model_dump(mode="json"))
print(solve(warm, time_limit_seconds=2.0, random_seed=42))
print(warm.makespan, warm.total_weighted_tardiness)

• Assignments are matched by lot and operation id. Any result of solve is accepted, feasible or not.
• A complete seed is scored as supplied, and solve returns it unchanged unless the search finds a strictly better schedule, so the score is never worse than the seed's. The search is not guaranteed to stay near the seed or to improve it.
• A partial seed cannot be scored, so it is decoded: it keeps its machines and relative order, but its start times are recomputed.
• 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, ineligible machines and wrong durations raise ValueError.

Exceptions and limits

• Times are plain integers in whatever unit you choose. Use one unit throughout. Inputs beyond 2^62 raise ValueError, and a cost that overflows 64 bits raises OverflowError.
• Operations in the same machine and family batch must have equal duration.

Try it

• Live demo ↗
• Jupyter notebook ↗
• On the solutions page →