discrete_optimization.ovensched.solvers package

Submodules

discrete_optimization.ovensched.solvers.cpsat module

class discrete_optimization.ovensched.solvers.cpsat.OvenSchedulingCpSatSolver(problem: OvenSchedulingProblem, params_objective_function: ParamsObjectiveFunction | None = None, **kwargs: Any)

Bases: SchedulingCpSatSolver[int], AllocationCpSatSolver[int, tuple[int, int]], WarmstartMixin

CP-SAT solver for the Oven Scheduling Problem.

This solver models: - Tasks that must be scheduled - Machines with availability windows and initial states - Batching: tasks with the same attribute can be batched together - Batch capacity constraints - Setup times and costs between different task attributes

get_task_start_or_end_variable(task: Task, start_or_end: StartOrEnd) → LinearExprT

Retrieve the variable storing the start or end time of given task.

get_task_unary_resource_is_present_variable(task: Task, unary_resource: UnaryResource) → LinearExprT

Return a 0-1 variable telling if the unary_resource is used for the task.

init_model(max_nb_batch_per_machine: int | None = None, **kwargs: Any) → None

Initialize the CP-SAT model.

Parameters:

• max_nb_batch_per_machine – Maximum number of batches per machine. If None, estimated as 4 * n_jobs / n_machines

• **kwargs – Additional arguments passed to parent init_model

problem: OvenSchedulingProblem

retrieve_solution(cpsolvercb: CpSolverSolutionCallback) → OvenSchedulingSolution

Construct a solution from the CP-SAT solver’s internal state.

Parameters:

cpsolvercb – The OR-Tools callback providing variable values

Returns:

An OvenSchedulingSolution

set_warm_start(solution: OvenSchedulingSolution) → None

Make the solver warm start from the given solution.

discrete_optimization.ovensched.solvers.dp module

DIDPpy-based solver for the Oven Scheduling Problem.

class discrete_optimization.ovensched.solvers.dp.DpOvenSchedulingSolver(problem: Problem, params_objective_function: ParamsObjectiveFunction | None = None, **kwargs: Any)

Bases: DpSolver

Dynamic Programming solver for the Oven Scheduling Problem using DIDPpy.

This solver properly models batching by: - Tracking current open batch on each machine - Managing batch duration (fixed or dynamic based on allow_batch_duration_update) - Checking duration compatibility when adding subsequent jobs to a batch - Two transition types: add to batch vs. close batch and start new one - Respecting machine availability windows - Using weighted multi-objective cost function (tardiness + processing + setup) - Optional dual bounds to guide search (use_dual_bounds=True) - Optional transition dominance rules (use_dominance=True)

Batch duration models: - Fixed (allow_batch_duration_update=False, default): Duration is set to first job’s

min_duration and never changes. Subsequent jobs must fit within this duration.

• Dynamic (allow_batch_duration_update=True): Duration can increase when adding jobs with larger min_duration, up to the minimum max_duration of all jobs in batch. More flexible but may slightly misevaluate tardiness.

The objective function correctly includes: - Tardiness costs (paid when each job is added to a batch) - Setup costs (paid when closing a batch and starting a new one) - Processing costs (paid when closing a batch + at base case for final batches)

Transition dominance rules (3 rules when use_dominance=True): 1. Add to batch > Close and start new (when job fits: avoids setup costs) 2. Non-late job > Late job (when same attribute: prioritizes on-time delivery) 3. Tighter deadline > Looser deadline (when both on time: reduces future conflicts)

init_model(**kwargs: Any) → None

Initialize the DIDPpy model with proper batching support.

Parameters:

• use_dual_bounds – If True, add dual bounds to guide search (default: False)

• use_dominance – If True, add transition dominance rules (default: True)

• allow_batch_duration_update – If True, allow batch duration to increase when adding jobs with larger min_duration (default: False). This provides more flexibility but may slightly misevaluate tardiness.

problem: OvenSchedulingProblem

retrieve_solution(sol: Solution) → Solution

Retrieve solution from DIDPpy by replaying transitions.

set_warm_start(solution: OvenSchedulingSolution) → None

Convert an OvenSchedulingSolution into a sequence of transitions for warm start.

Parameters:

solution – An existing solution to use as warm start

The conversion depends on the batch duration model: - Fixed duration model: Jobs in each batch are sorted by min_duration (descending)

to ensure the first job sets an appropriate batch duration

• Dynamic duration model: Jobs can be added in any feasible order

discrete_optimization.ovensched.solvers.greedy module

Greedy heuristic solver for Oven Scheduling Problem.

class discrete_optimization.ovensched.solvers.greedy.GreedyOvenSchedulingSolver(problem: OvenSchedulingProblem, params_objective_function: ParamsObjectiveFunction | None = None, **kwargs: Any)

Bases: SolverDO

Greedy heuristic solver for Oven Scheduling.

Strategy: Group jobs by attribute, greedily pack into batches respecting capacity, duration compatibility, and machine availability windows.

init_model(**kwargs: Any) → None

Initialize the model (no-op for greedy heuristic).

problem: OvenSchedulingProblem

solve(**kwargs: Any) → ResultStorage

Solve the problem using greedy heuristic.

Returns:

ResultStorage with the greedy solution

discrete_optimization.ovensched.solvers.mutations module

Mutation operators for the Oven Scheduling Problem.

This module provides mutation operators that work with the VectorOvenSchedulingSolution using the permutation encoding..

class discrete_optimization.ovensched.solvers.mutations.InvertBatchesOrderMutation(problem: OvenSchedulingProblem, **kwargs: Any)

Bases: Mutation

Invert Batches Order Reverses the order of a sequence of batches on a machine.

mutate(solution: Solution) → tuple[Solution, LocalMove]

Invert order of consecutive batches.

Strategy: 1. Decode to identify batches 2. Choose machine and range of batches 3. Reverse their order in the permutation

problem: OvenSchedulingProblem

class discrete_optimization.ovensched.solvers.mutations.MoveJobToExistingBatchMutation(problem: OvenSchedulingProblem, **kwargs: Any)

Bases: Mutation

Moves a job closer to an existing compatible batch in the permutation. This encourages the decoder to batch them together.

mutate(solution: Solution) → tuple[Solution, LocalMove]

Move a job close to a compatible batch.

Strategy: 1. Decode to identify batches 2. Pick a random batch 3. Find a job compatible with this batch (same attribute) 4. Move job close to batch tasks in permutation

problem: OvenSchedulingProblem

class discrete_optimization.ovensched.solvers.mutations.MoveJobToNewBatchMutation(problem: OvenSchedulingProblem, **kwargs: Any)

Bases: Mutation

Move Job to New Batch Moves a job away from its current batch neighbors to encourage creating a new batch.

mutate(solution: Solution) → tuple[Solution, LocalMove]

Move a job away from its batch to create a new batch.

Strategy: 1. Decode to identify batches 2. Pick a batch with at least 2 jobs 3. Move one job far from its batch neighbors

problem: OvenSchedulingProblem

class discrete_optimization.ovensched.solvers.mutations.MoveJobsToNewBatchMutation(problem: OvenSchedulingProblem, min_jobs_to_move: int = 2, max_jobs_to_move: int = 5, **kwargs: Any)

Bases: Mutation

Moves multiple jobs from one batch to create a new batch elsewhere.

mutate(solution: Solution) → tuple[Solution, LocalMove]

Move multiple jobs together to form a new batch.

Strategy: 1. Find a batch with enough jobs 2. Select subset of jobs (with same attribute) 3. Move them together to a new position

class discrete_optimization.ovensched.solvers.mutations.OvenPermutationInsert(problem: OvenSchedulingProblem, **kwargs: Any)

Bases: Mutation

Mutation operator that moves an element from one position to another.

mutate(solution: Solution) → tuple[Solution, LocalMove]

Apply insert mutation to a solution.

Parameters:

solution – The solution to mutate (must be VectorOvenSchedulingSolution)

Returns:

Tuple of (new solution, local move object)

class discrete_optimization.ovensched.solvers.mutations.OvenPermutationMixedMutation(problem: OvenSchedulingProblem, swap_prob: float = 0.4, insert_prob: float = 0.3, two_opt_prob: float = 0.2, shuffle_prob: float = 0.1, **kwargs: Any)

Bases: Mutation

Mixed mutation that randomly applies one of several mutation operators.

This provides diversity in the search process.

mutate(solution: Solution) → tuple[Solution, LocalMove]

Apply a randomly selected mutation to a solution.

Parameters:

solution – The solution to mutate (must be VectorOvenSchedulingSolution)

Returns:

Tuple of (new solution, local move object)

class discrete_optimization.ovensched.solvers.mutations.OvenPermutationPartialShuffle(problem: OvenSchedulingProblem, min_length: int = 2, max_length: int | None = None, **kwargs: Any)

Bases: Mutation

Mutation operator that shuffles a random subsequence of the permutation.

mutate(solution: Solution) → tuple[Solution, LocalMove]

Apply partial shuffle mutation to a solution.

Parameters:

solution – The solution to mutate (must be VectorOvenSchedulingSolution)

Returns:

Tuple of (new solution, local move object)

class discrete_optimization.ovensched.solvers.mutations.OvenPermutationSwap(problem: OvenSchedulingProblem, **kwargs: Any)

Bases: Mutation

Mutation operator that swaps two random positions in the permutation. This is a simple but effective mutation for permutation-based solutions. We dont use common SwapMutation to handle the cache mecanism happening in VectorOvenSchedulingSolution

mutate(solution: Solution) → tuple[Solution, LocalMove]

Apply swap mutation to a solution.

Parameters:

solution – The solution to mutate (must be VectorOvenSchedulingSolution)

Returns:

Tuple of (new solution, local move object)

class discrete_optimization.ovensched.solvers.mutations.OvenPermutationTwoOpt(problem: OvenSchedulingProblem, **kwargs: Any)

Bases: Mutation

2-opt mutation: reverses a random subsequence of the permutation.

This is a classic neighborhood operator for permutation problems.

mutate(solution: Solution) → tuple[Solution, LocalMove]

Apply 2-opt mutation to a solution.

Parameters:

solution – The solution to mutate (must be VectorOvenSchedulingSolution)

Returns:

Tuple of (new solution, local move object)

class discrete_optimization.ovensched.solvers.mutations.ScheduleAwareMixedMutation(problem: OvenSchedulingProblem, swap_batches_prob: float = 0.25, mjeb_prob: float = 0.25, mjnb_prob: float = 0.2, invert_prob: float = 0.15, move_jobs_prob: float = 0.15, **kwargs: Any)

Bases: Mutation

Mixed mutation combining all schedule-aware operators.

Randomly applies one of the schedule-aware mutations from the paper.

mutate(solution: Solution) → tuple[Solution, LocalMove]

Apply randomly selected schedule-aware mutation.

class discrete_optimization.ovensched.solvers.mutations.SwapBatchesMutation(problem: OvenSchedulingProblem, **kwargs: Any)

Bases: Mutation

Swap Batches (SB) mutation from the paper.

Swaps two batches on the same machine by reordering their tasks in the permutation. This changes the processing order of batches on a machine.

mutate(solution: Solution) → tuple[Solution, LocalMove]

Swap two batches on the same machine.

Strategy: 1. Decode permutation to identify batches 2. Choose a machine with at least 2 batches 3. Pick two batches to swap 4. Reorder permutation to swap these batches

problem: OvenSchedulingProblem

discrete_optimization.ovensched.solvers.optal module

OptalCP solver for the Oven Scheduling Problem.

class discrete_optimization.ovensched.solvers.optal.OvenObjectivesEnum(*values)

Bases: Enum

Enumeration of available objectives for the oven scheduling problem.

MAKESPAN = 'makespan'

NB_BATCH = 'nb_batch'

PROCESSING_TIME = 'processing_time'

SETUP_COST = 'setup_cost'

TARDINESS = 'tardiness'

class discrete_optimization.ovensched.solvers.optal.OvenSchedulingOptalSolver(problem: OvenSchedulingProblem, params_objective_function: ParamsObjectiveFunction | None = None, max_nb_batch_per_machine: int | None = None, setup_modeling: str = 'baseline', use_batch_count_vars: bool = False, use_explicit_batch_attrs: bool = False, use_incompatibility_constraints: bool = False, **kwargs: Any)

Bases: OptalCpSolver, WarmstartMixin

OptalCP solver for the Oven Scheduling Problem.

This solver uses the OptalCP constraint programming solver to model the batching problem with machines, setup times/costs, and capacity constraints.

init_model(**kwargs: Any) → None

Initialize the OptalCP model.

problem: OvenSchedulingProblem

retrieve_solution(result: cp.SolutionEvent) → OvenSchedulingSolution

Construct a solution from OptalCP solver results.

Parameters:

result – The OptalCP solution event

Returns:

An OvenSchedulingSolution

set_warm_start(solution: OvenSchedulingSolution) → None

Set warm start from a given solution.

Parameters:

solution – The solution to use for warm start

set_warm_start_from_previous_run()

Set warm start from the previous solve run.

Module contents

Solvers for the Oven Scheduling Problem.