Here we provide the data of the experiments conducted for the electronic book "Optimization Algorithms". These experiments have been done using the The Metaheuristic Optimization in Python, moptipy for short. All datasets are provided in the tar.xz format, which can be unpacked by the default archive manager of several Linux distributions as well as WinRAR.
The Job Shop Scheduling Problem (JSSP) is a classical NP-hard optimization problem where the goal is to find schedules (assignments of jobs to machines) that complete as fast as possible. Each of the n jobs of a JSSP instance must be processed by m machines in a job-specific sequence, requiring a specific runtime on each machine.
These algorithms make random search moves without using information from the objective function.
jssp_1rs.tar.xz: The results of the single random sampling algorithm. 514 kB packed, 2.3 MB unpacked.jssp_rs.tar.xz: The results of the (multiple) random sampling algorithm. 550 kB packed, 2.5 MB unpacked.jssp_rw_swap2.tar.xz: The results of a random walks using the operator swap2 that swaps two (different) job IDs. 483 kB packed, 1.9 MB unpacked.Hill climbers are algorithms are simple local searches that accept only strictly improving moves.
jssp_hc_swap2.tar.xz: The results of a hill climber using the operator swap2 that swaps two (different) job IDs. 680 kB packed, 3.0 MB unpacked.jssp_hcr_swap2.tar.xz: The results of the hill climber with restarts using the operator swap2 that swaps two (different) job IDs, for different restart settings. 6.7 MB packed, 32.4 MB unpacked.jssp_hc_swapn.tar.xz: The results of a hill climber using the operator swapn that swaps a randomly chosen number (different) of job IDs. 714 kB packed, 2.9 MB unpacked.jssp_hcr_swapn.tar.xz: The results of the hill climber with restarts using the operator swapn that swaps a randomly chosen number of (different) job IDs, for different restart settings. 6.7 MB packed, 31.7 MB unpacked.Random Local Search (RLS)-style algorithms are simple local searches that accept all moves that are either improving or lead to the same objective values, i.e., all non-worsening moves. Depending on the field and representation used, they are also known under different names, such as, for example, (1+1) EA if the search space are bit strings and the search operator flips each bit with the same probability.
jssp_rls_swap2.tar.xz: The results of a Random Local Search (RLS) using the operator swap2 that swaps two (different) job IDs. 910 kB packed, 3.9 MB unpacked.jssp_rls_swapn.tar.xz: The results of a Random Local Search (RLS) using the operator swapn that swaps a randomly chosen number of (different) job IDs. 840 kB packed, 3.3 MB unpacked.Evolutionary Algorithms (EAs) maintain a population of solutions. They start with a population of mu random solutions. In each iteration, they keep the mu best solutions in the population. Then they create lambda new solutions by applying search operators to them and add them to the population.
jssp_ea_no_binary_swap2.tar.xz: The results of an Evolutionary Algorithm (EA) using the unary operator swap2 that swaps two (different) job IDs and no binary operator. 56.2 MB packed, 239.9 MB unpacked.jssp_ea_gap_swap2.tar.xz: The results of an Evolutionary Algorithm (EA) using the unary operator swap2 that swaps two (different) job IDs and the binary generalized alternating position operator gap. 54.3 MB packed, 238.9 MB unpacked.jssp_generalEa.tar.xz: The results of a general Evolutionary Algorithm with configurable fitness assignment process, survival selection, and mating selection. As fitness assignment process, we use either the objective values directly, their ranks, or their ranks combined with the iteration indices. As selection algorithms, we test fitness proportionate selection, tournament selection with and without replacements, best selection, and random selection. All setups use the unary operator swap2 that swaps two (different) job IDs and the binary generalized alternating position operator gap at a rate of 0.125 as well as μ=λ∈{4,32}. 10.0 MB packed, 43.7 MB unpacked.Simulated Annealing (SA) is similar to RLS in that it is a local search that always accepts any non-worsening move. However, different from RLS, it also sometimes accepts a move to a solution worse than the current one. The probability to accept such a move is the higher the higher the current "temperature" is and the lower the worse the move is. The "temperature" is controlled by a temperature schedule.
jssp_sa_swap2.tar.xz: The results of a Simulated Annealing (SA) algorithm with exponential temperature schedule and the unary operator swap2 that swaps two (different) job IDs. 32.2 MB packed, 150.7 MB unpacked.Memetic Algorithms (MAs) are basically Evolutionary Algorithms where each solution is refined by another algorithm, usually a local search, for a pre-defined number of ls_fes FEs. We can implement this concept in several different ways, e.g., as a MA with hard-wired RLS, or as a MA where arbitrary algorithms can be plugged in. Here we provide the results of the former (MA+RLS) and the latter (MA+Simulated Annealing).
jssp_marls_gap_swap2.tar.xz: The results of an MA with hard-wired RLS using our binary operator gap and the unary operator swap2 in the RLS for different values of ls_fes and μ=λ. 34.2 MB packed, 185.7 MB unpacked.jssp_masa_gap_swap2.tar.xz: The results of an MA with Simulated Annealing (SA) plugged it, using our binary operator gap and the unary operator swap2 in the SA for different values of ls_fes and μ=λ. The SA is configured to have a starting temperature T_0 of 16 and has ε set such that after 80% of ls_fes has been consumed, the temperature will be approximately 0.22. 38.8 MB packed, 185.6 MB unpacked.This dataset is released under the Attribution-NonCommercial-ShareAlike 4.0 International license (CC BY‑NC‑SA 4.0), see http://creativecommons.org/licenses/by-nc-sa/4.0/ for a summary.
If you have any questions or suggestions, please contact Prof. Dr. Thomas Weise (汤卫思教授) of the Institute of Applied Optimization (应用优化研究所, IAO) of the School of Artificial Intelligence and Big Data (人工智能与大数据学院) at Hefei University (合肥学院) in Hefei, Anhui, China (中国安徽省合肥市) via email to tweise@hfuu.edu.cn with CC to tweise@ustc.edu.cn.