job_shop_lib.generation

Package for generating job shop instances.

InstanceGenerator	Common interface for all generators.
GeneralInstanceGenerator	Generates instances for job shop problems.
modular_instance_generator	Creates a generator function that produces job shop instances using the provided components.
generate_machine_matrix_with_recirculation	Generate a machine matrix with recirculation.
generate_machine_matrix_without_recirculation	Generate a machine matrix without recirculation.
generate_duration_matrix	Generates a duration matrix.
range_size_selector	Selects the number of jobs and machines based on the provided ranges and constraints.
choice_size_selector	Selects the number of jobs and machines from a list of options.
get_default_machine_matrix_creator	Creates a machine matrix generator function.
get_default_duration_matrix_creator	Creates a duration matrix generator function.
ReleaseDateStrategy	alias of Callable[[Random, int], int]
create_release_dates_matrix	Generate per-operation release dates for ragged job durations.
get_independent_release_date_strategy	Factory for an independent (pure random) release date strategy.
get_cumulative_release_date_strategy	Factory for a cumulative strategy allowing forward slack.
get_mixed_release_date_strategy	Factory for the mixed heuristic strategy.
compute_horizon_proxy	Compute the horizon proxy used previously for the mixed strategy.

class InstanceGenerator(num_jobs=(10, 20), num_machines=(5, 10), duration_range=(1, 99), name_suffix='generated_instance', seed=None, iteration_limit=None)

Bases: ABC

Common interface for all generators.

The class supports both single instance generation and iteration over multiple instances, controlled by the iteration_limit parameter. It implements the iterator protocol, allowing it to be used in a for loop.

Note

When used as an iterator, the generator will produce instances until it reaches the specified iteration_limit. If iteration_limit is None, it will continue indefinitely.

num_jobs_range

The range of the number of jobs to generate. If a single int is provided, it is used as both the minimum and maximum.

duration_range

The range of durations for each operation.

num_machines_range

The range of the number of machines available. If a single int is provided, it is used as both the minimum and maximum.

name_suffix

A suffix to append to each instance's name for identification.

seed

Seed for the random number generator to ensure reproducibility.

Parameters:

• num_jobs (int | tuple[int, int]) -- The range of the number of jobs to generate.

• num_machines (int | tuple[int, int]) -- The range of the number of machines available.

• duration_range (tuple[int, int]) -- The range of durations for each operation.

• name_suffix (str) -- Suffix for instance names.

• seed (int | None) -- Seed for the random number generator.

• iteration_limit (int | None) -- Maximum number of instances to generate in iteration mode.

abstract generate(num_jobs=None, num_machines=None)

Generates a single job shop instance

Parameters:

• num_jobs (int | None) -- The number of jobs to generate. If None, a random value within the specified range will be used.

• num_machines (int | None) -- The number of machines to generate. If None, a random value within the specified range will be used.

Return type:

JobShopInstance

property max_num_jobs: int

Returns the maximum number of jobs that can be generated.

property min_num_jobs: int

Returns the minimum number of jobs that can be generated.

property max_num_machines: int

Returns the maximum number of machines that can be generated.

property min_num_machines: int

Returns the minimum number of machines that can be generated.

class GeneralInstanceGenerator(num_jobs=(10, 20), num_machines=(5, 10), duration_range=(1, 99), allow_less_jobs_than_machines=True, allow_recirculation=False, machines_per_operation=1, name_suffix='classic_generated_instance', seed=None, iteration_limit=None)

Bases: InstanceGenerator

Generates instances for job shop problems.

This class is designed to be versatile, enabling the creation of various job shop instances without the need for multiple dedicated classes.

It supports customization of the number of jobs, machines, operation durations, and more.

The class supports both single instance generation and iteration over multiple instances, controlled by the iteration_limit parameter. It implements the iterator protocol, allowing it to be used in a for loop.

The number of operations per machine is equal to the number of machines

Note

When used as an iterator, the generator will produce instances until it reaches the specified iteration_limit. If iteration_limit is None, it will continue indefinitely.

num_jobs_range

The range of the number of jobs to generate. If a single int is provided, it is used as both the minimum and maximum.

duration_range

The range of durations for each operation.

num_machines_range

The range of the number of machines available. If a single int is provided, it is used as both the minimum and maximum.

machines_per_operation

Specifies how many machines each operation can be assigned to. If a single int is provided, it is used for all operations.

allow_less_jobs_than_machines

If True, allows generating instances where the number of jobs is less than the number of machines.

allow_recirculation

If True, a job can visit the same machine more than once.

name_suffix

A suffix to append to each instance's name for identification.

seed

Seed for the random number generator to ensure reproducibility.

Parameters:

• num_jobs (int | tuple[int, int]) -- The range of the number of jobs to generate.

• num_machines (int | tuple[int, int]) -- The range of the number of machines available.

• duration_range (tuple[int, int]) -- The range of durations for each operation.

• allow_less_jobs_than_machines (bool) -- Allows instances with fewer jobs than machines.

• allow_recirculation (bool) -- Allows jobs to visit the same machine multiple times.

• machines_per_operation (int | tuple[int, int]) -- Specifies how many machines each operation can be assigned to. If a single int is provided, it is used for all operations.

• name_suffix (str) -- Suffix for instance names.

• seed (int | None) -- Seed for the random number generator.

• iteration_limit (int | None) -- Maximum number of instances to generate in iteration mode.

generate(num_jobs=None, num_machines=None)

Generates a single job shop instance

Parameters:

• num_jobs (int | None) -- The number of jobs to generate. If None, a random value within the specified range will be used.

• num_machines (int | None) -- The number of machines to generate. If None, a random value within the specified range will be used.

Return type:

JobShopInstance

generate_duration_matrix(num_jobs, num_machines, duration_range, rng=None)

Generates a duration matrix.

Parameters:

• num_jobs (int) -- The number of jobs.

• num_machines (int) -- The number of machines.

• duration_range (tuple[int, int]) -- The range of the duration values.

• rng (Generator | None) -- A numpy random number generator.

Returns:

A duration matrix with shape (num_jobs, num_machines).

Return type:

ndarray[tuple[int, ...], dtype[int32]]

generate_machine_matrix_with_recirculation(num_jobs, num_machines, rng=None)

Generate a machine matrix with recirculation.

Parameters:

• num_jobs (int) -- The number of jobs.

• num_machines (int) -- The number of machines.

• rng (Generator | None) -- A numpy random number generator.

Returns:

A machine matrix with recirculation with shape (num_jobs, num_machines).

Return type:

ndarray[tuple[int, ...], dtype[int32]]

generate_machine_matrix_without_recirculation(num_jobs, num_machines, rng=None)

Generate a machine matrix without recirculation.

Parameters:

• num_jobs (int) -- The number of jobs.

• num_machines (int) -- The number of machines.

• rng (Generator | None) -- A numpy random number generator.

Returns:

A machine matrix without recirculation.

Return type:

ndarray[tuple[int, ...], dtype[int32]]

modular_instance_generator(machine_matrix_creator, duration_matrix_creator, *, name_creator=<function <lambda>>, release_dates_matrix_creator=None, deadlines_matrix_creator=None, due_dates_matrix_creator=None, seed=None)

Creates a generator function that produces job shop instances using the provided components.

Parameters:

• machine_matrix_creator (Callable[[Random], list[list[list[int]]] | list[list[int]]]) -- A callable that creates a machine matrix.

• duration_matrix_creator (Callable[[list[list[list[int]]] | list[list[int]], Random], list[list[int]]]) -- A callable that creates a duration matrix.

• name_creator (Callable[[int], str]) -- A callable that generates unique names for instances.

• release_dates_matrix_creator (Callable[[list[list[int]], Random], list[list[int]]] | None) -- An optional callable that generates release dates for jobs.

• deadlines_matrix_creator (Callable[[list[list[int]], Random], list[list[int | None]]] | None) -- An optional callable that generates deadlines for jobs.

• due_dates_matrix_creator (Callable[[list[list[int]], Random], list[list[int | None]]] | None) -- An optional callable that generates due dates for jobs.

• seed (int | None) -- An optional seed for random number generation.

Yields:

JobShopInstance -- A generated job shop instance created using the generated matrices.

Return type:

Generator[JobShopInstance, None, None]

Example

>>> from job_shop_lib.generation import (
...     get_default_machine_matrix_creator,
...     get_default_duration_matrix_creator,
...     modular_instance_generator,
... )
>>> machine_matrix_gen = get_default_machine_matrix_creator(
...     size_selector=lambda rng: (3, 3),
...     with_recirculation=False,
... )
>>> duration_matrix_gen = get_default_duration_matrix_creator(
...     duration_range=(1, 10),
... )
>>> instance_gen = modular_instance_generator(
...     machine_matrix_creator=machine_matrix_gen,
...     duration_matrix_creator=duration_matrix_gen,
...     seed=42,
... )
>>> instance = next(instance_gen)
>>> print(instance)
JobShopInstance(name=generated_instance_0, num_jobs=3, num_machines=3)
>>> print(instance.duration_matrix_array)
[[ 5.  6.  4.]
 [ 5.  7. 10.]
 [ 9.  9.  5.]]

Added in version 1.7.0.

range_size_selector(rng, num_jobs_range=(10, 20), num_machines_range=(5, 10), allow_less_jobs_than_machines=True)

Selects the number of jobs and machines based on the provided ranges and constraints.

Parameters:

• rng (Random) -- A random.Random instance.

• num_jobs_range (tuple[int, int]) -- A tuple specifying the inclusive range for the number of jobs.

• num_machines_range (tuple[int, int]) -- A tuple specifying the inclusive range for the number of machines.

• allow_less_jobs_than_machines (bool) -- If False, ensures that the number of jobs is not less than the number of machines.

Returns:

A tuple containing the selected number of jobs and machines.

Return type:

tuple[int, int]

choice_size_selector(rng, options)

Selects the number of jobs and machines from a list of options.

Parameters:

• rng (Random) -- A random.Random instance.

• options (list[tuple[int, int]]) -- A list of tuples, where each tuple contains a pair of integers representing the number of jobs and machines.

Returns:

A tuple containing the selected number of jobs and machines.

Return type:

tuple[int, int]

get_default_machine_matrix_creator(size_selector=<function <lambda>>, with_recirculation=True)

Creates a machine matrix generator function.

Internally, it wraps either generate_machine_matrix_with_recirculation() or generate_machine_matrix_without_recirculation() based on the with_recirculation parameter.

Note

The generated machine matrix will have the shape (num_jobs, num_machines).

Parameters:

• rng -- A random.Random instance.

• size_selector (Callable[[Random], tuple[int, int]]) -- A callable that takes a random.Random instance and returns a tuple (num_jobs, num_machines).

• with_recirculation (bool) -- If True, generates a machine matrix with recirculation; otherwise, without recirculation. Recirculation means that a job can visit the same machine more than once.

Returns:

A callable that generates a machine matrix when called with a random.Random instance.

Return type:

Callable[[Random], list[list[list[int]]] | list[list[int]]]

get_default_duration_matrix_creator(duration_range=(1, 99))

Creates a duration matrix generator function.

Internally, it wraps generate_duration_matrix().

Note

This function assumes that the machine matrix has the shape (num_jobs, num_machines).

Parameters:

duration_range (tuple[int, int]) -- A tuple specifying the inclusive range for operation durations.

Returns:

A callable that generates a duration matrix of shape (num_jobs, num_machines) when called with a machine matrix and a random.Random instance.

Return type:

Callable[[list[list[list[int]]] | list[list[int]], Random], list[list[int]]]

create_release_dates_matrix(duration_matrix, strategy=None, rng=None)

Generate per-operation release dates for ragged job durations.

Parameters:

• duration_matrix (list[list[int]]) -- Ragged list of per-job operation durations.

• strategy (Callable[[Random, int], int] | None) -- Callable implementing the release date policy. If None a default mixed strategy (alpha=0.7, beta=0.3) is built using the computed horizon proxy.

• rng (Random | None) -- Optional numpy random generator (one will be created if omitted).

Returns:

A ragged list mirroring duration_matrix structure with per- operation release dates.

Return type:

list[list[int]]

Added in version 1.7.0.

get_independent_release_date_strategy(max_release_time)

Factory for an independent (pure random) release date strategy.

The release date is drawn uniformly at random in the interval [0, max_release_time].

Parameters:

max_release_time (int) -- Inclusive upper bound for the random value.

Returns:

A callable implementing the independent release date strategy.

Return type:

Callable[[Random, int], int]

Added in version 1.7.0.

get_cumulative_release_date_strategy(maximum_slack=0)

Factory for a cumulative strategy allowing forward slack.

The release date is the cumulative previous processing time plus a random slack in [0, maximum_slack].

Parameters:

maximum_slack (int) -- Non-negative integer defining the maximum forward slack to add.

Returns:

A callable implementing the cumulative release date strategy.

Return type:

Callable[[Random, int], int]

get_mixed_release_date_strategy(alpha, beta, horizon_proxy)

Factory for the mixed heuristic strategy.

release_date = alpha * cumulative_previous + U(0, beta * horizon_proxy)

Parameters:

• alpha (float) -- Weight for the proportional cumulative component.

• beta (float) -- Weight for the random component upper bound.

• horizon_proxy (int) -- Non-negative proxy for the time horizon (e.g. derived from durations to scale the random component consistently).

Return type:

Callable[[Random, int], int]

compute_horizon_proxy(duration_matrix)

Compute the horizon proxy used previously for the mixed strategy.

It is defined as: round(total_duration / avg_operations_per_job) with protections against division by zero.

Parameters:

duration_matrix (Sequence[Sequence[int]]) -- Ragged list of per-job operation durations.

Returns:

The computed horizon proxy.

Return type:

int

See also

job_shop_lib.JobShopInstance.duration_matrix()

Added in version 1.7.0.