moptipy.examples.jssp package<a title="Link to this heading"class=headerlink href=#module-moptipy.examples.jssp>¶

moptipy.examples.jssp.demo_examples.demo_instance()[source]¶

Get the demo instance we use.

Return type:: Instance
Returns:: the demo instance

moptipy.examples.jssp.demo_examples.demo_point_in_search_space(optimum=False)[source]¶

Create a demo point in the search space.

Parameters:: optimum (bool, default: False) – should we return the optimal solution?
Return type:: ndarray
Returns:: the point

moptipy.examples.jssp.demo_examples.demo_search_space()[source]¶

Obtain an instance of the demo search space.

Return type:: Permutations
Returns:: the demo search space

moptipy.examples.jssp.demo_examples.demo_solution(optimum=False)[source]¶

Create a demo solution.

Parameters:: optimum (bool, default: False) – should we return the optimal solution?
Return type:: Gantt
Returns:: the demo solution

moptipy.examples.jssp.demo_examples.demo_solution_space()[source]¶

Obtain an instance of the demo solution space.

Return type:: GanttSpace
Returns:: the demo solution space

moptipy.examples.jssp.demo_examples.makespan_lower_bound_table(dirname, filename='makespan_lower_bound', instances=('demo', 'orb06', 'la38', 'abz8', 'yn4', 'swv14', 'dmu72', 'dmu67', 'ta70'))[source]¶

Make a table with the makespan lower bounds.

Larger lower bounds are taken from the repository https://github.com/thomasWeise/jsspInstancesAndResults.

Parameters:

dirname (str) – the directory where to store the generated file.
filename (str, default: 'makespan_lower_bound') – the filename
instances (Iterable[str], default: ('demo', 'orb06', 'la38', 'abz8', 'yn4', 'swv14', 'dmu72', 'dmu67', 'ta70')) – the instances

Return type:

Returns:

the generated file

moptipy.examples.jssp.evaluation module¶

Evaluate the results of the example experiment.

moptipy.examples.jssp.evaluation.ALL_NAMES: Final[tuple[str, ...]] = ('1rs', 'rs', 'hc_swap2', 'rls_swap2', 'rw_swap2', 'hc_swapn', 'rls_swapn', 'rw_swapn', 'hc_rot1', 'rls_rot1', 'rw_rot1')¶: the list of all algorithm names from the experiment

moptipy.examples.jssp.evaluation.LETTER_L: Final[str] = 'λ'¶: The letter lambda

moptipy.examples.jssp.evaluation.LETTER_M: Final[str] = 'μ'¶: The letter mu

moptipy.examples.jssp.evaluation.NAME_EA_MU_PLUS_1: Final[str] = 'μ+1_ea'¶: the name of the mu+1 EA

moptipy.examples.jssp.evaluation.NAME_EA_MU_PLUS_LOG_MU: Final[str] = 'μ+log₂μ_ea'¶: the name of the mu+ld(mu) EA

moptipy.examples.jssp.evaluation.NAME_EA_MU_PLUS_MU: Final[str] = 'μ+μ_ea'¶: the name of the mu+mu EA

moptipy.examples.jssp.evaluation.NAME_EA_MU_PLUS_SQRT_MU: Final[str] = 'μ+√μ_ea'¶: the name of the mu+sqrt(mu) EA

moptipy.examples.jssp.evaluation.algorithm_namer(name)[source]¶

Rename algorithm setups.

Parameters:: name (str) – the algorithm’s original name
Return type:: str
Returns:: the new name of the algorithm

moptipy.examples.jssp.evaluation.algorithm_sort_key(name)[source]¶

Get the algorithm sort key for a given algorithm name.

Parameters:: name (str) – the algorithm name
Return type:: int
Returns:: the sort key

moptipy.examples.jssp.evaluation.compute_end_results(results_dir, dest_dir)[source]¶

Get the end results, compute them if necessary.

Parameters:

results_dir (str) – the results directory
dest_dir (str) – the destination directory

Return type:

Returns:

the path to the end results file.

moptipy.examples.jssp.evaluation.compute_end_statistics(end_results_file, dest_dir)[source]¶

Get the end result statistics, compute them if necessary.

Parameters:

end_results_file (str) – the end results file
dest_dir (str) – the destination directory

Return type:

Returns:

the path to the end result statistics file.

moptipy.examples.jssp.evaluation.ea_family(name)[source]¶

Name the evolutionary algorithm setup.

Parameters:: name (str) – the full name
Return type:: str
Returns:: the short name of the family

moptipy.examples.jssp.evaluation.evaluate_experiment(results_dir='./results', dest_dir=None)[source]¶

Evaluate the experiment.

Parameters:

results_dir (str, default: './results') – the results directory
dest_dir (str | None, default: None) – the destination directory

Return type:

moptipy.examples.jssp.evaluation.gantt(end_results, algo, dest, source, best=False, insts=None)[source]¶

Plot the median Gantt charts.

Parameters:

end_results (Path) – the path to the end results
algo (str) – the algorithm
dest (Path) – the directory
source (Path) – the source directory
best (bool, default: False) – should we plot the best instance only (or, otherwise, the median)
insts (Optional[Iterable[str]], default: None) – the instances to use

Return type:

moptipy.examples.jssp.evaluation.get_end_results(file, insts=None, algos=None)[source]¶

Get a specific set of end results.

Parameters:

file (str) – the end results file
insts (Union[None, set[str], Callable[[str], bool]], default: None) – only these instances will be included if this parameter is provided
algos (Union[None, set[str], Callable[[str], bool]], default: None) – only these algorithms will be included if this parameter is provided

Return type:

list[EndResult]

moptipy.examples.jssp.evaluation.instance_sort_key(name)[source]¶

Get the instance sort key for a given instance name.

Parameters:: name (str) – the instance name
Return type:: int
Returns:: the sort key

moptipy.examples.jssp.evaluation.ma_family(name)[source]¶

Compute the Memetic Algorithm family without the ls steps.

Parameters:: name (str) – the algorithm name
Return type:: str
Returns:: the short name of the family

moptipy.examples.jssp.evaluation.makespans(end_results, algos, dest, x_label_location=1.0)[source]¶

Plot the end makespans.

Parameters:

end_results (Path) – the path to the end results
algos (list[str]) – the algorithms
dest (Path) – the directory
x_label_location (float, default: 1.0) – the location of the label of the x-axis

Return type:

moptipy.examples.jssp.evaluation.makespans_over_param(end_results, selector, x_getter, name_base, dest_dir, x_axis=<class 'moptipy.evaluation.axis_ranger.AxisRanger'>, x_label=None, algo_getter=None, title=None, legend_pos='right', title_x=0.5, y_label_location=1.0)[source]¶

Plot the performance over a parameter.

Parameters:

end_results (Path) – the end results path
selector (Callable[[str], bool]) – the selector for algorithms
name_base (str) – the basic name
dest_dir (str) – the destination directory
x_getter (Callable[[EndStatistics], int | float]) – the function computing the x-value for each statistics object
x_axis (Union[AxisRanger, Callable[[], AxisRanger]], default: <class 'moptipy.evaluation.axis_ranger.AxisRanger'>) – the axis ranger
x_label (str | None, default: None) – the x-axis label
algo_getter (Optional[Callable[[str], str]], default: None) – the optional algorithm name getter (use name_base if unspecified)
title (str | None, default: None) – the optional title (use name_base if unspecified)
legend_pos (str, default: 'right') – the legend position, set to “right”
title_x (float, default: 0.5) – the title x
y_label_location (float, default: 1.0) – the y label location

Return type:

Returns:

the list of generated files

moptipy.examples.jssp.evaluation.progress(algos, dest, source, log=True, millis=True)[source]¶

Plot the median Gantt charts.

Parameters:

algos (list[str]) – the algorithms
dest (Path) – the directory
source (Path) – the source directory
log (bool, default: True) – is the time logarithmically scaled?
millis (bool, default: True) – is the time measured in milliseconds?

Return type:

moptipy.examples.jssp.evaluation.sa_family(name)[source]¶

Name the simulated annealing setup.

Parameters:: name (str) – the full name
Return type:: str
Returns:: the short name of the family

moptipy.examples.jssp.evaluation.table(end_results, algos, dest, swap_stats=None)[source]¶

Tabulate the end results.

Parameters:

end_results (Path) – the path to the end results
algos (list[str]) – the algorithms
dest (Path) – the directory
swap_stats (Optional[Iterable[tuple[str, str]]], default: None) – the statistics to swap out

Return type:

moptipy.examples.jssp.evaluation.tests(end_results, algos, dest)[source]¶

Tabulate the end result tests.

Parameters:

end_results (Path) – the path to the end results
algos (list[str]) – the algorithms
dest (Path) – the directory

Return type:

moptipy.examples.jssp.experiment module¶

Run the moptipy example experiment.

moptipy.examples.jssp.experiment.ALGORITHMS: Final[list[Callable[[Instance, Permutations], Algorithm]]] = [<function <lambda>>, <function <lambda>>, <function <lambda>>, <function <lambda>>, <function <lambda>>, <function <lambda>>, <function <lambda>>, <function <lambda>>, <function <lambda>>, <function <lambda>>, <function <lambda>>]¶: The default set of algorithms for our experiments. Each of them is a Callable that receives two parameters, the instance inst and the permutation with repetitions-space pwr.

moptipy.examples.jssp.experiment.EXPERIMENT_RUNS: Final[int] = 23¶: The number of runs per instance in our JSSP experiment. For each combination of algorithm setup and JSSP instance, we will perform exactly this many runs.

moptipy.examples.jssp.experiment.EXPERIMENT_RUNTIME_MS: Final[int] = 300000¶: We will perform five minutes per run.

moptipy.examples.jssp.experiment.INSTANCES: Final[tuple[str, str, str, str, str, str, str, str]] = ('orb06', 'la38', 'abz8', 'yn4', 'swv14', 'dmu72', 'dmu67', 'ta70')¶: The default instances to be used in our experiment. These have been computed via instance_selector.propose_instances. The instances in this tuple are sorted by the scale of the search space, if that search space is the order-based encoding, i.e., permutations with repetitions. This is almost the same as an ordering by the number of possible (feasible or infeasible) Gantt charts than can be constructed, with one exception: For dmu67, the search space size is 2.768*(10**1241) and for dmu72, it is 3.862*(10**1226), i.e., dmu67 has a larger search order-based encoding search space than dmu72. However, for dmu72, we can construct 1.762*(10**967) different (feasible or infeasible) Gantt charts, whereas for dmu67, we can only construct 1.710*(10**958), i.e., fewer. Therefore, dmu67 in this ordering here comes after dmu72, but it would come before if we were sorting instances by the solution space size.

moptipy.examples.jssp.experiment.run_experiment(base_dir='./results', algorithms=(<function <lambda>>, <function <lambda>>, <function <lambda>>, <function <lambda>>, <function <lambda>>, <function <lambda>>, <function <lambda>>, <function <lambda>>, <function <lambda>>, <function <lambda>>, <function <lambda>>), instances=('orb06', 'la38', 'abz8', 'yn4', 'swv14', 'dmu72', 'dmu67', 'ta70'), n_runs=23, max_time=300000, max_fes=None)[source]¶

Run the experiment.

Parameters:

algorithms (Iterable[Callable[[Instance, Permutations], Algorithm]], default: (<function <lambda> at 0x7f668503aca0>, <function <lambda> at 0x7f66852427a0>, <function <lambda> at 0x7f6684e258a0>, <function <lambda> at 0x7f6684e27920>, <function <lambda> at 0x7f6684e279c0>, <function <lambda> at 0x7f6684e277e0>, <function <lambda> at 0x7f6684e27880>, <function <lambda> at 0x7f6684e27740>, <function <lambda> at 0x7f6684e276a0>, <function <lambda> at 0x7f6684e27600>, <function <lambda> at 0x7f6684e26de0>)) – the algorithm factories. Each factory receives as input one JSSP Instance and one instance of PermutationWithRepetition. It returns either an instance of Algorithm or of Execution.
instances (Iterable[str], default: ('orb06', 'la38', 'abz8', 'yn4', 'swv14', 'dmu72', 'dmu67', 'ta70')) – the JSSP instance names
base_dir (str, default: './results') – the base directory
n_runs (int, default: 23) – the number of runs
max_time (int | None, default: 300000) – the maximum runtime in milliseconds
max_fes (int | None, default: None) – the maximum runtime in FEs

Return type:

moptipy.examples.jssp.gantt module¶

A class for representing Gantt charts as objects.

class moptipy.examples.jssp.gantt.Gantt(space)[source]¶

Bases: ndarray

A class representing Gantt charts.

A Gantt chart is a diagram that visualizes when a job on a given machine begins or ends. We here represent it as a three-dimensional matrix. This matrix has one row for each machine and one column for each operation on the machine. In each cell, it holds three values: the job ID, the start, and the end time of the job on the machine. The Gantt chart has the additional attribute instance which references the JSSP instance for which the chart is constructed. Gantt charts must only be created by an instance of moptipy.examples.jssp.gantt_space.GanttSpace.

static from_log(file, instance=None)[source]¶

Load a Gantt chart from a log file.

Parameters:

file (str) – the log file path
instance (Instance | None, default: None) – the optional JSSP instance: if None is provided, we try to load it from the resources

Return type:

Gantt

Returns:

the Gantt chart

instance: Instance¶: the JSSP instance for which the Gantt chart is created

moptipy.examples.jssp.gantt_space module¶

Here we provide a Space of Gantt charts.

class moptipy.examples.jssp.gantt_space.GanttSpace(instance)[source]¶

Bases: Space

An implementation of the Space API of for Gantt charts.

create()[source]¶

Create a Gantt chart object without assigning jobs to machines.

Return type:: Gantt
Returns:: the Gantt chart

dtype: Final[dtype]¶: the data to be used for Gantt charts

from_str(text)[source]¶

Convert a string to a Gantt chart.

Parameters:: text (str) – the string
Return type:: Gantt
Returns:: the Gantt chart

instance: Final[Instance]¶: The JSSP Instance to which the Gantt record apply.

is_equal(x1, x2)[source]¶

Check if two Gantt charts have the same contents.

Parameters:

x1 (Gantt) – the first chart
x2 (Gantt) – the second chart

Return type:

bool

Returns:

True if both charts are for the same instance and have the same structure

log_parameters_to(logger)[source]¶

Log the parameters of the Gantt space to the given logger.

Parameters:: logger (KeyValueLogSection) – the logger for the parameters
Return type:: None

n_points()[source]¶

Get the number of possible Gantt charts without useless delays.

Return type:: int
Returns:: factorial(jobs) ** machines

>>> print(GanttSpace(Instance.from_resource("demo")).n_points())
7962624

shape: Final[tuple[int, int, int]]¶: The shape for the Gantt chart arrays.

to_str(x)[source]¶

Convert a Gantt chart to a string.

Parameters:: x (Gantt) – the Gantt chart
Return type:: str
Returns:: a string corresponding to the flattened Gantt array

validate(x)[source]¶

Check if a Gantt chart is valid and feasible.

This means that the operations of the jobs must appear in the right sequences and must not intersect in any way. The only exception are operations that need 0 time units. They are permitted to appear wherever.

Parameters:

x (Gantt) – the Gantt chart

Raises:

TypeError – if any component of the chart is of the wrong type
ValueError – if the Gantt chart is not feasible or the makespan is wrong

Return type:

moptipy.examples.jssp.gantt_space.KEY_SHAPE: Final[str] = 'shape'¶: the array shape

moptipy.examples.jssp.gantt_space.gantt_space_size(jobs, machines)[source]¶

Compute the size of the Gantt space.

Parameters:

jobs (int) – the number of jobs
machines (int) – the number of machines

Return type:

int

Returns:

the size of the search

>>> print(gantt_space_size(8, 5))
106562062388507443200000

moptipy.examples.jssp.instance module¶

A representation and collection of Job Shop Scheduling Problem instances.

The Job Shop Scheduling Problem (JSSP) is one of the classical NP-hard problems from operations research. Here we provide a class (Instance) to represent and load their data as well as a collection of common JSSP instances from literature.

Our problem instances are actually extensions of numpy.ndarray. They present the basic instance data as a matrix, where each row corresponds to a job. Each row has twice the number of machines elements. In an alternating fashion, we store the machines that the job needs to go to as well as the time that it needs on the machines, one by one. Additionally, the instance name, the number of machines, and the number of jobs are provided as attributes (although the latter two can easily be inferred from the shape of the matrix). Nevertheless, this memory layout and encapsulation as ndarray are the most efficient way to store the data I could come up with.

You can directly load the most common JSSP instances using from_resource() by providing their mnemonic name. With list_resources(), you can obtain a list of string mnemonic names of all JSSP instances available as resource.

This collection of common instances stems from the repositories [1-5], each of which containing some or all of them. The instances themselves were originally published by different researchers in literature [6-14].

John Edward Beasley. OR-Library: Distributing Test Problems by Electronic Mail. The Journal of the Operational Research Society (JORS). 41:1069-1072. November 1990. doi: https://doi.org/10.1057/jors.1990.166
Jelke Jeroen van Hoorn. Job Shop Instances and Solutions. 2015. http://jobshop.jjvh.nl
Jelke Jeroen van Hoorn. The Current State of Bounds on Benchmark Instances of the Job-Shop Scheduling Problem. Journal of Scheduling. 21(1):127-128. February 2018. doi: https://doi.org/10.1007/s10951-017-0547-8
Oleg V. Shylo. Job Shop Scheduling (Personal Homepage). August 2019. Knoxville, TN, USA. http://optimizizer.com/jobshop.php
Thomas Weise. jsspInstancesAndResults: Results, Data, and Instances of the Job Shop Scheduling Problem. Hefei, Anhui, China: Institute of Applied Optimization, School of Computer Science and Artificial Intelligence, Hefei University. 2019. http://github.com/thomasWeise/jsspInstancesAndResults. A GitHub repository with the common benchmark instances for the Job Shop Scheduling Problem as well as results from the literature, both in form of CSV files and R program code to access them.
Henry Fisher and Gerald L. Thompson. Probabilistic Learning Combinations of Local Job-Shop Scheduling Rules. Chapter 3.2 of John F. Muth and Gerald L. Thompson, editors, Industrial Scheduling, pages 225-251. 1963. Englewood Cliffs, NJ, USA: Prentice-Hall.
Joseph Adams, Egon Balas, and Daniel Zawack. The Shifting Bottleneck Procedure for Job Shop Scheduling. Management Science. 34(3):391-401. 1988. doi: https://doi.org/10.1287/mnsc.34.3.391
David Lee Applegate and William John Cook. A Computational Study of the Job-Shop Scheduling Problem. ORSA Journal on Computing 3(2):149-156. May 1991. doi: https://doi.org/10.1287/ijoc.3.2.149. The JSSP instances used were generated in Bonn, Germany in 1986.
Robert H. Storer, S. David Wu, and Renzo Vaccari. New Search Spaces for Sequencing Problems with Application to Job Shop Scheduling. Management Science. 38(10):1495-1509. 1992. doi: https://doi.org/10.1287/mnsc.38.10.1495
Takeshi Yamada and Ryohei Nakano. A Genetic Algorithm Applicable to Large-Scale Job-Shop Instances. In Reinhard Männer and Bernard Manderick, editors, Proceedings of Parallel Problem Solving from Nature 2 (PPSN II), September 28-30, 1992, Brussels, Belgium, pages 281-290. Amsterdam, The Netherlands: Elsevier. https://www.researchgate.net/publication/220701684
Stephen R. Lawrence. Resource Constrained Project Scheduling: An Experimental Investigation of Heuristic Scheduling Techniques (Supplement). 1984. Pittsburgh, PA, USA: Graduate School of Industrial Administration (GSIA), Carnegie-Mellon University.
Ebru Demirkol, Sanjay V. Mehta, and Reha Uzsoy. Benchmarks for Shop Scheduling Problems. European Journal of Operational Research (EJOR). 109(1):137-141. August 1998. doi: https://doi.org/10.1016/S0377-2217(97)00019-2
Éric D. Taillard. Benchmarks for Basic Scheduling Problems. European Journal of Operational Research (EJOR). 64(2):278-285. January 1993. doi: https://doi.org/10.1016/0377-2217(93)90182-M. http://mistic.heig-vd.ch/taillard/articles.dir/Taillard1993EJOR.pdf
André Henning. Praktische Job-Shop Scheduling-Probleme. Jena, Thüringen, Germany: Friedrich-Schiller-Universität Jena, Fakultät für Mathematik und Informatik. August 2022. https://www.db-thueringen.de/servlets/MCRFileNodeServlet/dbt_derivate_00001373/Dissertation.pdf

class moptipy.examples.jssp.instance.Instance(name: str, machines: int, jobs: int, matrix: ndarray, makespan_lower_bound: int | None = None)[source]¶

Bases: Component, ndarray

An instance of the Job Shop Scheduling Problem.

Besides the metadata, this object is a three-dimensional np.ndarray where the columns stand for jobs and the rows represent the operations of the jobs. Each row*column contains two values (third dimension), namely the machine where the operation goes and the time it will consume at that machine: I[job, operation, 0] = machine, I[job, operation, 1] = time that the job spents on machine.

static from_resource(name)[source]¶

Load the JSSP instances name provided as part of moptipy.

Parameters:: name (str) – the instance name
Return type:: Instance
Returns:: the instance

>>> jssp = Instance.from_resource("demo")
>>> print(jssp.jobs)
4
>>> print(jssp.machines)
5
>>> print(jssp)
demo

static from_stream(name, stream)[source]¶

Load an instance from a text stream.

Parameters:

name (str) – the name of the instance to be loaded
stream (Iterable[str]) – the text stream

Return type:

Instance

Returns:

the instance

static from_text(name, rows)[source]¶

Convert a name and a set of rows of text to an JSSP instance.

Parameters:

name (str) – the name of the instance
rows (list[str]) – the rows

Return type:

Instance

Returns:

the JSSP Instance

jobs: int¶: the number of jobs == self.shape[0]

static list_resources()[source]¶

Get a tuple with all JSSP instances provided in the moptipy resources.

Return type:: tuple[str, ...]
Returns:: a tuple with all instance names that are valid parameters to Instance.from_resource()

>>> print(Instance.list_resources()[0:3])
('abz5', 'abz6', 'abz7')

log_parameters_to(logger)[source]¶

Log the parameters describing this JSSP instance to the logger.

Parameters:: logger (KeyValueLogSection) – the logger for the parameters
Return type:: None

>>> from moptipy.utils.logger import InMemoryLogger
>>> with InMemoryLogger() as l:
...     with l.key_values("I") as kv:
...         Instance.from_resource("abz8").log_parameters_to(kv)
...     print(repr('@'.join(l.get_log())))
'BEGIN_I@name: abz8@class: moptipy.examples.jssp.instance.Instance@machines: 15@jobs: 20@makespanLowerBound: 648@makespanUpperBound: 7586@dtype: b@END_I'

machines: int¶: the number of machines == self.shape[1]

makespan_lower_bound: int¶: the lower bound of the makespan of this JSSP instance

makespan_upper_bound: int¶: the upper bound of the makespan of this JSSP instance

name: str¶: the name of the instance

moptipy.examples.jssp.instance.JOBS: Final[str] = 'jobs'¶: The number of jobs in the instance.

moptipy.examples.jssp.instance.MACHINES: Final[str] = 'machines'¶: The number of machines in the instance.

moptipy.examples.jssp.instance.MAKESPAN_LOWER_BOUND: Final[str] = 'makespanLowerBound'¶: The lower bound of the makespan of the instance.

moptipy.examples.jssp.instance.MAKESPAN_UPPER_BOUND: Final[str] = 'makespanUpperBound'¶: The upper bound of the makespan of the instance.

moptipy.examples.jssp.instance.SCOPE_INSTANCE: Final[str] = 'inst'¶: the recommended scope under which instance data should be stored

moptipy.examples.jssp.instance.check_instance(inst)[source]¶

Check whether the contents of a JSSP instance are OK.

This method thoroughly checks the contents of an instance and the types of all of its members. If your instances passes this method without any error, it is a valid JSSP instance that can be used for experiments. All instances in our benchmark set listed above will pass this test.

Parameters:: inst (Instance) – the instance
Return type:: Instance
Returns:: the instance, if its contents are OK

moptipy.examples.jssp.instance.compute_makespan_lower_bound(machines, jobs, matrix)[source]¶

Compute the lower bound for the makespan of a JSSP instance data.

Parameters:

machines (int) – the number of machines
jobs (int) – the number of jobs
matrix (ndarray) – the matrix with the instance data

Return type:

int

Returns:

the lower bound for the makespan

moptipy.examples.jssp.instance_selector module¶

Code for selecting interesting instances for smaller-scale experiments.

moptipy.examples.jssp.instance_selector.compute_instances_that_are_too_easy()[source]¶

Compute the set of instances that are too easy to be of any interest.

For our educational experiments, we need instances that are not always solved to optimality by simple algorithms. Otherwise, for example, the box plots of the end results will collapse to single lines. Then, it will also be impossible to really say which algorithm performs best on the instance. See the documentation of __is_instance_too_easy for the conditions that lead to the rejection of an instance

Return type:: tuple[str, ...]
Returns:: the tuple of instance names that should not be included in the experiment

moptipy.examples.jssp.instance_selector.propose_instances(n, get_instances=<function __get_instances>)[source]¶

Propose a set of instances to be used for our experiment.

This function is used to obtain the instances chosen for the JSSP experiment. You can also use it for other experiments, by using your own instance source and/or for selecting more or less JSSP instances.

Basically, it will accept a function get_instances, which must produce a sequence of Instance objects. Each instance has a name (e.g., dmu14) and a group, where the group is the name without any numerical suffix (e.g., dmu). This function will then select n instances from the instance set with the goal to maximize the diversity of the instances, to include instances from as many groups as possible, and to include one instance of the smallest and one of the largest scale. The diversity is measured in terms of the numbers of jobs and machines, the instance scale, the minimum and maximum operation length, the standard deviation of the mean operation lengths over the jobs, the makespan bounds, and so on.

First, features are computed for each instance. Second, the instances are clustered into n clusters. Third, we try to pick groups for each cluster such that a) the minimum and maximum-scale instances can be included and b) that instances from as many groups as possible are picked. Third, we then randomly pick one instance for each cluster from the selected group (while trying to pick the minimum and maximum-scale instances). Finally, the chosen instance names are listed as sorted tuple and returned.

Parameters:

n (int) – the number of instances to be proposed
get_instances (Callable, default: <function __get_instances at 0x7f66817a8180>) – a function returning an iterable of instances.

Return type:

tuple[str, ...]

Returns:

a tuple with the instance names

moptipy.examples.jssp.makespan module¶

An objective function for minimizing the makespan of Gantt charts.

class moptipy.examples.jssp.makespan.Makespan(instance)[source]¶

Bases: Objective

Compute the makespan of a Gantt chart (for minimization).

is_always_integer()[source]¶

Return True because makespan() always returns int values.

Retval True:: always
Return type:: bool

lower_bound()[source]¶

Get the lower bound of the makespan.

Return type:: int
Returns:: the lower bound

upper_bound()[source]¶

Get the upper bound of the makespan.

Return type:: int
Returns:: the sum of all job execution times.

moptipy.examples.jssp.makespan.makespan(x)[source]¶

Get the makespan corresponding to a given Gantt chart.

The makespan corresponds to the maximum of the end times of the last operation on each machine. This is jitted for performance.

Parameters:: x (Gantt) – the Gantt chart.
Return type:: int
Returns:: the maximum of any end time stored in the chart

moptipy.examples.jssp.ob_encoding module¶

An implementation of the operation-based encoding for JSSPs.

Mitsuo Gen, Yasuhiro Tsujimura, and Erika Kubota. Solving Job-Shop Scheduling Problems by Genetic Algorithm. In Humans, Information and Technology: Proceedings of the 1994 IEEE International Conference on Systems, Man and Cybernetics, October 2-5, 1994, San Antonio, TX, USA, volume 2. Piscataway, NJ, USA: IEEE. ISBN: 0-7803-2129-4. doi: https://doi.org/10.1109/ICSMC.1994.400072. http://read.pudn.com/downloads151/doc/658565/00400072.pdf.
Christian Bierwirth. A Generalized Permutation Approach to Job Shop Scheduling with Genetic Algorithms. Operations-Research-Spektrum (OR Spectrum), 17(2-3):87-92, June 1995. doi: https://doi.org/10.1007/BF01719250. https://www.researchgate.net/publication/240263036.
Christian Bierwirth, Dirk C. Mattfeld, and Herbert Kopfer. On Permutation Representations for Scheduling Problems. In Hans-Michael Voigt, Werner Ebeling, Ingo Rechenberg, and Hans-Paul Schwefel, editors, Proceedings of the 4th International Conference on Parallel Problem Solving from Nature (PPSN IV), September 22-24, 1996, Berlin, Germany, pages 310-318. Volume 1141/1996 of Lecture Notes in Computer Science (LNCS), Berlin, Germany: Springer-Verlag GmbH. ISBN: 3-540-61723-X. doi: https://doi.org/10.1007/3-540-61723-X_995. https://www.researchgate.net/publication/2753293.
Guoyong Shi, Hitoshi Iima, and Nobuo Sannomiya. New Encoding Scheme for Solving Job Shop Problems by Genetic Algorithm. In Proceedings of the 35th IEEE Conference on Decision and Control (CDC’96), December 11-13, 1996, Kobe, Japan, volume 4, pages 4395-4400. Piscataway, NJ, USA: IEEE. ISBN: 0-7803-3590-2. doi: https://doi.org/10.1109/CDC.1996.577484. https://www.researchgate.net/publication/224238934.

moptipy.examples.jssp.ob_encoding.KEY_NUMPY_TYPE_JOB_IDX: Final[str] = 'dtypeJobIdx'¶: the numpy data type for job indices

moptipy.examples.jssp.ob_encoding.KEY_NUMPY_TYPE_JOB_TIME: Final[str] = 'dtypeJobTime'¶: the numpy data type for job times

moptipy.examples.jssp.ob_encoding.KEY_NUMPY_TYPE_MACHINE_IDX: Final[str] = 'dtypeMachineIdx'¶: the numpy data type for machine indices

class moptipy.examples.jssp.ob_encoding.OperationBasedEncoding(instance)[source]¶

Bases: Encoding

An operation-based encoding for the Job Shop Scheduling Problem (JSSP).

The operation-based encoding for the Job Shop Scheduling Problem (JSSP) maps permutations with repetitions to Gantt charts. In the operation-based encoding, the search space consists of permutations with repetitions of length n*m, where n is the number of jobs in the JSSP instance and m is the number of machines. In such a permutation with repetitions, each of the job ids from 0..n-1 occurs exactly m times. In the encoding, the permutations are processed from beginning to end and the jobs are assigned to machines in exactly the order in which they are encountered. If a job is encountered for the first time, we place its first operation onto the corresponding machine. If we encounter it for the second time, its second operation is placed on its corresponding machine, and so on.

decode(x, y)[source]¶

Map an operation-based encoded array to a Gantt chart.

Parameters:

x (ndarray) – the array
y (ndarray) – the Gantt chart

Return type:

log_parameters_to(logger)[source]¶

Log all parameters of this component as key-value pairs.

Parameters:: logger (KeyValueLogSection) – the logger for the parameters
Return type:: None

moptipy.examples.jssp.ob_encoding.decode(x, machine_idx, job_time, job_idx, instance, y)[source]¶

Map an operation-based encoded array to a Gantt chart.

Parameters:

x (ndarray) – the source array, i.e., multi-permutation
machine_idx (ndarray) – array of length m for machine indices
job_time (ndarray) – array of length n for job times
job_idx (ndarray) – length n array of current job operations
instance (ndarray) – the instance data matrix
y (ndarray) – the output array, i.e., the Gantt chart

Return type:

moptipy.examples.jssp.plot_gantt_chart module¶

Plot a Gantt chart into one figure.

moptipy.examples.jssp.plot_gantt_chart.marker_lb(x)[source]¶

Compute the marker for the lower bound.

Parameters:: x (Gantt) – the Gantt chart
Return type:: tuple[str, int | float]
Returns:: the lower bound marker

moptipy.examples.jssp.plot_gantt_chart.marker_makespan(x)[source]¶

Compute the marker for the makespan.

Parameters:: x (Gantt) – the Gantt chart
Return type:: tuple[str, int | float]
Returns:: the makespan marker

moptipy.examples.jssp.plot_gantt_chart.plot_gantt_chart(gantt, figure, markers=(<function marker_lb>, ), x_axis=<function <lambda>>, importance_to_line_width_func=<function importance_to_line_width>, importance_to_font_size_func=<function importance_to_font_size>, info=<function <lambda>>, x_grid=False, y_grid=False, x_label=<function Lang.translate_call.<locals>.__trc>, x_label_inside=True, x_label_location=1.0, y_label=<function Lang.translate_call.<locals>.__trc>, y_label_inside=True, y_label_location=0.5)[source]¶

Plot a Gantt chart.

Parameters:

gantt (Gantt | str) – the gantt chart or a path to a file to load it from
figure (Axes | Figure) – the figure
markers (Optional[Iterable[Union[tuple[str, int | float], Callable[[Gantt], tuple[str, int | float]]]]], default: (<function marker_lb at 0x7f6684ce5080>,)) – a set of markers
x_axis (Union[AxisRanger, Callable[[Gantt], AxisRanger]], default: <function <lambda> at 0x7f6684ce5620>) – the ranger for the x-axis
info (Union[None, str, Callable[[Gantt], str]], default: <function <lambda> at 0x7f6684ce5940>) – the optional info header
importance_to_font_size_func (Callable[[int], float], default: <function importance_to_font_size at 0x7f668579afc0>) – the function converting importance values to font sizes
importance_to_line_width_func (Callable[[int], float], default: <function importance_to_line_width at 0x7f668579b1a0>) – the function converting importance values to line widths
x_grid (bool, default: False) – should we have a grid along the x-axis?
y_grid (bool, default: False) – should we have a grid along the y-axis?
x_label (Union[None, str, Callable[[Gantt], str]], default: <function Lang.translate_call.<locals>.__trc at 0x7f6684ce6200>) – a callable returning the label for the x-axis, a label string, or None if no label should be put
x_label_inside (bool, default: True) – put the x-axis label inside the plot (so that it does not consume additional vertical space)
x_label_location (float, default: 1.0) – the location of the x-label
y_label (Union[None, str, Callable[[Gantt], str]], default: <function Lang.translate_call.<locals>.__trc at 0x7f6684ce77e0>) – a callable returning the label for the y-axis, a label string, or None if no label should be put
y_label_inside (bool, default: True) – put the y-axis label inside the plot (so that it does not consume additional horizontal space)
y_label_location (float, default: 0.5) – the location of the y-label

Return type:

Axes

Returns:

the axes object to allow you to add further plot elements

moptipy.examples.jssp.plots module¶

The JSSP-example specific plots.

moptipy.examples.jssp.plots.plot_end_makespans(end_results, name_base, dest_dir, instance_sort_key=<function <lambda>>, algorithm_sort_key=<function <lambda>>, algorithm_namer=<function <lambda>>, x_label_location=1.0)[source]¶

Plot a set of end result boxes/violins functions into one chart.

Parameters:

end_results (Iterable[EndResult]) – the iterable of end results
name_base (str) – the basic name
dest_dir (str) – the destination directory
instance_sort_key (Callable, default: <function <lambda> at 0x7f6684ce7f60>) – the sort key function for instances
algorithm_sort_key (Callable, default: <function <lambda> at 0x7f6684ce6980>) – the sort key function for algorithms
algorithm_namer (Callable[[str], str], default: <function <lambda> at 0x7f6684ce7b00>) – the name function for algorithms receives an algorithm ID and returns an instance name; default=identity function
x_label_location (float, default: 1.0) – the location of the label of the x-axis

Return type:

Returns:

the list of generated files

moptipy.examples.jssp.plots.plot_end_makespans_over_param(end_results, name_base, dest_dir, x_getter, algorithm_getter=<function <lambda>>, instance_sort_key=<function <lambda>>, algorithm_sort_key=<function <lambda>>, title=None, x_axis=<class 'moptipy.evaluation.axis_ranger.AxisRanger'>, x_label=None, x_label_location=1.0, plot_single_instances=True, plot_instance_summary=True, legend_pos='upper right', title_x=0.5, y_label_location=1.0)[source]¶

Plot the performance over a parameter.

Parameters:

end_results (Iterable[EndResult]) – the iterable of end results
name_base (str) – the basic name
dest_dir (str) – the destination directory
title (str | None, default: None) – the optional title
x_getter (Callable[[EndStatistics], int | float]) – the function computing the x-value for each statistics object
algorithm_getter (Callable[[EndStatistics], str | None], default: <function <lambda> at 0x7f6684fa53a0>) – the algorithm getter
instance_sort_key (Callable, default: <function <lambda> at 0x7f6684fa5120>) – the sort key function for instances
algorithm_sort_key (Callable, default: <function <lambda> at 0x7f6684fa68e0>) – the sort key function for algorithms
x_axis (Union[AxisRanger, Callable[[], AxisRanger]], default: <class 'moptipy.evaluation.axis_ranger.AxisRanger'>) – the x_axis ranger
x_label (str | None, default: None) – the x-label
x_label_location (float, default: 1.0) – the location of the x-labels
plot_single_instances (bool, default: True) – shall we plot the values for each single instance?
plot_instance_summary (bool, default: True) – shall we plot the value over all instances?
legend_pos (str, default: 'upper right') – the legend position
title_x (float, default: 0.5) – the title position
y_label_location (float, default: 1.0) – the location of the y label

Return type:

Returns:

the list of generated files

moptipy.examples.jssp.plots.plot_progresses(results_dir, algorithms, name_base, dest_dir, time_unit='ms', log_time=True, instance_sort_key=<function <lambda>>, algorithm_sort_key=<function <lambda>>, x_label_location=0.0, include_runs=False, algorithm_namer=<function <lambda>>)[source]¶

Plot a set of end result boxes/violins functions into one chart.

Parameters:

results_dir (str) – the directory with the log files
algorithms (Iterable[str]) – the set of algorithms to plot together
name_base (str) – the basic name
dest_dir (str) – the destination directory
time_unit (str, default: 'ms') – the time unit to plot
log_time (bool, default: True) – should the time axis be scaled logarithmically?
instance_sort_key (Callable, default: <function <lambda> at 0x7f6684ce5c60>) – the sort key function for instances
algorithm_sort_key (Callable, default: <function <lambda> at 0x7f6684ce5b20>) – the sort key function for algorithms
x_label_location (float, default: 0.0) – the location of the x-labels
include_runs (bool, default: False) – should we include the pure runs as well?
algorithm_namer (Callable[[str], str], default: <function <lambda> at 0x7f668521fba0>) – the name function for algorithms receives an algorithm ID and returns an instance name; default=identity function

Return type:

Returns:

the list of generated files

moptipy.examples.jssp.plots.plot_stat_gantt_charts(end_results, results_dir, name_base, dest_dir, instance_sort_key=<function <lambda>>, statistic=<function median>)[source]¶

Plot a set of Gantt charts following a specific statistics.

Parameters:

end_results (Iterable[EndResult]) – the iterable of end results
results_dir (str) – the result directory
name_base (str) – the basic name
dest_dir (str) – the destination directory
instance_sort_key (Callable, default: <function <lambda> at 0x7f6684ce6b60>) – the sort key function for instances
statistic (Callable[[Iterable[int | float]], int | float], default: <function median at 0x7f66a9e6e200>) – the statistic to use

Return type:

Returns:

the list of generated files

moptipy.examples.jssp.spaces_sizes module¶

Computations regarding the size of the solution spaces in a JSSP.

We represent solutions for a Job Shop Scheduling Problems (JSSPs) as Gantt diagrams. Assume that we look at JSSPs with n jobs and m machines. The number of possible Gantt charts (without useless delays) is (jobs!)**machines.

However, not all of them are necessarily feasible. If all jobs pass through all machines in the same order, then all of the possible Gantt charts are also feasible. However, if, say job 0 first goes to machine 0 and then to machine 1 and job 1 first goes to machine 1 and then to machine 0, there are possible Gantt charts with deadlocks: If we put the second operation of job 0 to be the first operation to be done by machine 1 and put the second operation of job 1 to be the first operation to be done by machine 0, we end up with an infeasible Gantt chart, i.e., one that cannot be executed. Thus, the question arises: “For a given number n of jobs and m of machines, what is the instance with the fewest feasible Gantt charts?”

Well, I am sure that there are clever algorithms to compute this. Maybe we can even ave an elegant combinatorial formula. But I do not want to spend much time on this subject (and maybe would not be able to figure it out even if I wanted to…). So we try to find this information using a somewhat brute force approach: By enumerating instances and, for each instance, the Gantt charts, and count how many of them are feasible.

moptipy.examples.jssp.spaces_sizes.gantt_min_feasible(jobs, machines)[source]¶

Find the minimum number of feasible gantt charts.

Parameters:

jobs (int) – the number of jobs
machines (int) – the number of machines

Return type:

tuple[int, tuple[tuple[int, ...], ...]]

Returns:

the minimum number of feasible solutions for any instance of the given configuration and one example of such an instance

moptipy.examples.jssp.spaces_sizes.make_gantt_space_size_table(dest='solution_space_size.md', instances=('orb06', 'la38', 'abz8', 'yn4', 'swv14', 'dmu72', 'dmu67', 'ta70', 'demo'))[source]¶

Print a table of solution space sizes.

Parameters:

dest (str, default: 'solution_space_size.md') – the destination file
instances (Iterable[str], default: ('orb06', 'la38', 'abz8', 'yn4', 'swv14', 'dmu72', 'dmu67', 'ta70', 'demo')) – the instances to add

Return type:

Returns:

the fully-qualified path to the generated file

moptipy.examples.jssp.spaces_sizes.make_search_space_size_table(dest='solution_space_size.md', instances=('orb06', 'la38', 'abz8', 'yn4', 'swv14', 'dmu72', 'dmu67', 'ta70', 'demo'))[source]¶

Print a table of search space sizes.

Parameters:

dest (str, default: 'solution_space_size.md') – the destination file
instances (Iterable[str], default: ('orb06', 'la38', 'abz8', 'yn4', 'swv14', 'dmu72', 'dmu67', 'ta70', 'demo')) – the instances to add

Return type: