job_shop_lib.dispatching.rules

Contains the dispatching rules for the job shop scheduling problem.

shortest_processing_time_rule(dispatcher)

Dispatches the operation with the shortest duration.

Parameters:

dispatcher (Dispatcher)

Return type:

Operation

first_come_first_served_rule(dispatcher)

Dispatches the operation with the lowest position in job.

Parameters:

dispatcher (Dispatcher)

Return type:

Operation

most_work_remaining_rule(dispatcher)

Dispatches the operation which job has the most remaining work.

Parameters:

dispatcher (Dispatcher)

Return type:

Operation

most_operations_remaining_rule(dispatcher)

Dispatches the operation which job has the most remaining operations.

Parameters:

dispatcher (Dispatcher)

Return type:

Operation

random_operation_rule(dispatcher)

Dispatches a random operation.

Parameters:

dispatcher (Dispatcher)

Return type:

Operation

score_based_rule(score_function)

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)

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]

shortest_processing_time_score(dispatcher)

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

Parameters:

dispatcher (Dispatcher)

Return type:

list[int]

first_come_first_served_score(dispatcher)

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

Parameters:

dispatcher (Dispatcher)

Return type:

list[int]

class MostWorkRemainingScorer

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)

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

Parameters:

dispatcher (Dispatcher)

Return type:

Sequence[int]

most_operations_remaining_score(dispatcher)

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

Parameters:

dispatcher (Dispatcher)

Return type:

list[int]

random_score(dispatcher)

Scores each job randomly.

Parameters:

dispatcher (Dispatcher)

Return type:

list[int]

dispatching_rule_factory(dispatching_rule)

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 DispatchingRuleType(value, names=None, *, module=None, qualname=None, type=None, start=1, boundary=None)

Bases: str, Enum

Enumeration of dispatching rules for the job shop scheduling problem.

SHORTEST_PROCESSING_TIME = 'shortest_processing_time'

FIRST_COME_FIRST_SERVED = 'first_come_first_served'

MOST_WORK_REMAINING = 'most_work_remaining'

MOST_OPERATIONS_REMAINING = 'most_operations_remaining'

RANDOM = 'random'

class MachineChooserType(value, names=None, *, module=None, qualname=None, type=None, start=1, boundary=None)

Bases: str, Enum

Enumeration of machine chooser strategies for the job shop scheduling

FIRST = 'first'

RANDOM = 'random'

machine_chooser_factory(machine_chooser)

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) -- 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:

ValueError -- If the machine_chooser argument is not recognized or is not supported.

Return type:

Callable[[Dispatcher, Operation], int]

class DispatchingRuleSolver(dispatching_rule=DispatchingRuleType.MOST_WORK_REMAINING, machine_chooser=MachineChooserType.FIRST, ready_operations_filter=ReadyOperationsFilterType.DOMINATED_OPERATIONS)

Bases: BaseSolver

Solves a job shop instance using a dispatching rule.

Parameters:

• dispatching_rule (str | Callable[[Dispatcher], Operation])

• machine_chooser (str | Callable[[Dispatcher, Operation], int])

• ready_operations_filter (str | Callable[[Dispatcher, list[Operation]], list[Operation]] | None)

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.

pruning_function

The pruning function to use. It is used to initialize the dispatcher object internally when calling the solve method.

__init__(dispatching_rule=DispatchingRuleType.MOST_WORK_REMAINING, machine_chooser=MachineChooserType.FIRST, ready_operations_filter=ReadyOperationsFilterType.DOMINATED_OPERATIONS)

Initializes the solver with the given dispatching rule, machine chooser and pruning function.

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 DispatchingRule enum 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 MachineChooser enum 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 (str | Callable[[Dispatcher, list[Operation]], list[Operation]] | None) -- The ready operations filter to use. It can be a string with the name of the pruning function, a PruningFunction enum member, or a callable that takes a dispatcher and a list of operations and returns a list of operations that should be considered for dispatching.

solve(instance, dispatcher=None)

Returns a schedule for the given job shop instance using the dispatching rule algorithm.

Parameters:

• instance (JobShopInstance)

• dispatcher (Dispatcher | None)

Return type:

Schedule

step(dispatcher)

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

observer_based_most_work_remaining_rule(dispatcher)

Parameters:

dispatcher (Dispatcher)

Return type:

Operation