job_shop_lib.constraint_programming

Contains solvers based on Constraint Programming (CP).

CP defines the Job Shop Scheduling Problem through constraints and focuses on finding a feasible solution. It usually aims to minimize an objective function, typically the makespan. One of the advantages of these methods is that they are not restricted to linear constraints.

class ORToolsSolver(max_time_in_seconds=None, log_search_progress=False)[source]

Bases: BaseSolver

Solver based on OR-Tools' CP-SAT solver.

log_search_progress

Whether to log the search progress to the console.

Type:

bool

max_time_in_seconds

The maximum time in seconds to allow the solver to search for a solution. If no solution is found within this time, a NoSolutionFoundError is raised. If None, the solver will run until an optimal solution is found.

Type:

float | None

model

The OR-Tools' CP-SAT model.

Type:

cp_model.CpModel

solver

The OR-Tools' CP-SAT solver.

Type:

cp_model.CpSolver

Parameters:
  • max_time_in_seconds (float | None) -- The maximum time in seconds to allow the solver to search for a solution. If no solution is found within this time, a NoSolutionFoundError is raised. If None, the solver will run until an optimal solution is found.

  • log_search_progress (bool) -- Whether to log the search progress to the console.

__call__(instance)[source]

Equivalent to calling the solve() method.

This method is necessary because, in JobShopLib, solvers are defined as callables that receive an instance and return a schedule.

Parameters:

instance (JobShopInstance) -- The job shop instance to be solved.

Returns:

The best schedule found by the solver. Its metadata contains the following information:

  • status (str): "optimal" or "feasible"

  • elapsed_time (float): The time taken to solve the problem

  • makespan (int): The total duration of the schedule

  • solved_by (str): "ORToolsSolver"

Return type:

Schedule

solve(instance)[source]

Creates the variables, constraints and objective, and solves the problem.

Parameters:

instance (JobShopInstance) -- The job shop instance to be solved.

Returns:

The best schedule found by the solver. Its metadata contains the following information:

  • status (str): "optimal" or "feasible"

  • elapsed_time (float): The time taken to solve the problem

  • makespan (int): The total duration of the schedule

  • solved_by (str): "ORToolsSolver"

Raises:

NoSolutionFoundError -- If no solution could be found for the given problem within the time limit.

Return type:

Schedule