labscheduler.solvers.simple_scheduler module¶
A very basic solver.
The code excerpt is from the simple_scheduler.py file and contains the implementation of the SimpleSolver class, which is a solver for the Job Shop Scheduling Problem (JSSP). The class inherits from the JSSPSolver class and implements the compute_schedule method, which takes an instance of the JSSP and computes a schedule for it. The method uses a simple algorithm that schedules the operations sequentially, i.e. no operations will be done in parallel.
The SimpleSolver class contains several instance variables, including the JSSP instance, a list of operations, a list of machines, and a minimum start time. The class also contains several methods, including is_solvable, which always returns True, and compute_schedule, which computes a schedule for the JSSP instance.
The compute_schedule method computes a schedule for the JSSP instance using a simple algorithm that schedules the operations sequentially. The method first initializes a dictionary to store the schedule and sets the minimum start time to the current time plus an offset. The method then identifies the operations that have already started and the operations that have not yet started. The method computes the minimum start time for the operations that have not yet started based on the start times of the operations that have already started.
The method then creates a directed acyclic graph (DAG) representing the JSSP instance and performs a topological sort on the graph to determine the order in which the operations should be scheduled. The method then iterates over the operations in the sorted order and assigns each operation to a machine. The method updates the schedule and the start time based on the duration of the operation.
Overall, the SimpleSolver class implements a simple algorithm that schedules the operations sequentially to solve the JSSP. The algorithm is relatively simple and easy to implement, making it a good choice for demonstration and test purposes. However, the algorithm does not take into account machine capacities or other constraints and may not be suitable for more complex JSSP problems.
(GitHub Copilot)
- class labscheduler.solvers.simple_scheduler.SimpleSolver[source]¶
Bases:
JSSPSolverA very simple algorithm, that schedules the operations sequentially, i.e. no operations will be done in parallel. It is only intended for demonstration and test purposes
- _abc_impl = <_abc._abc_data object>¶
- compute_schedule(inst: JSSP, time_limit: float, offset: float, **kwargs) tuple[dict[str, ScheduledAssignment] | None, SolutionQuality][source]¶
Compute a schedule for the given JSSP instance using this algorithm.
- Parameters:
inst (JSSP) – The JSSP instance to compute the schedule for.
time_limit (float) – The maximum time limit for the computation.
offset (float) – The offset time to start the schedule from.
**kwargs – Additional keyword arguments.
- Returns:
The computed schedule, or None if no schedule could be computed.
- Return type:
Optional[Schedule]
- static get_algorithm_info() AlgorithmInfo[source]¶
Get information about this algorithm.
- Returns:
An object containing information about this algorithm.
- Return type:
