labscheduler.solvers.MIP_solver module

Implementation of the JSSPSolver interface using MIPs and PySCIPOpt. Solving JSSP with MIP models gets very time-consuming with increasing size. This module can include any other implementation of the JSSPSolver interface as primal heuristic. Find the documentation of SCIP here: https://www.scipopt.org/

class labscheduler.solvers.MIP_solver.JSSPHeuristicWrapper(solver: JSSPSolver, inst: JSSP, jssp_model: JSSPModel, offset: float = 0, timelimit: float = 60)

Bases: Heur

Wrapper to include any implementation of the interface solver_interface.JSSPSolver as primal heuristic in SCIP. This primal heuristic will run once in the beginning of the MIP solving process to try to find a upper bound (i.e. feasible solution). Multiple instances can be added to include more than one algorithm implementation.

heurexec(heurtiming, nodeinfeasible)

Interface method of SCIP calling the heuristic execution

inst: JSSP

jssp_model: JSSPModel

solver: JSSPSolver

timelimit: float

class labscheduler.solvers.MIP_solver.JSSPModel(scip_model: Model, T: Variable, x: dict[str, Variable], y: dict[str, dict[str, list[Variable]]], s: dict[str, dict[str, Variable]], f: dict[str, dict[str, Variable]], h: dict[str, dict[str, dict[str, list[Variable]]]], ref_time: datetime)

Bases: object

Container class to contain a SCIP model and the various variables. For their Documentation see [https://gitlab.com/opensourcelab/labscheduler/-/blob/develop/docs/tex_files/mip_translation.tex?ref_type=heads]

T: Variable

f: dict[str, dict[str, Variable]]

h: dict[str, dict[str, dict[str, list[Variable]]]]

ref_time: datetime

s: dict[str, dict[str, Variable]]

scip_model: Model

property solution_found: bool

x: dict[str, Variable]

y: dict[str, dict[str, list[Variable]]]

class labscheduler.solvers.MIP_solver.MIPSolver

Bases: JSSPSolver

_abc_impl = <_abc._abc_data object>

compute_schedule(inst: JSSP, time_limit: float, offset: float, **kwargs) → tuple[dict[str, ScheduledAssignment] | None, SolutionQuality]

Tries to compute a schedule for the given JSSP instance. Depending on the algorithm there might be no guaranty a solution is found. :param inst: The Problem instance :param time_limit: Maximum computation time(in seconds) the solver is allowed :param offset: Minimum time(in seconds) between call of the function and start time scheduled for any operation :param kwargs: Optional arguments custom to a solver :return: A valid schedule or None

static get_algorithm_info() → AlgorithmInfo

Every algorithm should provide this basic information about itself :return: A typing.NamedTuple containing name, optimality, success guaranty and recommended maximum problem size

heuristics: list[JSSPSolver]

static include_heuristic(inst: JSSP, jssp_model: JSSPModel, solver: JSSPSolver, offset: float, timelimit: float)

is_solvable(inst: JSSP)

Checks whether the JSSP instance is solvable at all

static setup_mip(inst: JSSP, offset: float) → JSSPModel

Sets up all variables and constraints and saved them into a container class :param inst: scheduling problem instance :param offset: time until first scheduled job may start :return: container with scip model and structured links to variables

static translate_assignments(inst: JSSP, jssp_model: JSSPModel) → dict[str, ScheduledAssignment]

static tune_params(m: Model, time_limit: float)

Some SCIP parameter settings to tune the solver

labscheduler.solvers.MIP_solver.cap(list1, list2)

Utility method to construct a list containing all elements, that are in both lists