-
Notifications
You must be signed in to change notification settings - Fork 4
/
Copy pathJobshopBenchmark instances2.txt
441 lines (381 loc) · 14.2 KB
/
JobshopBenchmark instances2.txt
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
This file contains procedures and data to create a set of 80 JSP test
instances proposed by
E. Taillard (1993),
Benchmarks for basic scheduling problems,
European Journal of Operational Research 64, 278-285.
Contributed by
Dirk C. Mattfeld (email [email protected]) and
Rob J.M. Vaessens (email [email protected]).
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
In order to obtain the 80 instances ta01-ta80 choose one of the three
different ways described below:
o Connect to Taillard's WWW home page directly. His address is:
http://www.idsia.ch/~eric/
The contents of files are self-explaining, although you may have to
convert them into a machine-readable format. Obtaining the data may
be a tedious work. You will find lower- and upper bounds for the
problems at Taillard's WWW page too.
o Write a PASCAL program using the procedures and seeds below. The procedures
are taken from the paper "Benchmarks for Basic Scheduling Problems" directly.
You have to add a main-procedure as well as a file-generation procedure
yourself.
************* procedures **************
function unif(var seed : integer; low, high : integer): integer;
(* generate a random number uniformly between low and high *)
const
m = 2147483647;
a = 16807;
b = 127773;
c = 2836;
var
k : integer;
value_0_1 : double; (* floating point coded on 64 bits *)
begin
k := seed div b ;
seed := a * (seed mod b) - k * c;
if seed < 0 then seed := seed + m ;
value_0_1 := seed / m ;
unif := low + trunc(value_0_1 * (high - low + 1))
end;
procedure generate_job_shop(var time_seed, machine_seed : integer;
nb_jobs, nb_machines : integer;
var d, M : matrix);
(* type matrix = array[1..20, 1..100] of integer; must be declared above *)
(* generate processing times d[i,j] and machines M[i, j] *)
(* of the ith operation of job j *)
var i, j : integer;
procedure swap(var a, b : integer);
var temp : integer;
begin
temp := a; a := b; b := temp
end;
begin
for j := 1 to nb_jobs do
for i := 1 to nb_machines do
d[i, j] := unif(time_seed, 1, 99);
for j := 1 to nb_jobs do
for i := 1 to nb_machines do
M[i, j] := i;
for j := 1 to nb_jobs do
for i := 1 to nb_machines do
swap(M[i, j], M[unif(machine_seed, i, nb_machines), j])
end;
********** data **********
Time seed, Machine seed, instance
15 jobs 15 machines
840612802 398197754 ta01
1314640371 386720536 ta02
1227221349 316176388 ta03
342269428 1806358582 ta04
1603221416 1501949241 ta05
1357584978 1734077082 ta06
44531661 1374316395 ta07
302545136 2092186050 ta08
1153780144 1393392374 ta09
73896786 1544979948 ta10
20 jobs 15 machines
533484900 317419073 ta11
1894307698 1474268163 ta12
874340513 509669280 ta13
1124986343 1209573668 ta14
1463788335 529048107 ta15
1056908795 25321885 ta16
195672285 1717580117 ta17
961965583 1353003786 ta18
1610169733 1734469503 ta19
532794656 998486810 ta20
20 jobs 20 machines
1035939303 773961798 ta21
5997802 1872541150 ta22
1357503601 722225039 ta23
806159563 1166962073 ta24
1902815253 1879990068 ta25
1503184031 1850351876 ta26
1032645967 99711329 ta27
229894219 1158117804 ta28
823349822 108033225 ta29
1297900341 489486403 ta30
30 jobs 15 machines
98640593 1981283465 ta31
1839268120 248890888 ta32
573875290 2081512253 ta33
1670898570 788294565 ta34
1118914567 1074349202 ta35
178750207 294279708 ta36
1549372605 596993084 ta37
798174738 151685779 ta38
553410952 1329272528 ta39
1661531649 1173386294 ta40
30 jobs 20 machines
1841414609 1357882888 ta41
2116959593 1546338557 ta4@
796392706 1230864158 ta43
532496463 254174057 ta44
2020525633 978943053 ta45
524444252 185526083 ta46
1569394691 487269855 ta47
1460267840 1631446539 ta48
198324822 1937476577 ta49
38071822 1541985579 ta50
50 jobs 15 machines
17271 718939 ta51
660481279 449650254 ta52
352229765 949737911 ta53
1197518780 166840558 ta54
1376020303 483922052 ta55
2106639239 955932362 ta56
1765352082 1209982549 ta57
1105092880 1349003108 ta58
907248070 919544535 ta59
2011630757 1845447001 ta60
50 jobs 20 machines
8493988 2738939 ta61
1991925010 709517751 ta62
342093237 786960785 ta63
1634043183 973178279 ta64
341706507 286513148 ta65
320167954 1411193018 ta66
1089696753 298068750 ta67
433032965 1589656152 ta68
615974477 331205412 ta69
236150141 592292984 ta70
100 jobs 20 machines
302034063 1203569070 ta71
1437643198 1692025209 ta72
1792475497 1039908559 ta73
1647273132 1012841433 ta74
696480901 1689682358 ta75
1785569423 1092647459 ta76
117806902 739059626 ta77
1639154709 1319962509 ta78
2007423389 749368241 ta79
682761130 262763021 ta80
********** verification **********
generate_job_shop(time_seed, machine_seed, 4, 4, d, M) should
provide, with time_seed = 1166510396 and machine_seed = 164000672
initially :
(d(i,j])= (M[i,j])=
54 9 38 95 3 4 1 1
34 15 19 34 1 1 2 3
61 89 28 7 4 2 3 2
2 70 87 29 2 3 4 4
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
o Use the C program below. It generates all 80 instance-files in one
run. The first line of each instance contains the number of jobs and
the number of machines. The remaining lines contain one job each,
listing the machine number and processing time for each step of the
job. You may choose whether the machine indices start with 0 or 1.
/*
Program to generate the 80 job shop instances proposed by
Taillard, E. D.: "Benchmarks for basic scheduling problems",
EJOR vol. 64, pp. 278-285, 1993
Originaly written by Taillard in PASCAL, re-written in C by
Dirk C. Mattfeld, University of Bremen <[email protected]> and
Rob J.M. Vaessens, Eindhoven University of Technology <[email protected]>.
Last update : 2/7/1996.
UNIX compile: cc -o jsp_gen jsp_gen.c -lm
Tested on the machines/systems/compilers listed below.
DEC 5000 Ultrix 4.2 cc
SUN 10 Solaris 2 cc
IBM 6000 AIX 3.x xlc
Atari ST TOS pure c
IBM-PC DOS 6.2 MS-C
IBM-PC Linux gcc
Care should be taken on 64 bit machines (e.g. Cray). There,
'long' and 'double' contain 128 bit. In this case replace all
'long' and 'double' with the appropriate 64 bit type.
Verification file 'ta01' (if VERIFY == 1 and FIRMACIND == 1)
4 4
3 54 1 34 4 61 2 2
4 9 1 15 2 89 3 70
1 38 2 19 3 28 4 87
1 95 3 34 2 7 4 29
*/
#define ANSI_C 0 /* 0: K&R function style convention */
#define VERIFY 0 /* 1: produce the verification file */
#define FIRMACIND 0 /* 0,1: first machine index */
#include <stdio.h>
#include <math.h>
struct problem {
long rand_time; /* random seed for jobs */
long rand_mach; /* random seed for mach */
short num_jobs; /* number of jobs */
short num_mach; /* number of machines */
};
#if VERIFY == 1
struct problem S[] = {
{ 0, 0, 0, 0},
{1166510396, 164000672, 4, 4},
{ 0, 0, 0, 0}};
#else /* VERIFY */
struct problem S[] = {
{ 0, 0, 0, 0}, /* 15 jobs 15 machines */
{ 840612802, 398197754, 15, 15 },
{ 1314640371, 386720536, 15, 15 },
{ 1227221349, 316176388, 15, 15 },
{ 342269428, 1806358582, 15, 15 },
{ 1603221416, 1501949241, 15, 15 },
{ 1357584978, 1734077082, 15, 15 },
{ 44531661, 1374316395, 15, 15 },
{ 302545136, 2092186050, 15, 15 },
{ 1153780144, 1393392374, 15, 15 },
{ 73896786, 1544979948, 15, 15 },
/* 20 jobs 15 machines */
{ 533484900, 317419073, 20, 15 },
{ 1894307698, 1474268163, 20, 15 },
{ 874340513, 509669280, 20, 15 },
{ 1124986343, 1209573668, 20, 15 },
{ 1463788335, 529048107, 20, 15 },
{ 1056908795, 25321885, 20, 15 },
{ 195672285, 1717580117, 20, 15 },
{ 961965583, 1353003786, 20, 15 },
{ 1610169733, 1734469503, 20, 15 },
{ 532794656, 998486810, 20, 15 },
/* 20 jobs 20 machines */
{ 1035939303, 773961798, 20, 20 },
{ 5997802, 1872541150, 20, 20 },
{ 1357503601, 722225039, 20, 20 },
{ 806159563, 1166962073, 20, 20 },
{ 1902815253, 1879990068, 20, 20 },
{ 1503184031, 1850351876, 20, 20 },
{ 1032645967, 99711329, 20, 20 },
{ 229894219, 1158117804, 20, 20 },
{ 823349822, 108033225, 20, 20 },
{ 1297900341, 489486403, 20, 20 },
/* 30 jobs 15 machines */
{ 98640593, 1981283465, 30, 15 },
{ 1839268120, 248890888, 30, 15 },
{ 573875290, 2081512253, 30, 15 },
{ 1670898570, 788294565, 30, 15 },
{ 1118914567, 1074349202, 30, 15 },
{ 178750207, 294279708, 30, 15 },
{ 1549372605, 596993084, 30, 15 },
{ 798174738, 151685779, 30, 15 },
{ 553410952, 1329272528, 30, 15 },
{ 1661531649, 1173386294, 30, 15 },
/* 30 jobs 20 machines */
{ 1841414609, 1357882888, 30, 20 },
{ 2116959593, 1546338557, 30, 20 },
{ 796392706, 1230864158, 30, 20 },
{ 532496463, 254174057, 30, 20 },
{ 2020525633, 978943053, 30, 20 },
{ 524444252, 185526083, 30, 20 },
{ 1569394691, 487269855, 30, 20 },
{ 1460267840, 1631446539, 30, 20 },
{ 198324822, 1937476577, 30, 20 },
{ 38071822, 1541985579, 30, 20 },
/* 50 jobs 15 machines */
{ 17271, 718939, 50, 15 },
{ 660481279, 449650254, 50, 15 },
{ 352229765, 949737911, 50, 15 },
{ 1197518780, 166840558, 50, 15 },
{ 1376020303, 483922052, 50, 15 },
{ 2106639239, 955932362, 50, 15 },
{ 1765352082, 1209982549, 50, 15 },
{ 1105092880, 1349003108, 50, 15 },
{ 907248070, 919544535, 50, 15 },
{ 2011630757, 1845447001, 50, 15 },
/* 50 jobs 20 machines */
{ 8493988, 2738939, 50, 20 },
{ 1991925010, 709517751, 50, 20 },
{ 342093237, 786960785, 50, 20 },
{ 1634043183, 973178279, 50, 20 },
{ 341706507, 286513148, 50, 20 },
{ 320167954, 1411193018, 50, 20 },
{ 1089696753, 298068750, 50, 20 },
{ 433032965, 1589656152, 50, 20 },
{ 615974477, 331205412, 50, 20 },
{ 236150141, 592292984, 50, 20 },
/* 100 jobs 20 machines */
{ 302034063, 1203569070, 100, 20 },
{ 1437643198, 1692025209, 100, 20 },
{ 1792475497, 1039908559, 100, 20 },
{ 1647273132, 1012841433, 100, 20 },
{ 696480901, 1689682358, 100, 20 },
{ 1785569423, 1092647459, 100, 20 },
{ 117806902, 739059626, 100, 20 },
{ 1639154709, 1319962509, 100, 20 },
{ 2007423389, 749368241, 100, 20 },
{ 682761130, 262763021, 100, 20 },
{ 0, 0, 0, 0 }};
#endif /* VERIFY */
/* generate a random number uniformly between low and high */
#if ANSI_C == 1
short unif (long *seed, short low, short high)
#else
short unif (seed, low, high)
long *seed; short low, high;
#endif
{
static long m = 2147483647, a = 16807, b = 127773, c = 2836;
double value_0_1;
long k = *seed / b;
*seed = a * (*seed % b) - k * c;
if(*seed < 0) *seed = *seed + m;
value_0_1 = *seed / (double) m;
return low + floor(value_0_1 * (high - low + 1));
}
/* Maximal 100 jobs and 20 machines are provided. */
/* For larger problems extend array sizes. */
short d[101][21]; /* duration */
short M[101][21]; /* machine */
#if ANSI_C == 1
void generate_job_shop(short p) /* Fill d and M according to S[p] */
#else
void generate_job_shop(p)
short p;
#endif
{
short i, j;
long time_seed = S[p].rand_time;
long machine_seed = S[p].rand_mach;
for(i = 0; i < S[p].num_jobs; ++i) /* determine a random duration */
for (j = 0; j < S[p].num_mach; ++j) /* for all operations */
d[i][j] = unif(&time_seed, 1, 99); /* 99 = max. duration of op. */
for(i = 0; i < S[p].num_jobs; ++i) /* determine a machine */
for (j = 0; j < S[p].num_mach; ++j) /* for all operations */
M[i][j] = j; /* assign the machine j */
for(i = 0; i < S[p].num_jobs; ++i) { /* for all jobs */
for (j = 0; j < S[p].num_mach; ++j) { /* for all machines*/
int k = unif(&machine_seed, j, S[p].num_mach-1); /* get rand index */
short t = M[i][j]; /* swap positions j and k */
M[i][j] = M[i][k];
M[i][k] = t;
}
}
}
#if ANSI_C == 1
void write_problem(short p) /* write out problem */
#else
void write_problem(p)
short p;
#endif
{
short i, j;
FILE *f = NULL;
char name[5];
sprintf(name,"ta%02d", p); /* file name construction */
if(!(f = fopen(name,"w"))) { /* open file for writing */
fprintf(stderr,"file %s error\n", name);
return;
}
fprintf(f,"%d %d\n", S[p].num_jobs, S[p].num_mach); /* write header line */
for(i = 0; i < S[p].num_jobs; ++i) {
for(j = 0; j < S[p].num_mach; ++j) {
fprintf(f,"%2d %2d ", M[i][j]+FIRMACIND, d[i][j]); /* write machine and job */
}
fprintf(f,"\n"); /* newline == End of job */
}
fclose(f); /* close file */
}
int main()
{
short i = 1;
while(S[i].rand_time) { /* for i == 1 up to NULL entry */
generate_job_shop(i); /* generate problem i */
write_problem(i); /* write out problem i */
++i; /* increment i */
}
return 0;
}
+++++++++++++++++++ EOF ++++++++++++++++++++++++++++++++++++