License

Job Shop Scheduling Problem Benchmark Instances

About The Project¶

This project contains all Job Shop Scheduling Problem (JSP) benchmark instances from http://jobshop.jjvh.nl/ and some utility functions to work with JSP instances. The project contains a parser to read the instances in the .txt files with JPS instances in taillard and standard format. For more info about the formatting see: http://jobshop.jjvh.nl/explanation.php The benchmark instances can be imported as a numpy array. The instances have the shape (2, n_jobs, n_machines), where the last dimension contains the processing time and the release time of the job on the machine. So the instance-numpy-array consists of two numpy arrays, the first array contains the order of the machines and the second array contains the processing times of the tasks on the machines. Here is a minimal example of how to define a instance:

import numpy as np
custom_jsp_instance = np.array([
    [
        [0, 1, 2, 3],  # job 0 (machine0, machine1, machine2, machine3)
        [0, 2, 1, 3]  # job 1 (machine0, machine1, machine2, machine3)
    ],
    [
        [11, 3, 3, 12],  # task durations of job 0
        [5, 16, 7, 4]  # task durations of job 1
    ]
])

Installation¶

Install the package with pip:

   pip install jsp-instance-utils

Importing a JSP instance OR-tools Solver¶

jsp-instance-utils contains provides a implementation of the OR-tools solver for the JSP in the numpy array format provided by jsp-instance-utils. The following example shows how to import and solve the ft06 instance with the OR-tools solver:

from jsp_instance_utils.instances import ft06
from jsp_instance_utils.jsp_or_tools_solver import solve_jsp

makespan, status, *_ = solve_jsp(jsp_instance=ft06, plot_results=True)

assert status == "OPTIMAL"
assert makespan == 55

The code above yields the following output, if the plot_results flag is set to True:

Available Instances¶

All instances are available in the jsp_instance_utils.instances module. You can also find them on this website: http://jobshop.jjvh.nl/

More Examples¶

For more examples you can have a look at the test files in the tests directory.

Instance Information and Statistics¶

This section is based on the GitHub Repo jsspInstancesAndResults by Thomas Weise. The linked Repo is essentially a equivalent to this one, but for the programming language R.

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.

id	ref	jobs	machines	lb	lb ref	bks	bks ref	t(bks) in s	t(bks) ref
abz5	ABZ	10	10	1234	AC	1234	AC	0.04	AZ
abz6	ABZ	10	10	943	AC	943	AC	0.03	AZ
abz7	ABZ	20	15	656	M	656	H	1000	H
abz8	ABZ	20	15	648	VLS	665	H	1000	H
abz9	ABZ	20	15	678	KNF	678	ZSR	3.25	AZ
dmu01	DMU1	20	15	2501	BB	2563	H	332.87	PLC
dmu02	DMU1	20	15	2651	BB	2706	H	179.24	PLC
dmu03	DMU1	20	15	2731	BB	2731	H	388.59	PLC
dmu04	DMU1	20	15	2601	BB	2669	H	96.54	PLC
dmu05	DMU1	20	15	2749	BB	2749	H	303	PLC
dmu06	DMU1	20	20	3042	vH2	3244	PSV	10000	PSV
dmu07	DMU1	20	20	2828	vH2	3046	PSV	360.58	PLC
dmu08	DMU1	20	20	3051	GL	3188	PSV	295.81	PLC
dmu09	DMU1	20	20	2956	GL	3092	H	500	H
dmu10	DMU1	20	20	2858	GL	2984	PSV	10000	PSV
dmu11	DMU1	30	15	3395	DMU	3430	PLC	1496.85	PLC
dmu12	DMU1	30	15	3481	DMU	3492	SS
dmu13	DMU1	30	15	3681	DMU	3681	GR	622.13	PLC
dmu14	DMU1	30	15	3394	DMU	3394	H	3.02	PLC
dmu15	DMU1	30	15	3343	GL	3343	H	1.77	PLC
dmu16	DMU1	30	20	3734	GL	3751	GR
dmu17	DMU1	30	20	3709	GL	3814	SS
dmu18	DMU1	30	20	3844	DMU	3844	GR	3787.4	PLC
dmu19	DMU1	30	20	3672	vH2	3765	SS
dmu20	DMU1	30	20	3604	DMU	3710	PLC	701.29	PLC
dmu21	DMU1	40	15	4380	DMU	4380	H	0.69	PLC
dmu22	DMU1	40	15	4725	DMU	4725	H	1.48	PLC
dmu23	DMU1	40	15	4668	DMU	4668	H	1.3	PLC
dmu24	DMU1	40	15	4648	DMU	4648	H	0.75	PLC
dmu25	DMU1	40	15	4164	DMU	4164	H	0.6	PLC
dmu26	DMU1	40	20	4647	DMU	4647	GR	1631.43	PLC
dmu27	DMU1	40	20	4848	DMU	4848	H	12.16	PLC
dmu28	DMU1	40	20	4692	DMU	4692	H	17.68	PLC
dmu29	DMU1	40	20	4691	DMU	4691	H	63.49	PLC
dmu30	DMU1	40	20	4732	DMU	4732	H	123	PLC
dmu31	DMU1	50	15	5640	DMU	5640	H	0.84	PLC
dmu32	DMU1	50	15	5927	DMU	5927	H	0.62	PLC
dmu33	DMU1	50	15	5728	DMU	5728	H	0.43	PLC
dmu34	DMU1	50	15	5385	DMU	5385	H	2.22	PLC
dmu35	DMU1	50	15	5635	DMU	5635	H	0.71	PLC
dmu36	DMU1	50	20	5621	DMU	5621	H	7.83	PLC
dmu37	DMU1	50	20	5851	DMU	5851	H	11.38	PLC
dmu38	DMU1	50	20	5713	DMU	5713	H	10.66	PLC
dmu39	DMU1	50	20	5747	DMU	5747	H	2.02	PLC
dmu40	DMU1	50	20	5577	DMU	5577	H	4.91	PLC
dmu41	DMU1	20	15	3007	GL	3248	PLC	417.84	PLC
dmu42	DMU1	20	15	3224	vH2	3390	PLC	448.95	PLC
dmu43	DMU1	20	15	3292	GL	3441	GR	399.33	PLC
dmu44	DMU1	20	15	3299	vH2	3475	SS
dmu45	DMU1	20	15	3039	vH2	3272	GR
dmu46	DMU1	20	20	3575	GL	4035	GR	984.86	PLC
dmu47	DMU1	20	20	3522	GL	3939	GR
dmu48	DMU1	20	20	3447	GL	3763	SS
dmu49	DMU1	20	20	3403	GL	3710	PLC	633.84	PLC
dmu50	DMU1	20	20	3496	GL	3729	PLC	609.62	PLC
dmu51	DMU1	30	15	3954	vH2	4156	SS
dmu52	DMU1	30	15	4094	vH2	4311	PLC	2232.6	PLC
dmu53	DMU1	30	15	4141	GL	4390	SS
dmu54	DMU1	30	15	4202	GL	4362	SS
dmu55	DMU1	30	15	4146	vH2	4270	SS
dmu56	DMU1	30	20	4554	GL	4941	PLC	3825.44	PLC
dmu57	DMU1	30	20	4302	GL	4663	PLC	3649.41	PLC
dmu58	DMU1	30	20	4319	GL	4708	PLC	3639.68	PLC
dmu59	DMU1	30	20	4219	vH2	4619	SS
dmu60	DMU1	30	20	4319	GL	4739	SS
dmu61	DMU1	40	15	4917	GL	5172	SS
dmu62	DMU1	40	15	5041	vH2	5251	SS
dmu63	DMU1	40	15	5111	GL	5323	SS
dmu64	DMU1	40	15	5130	DMU	5240	SS
dmu65	DMU1	40	15	5107	vH2	5190	SS
dmu66	DMU1	40	20	5397	vH2	5717	PLC	9543.86	PLC
dmu67	DMU1	40	20	5589	GL	5779	SS
dmu68	DMU1	40	20	5426	GL	5765	SS
dmu69	DMU1	40	20	5423	GL	5709	PLC	8107.63	PLC
dmu70	DMU1	40	20	5501	GL	5889	SS
dmu71	DMU1	50	15	6080	GL	6223	PLC	9835.11	PLC
dmu72	DMU1	50	15	6395	GL	6463	SS
dmu73	DMU1	50	15	6001	GL	6153	SS
dmu74	DMU1	50	15	6123	GL	6196	SS
dmu75	DMU1	50	15	6029	GL	6189	SS
dmu76	DMU1	50	20	6342	GL	6807	SS
dmu77	DMU1	50	20	6499	GL	6792	SS
dmu78	DMU1	50	20	6586	GL	6770	PLC	10346.61	PLC
dmu79	DMU1	50	20	6650	GL	6952	SS
dmu80	DMU1	50	20	6459	GL	6673	SS
ft06	FT	6	6	55	FTM	55	CP	0	AZ
ft10	FT	10	10	930	CP	930	CP	0.06	AZ
ft20	FT	20	5	1165	MF	1165	CP	0.18	PLC
la01	L	10	5	666	ABZ	666	AC	0	AZ
la02	L	10	5	655	ABZ	655	AC	0.015	AZ
la03	L	10	5	597	AC	597	AC	0.016	AZ
la04	L	10	5	590	AC	590	AC	0.015	AZ
la05	L	10	5	593	ABZ	593	AC	0	AZ
la06	L	15	5	926	ABZ	926	AC	0	AZ
la07	L	15	5	890	ABZ	890	AC	0	AZ
la08	L	15	5	863	ABZ	863	AC	0	AZ
la09	L	15	5	951	ABZ	951	AC	0	AZ
la10	L	15	5	958	ABZ	958	AC	0	AZ
la11	L	20	5	1222	ABZ	1222	AC	0	AZ
la12	L	20	5	1039	ABZ	1039	AC	0	AZ
la13	L	20	5	1150	ABZ	1150	AC	0	AZ
la14	L	20	5	1292	ABZ	1292	AC	0	AZ
la15	L	20	5	1207	ABZ	1207	AC	0.016	AZ
la16	L	10	10	945	CP1	945	AC	0.06	CCC
la17	L	10	10	784	CP1	784	AC	0.016	AZ
la18	L	10	10	848	AC	848	AC	0.015	AZ
la19	L	10	10	842	AC	842	AC	0.025	AZ
la20	L	10	10	902	AC	902	AC	0.031	AZ
la21	L	15	10	1046	VAL	1046	YN1	7.33	PLC
la22	L	15	10	927	AC	927	AC	0.109	AZ
la23	L	15	10	1032	ABZ	1032	AC	0.047	AZ
la24	L	15	10	935	AC	935	AC	0.2	AZ
la25	L	15	10	977	AC	977	AC	0.33	AZ
la26	L	20	10	1218	ABZ	1218	AC	0.078	AZ
la27	L	20	10	1235	ABZ	1235	YN1	0.95	AZ
la28	L	20	10	1216	ABZ	1216	AC	0.109	AZ
la29	L	20	10	1152	M	1152	H	1000	H
la30	L	20	10	1355	ABZ	1355	AC	0.093	AZ
la31	L	30	10	1784	ABZ	1784	AC	0	AZ
la32	L	30	10	1850	ABZ	1850	AC	0.047	AZ
la33	L	30	10	1719	ABZ	1719	AC	0.031	AZ
la34	L	30	10	1721	ABZ	1721	AC	0.156	AZ
la35	L	30	10	1888	ABZ	1888	AC	0.046	AZ
la36	L	15	15	1268	CP1	1268	AC	0.57	AZ
la37	L	15	15	1397	AC	1397	AC	0.51	AZ
la38	L	15	15	1196	VAL	1196	NS	1.25	AZ
la39	L	15	15	1233	AC	1233	AC	0.5	AZ
la40	L	15	15	1222	AC	1222	AC	384.8	PLC
orb01	AC	10	10	1059	AC	1059	AC	0.06	AZ
orb02	AC	10	10	888	AC	888	AC	0.06	AZ
orb03	AC	10	10	1005	AC	1005	AC	0.15	AZ
orb04	AC	10	10	1005	AC	1005	AC	0.1	CCC
orb05	AC	10	10	887	AC	887	AC	0.76	AZ
orb06	AC	10	10	1010	JM	1010	BV1	0.72	AZ
orb07	AC	10	10	397	JM	397	H	0.02	AZ
orb08	AC	10	10	899	JM	899	BV1	0.09	AZ
orb09	AC	10	10	934	JM	934	BV1	0.09	AZ
orb10	AC	10	10	944	JM	944	BV1	0.03	AZ
swv01	SWV	20	10	1407	M	1407	H	575.76	PLC
swv02	SWV	20	10	1475	M	1475	H	136.94	AZ
swv03	SWV	20	10	1398	BB	1398	H	613	PLC
swv04	SWV	20	10	1464	VLS	1464	VLS2	30000	VLS2
swv05	SWV	20	10	1424	M	1424	H	1000	H
swv06	SWV	20	15	1630	VLS	1671	PLC, VLS2	385.73	PLC
swv07	SWV	20	15	1513	VLS	1594	GR
swv08	SWV	20	15	1671	VLS	1752	PLC, VLS2	503	PLC
swv09	SWV	20	15	1633	VLS	1655	PLC, VLS2	521.91	PLC
swv10	SWV	20	15	1663	VLS	1743	GR	441.4	PLC
swv11	SWV	50	10	2983	V1	2983	NS2	940.68	PLC
swv12	SWV	50	10	2972	V1	2977	PLC	6097.35	PLC
swv13	SWV	50	10	3104	V1	3104	H	1000	H
swv14	SWV	50	10	2968	BV	2968	H	422.81	PLC
swv15	SWV	50	10	2885	V1	2885	PLC	6000.57	PLC
swv16	SWV	50	10	2924	SWV	2924	H	1000	H
swv17	SWV	50	10	2794	SWV	2794	H	1000	H
swv18	SWV	50	10	2852	SWV	2852	H	1000	H
swv19	SWV	50	10	2843	SWV	2843	H	1000	H
swv20	SWV	50	10	2823	SWV	2823	H	1000	H
ta01	T	15	15	1231	T	1231	H	2.93	PLC
ta02	T	15	15	1244	V	1244	NS	38.09	PLC
ta03	T	15	15	1218	BB	1218	H	43.66	PLC
ta04	T	15	15	1175	BB	1175	PM	38.72	PLC
ta05	T	15	15	1224	BB	1224	H	11.24	PLC
ta06	T	15	15	1238	BB	1238	H	178.06	PLC
ta07	T	15	15	1227	BB	1227	H	1000	H
ta08	T	15	15	1217	BB	1217	H	2.43	PLC
ta09	T	15	15	1274	BB	1274	H	18.66	PLC
ta10	T	15	15	1241	V	1241	H	42.25	PLC
ta11	T	20	15	1357	VLS	1357	BFW	186.19	PLC
ta12	T	20	15	1367	VLS	1367	H	206.06	PLC
ta13	T	20	15	1342	VLS	1342	H	161.37	PLC
ta14	T	20	15	1345	V	1345	NS	6	SS
ta15	T	20	15	1339	VLS	1339	PSV	173.45	PLC
ta16	T	20	15	1360	VLS	1360	H	63.41	PLC
ta17	T	20	15	1462	S	1462	H	1000	H
ta18	T	20	15	1377	VLS	1396	H	91.13	PLC
ta19	T	20	15	1332	VLS	1332	PSV	145.42	PLC
ta20	T	20	15	1348	VLS	1348	PSV	216.72	PLC
ta21	T	20	20	1642	VLS	1642	BFW	3600	BFW
ta22	T	20	20	1561	VLS	1600	H	228.9	PLC
ta23	T	20	20	1518	VLS	1557	H	359.79	PLC
ta24	T	20	20	1644	VLS	1644	VLS2	30000	VLS2
ta25	T	20	20	1558	VLS	1595	NS2	416.08	PLC
ta26	T	20	20	1591	VLS	1643	GR	30000	VLS2
ta27	T	20	20	1652	VLS	1680	H	254.74	PLC
ta28	T	20	20	1603	VLS	1603	PSV	1514	SS
ta29	T	20	20	1573	VLS	1625	H	93.53	PLC
ta30	T	20	20	1519	VLS	1584	H	388.66	PLC
ta31	T	30	15	1764	T	1764	H	6	SS
ta32	T	30	15	1774	T	1784	S2
ta33	T	30	15	1788	VLS	1791	PSV	457.55	PLC
ta34	T	30	15	1828	T	1829	H	315.71	PLC
ta35	T	30	15	2007	V	2007	PM	0.56	PLC
ta36	T	30	15	1819	V	1819	H	15	SS
ta37	T	30	15	1771	T	1771	GR	652.24	PLC
ta38	T	30	15	1673	T	1673	H	45	SS
ta39	T	30	15	1795	V	1795	H	6	SS
ta40	T	30	15	1651	VLS	1669	GR	30000	VLS2
ta41	T	30	20	1906	VLS	2005	VLS2	30000	VLS2
ta42	T	30	20	1884	VLS	1937	GR	30000	VLS2
ta43	T	30	20	1809	V	1846	PLC	1726.78	PLC
ta44	T	30	20	1948	VLS	1979	VLS2	30000	VLS2
ta45	T	30	20	1997	V	2000	H	1057.79	PLC
ta46	T	30	20	1957	VLS	2004	GR	30000	VLS2
ta47	T	30	20	1807	VLS	1889	PLC, VLS2	1030.88	PLC
ta48	T	30	20	1912	V	1937	SS	3008	SS
ta49	T	30	20	1931	VLS	1961	VLS2	30000	VLS2
ta50	T	30	20	1833	VLS	1923	PLC, VLS2	1318.05	PLC
ta51	T	50	15	2760	T	2760	PM	2000	H
ta52	T	50	15	2756	T	2756	PM	2000	H
ta53	T	50	15	2717	T	2717	PM	2000	H
ta54	T	50	15	2839	T	2839	PM	2000	H
ta55	T	50	15	2679	T	2679	NS	2000	H
ta56	T	50	15	2781	T	2781	PM	2000	H
ta57	T	50	15	2943	T	2943	PM	2000	H
ta58	T	50	15	2885	T	2885	PM	2000	H
ta59	T	50	15	2655	T	2655	PM	2000	H
ta60	T	50	15	2723	T	2723	PM	2000	H
ta61	T	50	20	2868	T	2868	NS	2000	H
ta62	T	50	20	2869	V	2869	C
ta63	T	50	20	2755	T	2755	NS	2000	H
ta64	T	50	20	2702	BV	2702	NS	2000	H
ta65	T	50	20	2725	T	2725	NS	2000	H
ta66	T	50	20	2845	T	2845	NS	2000	H
ta67	T	50	20	2825	V	2825	H	2000	H
ta68	T	50	20	2784	BV	2784	NS	2000	H
ta69	T	50	20	3071	T	3071	NS	2000	H
ta70	T	50	20	2995	T	2995	NS	2000	H
ta71	T	100	20	5464	T	5464	PM	2000	H
ta72	T	100	20	5181	T	5181	PM	2000	H
ta73	T	100	20	5568	T	5568	PM	2000	H
ta74	T	100	20	5339	T	5339	PM	2000	H
ta75	T	100	20	5392	T	5392	PM	2000	H
ta76	T	100	20	5342	T	5342	PM	2000	H
ta77	T	100	20	5436	T	5436	PM	2000	H
ta78	T	100	20	5394	T	5394	PM	2000	H
ta79	T	100	20	5358	T	5358	PM	2000	H
ta80	T	100	20	5183	T	5183	NS	2000	H
yn1	YN	20	20	884	KNF	884	ZSR	169.29	PLC
yn2	YN	20	20	870	BB	904	GR	202.22	PLC
yn3	YN	20	20	859	VLS	892	NS2	344.15	PLC
yn4	YN	20	20	929	VLS	968	H	320.51	PLC

Literature Sources¶

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

Development Setup¶

If you want to check out the code and implement new features or fix bugs, you can set up the project as follows:

Clone the Repository¶

clone the repository in your favorite code editor (for example PyCharm, VSCode, Neovim, etc.)

using https:

git clone https://github.com/Alexander-Nasuta/jsp-instance-utils

or by using the GitHub CLI:

gh repo clone Alexander-Nasuta/jsp-instance-utils

if you are using PyCharm, I recommend doing the following additional steps:

mark the src folder as source root (by right-clicking on the folder and selecting Mark Directory as -> Sources Root)
mark the tests folder as test root (by right-clicking on the folder and selecting Mark Directory as -> Test Sources Root)
mark the resources folder as resources root (by right-clicking on the folder and selecting Mark Directory as -> Resources Root)

Create a Virtual Environment (optional)¶

Most Developers use a virtual environment to manage the dependencies of their projects. I personally use conda for this purpose.

When using conda, you can create a new environment with the name ‘my-jsp-instance-utils’ following command:

conda create -n my-jsp-instance-utils python=3.11

Feel free to use any other name for the environment or a more recent version of python. Activate the environment with the following command:

conda activate my-jsp-instance-utils

Replace my-jsp-instance-utils with the name of your environment, if you used a different name.

You can also use venv or virtualenv to create a virtual environment. In that case please refer to the respective documentation.

Install the Dependencies¶

To install the dependencies for development purposes, run the following command:

pip install -r requirements_dev.txt
pip install tox

The testing package tox is not included in the requirements_dev.txt file, because it sometimes causes issues when using github actions. Github Actions uses an own tox environment (namely ‘tox-gh-actions’), which can cause conflicts with the tox environment on your local machine.

Reference: Automated Testing in Python with pytest, tox, and GitHub Actions.

Install the Project in Editable Mode¶

To install the project in editable mode, run the following command:

pip install -e .

This will install the project in editable mode, so you can make changes to the code and test them immediately.

Run the Tests¶

This project uses pytest for testing. To run the tests, run the following command:

pytest

For testing with tox run the following command:

tox

Tox will run the tests in a separate environment and will also check if the requirements are installed correctly.

Building and Publishing the Project to PyPi¶

In order to publish the project to PyPi, the project needs to be built and then uploaded to PyPi.

To build the project, run the following command:

python -m build

It is considered good practice use the tool twine for checking the build and uploading the project to PyPi. By default the build command creates a dist folder with the built project files. To check all the files in the dist folder, run the following command:

twine check dist/**

If the check is successful, you can upload the project to PyPi with the following command:

twine upload dist/**

Documentation¶

This project uses sphinx for generating the documentation. It also uses a lot of sphinx extensions to make the documentation more readable and interactive. For example the extension myst-parser is used to enable markdown support in the documentation (instead of the usual .rst-files). It also uses the sphinx-autobuild extension to automatically rebuild the documentation when changes are made. By running the following command, the documentation will be automatically built and served, when changes are made (make sure to run this command in the root directory of the project):

sphinx-autobuild ./docs/source/ ./docs/build/html/

This project features most of the extensions featured in this Tutorial: Document Your Scientific Project With Markdown, Sphinx, and Read the Docs | PyData Global 2021.

Contact¶

If you have any questions or feedback, feel free to contact me via email or open an issue on repository.

License¶

Distributed under the MIT License. See LICENSE.txt for more information.

Contents: