job_shop_lib.dispatching.rules¶

Contains the dispatching rules for the job shop scheduling problem.

Main objects:

`DispatchingRuleSolver`	Solves a job shop instance using a dispatching rule.
`DispatchingRuleType`	Enumeration of dispatching rules for the job shop scheduling problem.
`dispatching_rule_factory`	Creates and returns a dispatching rule function based on the specified dispatching rule name.
`MachineChooserType`	Enumeration of machine chooser strategies for the job shop scheduling
`machine_chooser_factory`	Creates and returns a machine chooser function based on the specified machine chooser strategy name.
`MachineChooser`	alias of `Callable`[[`Dispatcher`, `Operation`], `int`]

Dispatching rules:

`shortest_processing_time_rule`	Dispatches the operation with the shortest duration.
`largest_processing_time_rule`	Dispatches the operation with the longest duration.
`first_come_first_served_rule`	Dispatches the operation with the lowest position in job.
`most_work_remaining_rule`	Dispatches the operation which job has the most remaining work.
`most_operations_remaining_rule`	Dispatches the operation which job has the most remaining operations.
`random_operation_rule`	Dispatches a random operation.
`score_based_rule`	Creates a dispatching rule based on a scoring function.
`score_based_rule_with_tie_breaker`	Creates a dispatching rule based on multiple scoring functions.
`observer_based_most_work_remaining_rule`	Dispatching rule that uses the `MostWorkRemainingScorer` to select the next operation.

Dispatching rule scorers:

`shortest_processing_time_score`	Scores each job based on the duration of the next operation.
`largest_processing_time_score`	Scores each job based on the duration of the next operation.
`first_come_first_served_score`	Scores each job based on the position of the next operation.
`MostWorkRemainingScorer`	Scores each job based on the remaining work in the job.
`most_operations_remaining_score`	Scores each job based on the remaining operations in the job.
`random_score`	Scores each job randomly.

class DispatchingRuleSolver(dispatching_rule=DispatchingRuleType.MOST_WORK_REMAINING, machine_chooser=MachineChooserType.FIRST, ready_operations_filter=(ReadyOperationsFilterType.DOMINATED_OPERATIONS, ReadyOperationsFilterType.NON_IMMEDIATE_OPERATIONS))[source]¶

Bases: BaseSolver

Solves a job shop instance using a dispatching rule.

dispatching_rule¶: The dispatching rule to use. It is a callable that takes a dispatcher and returns the operation to be dispatched next.

machine_chooser¶: Used to choose the machine where the operation will be dispatched to. It is only used if the operation can be dispatched to multiple machines.

ready_operations_filter¶: The ready operations filter to use. It is used to initialize the dispatcher object internally when calling the solve method.

Parameters:

dispatching_rule (str | Callable[[Dispatcher], Operation]) -- The dispatching rule to use. It can be a string with the name of the dispatching rule, a DispatchingRuleType member, or a callable that takes a dispatcher and returns the operation to be dispatched next.
machine_chooser (str | Callable[[Dispatcher, Operation], int]) -- The machine chooser to use. It can be a string with the name of the machine chooser, a MachineChooserType member, or a callable that takes a dispatcher and an operation and returns the machine id where the operation will be dispatched.
ready_operations_filter (Iterable[Callable[[Dispatcher, list[Operation]], list[Operation]] | str | ReadyOperationsFilterType] | str | ReadyOperationsFilterType | Callable[[Dispatcher, list[Operation]], list[Operation]] | None) --
The ready operations filter to use. It can be either:
- a string with the name of the pruning function
- a :class`ReadyOperationsFilterType` enum member.
- a callable that takes a dispatcher and a list of operations and returns a list of operations that should be considered for dispatching,
- a list with names or actual ready operations filters to be used. If a list is provided, a composite filter will be created using the specified filters.

See also

job_shop_lib.dispatching.rules.dispatching_rule_factory()
job_shop_lib.dispatching.rules.machine_chooser_factory()
ready_operations_filter_factory()
create_composite_operation_filter()

solve(instance, dispatcher=None)[source]¶

Solves the instance using the dispatching rule and machine chooser algorithms.

Parameters:

instance (JobShopInstance) -- The job shop instance to be solved.
dispatcher (Dispatcher | None) -- The dispatcher object that will be used to dispatch the operations. If not provided, a new dispatcher will be created using the ready operations filter provided in the constructor.

Returns:

The schedule obtained after solving the instance.

Return type:

Schedule

Tip

Another way to use the solver is by calling it as a function. This will call the solve method internally and will add metadata to the schedule. For example:

solver = DispatchingRuleSolver()
schedule = solver(instance)

step(dispatcher)[source]¶

Executes one step of the dispatching rule algorithm.

Parameters:: dispatcher (Dispatcher) -- The dispatcher object that will be used to dispatch the operations.
Return type:: None

class DispatchingRuleType(value, names=<not given>, *values, module=None, qualname=None, type=None, start=1, boundary=None)[source]¶

Bases: str, Enum

Enumeration of dispatching rules for the job shop scheduling problem.

SHORTEST_PROCESSING_TIME = 'shortest_processing_time'¶

LARGEST_PROCESSING_TIME = 'largest_processing_time'¶

FIRST_COME_FIRST_SERVED = 'first_come_first_served'¶

MOST_WORK_REMAINING = 'most_work_remaining'¶

MOST_OPERATIONS_REMAINING = 'most_operations_remaining'¶

RANDOM = 'random'¶

dispatching_rule_factory(dispatching_rule)[source]¶

Creates and returns a dispatching rule function based on the specified dispatching rule name.

The dispatching rule function determines the order in which operations are selected for execution based on certain criteria such as shortest processing time, first come first served, etc.

Parameters:: dispatching_rule (str | DispatchingRuleType) -- The name of the dispatching rule to be used. Supported values are 'shortest_processing_time', 'first_come_first_served', 'most_work_remaining', and 'random'.
Returns:: A function that takes a Dispatcher instance as input and returns an Operation based on the specified dispatching rule.
Raises:: ValidationError -- If the dispatching_rule argument is not recognized or it is not supported.
Return type:: Callable[[Dispatcher], Operation]

class MachineChooserType(value, names=<not given>, *values, module=None, qualname=None, type=None, start=1, boundary=None)[source]¶

Bases: str, Enum

Enumeration of machine chooser strategies for the job shop scheduling

FIRST = 'first'¶

RANDOM = 'random'¶

machine_chooser_factory(machine_chooser)[source]¶

Creates and returns a machine chooser function based on the specified machine chooser strategy name.

The machine chooser function determines which machine an operation should be assigned to for execution. The selection can be based on different strategies such as choosing the first available machine or selecting a machine randomly.

Parameters:: machine_chooser (str | Callable[[Dispatcher, Operation], int]) -- The name of the machine chooser strategy to be used. Supported values are 'first' and 'random'.
Returns:: A function that takes a Dispatcher and an Operation as input and returns the index of the selected machine based on the specified machine chooser strategy.
Raises:: ValidationError -- If the machine_chooser argument is not recognized or is not supported.
Return type:: Callable[[Dispatcher, Operation], int]

shortest_processing_time_rule(dispatcher)[source]¶

Dispatches the operation with the shortest duration.

Parameters:: dispatcher (Dispatcher)
Return type:: Operation

first_come_first_served_rule(dispatcher)[source]¶

Dispatches the operation with the lowest position in job.

Parameters:: dispatcher (Dispatcher)
Return type:: Operation

most_work_remaining_rule(dispatcher)[source]¶

Dispatches the operation which job has the most remaining work.

The remaining work of a job is defined as the sum of the durations of all unscheduled operations in that job. The operation with the highest remaining work is selected for dispatching. Note that uncompleted but scheduled operations are not considered in this rule, only unscheduled operations are taken into account.

Parameters:: dispatcher (Dispatcher) -- The Dispatcher instance containing the job shop instance and the current state of the schedule.
Returns:: The operation that belongs to the job with the most remaining work.
Return type:: Operation

most_operations_remaining_rule(dispatcher)[source]¶

Dispatches the operation which job has the most remaining operations.

The remaining operations of a job are defined as the number of uncompleted operations in that job. The operation with the highest number of remaining operations is selected for dispatching. Note that uncompleted but scheduled operations are considered in this rule.

Parameters:: dispatcher (Dispatcher) -- The Dispatcher instance containing the job shop instance and the current state of the schedule.
Returns:: The operation that belongs to the job with the most remaining operations.
Return type:: Operation

random_operation_rule(dispatcher)[source]¶

Dispatches a random operation.

Parameters:: dispatcher (Dispatcher)
Return type:: Operation

largest_processing_time_score(dispatcher)[source]¶

Scores each job based on the duration of the next operation.

The score is the duration of the next operation in each job. Jobs with longer next operations will have higher scores.

Parameters:: dispatcher (Dispatcher) -- The Dispatcher instance containing the job shop instance and the current state of the schedule.
Returns:: A list of scores for each job, where the score is the duration of the next operation in that job.
Return type:: list[int]

largest_processing_time_rule(dispatcher)[source]¶

Dispatches the operation with the longest duration.

Parameters:: dispatcher (Dispatcher)
Return type:: Operation

score_based_rule(score_function)[source]¶

Creates a dispatching rule based on a scoring function.

Parameters:: score_function (Callable[[Dispatcher], Sequence[float]]) -- A function that takes a Dispatcher instance as input and returns a list of scores for each job.
Returns:: A dispatching rule function that selects the operation with the highest score based on the specified scoring function.
Return type:: Callable[[Dispatcher], Operation]

score_based_rule_with_tie_breaker(score_functions)[source]¶

Creates a dispatching rule based on multiple scoring functions.

If there is a tie between two operations based on the first scoring function, the second scoring function is used as a tie breaker. If there is still a tie, the third scoring function is used, and so on.

Parameters:: score_functions (list[Callable[[Dispatcher], Sequence[int]]]) -- A list of scoring functions that take a Dispatcher instance as input and return a list of scores for each job.
Return type:: Callable[[Dispatcher], Operation]

observer_based_most_work_remaining_rule(dispatcher)¶

Parameters:: dispatcher (Dispatcher)
Return type:: Operation

shortest_processing_time_score(dispatcher)[source]¶

Scores each job based on the duration of the next operation.

The score is the negative duration of the next operation in each job. This means that jobs with shorter next operations will have higher scores.

Parameters:: dispatcher (Dispatcher) -- The Dispatcher instance containing the job shop instance and the current state of the schedule.
Returns:: A list of scores for each job, where the score is the negative duration of the next operation in that job.
Return type:: list[int]

first_come_first_served_score(dispatcher)[source]¶

Scores each job based on the position of the next operation.

The score is the negative position of the next operation in each job. This means that jobs with operations that are earlier in the job will have higher scores.

Parameters:: dispatcher (Dispatcher) -- The Dispatcher instance containing the job shop instance and the current state of the schedule.
Returns:: A list of scores for each job, where the score is the negative position of the next operation in that job.
Return type:: list[int]

class MostWorkRemainingScorer[source]¶

Bases: object

Scores each job based on the remaining work in the job.

This class is conceptually a function: it can be called with a Dispatcher instance as input, and it returns a list of scores for each job. The reason for using a class instead of a function is to cache the observers that are created for each dispatcher instance. This way, the observers do not have to be retrieved every time the function is called.

__call__(dispatcher)[source]¶

Scores each job based on the remaining work in the job.

Parameters:: dispatcher (Dispatcher)
Return type:: Sequence[int]

most_operations_remaining_score(dispatcher)[source]¶

Scores each job based on the remaining operations in the job.

The score is the number of uncompleted operations in each job. This means that jobs with more uncompleted operations will have higher scores.

Parameters:: dispatcher (Dispatcher) -- The Dispatcher instance containing the job shop instance and the current state of the schedule.
Returns:: A list of scores for each job, where the score is the number of uncompleted operations in that job.
Return type:: list[int]

random_score(dispatcher)[source]¶

Scores each job randomly.

This function generates a random score for each job in the job shop instance. The scores are integers between 0 and 100, inclusive.

Parameters:: dispatcher (Dispatcher) -- The Dispatcher instance containing the job shop instance and the current state of the schedule.
Returns:: A list of random scores for each job, where each score is an integer between 0 and 100.
Return type:: list[int]