Job-shop scheduling with transportation

This web site contains files with test instances for scheduling a robot in a job-shop environment.

• J. Hurink, S. Knust: A tabu search algorithm for scheduling a single robot in a job-shop environment
  Discrete Applied Mathematics 119 (2002), 181-203.
• P. Brucker, S. Knust: Lower bounds for scheduling a single robot in a job-shop environment
  Annals of Operations Research 115 (2002), 147-172.
• J. Hurink, S. Knust: Tabu search algorithms for job-shop problems with a single transport robot
  European Journal of Operational Research 162 (2005), 99-111.

• Job-shop instances with a single robot, 6 jobs: Instances   Format of instances
• Job-shop instances with a single robot, 10 jobs: Instances   Format of instances

• Single machine instances for the robot for a fixed machine selection, 30 transport operations: Format of instances

  Problem	Sum tjkl	LB	UBpr	II	TS1	TS2	TS	CP2	IHT1	IHT2	IHT3	LP1	LP2	LP4	LP6
  P1_tjkl_t'kl.1	124	138	155	144	139	139	138	126	127	132	133	128	128	128	138
  P1_tjkl_t'kl.2	118	131	151	140	132	132	131	121	122	123	125	121	121	122	131
  P1_tjkl_t'kl.3	132	145	159	151	146	146	145	134	135	142	143	136	137	137	145
  P1_tjkl_t'kl.4	96	109	124	116	111	111	111	100	102	108	108	102	102	102	109
  P1_tjkl_t'kl.5	114	126	141	133	127	126	126	116	117	122	123	118	118	118	126
  P1_tjkl_t'kl.6	119	131	144	142	132	132	132	121	122	123	125	122	122	122	131
  P1_tjkl_t'kl.7	117	129	145	139	130	131	129	119	119	121	122	121	121	121	129
  P1_tjkl_t'kl.8	123	136	147	141	137	136	136	126	126	130	131	127	129	129	136
  P1_D1_d1	66	87	96	94	87	87	87	75	83	86	87	76	77	77	87
  P1_D1_t1	66	81	87	85	82	82	82	71	79	81	81	73	74	74	81
  P1_D2_d1	132	151	165	162	153	153	153	134	137	149	149	136	136	136	151
  P1_D2_d2	132	164	189	188	174	171	169	134	146	158	158	136	136	138	164
  P1_D2_t1	132	144	160	150	144	144	144	134	136	143	143	135	135	136	144
  P1_D2_t2	132	152	170	165	154	153	153	134	138	150	152	136	136	136	152
  P1_D3_d1	198	217	240	232	219	217	217	200	200	203	206	201	201	201	217
  P1_D3_d2	198	230	281	262	233	234	233	200	205	216	222	202	202	202	230
  P1_D3_d3	198	243	276	276	251	249	246	200	215	224	234	203	203	203	243
  P1_D3_t1	198	210	220	216	210	211	210	200	200	200	200	201	201	201	210
  P1_D3_t2	198	218	237	231	220	220	219	200	201	205	207	202	202	202	218
  P1_D3_t3	198	227	252	246	230	231	227	200	203	214	216	203	203	203	227
  P1_D5_d5	330	397	454	454	407	409	397	332	338	344	348	334	334	334	397
  P1_tkl_t'kl.1	121	141	147	144	144	143	143	123	131	137	138	125	127	128	141
  P1_tkl_t'kl.2	127	151	188	175	156	153	152	129	133	141	144	132	132	133	151
  P1_tkl_t'kl.3	114	130	156	141	133	133	132	116	117	120	121	117	118	119	130
  P1_T2_t2	60	81	97	87	82	83	82	67	76	79	80	68	68	73	81
  P1_T3_t1	90	102	111	109	102	102	102	92	93	97	98	94	95	96	102
  P1_T3_t2	90	110	122	122	110	112	110	92	96	105	107	95	96	96	110
  P1_T3_t3	90	117	149	137	120	118	117	92	102	112	113	95	96	96	117
  P1_T5_t2	150	168	182	174	168	168	168	152	152	154	156	154	154	155	168
  P1_T5_t5	150	188	218	218	190	192	190	152	160	170	175	155	155	155	188

•   Single machine instances for the robot for a fixed machine selection, 90 transport operations: Format of instances

  Problem	Sum tjkl	LB	UBpr	II	TS1	TS2	TS	CP2	IHT1	IHT2	IHT3
  P2_D2_d2	446	1002	1134	1061	1007	1007	1005	993	997	997	1002
  P2_D3_d1	669	1146	1283	1178	1149	1149	1149	1145	1146	1146	1146
  P2_D3_d2	669	1165	1363	1267	1180	1180	1176	1154	1165	1165	1165
  P2f0.1_D1_d1	223	288	413	377	346	347	336	262	277	287	288
  P2f0.2_D1_d1	223	334	435	414	377	374	370	313	336	336	334
  P2f0.5_D1_d1	223	573	624	596	577	577	577	571	573	573	573
  P2f0.2_tjkl_t'kl	302	343	412	400	377	375	374	339	341	343	343
  P2f0.2_tkl_t'kl	350	400	531	499	468	467	462	400	400	400	400
  P2f0.3_tjkl_t'kl.1	357	421	490	472	448	445	445	415	421	421	421
  P2f0.3_tjkl_t'kl.2	302	417	481	451	435	434	433	416	417	417	417

  Problem: the benchmark problem, Sum tjkl : the sum of all transportation times of the transport operations, LB: the best known lower bound for the problem, UBpr: the best objective value obtained by the priority-based heuristic, II: the objective value obtained by iterative improvement, TS1: the objective value obtained by a version of the tabu search algorithm with TLmin = 3,  TLmax = 16 and maxiter=500, TS2: the objective value obtained by a version of the tabu search algorithm with TLmin = 4,  TLmax = 14 and maxiter=1500, TS: the best objective value found by a version of the tabu search algorithm. CP2: the lower bound obtained by procedure Constraint_Propagation_2 IHT1, IHT2, IHT3: the lower bounds obtained by first applying Constraint_Propagation 2 and then the procedure Improve_Heads_Tails_i for i=1,2,3, respectively LPq: the lower bounds obtained by first applying the procedure Constraint_Propagation_2 and then the chain-packing bound procedure for a decomposition into subsets of q chains