• 1. Introduction
• 2. Installing the R Package
• 3. Provided Data
• 4. Instance Information and Statistics
• 5. Literature Sources
• 6. Cite this Package as follows
• 7. Repository Structure
• 8. Additional Functionality in the R Package
• 9. Other Useful Resources
  • 9.1. Overviews of Results
  • 9.2. Benchmark Instances
• 10. License
• 11. Contact

This is a repository with a data set including instances and results from literature on the Job Shop Scheduling Problem (JSSP). Many papers on the JSSP include tables of result statistics. Here we try to provide such results from many papers in one central location, in order to make it easier to compare new works with the existing ones.

The data is presented both as text files as well as in form of an R package. This means you can either read it using your favorite programming language or by loading and processing it directly via R. We link all the data presented here directly with BibTeX entries and present the results for the different algorithms all together as well as summarize the state-of-the-art. Since the summarization and joining of data is done automatically, we can always easily add more information. If you published a paper on the JSSP, just send it to me and I will add the results.

Our goal is to have an update-able archive of the state-of-the-art results, directly linked with BibTeX entries and the functionality to generate result tables and to compare algorithms with said state-of-the-art. Currently, this project is just a preliminary version. I begun searching papers from 2019 backwards and also include papers referenced by similar repositories and some papers I found (more or less randomly), so many important works are probably still missing.

You can easily install the R by executing the following script in R:

if(!require("devtools")) {
  install.packages("devtools");
  library("devtools");
}
install_github("thomasWeise/jsspInstancesAndResults")

While all data is easily accessible within the R package, you can also access the raw data in form of comma-separated-values (CSV) text files as follows:

• All the results from our literature survey as CSV file, equivalent to loading jssp.results in the R package.
• the instance information with the best-known solutions from the papers analyzed in the study above, equivalent to loading jssp.instances in the R package.
• the raw BibTeX file with all references to literature, equivalent to loading jssp.bibliography in the R package. All the references in the results and instances data refere to keys in this bibliography.
• the OR Library format of all instances in the study in a single file, equivalent to loading jssp.instance.data in the R package
• the plain instance information as CSV file, mainly with infos from Jelke Jeroen van Hoorn's website http://jobshop.jjvh.nl

Of course, such a survey can never be complete. Thus, please expect that some data may be missing. Also, we try to provide some meta-data on the algorithms applied as well as the systems on which the experiments were run. Here, it is very easy to mis-interpret something or to make a mistake. If you have additional papers from which we can include results or wish to correct an error, contact me anytime.

Computer-processable information about the JSSP instances can be found here as CSV and in the data frame jssp.instances in the R package.

The rows have the following meaning:

• id the unique identifier of the instance, as used in the literature (unsolved instances are marked in bold)
• ref the reference to the publication where the instance was first mentioned/created
• jobs the number of jobs in the instance
• machines the number of machines in the instance
• lb the lower bound for the makespan of any solution for the instance
• lb ref the reference to the earliest publication (in this survey) that mentioned this lower bound
• bks the makespan of the best-known solution (in terms of the makespan), based on this survey
• bks ref the reference(s) to the earliest publication(s) in this survey that mentioned the bks
• t(bks) in s the fastest time reported (in seconds), by any of the references in the study, for reaching bks
• t(bks) ref the reference(s) of the publications reporting t(bks)

Please, please take the column t(bks) with many grains of salt. First, we just report the time, regardless of which computer was used to obtain the result or even whether parallelism was applied or not. Second sometimes a minimum time to reach the best result of the run is given in a paper, sometimes we just have the maximum runtime used, sometimes we have a buget – and some publications do not report a runtime at all. Hence, our data here is very incomplete and unreliable and for some instances, we may not have any proper runtime value at all Therefore, this column is not to be understood as a normative a reliable information, more as a very rough guide regarding where we are standing right now. And, needless to say, it is only populated with the information extracted from the papers used in this study, so it may not even be representative.

The data in this study has been taken from the following literature sources. We used http://jobshop.jjvh.nl as starting point for the search, but included additional papers. You can find the full BibTeX entries for the below references in our bibliography. The bibliography keys there will start with the same mnemonic as used here, but here we shortened these keys for the sake of brevity.

A

Abdelmaguid TF (2010). “Representations in Genetic Algorithm for the Job Shop Scheduling Problem: A Computational Study.” Journal of Software Engineering and Applications (JSEA), 3(12), 1155-1162. doi:10.4236/jsea.2010.312135, http://www.scirp.org/journal/paperinformation.aspx?paperid=3561. BibTeX:A2010RIGAFTJSPACS

A2

Asadzadeh L (2015). “A Local Search Genetic Algorithm for the Job Shop Scheduling Problem with Intelligent Agents.” Computers & Industrial Engineering, 85, 376-383. doi:10.1016/j.cie.2015.04.006. BibTeX:A2015ALSGAFTJSSPWIA

ABZ

Adams J, Balas E, Zawack D (1988). “The Shifting Bottleneck Procedure for Job Shop Scheduling.” Management Science, 34(3), 391-401. doi:10.1287/mnsc.34.3.391. BibTeX:ABZ1988TSBPFJSS

AC

Applegate DL, Cook WJ (1991). “A Computational Study of the Job-Shop Scheduling Problem.” ORSA Journal on Computing, 3(2), 149-156. doi:10.1287/ijoc.3.2.149, the JSSP instances used were generated in Bonn in 1986. BibTeX:AC1991ACSOTJSSP

AF

Aydin ME, Fogarty TC (2002). “Modular Simulated Annealing for Job Shop Scheduling running on Distributed Resource Machine (DRM).” London South Bank University, Faculty of Business, Computing and Information Management, London, England, UK. http://www.soc.napier.ac.uk/~benp/dream/dreampaper6a.pdf. BibTeX:AF2002MSAFJSSRODRMD

AK

Abdel-Kader RF (2018). “An Improved PSO Algorithm with Genetic and Neighborhood-Based Diversity Operators for the Job Shop Scheduling Problem.” Applied Artificial Intelligence - An International Journal, 32(5), 433-462. doi:10.1080/08839514.2018.1481903. BibTeX:AK2018AIPAWGANBDOFTJSSP

AKZ

Akram K, Kamal K, Zeb A (2016). “Fast Simulated Annealing Hybridized with Quenching for Solving Job Shop Scheduling Problem.” Applied Soft Computing Journal (ASOC), 49, 510-523. doi:10.1016/j.asoc.2016.08.037. BibTeX:AKZ2016FSAHWQFSJSSP

AMC

Angel JM, Martínez MR, Castillo LRM, Solis LS (2014). “Un Modelo Híbrido de Inteligencia Computacional para Resolver el Problema de Job Shop Scheduling.” Research in Computing Science, 79(Advances in Intelligent Information Technologies), 9-20. http://www.rcs.cic.ipn.mx/2014_79/RCS_79_2014.pdf. BibTeX:AMCS2014UMHDICPREPDJSS

ASS

Amaria K, Souier M, Sar Z (2014). “Artificial Bee Colony (ABC) Algorithm for the Job-Shop Scheduling Problem.” In Proceedings of the 5th International Conference on Metaheuristics and Nature Inspired Computing (META'14), October 27-31, 2014, Marrakech, Morocco. The paper reports makespan 53 for ft06, which is below the lower bound of 55 and thus is not included in our dataset., https://meta2014.sciencesconf.org/42589/document. BibTeX:ASS2014ABCAAFTJSSP

AZ

Amirghasemi M, Zamani R (2015). “An Effective Asexual Genetic Algorithm for Solving the Job Shop Scheduling Problem.” Computers & Industrial Engineering, 83, 123-138. doi:10.1016/j.cie.2015.02.011. BibTeX:AZ2015AEAGAFSTJSSP

B

Bierwirth C (1995). “A Generalized Permutation Approach to Job Shop Scheduling with Genetic Algorithms.” Operations-Research-Spektrum (OR Spectrum), 17(2-3), 87-92. doi:10.1007/BF01719250, http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.52.7392&type=pdf. BibTeX:B1995AGPATJSSWGA

BB

Brinkkötter W, Brucker P (2001). “Solving Open Benchmark Instances for the Job-Shop Problem by Parallel Head-Tail Adjustments.” Journal of Scheduling, 4(1), 53-64. doi:10.1002/1099-1425(200101/02)4:1<53::AID-JOS59>3.0.CO;2-Y4:1<53::AID-JOS59>3.0.CO;2-Y). BibTeX:BB2001SOBIFTJSPBPHTA

BFW

Beck JC, Feng TK, Watson J (2011). “Combining Constraint Programming and Local Search for Job-Shop Scheduling.” INFORMS Journal on Computing, 23(1), 1-14. doi:10.1287/ijoc.1100.0388, http://cfwebprod.sandia.gov/cfdocs/CompResearch/docs/ists-sgmpcs.pdf. BibTeX:BFW2011CCPALSFJSS

BV

Balas E, Vazacopoulos A (1994). “Guided Local Search with Shifting Bottleneck for Job Shop Scheduling.” Management Science Research Report MSSR–609, Graduate School of Industrial Administration (GSIA), Carnegie Mellon University, Pittsburgh, PA, USA. revised November 1995. BibTeX:BV1994GLSWSBFJSS

BV1

Balas E, Vazacopoulos A (1998). “Guided Local Search with Shifting Bottleneck for Job Shop Scheduling.” Management Science, 44(2), 262-275. doi:10.1287/mnsc.44.2.262, reports 307 as makespan for orb07, probably a typo, as the lower bound is 397. BibTeX:BV1998GLSWSBFJSS

C

Caldeira JP (2003). “Private Communication of Result 2869 for ta62 to Éric D. Taillard, listed on Éric Taillard's Page.” http://mistic.heig-vd.ch/taillard/problemes.dir/ordonnancement.dir/jobshop.dir/best_lb_up.txt. BibTeX:C2003PCOR2FTTETLOETP

CCC

Cruz-Chávez MA, Cruz Rosales MH, Zavala-Díaz JC, Aguilar JAH, Rodrıguez-Leó A, Avelino JCP, Orziz MEL, Salinas OH (2019). “Hybrid Micro Genetic Multi-Population Algorithm With Collective Communication for the Job Shop Scheduling Problem.” IEEE Access, 7, 82358-82376. doi:10.1109/ACCESS.2019.2924218, http://ieeexplore.ieee.org/document/8743353. BibTeX:CCCRZDARLAOS2019HMGMPAWCCFTJSSP

CP

Carlier J, Pinson É (1989). “An Algorithm for Solving the Job-Shop Problem.” Management Science, 35(2), 164-176. doi:10.1287/mnsc.35.2.164, jstor: 2631909. BibTeX:CP1989AAFSTJSP

CP1

Carlier J, Pinson É (1990). “A Practical Use of Jackson's Preemptive Schedule for Solving the Job Shop Problem.” Annals of Operations Research, 26(1-4), 269-287. BibTeX:CP1990APUOJPSFSTJSP

CPL

Cheng TCE, Peng B, Lü Z (2016). “A Hybrid Evolutionary Algorithm to Solve the Job Shop Scheduling Problem.” Annals of Operations Research, 242(2), 223-237. doi:10.1007/s10479-013-1332-5, The paper reports 555 as average makespan of HEA for ft20, which is an obvious typo because the other columns have 1165, which is the lower bound. BibTeX:CPL2016AHEATSTJSSP

DMU

Demirkol E, Mehta SV, Uzsoy R (1996). “Benchmarking for Shop Scheduling Problems.” Research Memorandum 96-4, School of Industrial Engineering, Purdue University, West Lafayette, IN, USA. BibTeX:DMU1996BFSSP

DMU1

Demirkol E, Mehta SV, Uzsoy R (1998). “Benchmarks for Shop Scheduling Problems.” European Journal of Operational Research (EJOR), 109(1), 137-141. doi:10.1016/S0377-2217(97)00019-200019-2). BibTeX:DMU1998BFSSP

DPN

Dao T, Pan T, Nguyen T, Pan J (2018). “Parallel Bat Algorithm for Optimizing Makespan in Job Shop Scheduling Problems.” Journal of Intelligent Manufacturing, 29(2), 451-462. doi:10.1007/s10845-015-1121-x. BibTeX:DPNP2018PBAFOMIJSSP

FGB

Flórez E, Gómez W, Bautista L (2013). “An Ant Colony Optimization Algorithm for Job Shop Scheduling Problem.” Computing Research Repository (CoRR) abs/1309.5110, arXiv. https://arxiv.org/pdf/1309.5110.pdf. BibTeX:FGB2013AACOAFJSSP

FT

Fisher H, Thompson GL (1963). “Probabilistic Learning Combinations of Local Job-Shop Scheduling Rules.” In Muth JF, Thompson GL (eds.), Industrial Scheduling, 225-251. Prentice-Hall, Englewood Cliffs, NJ, USA. BibTeX:FT1963PLCOLJSSR

FTM

Florian M, Trepant P, McMahon G (1971). “An Implicit Enumeration Algorithm for the Machine Sequencing Problem.” Management Science, 17(12), B-782-B-792. doi:10.1287/mnsc.17.12.B782, jstor: 2629469. BibTeX:FTM1971AIEAFTMSP

GL

Gharbi A, Labidi M (2010). “Extending the Single Machine-Based Relaxation Scheme for the Job Shop Scheduling Problem.” Electronic Notes in Discrete Mathematics, 36, 1057-1064. doi:10.1016/j.endm.2010.05.134, this algorithm was used to solve several JSSP instances of the OR Library. BibTeX:GL2010ETSMBRSFTJSSP

GLW

Gao L, Li X, Wen X, Lu C, Wen F (2015). “A Hybrid Algorithm based on a New Neighborhood Structure Evaluation Method for Job Shop Scheduling Problem.” Computers & Industrial Engineering, 88, 417-429. doi:10.1016/j.cie.2015.08.002. BibTeX:GLWLW2015AHABOANNSEMFSSP

GR

Gonçalves JF, Resende MGC (2014). “An Extended Akers Graphical Method with a Biased Random-Key Genetic Algorithm for Job-Shop Scheduling.” International Transactions on Operational Research (ITOR), 21(2), 215-246. doi:10.1111/itor.12044, http://mauricio.resende.info/doc/brkga-jss2011.pdf. BibTeX:GR2014AEAGMWABRKGAFJSS

GTK

Gen M, Tsujimura Y, Kubota E (1994). “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. ISBN 0-7803-2129-4, doi:10.1109/ICSMC.1994.400072, http://read.pudn.com/downloads151/doc/658565/00400072.pdf. BibTeX:GTK1994SJSSPBGA

GvH

Gromicho JAS, van Hoorn JJ, Saldanha-da-Gama F, Timmer GT (2009). “Exponentially Better than Brute Force: Solving the Job-Shop Scheduling Problem Optimally by Dynamic Programming.” Research Memorandum 2009-56, Faculty of Economics and Business Administration, Vrije Universiteit Amsterdam, Amsterdam, The Netherlands. http://degree.ubvu.vu.nl/repec/vua/wpaper/pdf/20090056.pdf. BibTeX:GvHSGT2009

H

Henning A (2002). Praktische Job-Shop Scheduling-Probleme. Ph.D. thesis, Friedrich-Schiller-Universität Jena, Jena, Germany. alternate url: https://nbn-resolving.org/urn:nbn:de:gbv:27-20060809-115700-4, http://www.db-thueringen.de/servlets/DocumentServlet?id=873. BibTeX:H2002PJSSP

HRS

Hernández-Ramírez L, Solis JF, Castilla-Valdez G, González-Barbosa JJ, Terán-Villanueva D, Morales-Rodríguez ML (2019). “A Hybrid Simulated Annealing for Job Shop Scheduling Problem.” International Journal of Combinatorial Optimization Problems and Informatics (IJCOPI), 10(1), 6-15. published 2018-08-10, http://ijcopi.org/index.php/ojs/article/view/111. BibTeX:HRSCVGBTVMR2019AHSAFJSSP

HY

Han B, Yang J (2020). “Research on Adaptive Job Shop Scheduling Problems Based on Dueling Double DQN.” IEEE Access, 8, 186474-186495. doi:10.1109/ACCESS.2020.3029868. BibTeX:HY2020ROAJSSPBODDD

JM

Jain AS, Meeran S (1999). “Deterministic Job-Shop Scheduling: Past, Present and Future.” European Journal of Operational Research (EJOR), 113(2), 390-434. doi:10.1016/S0377-2217(98)00113-100113-1). BibTeX:JM1999DJSSPPAF

JPD

Jorapur V, Puranik VS, Deshpande AS, Sharma MR (2014). “Comparative Study of Different Representations in Genetic Algorithms for Job Shop Scheduling Problem.” Journal of Software Engineering and Applications (JSEA), 7(7), 571-580. doi:10.4236/jsea.2014.77053, http://www.scirp.org/journal/paperinformation.aspx?paperid=46670. BibTeX:JPDS2014CAODRIGAFJSSP

JZ

Jiang T, Zhang C (2018). “Application of Grey Wolf Optimization for Solving Combinatorial Problems: Job Shop and Flexible Job Shop Scheduling Cases.” IEEE Access, 6, 26231-26240. doi:10.1109/ACCESS.2018.2833552, http://ieeexplore.ieee.org/document/8355479. BibTeX:JZ2018AOGWOFSCPJSAFJSSC

K

Kolonko M (1999). “Some New Results on Simulated Annealing Applied to the Job Shop Scheduling Problem.” European Journal of Operational Research (EJOR), 113(1), 123-136. doi:10.1016/S0377-2217(97)00420-700420-7). BibTeX:K1999SNROSAATTJSSP

K2

Kurdi M (2015). “A New Hybrid Island Model Genetic Algorithm for Job Shop Scheduling Problem.” Computers & Industrial Engineering, 88, 273-283. doi:10.1016/j.cie.2015.07.015. BibTeX:K2015ANHIMGAFJSSP

KNF

Koshimura M, Nabeshima H, Fujita H, Hasegawa R (2010). “Solving Open Job-Shop Scheduling Problems by SAT Encoding.” IEICE Transactions on Information and Systems, E93.D(8), 2316-2318. doi:10.1587/transinf.E93.D.2316. BibTeX:KNFH2010SOJSSPBSE

KV

Kulkarni K, Venkateswaran J (2014). “Iterative Simulation and Optimization Approach for Job Shop Scheduling.” In Buckley SJ, Miller JA (eds.), Proceedings of the 2014 Winter Simulation Conference, December 7-10, 2014, Savannah, GA, USA, 1620-1631. doi:10.1109/WSC.2014.7020013, https://www.anylogic.com/upload/iblock/5aa/5aa2987b839049668eeef8a21c811e6b.pdf. BibTeX:KV2014ISAOAFJSS

L

Lawrence SR (1984). Resource Constrained Project Scheduling: An Experimental Investigation of Heuristic Scheduling Techniques (Supplement). Ph.D. thesis, Graduate School of Industrial Administration (GSIA), Carnegie-Mellon University, Pittsburgh, PA, USA. BibTeX:L1998RCPSAEIOHSTS

LWF

Li L, Weng W, Fujimura S (2017). “An Improved Teaching-Learning-based Optimization Algorithm to Solve Job Shop Scheduling Problems.” In Zhu G, Yao S, Cui X, Xu S (eds.), 16th IEEE/ACIS International Conference on Computer and Information Science (ICIS'17), May 24-26, 2017, Wuhan, China, 797-801. ISBN 978-1-5090-5507-4, doi:10.1109/ICIS.2017.7960101. BibTeX:LWF2017AITLBOATSJSSP

LYL

Liu M, Yao X, Li Y (2020). “Hybrid Whale Optimization Algorithm Enhanced with Lévy Flight and Differential Evolution for Job Shop Scheduling Problems.” Applied Soft Computing Journal (ASOC), 87, 105954. doi:10.1016/j.asoc.2019.105954, Originally, the paper had two typos in the results. It reports an average result (918.4) for WSO-LFDE on la20, which is worse than the worst result (902) it reports. We therefore ignore the worst reported result for that algorithm on that instance, since it was probably accidentally copy-pasted from the best result. On instance la23, the lower bound is 1032 but the result 1023 is reported, which is clearly an accidental typo. These typos are currently fixed in an erratum process. BibTeX:LYL2020HWOAEWLFADEFJSSP

M

Martin PD (1996). A Time-Oriented Approach to Computing Optimal Schedules for the Job-Shop Scheduling Problem. Ph.D. thesis, School of Operations Research and Industrial Engineering, Cornell University, Ithaca, NY, USA. oclc: 64683112. BibTeX:M1996ATOATCOSFTJSSP

M2

Mahapatra DK (2012). “Bachelor's Thesis: Job Shop Scheduling using Artificial Immune System.” guided by Prof. S. S. Mahapatra, http://pdfs.semanticscholar.org/a350/070a2612d046d11feb33e64d1ab58cd8870d.pdf. BibTeX:M2012JSSUAIS

MF

McMahon G, Florian M (1975). “On Scheduling with Ready Times and Due Dates to Minimize Maximum Lateness.” Operations Research, 23(3), 475-482. doi:10.1287/opre.23.3.475, jstor: 169697. BibTeX:MF1975OSWRTADDTMML

MHT

Mui NH, Hoa VD, Tuyen LT (2012). “A Parallel Genetic Algorithm for the Job Shop Scheduling Problem.” In Proceedings of the IEEE International Symposium on Signal Processing and Information Technology (ISSPIT'12), December 12-15, 2012, Ho Chi Minh City, Vietnam, 19-24. ISBN 978-1-4673-5604-6, doi:10.1109/ISSPIT.2012.6621254. BibTeX:MHT2012APGAFTJSSP

MM

Magalhães-Mendes J (2013). “A Comparative Study of Crossover Operators for Genetic Algorithms to Solve the Job Shop Scheduling Problem.” WSEAS Transactions on Computers, 12(4), 164-173. http://www.wseas.org/multimedia/journals/computers/2013/5705-156.pdf. BibTeX:MM2013ACSOCOFGATSTJSSP

MNK

Maqsood S, Noor S, Khan MK, Wood A (2012). “Hybrid Genetic Algorithm (GA) for Job Shop Scheduling Problems and its Sensitivity Analysis.” International Journal of Intelligent Systems Technologies and Applications (IJISTA), 11(1/2), 49-62. doi:10.1504/IJISTA.2012.046543. BibTeX:MNKW2012HGAGFJSSPAISA

MTS

Miller-Todd J, Steinhöfel K, Veenstra P (2018). “Firefly-Inspired Algorithm for Job Shop Scheduling.” In Böckenhauer H, Komm D, Unger W (eds.), Adventures Between Lower Bounds and Higher Altitudes - Essays Dedicated to Juraj Hromkovič on the Occasion of His 60th Birthday, volume 11011 series Lecture Notes in Computer Science (LNCS), 423-433. Springer. ISBN 978-3-319-98354-7, doi:10.1007/978-3-319-98355-4_24. BibTeX:MTSV2018FIAFJSS

N

Nazif H (2015). “Solving Job Shop Scheduling Problem Using an Ant Colony Algorithm.” Journal of Asian Scientific Research, 5(5), 261-268. doi:10.18488/journal.2/2015.5.5/2.5.261.268, http://www.aessweb.com/pdf-files/jasr-2015-5(5)-261-268.pdf. BibTeX:N2015SJSSPUAACO

NA

Narendhar S, Amudha T (2012). “A Hybrid Bacterial Foraging Algorithm For Solving Job Shop Scheduling Problems.” International Journal of Programming Languages and Applications (IJPLA), 2(4), 1-11. doi:10.5121/ijpla.2012.2401, Also available via Computing Research Repository (CoRR) abs/1211.4971 at arXiv:1211.4971v1 [cs.NE], https://arxiv.org/pdf/1211.4971.pdf. BibTeX:NA2012AHBFAFSJSSP

NS

Nowicki E, Smutnicki C (1996). “A Fast Taboo Search Algorithm for the Job Shop Problem.” Management Science, 42(6), 783-938. doi:10.1287/mnsc.42.6.797, jstor: 2634595, http://pacciarelli.inf.uniroma3.it/CORSI/MSP/NowickiSmutnicki96.pdf. BibTeX:NS1996AFTSAFTJSP

NS2

Nowicki E, Smutnicki C (2005). “An Advanced Taboo Search Algorithm for the Job Shop Problem.” Journal of Scheduling, 8(2), 145-159. doi:10.1007/s10951-005-6364-5. BibTeX:NS2005AATSAFTJSP

NZJ

Nguyen S, Zhang M, Johnston M, Tan KC (2013). “A Computational Study of Representations in Genetic Programming to Evolve Dispatching Rules for the Job Shop Scheduling Problem.” IEEE Transactions on Evolutionary Computation (TEVC), 17(5), 621-639. doi:10.1109/TEVC.2012.2227326. BibTeX:NZJT2013ACSORIGPTED

ODP

Oliveira JA, Dias L, Pereira G (2010). “Solving the Job Shop Problem with a Random Keys Genetic Algorithm with Instance Parameters.” In Rodrigues H, Herskovits J, Soares CM, Guedes JM, Folgado J, Araújo A, Moleiro F, Kuzhichalil JP, Madeira JA, Dimitrovová Z (eds.), Proceedings of the 2nd International Conference on Engineering Optimization (EngOpt2010), September 6-9, 2010, Lisbon, Portugal. ISBN 978-989-96264-3-0, http://www1.dem.ist.utl.pt/engopt2010/Book_and_CD/Papers_CD_Final_Version/pdf/08/01512-01.pdf. BibTeX:ODP2010STJSPWARKGAWIP

OV

Ombuki BM, Ventresca M (2004). “Local Search Genetic Algorithms for the Job Shop Scheduling Problem.” Applied Intelligence - The International Journal of Research on Intelligent Systems for Real Life Complex Problems, 21(1), 99-109. doi:10.1023/B:APIN.0000027769.48098.91. BibTeX:OV2004LSGAFTJSSP

P

Pongchairerks P (2014). “Variable Neighbourhood Search Algorithms Applied to Job-Shop Scheduling Problems.” International Journal of Mathematics in Operational Research (IJMOR), 6(6), 752-774. doi:10.1504/IJMOR.2014.065421. BibTeX:P2014VNSAATJSSP

P2

Pongchairerks P (2019). “A Two-Level Metaheuristic Algorithm for the Job-Shop Scheduling Problem.” Complexity, 2019(8683472), 1-11. doi:10.1155/2019/8683472, http://www.hindawi.com/journals/complexity/2019/8683472/. BibTeX:P2019ATLMAFTJSSP

PLC

Peng B, Lü Z, Cheng TCE (2015). “A Tabu Search/Path Relinking Algorithm to Solve the Job Shop Scheduling Problem.” Computers & Operations Research, 53, 154-164. doi:10.1016/j.cor.2014.08.006, A February 2014 preprint is available as arXiv:1402.5613v1 [cs.DS], http://arxiv.org/abs/1402.5613. BibTeX:PLC2015ATSPRATSTJSSP

PM

Pezzella F, Merelli E (2000). “A Tabu Search Method Guided by Shifting Bottleneck for the Job Shop Scheduling Problem.” European Journal of Operational Research (EJOR), 120(2), 297-310. doi:10.1016/S0377-2217(99)00158-700158-7), https://www2.cs.sfu.ca/CourseCentral/827/havens/papers/topic%2310(JobShop)/Tabu%20With%20Shifting.pdf. BibTeX:PM2000ATSMGBSBFTJSSP

PPH

Pérez E, Posada M, Herrera F (2012). “Analysis of New Niching Genetic Algorithms for Finding Multiple Solutions in the Job Shop Scheduling.” Journal of Intelligent Manufacturing, 23(3), 341-356. doi:10.1007/s10845-010-0385-4, reports result 595.97 for la03, which is below the lower bound of 597 and thus not included in our data set. BibTeX:PPH2012AONNGAFMSITJSS

PSV

Pardalos PM, Shylo OV, Vazacopoulos A (2010). “Solving Job Shop Scheduling Problems Utilizing the Properties of Backbone and "Big Valley".” Computational Optimization and Applications, 47(1), 61-76. doi:10.1007/s10589-008-9206-5. BibTeX:PSV2010SJSSPUTPOBABV

QL

Qiu X, Lau HYK (2014). “An AIS-based Hybrid Algorithm for Static Job Shop Scheduling Problem.” Journal of Intelligent Manufacturing, 25(3), 489-503. doi:10.1007/s10845-012-0701-2. BibTeX:QL2014AABHAFSSSP

RNK

Raeesi N. MR, Kobti Z (2012). “A Knowledge-Migration-Based Multi-Population Cultural Algorithm to Solve Job Shop Scheduling.” In Youngblood GM, McCarthy PM (eds.), Proceedings of the Twenty-Fifth International Florida Artificial Intelligence Research Society Conference (FLAIRS'12), May 23-25, 2012, Marco Island, FL, USA. ISBN 978-1-57735-558-8, http://www.aaai.org/ocs/index.php/FLAIRS/FLAIRS12/paper/view/4378/4768. BibTeX:RNK2012AKMBMPCATSJSS

S

Schilham R (2000). “Results listed on Éric Taillard's Page.” see also http://jobshop.jjvh.nl/, http://mistic.heig-vd.ch/taillard/problemes.dir/ordonnancement.dir/ordonnancement.html. BibTeX:S200RLOETP

S2

Shylo OV (2019). “Job Shop Scheduling (Personal Homepage).” http://optimizizer.com/jobshop.php. BibTeX:S2019JSSPH

SB

Sabuncuoğlu İ, Bayiz M (1999). “Job Shop Scheduling with Beam Search.” European Journal of Operational Research (EJOR), 118(2), 390-412. doi:10.1016/S0377-2217(98)00319-100319-1), http://yoksis.bilkent.edu.tr/doi_getpdf/articles/10.1016-S0377-2217(98)00319-1.pdf. BibTeX:SB1999JSSWBS

SIS

Shi G, Iima H, Sannomiya N (1997). “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, 4395-4400. ISBN 0-7803-3590-2, doi:10.1109/CDC.1996.577484. BibTeX:SIS1997NESFSJSPBGA

SK

Sakuma J, Kobayashi S (2000). “Extrapolation-Directed Crossover for Job-Shop Scheduling Problems: Complementary Combination with JOX.” In Whitley LD, Goldberg DE, Cantú-Paz E, Spector L, Parmee IC, Beyer H (eds.), Proceedings of the Genetic and Evolutionary Computation Conference (GECCO'00), July 8-12, 2000, Las Vegas, NV, USA, 973-980. ISBN 1-55860-708-0. BibTeX:SK2000EDCFJSSPCCWJ

SMM

Sahana SK, Mukherjee I, Mahanti PK (2018). “Parallel Artificial Bee Colony (PABC) for Job Shop Scheduling Problems.” Advances in Information Sciences and Service Sciences (AISS), 10(3), 1-11. reports 661 as result for abz9 which is below the lower bound 678 and thus not included in our data set, http://www.globalcis.org/aiss/ppl/AISS3877PPL.pdf. BibTeX:SMM2018PABCPFJSSP

SS

Shylo OV, Shams H (2018). “Boosting Binary Optimization via Binary Classification: A Case Study of Job Shop Scheduling.” cs.AI/math.OC abs/1808.10813, arXiv. Many results are available in the GitHub repository https://github.com/quasiquasar/gta-jobshop-data. We just use a subset (namely, samples after 3, 5, 30, and 60 minutes, and the end results) to compute statistics. The paper reports some new bks for which the creating runs are not contained in the GitHub repository, verified via email with the authors, as well as bound 6196 for both dmu74 and dmu75. Other results have been published on Prof. Shylo's website http://optimizizer.com/DMU.php for the same paper (including dmu17), https://arxiv.org/pdf/1808.10813. BibTeX:SS2018BBOVBCACSOJSS

SSS

Sharma N, Sharma H, Sharma A (2018). “Beer Froth Artificial Bee Colony Algorithm for Job-Shop Scheduling Problem.” Applied Soft Computing Journal (ASOC), 68, 507-524. doi:10.1016/j.asoc.2018.04.001. BibTeX:SSS2018BFABCAFJSSP

SWV

Storer RH, Wu SD, Vaccari R (1992). “New Search Spaces for Sequencing Problems with Application to Job Shop Scheduling.” Management Science, 38(10), 1495-1509. doi:10.1287/mnsc.38.10.1495. BibTeX:SWV1992NSSFSPWATJSS

T

Taillard ÉD (1993). “Benchmarks for Basic Scheduling Problems.” European Journal of Operational Research (EJOR), 64(2), 278-285. doi:10.1016/0377-2217(93)90182-M90182-M). BibTeX:T199BFBSP

V

Vaessens RJM (1995). “Results listed on Éric Taillard's Page.” see also http://jobshop.jjvh.nl/, http://mistic.heig-vd.ch/taillard/problemes.dir/ordonnancement.dir/ordonnancement.html. BibTeX:V1995RLOETP

V1

Vaessens RJM (1996). “Addition to John Edward Beasley's OR Library.” see also http://jobshop.jjvh.nl/, http://people.brunel.ac.uk/~mastjjb/jeb/orlib/files/jobshop1.txt. BibTeX:V1996ATJEBOL

VAL

Vaessens RJM, Aarts EHL, Lenstra JK (1996). “Job Shop Scheduling by Local Search.” INFORMS Journal on Computing, 8(3), 302-317. doi:10.1287/ijoc.8.3.302. BibTeX:VAL1996JSSBLS

vH

van Hoorn JJ (2015). “Job Shop Instances and Solutions.” http://jobshop.jjvh.nl. BibTeX:vH2015JSIAS

vH2

van Hoorn JJ (2016). Dynamic Programming for Routing and Scheduling: Optimizing Sequences of Decisions. Ph.D. thesis, Vrije Universiteit Amsterdam, Amsterdam, The Netherlands. http://jobshop.jjvh.nl/dissertation. BibTeX:vH2016DPFRASOSOD

VLS

Vilím P, Laborie P, Shaw P (2015). “Failure-Directed Search for Constraint-Based Scheduling.” In Michel L (ed.), International Conference Integration of AI and OR Techniques in Constraint Programming: Proceedings of 12th International Conference on AI and OR Techniques in Constriant Programming for Combinatorial Optimization Problems (CPAIOR'2015), May 18-22, 2015, Barcelona, Spain, volume 9075 series Lecture Notes in Computer Science (LNCS) and Theoretical Computer Science and General Issues book sub series (LNTCS), 437-453. ISBN 978-3-319-18007-6, doi:10.1007/978-3-319-18008-3_30. BibTeX:VLS2015FDSFCBS

VLS2

Vilím P, Laborie P, Shaw P (2015). “Failure-Directed Search for Constraint-Based Scheduling - Detailed Experimental Results.” The detailed experimental results of the paper "Failure-Directed Search for Constraint-Based Scheduling" by the same authors, in International Conference Integration of AI and OR Techniques in Constraint Programming: Proceedings of 12th International Conference on AI and OR Techniques in Constriant Programming for Combinatorial Optimization Problems (CPAIOR'2015), May 18-22, 2015, Barcelona, Spain, pages 437-453, doi:10.1007/978-3-319-18008-3_30., http://vilim.eu/petr/cpaior2015-results.pdf. BibTeX:VLS2015FDSFCBSDER

W

Weise T (2019-2020). “jsspInstancesAndResults: Results, Data, and Instances of the Job Shop Scheduling Problem.” 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 as well as R program code to access them., https://github.com/thomasWeise/jsspInstancesAndResults. BibTeX:W2019JRDAIOTJSSP

WCL

Wang L, Cai J, Li M (2016). “An Adaptive Multi-Population Genetic Algorithm for Job-Shop Scheduling Problem.” Advances in Manufacturing, 4(2), 142-149. doi:10.1007/s40436-016-0140-y. BibTeX:WCL2016AAMPGAFJSSP

WD

Wang X, Duan H (2014). “A Hybrid Biogeography-based Optimization Algorithm for Job Shop Scheduling Problem.” Computers & Industrial Engineering, 73, 96-114. doi:10.1016/j.cie.2014.04.006, http://hbduan.buaa.edu.cn/papers/2014CAIE_Wang_Duan.pdf. BibTeX:WD2014AHBBOAFJSSP

WGK

Weckman GR, Ganduri CV, Koonce DA (2008). “A Neural Network Job-Shop Scheduler.” Journal of Intelligent Manufacturing, 19, 191-201. doi:10.1007/s10845-008-0073-9. BibTeX:WGK2008ANNJSS

WTC

Wang S, Tsai C, Chiang M (2018). “A High Performance Search Algorithm for Job-Shop Scheduling Problem.” In Shakshuki EM, Yasar A (eds.), The 9th International Conference on Emerging Ubiquitous Systems and Pervasive Networks (EUSPN'18) / The 8th International Conference on Current and Future Trends of Information and Communication Technologies in Healthcare (ICTH'18) / Affiliated Workshops, November 5-8, 2018, Leuven, Belgium, volume 141 series Procedia Computer Science, 119-126. doi:10.1016/j.procs.2018.10.157. BibTeX:WTC2018AHPSAFJSSP

YN

Yamada T, Nakano R (1992). “A Genetic Algorithm Applicable to Large-Scale Job-Shop Instances.” In Männer R, Manderick B (eds.), Proceedings of Parallel Problem Solving from Nature 2 (PPSN II), September 28-30, 1992, Brussels, Belgium, 281-290. BibTeX:YN1992AGAATLSJSI

YN1

Yamada T, Nakano R (1997). “Genetic Algorithms for Job-Shop Scheduling Problems.” In Proceedings of Modern Heuristic for Decision Support, March18-19, 1997, London, England, UK, 67-81. BibTeX:YN1997GAFJSSP

ZHZ

Zupan H, Herakovič N, Žerovnik J (2016). “A Heuristic for the Job Shop Scheduling Problem.” In Papa G, Mernik M (eds.), The 7th International Conference on Bioinspired Optimization Methods and their Application (BIOMA'16), May 18-20, 2016, Bled, Slovenia, 187-198. ISBN 978-961-264-093-4, http://bioma.ijs.si/conference/BIOMA2016Proceedings.pdf. BibTeX:ZHZ2016AHFTJSSP

ZLR

Zhang C, Li P, Rao Y, Guan Z (2008). “A Very Fast TS/SA Algorithm for the Job Shop Scheduling Problem.” Computers & Operations Research, 35(1), 282-294. doi:10.1016/j.cor.2006.02.024. BibTeX:ZLRG2008AVFTAFTJSSP

ZRL

Zhang C, Rao Y, Li P (2008). “An Effective Hybrid Genetic Algorithm for the Job Shop Scheduling Problem.” International Journal of Advanced Manufacturing Technology (JAMT), 39, 965-974. doi:10.1007/s00170-007-1354-8. BibTeX:ZRL2008AEHGAFTJSSP

ZSR

Zhang C, Shao X, Rao Y, Qiu H (2008). “Some New Results on Tabu Search Algorithm Applied to the Job-Shop Scheduling Problem.” In Jaziri W (ed.), Tabu Search. IntechOpen, London, England, UK. ISBN 978-3-902613-34-9, doi:10.5772/5593, http://www.intechopen.com/books/tabu_search/some_new_results_on_tabu_search_algorithm_applied_to_the_job-shop_scheduling_problem. BibTeX:ZSRQ2008SNROTSAATTJSSP

Weise T (2019-2020). “jsspInstancesAndResults: Results, Data, and Instances of the Job Shop Scheduling Problem.” 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 as well as R program code to access them., https://github.com/thomasWeise/jsspInstancesAndResults.

@misc{W2019JRDAIOTJSSP,
  title = {jsspInstancesAndResults: Results, Data, and Instances of the Job Shop Scheduling Problem},
  author = {Thomas Weise},
  publisher = {Institute of Applied Optimization, Hefei University},
  address = {Hefei, Anhui, China},
  year = {2019--2020},
  url = {https://github.com/thomasWeise/jsspInstancesAndResults},
  note = {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 as well as R program code to access them.}
}

In the folder data-raw, we provide the R scripts used to generate the data frames in the package, the complete data CSV files, and this README. The idea is that we maintain a central BibTeX file (reflected in data frame jssp.bibliography) and a list of algorithms as well as a list of basic instance information. For each algorithm, a CSV text file is included with the results of that algorithm in the corresponding publication. The scripts then merge all this information into one central CSV file with all the results and provide the data as data frame jssp.results. From these results, we then automatically update the instance information and obtain an instance information file with best-known solutions, reflected in data frame jssp.instances. This is then used together with the bibliography to build our README.md. This structure allows us to easily update the repository with new results, while providing the full table of all data from literature. Finally, we generate a single, OR-Library compatible file with all of the JSSP instances in this study, such that you can easily load them and do your own experiments. The data from this file is provided as the list jssp.instance.data in the R package. In summary, all the data is provided both as text files for processing with arbitary tools and as as data frames/lists jssp.bibliography, jssp.results, jssp.instances, and jssp.instance.data if you install this repository as R package (see above).

In the package jsspInstancesAndResults, we additionally provide the functionality to transform different representations for candidate solutions into Gantt charts (which are directly checked and evaluated in the process). Existing Gantt charts can also be evaluated, i.e., we can check whether the Gantt chart is correct and compute its makespan. If the plotteR package is installed, then the Gantt charts can directly be plotted.

data.oo <- c( 2L,  8L, 10L, 12L,  7L, 20L, 18L,   1L,  6L, 11L,
             17L,  9L, 28L,  5L, 30L, 19L, 21L,  38L, 22L,  3L,
             40L, 15L, 48L, 13L, 31L, 27L, 37L,  16L, 58L, 41L,
             50L, 32L, 25L, 23L, 47L,  4L, 68L,  60L, 29L, 39L,
             51L, 26L, 42L, 35L, 33L, 49L, 57L,  70L, 36L, 45L,
             61L, 14L, 55L, 67L, 78L, 43L, 71L,  53L, 52L, 80L,
             59L, 63L, 24L, 81L, 46L, 90L, 62L, 100L, 73L, 65L,
             88L, 56L, 72L, 77L, 34L, 87L, 44L,  98L, 69L, 66L,
             75L, 79L, 54L, 83L, 89L, 82L, 76L,  64L, 91L, 74L,
             99L, 93L, 92L, 86L, 84L, 85L, 96L,  95L, 97L, 94L);
result <- jssp.oo.to.gantt(data.oo, "orb07");
print(result$makespan);
# [1] 397
plotteR::plot.gantt(result$gantt);

Many of the data in this package are gathered from different sources in the internet, which were our starting point to explore and add results from quite a few publications.

Besides our repository, the following sources in the web provide useful information about the state-of-the-art on the JSSP:

• Many of the information about the problem instances are taken from incredibly great website http://jobshop.jjvh.nl run by Jelke Jeroen van Hoorn, while the results are taken from their individual publications.
• The websites http://optimizizer.com/jobshop.php run by Oleg V. Shylo, which holds many results on the JSSP as well.
• Éric Taillard's Page http://mistic.heig-vd.ch/taillard/problemes.dir/ordonnancement.dir/ordonnancement.html

• OR-Library with the abz*, la*, orb*, swv*, and yn* instances
• Oleg V. Shylo's website (http://optimizizer.com/DMU.php) with the dmu* instances
• Éric Taillard's Page http://mistic.heig-vd.ch/taillard/problemes.dir/ordonnancement.dir/ordonnancement.html with the ta* instances
• A repository with instances of the JSSP can be found at http://github.com/tamy0612/JSPLIB.

Any content in this repository which originates from other sources is licensed under the licensing conditions of the respective owners. This includes the results of works published in literature as well as the benchmarking instances. Any of the above which permits me setting a license and any content contributed by myself is under the GNU GENERAL PUBLIC LICENSE Version 3, 29 June 2007.

If you have any questions or suggestions, please contact Prof. Dr. Thomas Weise of the Institute of Applied Optimization at Hefei University in Hefei, Anhui, China via email to [email protected] and [email protected].