Soumen Atta1, Priya Ranjan Sinha Mahapatra1, Anirban Mukhopadhyay1,☆
1Department of Computer Science and Engineering, University of Kalyani, Kalyani-741235, West Bengal, India
☆Corresponding author: anirban@klyuniv.ac.in
The instances for the Tool Indexing Problem (TIP) mentioned in this page are adapted from the Single Row Facility Layout Problem (SRFLP) [1, 2] and the original instances of SRFLP can be found from http://www.miguelanjos.com/flplib. In the table shown below, the symbol 'x' in the 'Solution' column represents an empty slot.
Click here to download all the instances as single zip file
| Instance | No. of Tools | No. of Slots | Solution | Cost |
|
60 |
100 |
39 58 18 29 1 50 x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x 28 34 48 27 11 40 56 21 12 13 24 6 54 25 3 16 7 9 15 36 8 32 51 33 46 4 44 35 57 47 26 17 2 49 38 5 31 37 59 53 22 43 42 30 10 14 45 55 23 52 60 19 20 41 |
54053 |
|
|
60 |
100 |
x x x x x x x x x x x x x x x x x x x x x x x x x 53 28 10 19 44 29 40 46 41 50 34 15 30 24 14 9 21 32 5 33 36 37 18 25 56 45 17 52 22 31 2 4 42 8 47 49 48 58 38 16 23 39 51 59 57 54 43 6 27 55 7 1 13 12 3 26 35 11 20 60 x x x x x x x x x x x x x x x |
31274 |
|
|
60 |
100 |
x x x x x x 40 6 26 13 27 1 47 34 53 49 22 15 36 43 54 23 52 60 30 51 56 10 39 32 28 45 58 46 33 55 18 25 31 8 35 14 21 2 41 9 17 7 44 20 48 11 37 12 57 16 24 50 42 59 3 19 29 38 5 4 x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x |
23510 |
|
|
60 |
100 |
x x x x x x x x x x x x x x 20 19 31 22 57 36 39 10 7 55 50 24 23 44 56 33 6 4 40 5 53 27 45 59 48 3 14 17 21 15 58 37 2 35 11 60 42 29 30 26 16 52 18 47 28 1 34 49 54 38 8 25 32 41 9 46 51 43 12 x x x x x x x x x x x x x x 13 x x x x x x x x x x x x |
11592 |
|
|
60 |
100 |
x x x x x x x x 39 53 55 30 40 4 9 7 10 13 35 37 47 19 25 41 16 36 59 50 8 20 60 54 17 48 46 6 2 28 24 56 21 27 42 58 26 31 29 18 14 22 32 45 1 52 3 23 15 43 34 51 5 57 12 11 44 49 33 38 x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x |
15168 |
|
|
70 |
100 |
x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x 40 22 50 8 39 35 29 30 57 11 17 38 61 26 25 55 59 20 46 64 12 24 70 44 66 3 14 58 21 23 7 54 6 60 52 36 18 34 42 45 33 56 67 10 13 48 16 4 43 49 27 68 9 5 51 19 41 15 1 65 2 69 37 63 32 62 28 31 53 47 |
42296 |
|
|
70 |
100 |
27 61 66 48 31 16 65 69 59 38 62 10 53 47 52 41 57 x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x 21 39 28 56 45 64 50 36 19 63 13 58 26 49 3 67 1 4 18 25 30 9 23 29 7 8 11 33 44 6 60 43 70 46 55 2 5 14 40 20 32 42 24 51 54 17 35 34 15 22 12 68 37 |
51723 |
|
|
70 |
100 |
33 57 56 62 13 34 44 16 69 22 x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x 8 52 30 54 63 47 50 19 32 2 17 20 26 51 49 7 27 21 70 65 61 9 11 68 67 6 4 42 10 23 14 5 1 41 37 40 55 39 59 58 25 24 18 60 36 45 35 3 29 53 64 38 46 15 28 43 66 12 31 48 |
43794 |
|
|
70 |
100 |
33 22 64 29 58 18 5 54 52 14 34 9 60 43 15 12 26 49 67 7 6 30 51 46 63 25 16 66 x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x 41 35 8 38 13 37 4 19 3 65 45 31 39 59 47 20 32 55 1 36 23 69 44 21 48 40 17 27 56 28 50 70 57 10 53 62 2 68 11 61 42 24 |
27702 |
|
|
70 |
100 |
66 36 11 5 63 35 70 12 16 39 50 25 34 14 45 30 10 40 8 33 18 31 41 2 37 6 1 23 51 22 58 24 32 44 62 20 27 x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x 28 67 17 64 38 19 21 26 68 9 56 55 47 69 43 65 59 15 53 7 13 60 29 49 54 52 42 4 48 46 57 61 3 |
134238 |
|
|
75 |
100 |
32 70 45 4 75 31 43 68 13 21 66 53 17 34 19 3 24 12 71 37 55 7 62 22 8 74 42 26 15 18 27 35 41 56 65 30 25 44 11 57 40 28 72 50 23 49 48 14 6 61 20 36 46 60 2 64 x x x x x x x x x x x x x x x x x x x x x x x x x 67 9 58 38 69 47 29 33 16 59 63 52 5 54 39 73 51 1 10 |
66630 |
|
|
75 |
100 |
38 69 45 40 48 31 35 74 68 59 17 9 27 15 19 11 53 8 10 4 67 33 71 52 18 24 34 46 7 23 39 75 66 5 6 14 65 1 60 62 28 47 3 12 72 22 61 56 32 57 26 49 x x x x x x x x x x x x x x x x x x x x x x x x x 51 2 25 13 44 42 55 64 43 37 54 29 21 20 16 70 73 36 63 58 50 30 41 |
111806 |
|
|
75 |
100 |
34 16 31 73 27 18 2 49 52 66 72 6 8 70 25 32 29 46 13 1 53 14 51 50 71 63 43 69 47 15 42 x x x x x x x x x x x x x x x x x x x x x x x x x 10 22 68 17 20 33 36 19 23 54 4 64 41 26 5 60 35 61 40 65 74 57 21 55 45 62 38 28 56 11 7 24 30 9 75 58 67 59 12 44 37 3 48 39 |
38151 |
|
|
75 |
100 |
x x x x x x x x x x x x x x x x x x 36 9 66 21 6 23 61 69 17 26 38 72 73 49 2 68 74 43 32 45 25 51 18 11 54 59 4 1 58 71 13 24 19 63 34 67 28 44 35 53 46 20 40 12 29 39 30 65 31 64 3 55 16 33 47 75 41 22 57 42 50 70 52 48 37 62 7 5 15 27 14 10 56 60 8 x x x x x x x |
106341 |
|
|
75 |
100 |
74 29 1 16 53 59 48 18 15 11 69 70 14 10 66 45 21 62 61 67 36 57 33 54 60 26 12 13 24 27 x x x x x x x x x x x x x x x x x x x x x x x x x 22 17 43 52 20 37 31 63 9 75 50 19 8 2 72 38 58 64 40 6 65 51 56 41 4 30 3 55 39 23 32 49 5 73 71 44 47 28 7 25 46 35 42 68 34 |
47017 |
|
|
80 |
100 |
25 72 78 70 x x x x x x x x x x x x x x x x x x x x 55 60 80 65 16 34 14 29 12 67 2 21 68 46 44 49 62 19 17 27 56 40 54 61 39 43 63 20 45 41 47 51 52 75 32 10 13 58 66 48 9 23 76 24 53 6 5 33 42 15 36 73 22 35 8 59 74 37 69 26 50 38 31 3 71 1 30 64 57 7 4 11 77 28 18 79 |
54463 |
|
|
80 |
100 |
20 15 32 7 54 30 80 72 60 78 73 64 2 51 75 63 13 49 69 28 74 43 45 61 68 52 42 70 66 48 11 24 x x x x x x x x x x x x x x x x x x x x 57 18 17 22 77 55 46 10 29 33 5 26 23 40 12 58 44 41 53 14 47 62 50 27 9 56 79 37 38 6 1 4 39 25 67 34 3 35 71 59 8 21 65 36 16 76 19 31 |
52853 |
|
|
80 |
100 |
49 16 58 20 68 33 65 46 24 66 40 63 74 x x x x x x x x x x x x x x x x x x x x 57 54 61 29 53 34 21 13 36 71 70 39 69 50 35 8 52 3 22 27 32 30 48 72 56 76 64 44 17 77 25 80 23 51 78 10 14 11 7 67 55 9 19 15 41 59 1 4 12 31 73 2 79 38 28 26 60 75 62 6 5 47 45 18 42 43 37 |
95091 |
|
|
80 |
100 |
17 31 32 78 67 79 43 54 75 28 30 35 80 34 7 42 71 38 64 21 29 66 60 47 69 x x x x x x x x x x x x x x x x x x x x 41 56 44 61 59 50 24 48 40 58 49 22 57 51 37 55 36 10 5 52 26 20 13 39 68 45 63 73 19 11 65 23 33 53 1 25 8 70 77 74 3 27 72 2 15 12 16 18 62 14 9 4 6 76 46 |
100828 |
|
|
80 |
100 |
x x x x x x x x x x x x 26 53 17 58 60 2 52 27 68 74 38 6 73 21 61 10 47 34 79 1 54 33 70 76 30 37 28 9 49 75 22 71 31 36 55 24 67 15 44 66 80 32 19 43 65 4 62 20 8 18 14 72 50 45 77 3 63 16 23 78 57 5 51 56 29 35 64 42 69 40 13 59 39 12 41 7 11 46 25 48 x x x x x x x x |
36217 |
|
|
36 |
60 |
7 1 4 5 13 12 11 6 20 14 27 23 28 19 29 30 32 34 33 31 21 22 26 25 24 x x x 36 x x x x x x x x x x x x 35 x x x x x x x x x 16 17 2 18 3 15 9 8 10 |
10289 |
|
|
42 |
60 |
25 29 11 7 5 17 34 42 12 27 20 10 13 31 19 32 18 26 35 9 15 14 40 4 2 30 39 33 21 28 38 37 1 24 3 36 22 23 16 8 6 x x x x x x x x x x x x x x x x x x 41 |
24406 |
|
|
49 |
60 |
19 36 47 25 28 42 13 7 46 35 41 14 20 18 29 1 9 15 10 34 12 11 45 38 43 6 37 27 2 40 48 3 23 31 49 33 22 44 5 8 16 39 30 21 32 17 x x x x x x x x x x x 24 26 4 |
36538 |
|
|
56 |
60 |
5 44 29 7 52 36 51 32 14 28 23 49 11 30 3 42 9 33 50 56 8 24 55 38 22 53 54 25 16 21 6 19 2 x x x x 26 43 45 46 4 15 31 12 27 17 20 39 34 37 48 1 47 18 35 10 40 13 41 |
52703 |
|
|
64 |
100 |
x x x 57 31 53 10 9 42 25 19 8 2 63 58 26 50 37 35 17 44 1 56 33 45 64 13 49 21 59 7 16 4 22 24 62 23 52 14 29 20 55 38 51 47 6 18 39 5 48 40 60 30 43 28 46 32 11 54 34 12 36 27 41 3 61 15 x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x |
95191 |
|
|
72 |
100 |
46 49 33 50 13 37 63 32 39 16 6 71 44 57 55 9 51 42 40 48 36 41 68 15 19 58 66 69 25 20 4 72 62 43 3 5 45 24 34 11 54 x x x x x x x x x x x x x x x x x x x x x x x x x x x x 12 56 53 29 31 18 8 35 64 60 27 67 10 2 21 26 17 70 28 14 22 47 65 30 52 23 61 1 7 38 59 |
132613 |
|
|
81 |
100 |
55 11 42 22 57 78 45 52 44 62 1 5 32 13 68 58 27 43 73 72 8 75 18 59 71 10 53 24 28 29 46 64 2 79 16 54 20 26 51 12 63 37 76 34 80 77 60 40 47 25 x x x x x x x x x x x x x x x x x x x 30 4 65 69 67 23 33 74 3 66 56 61 38 49 21 41 50 48 17 6 9 19 81 14 31 7 15 36 39 35 70 |
183934 |
|
|
100 |
100 |
35 7 99 3 46 23 29 61 12 45 10 26 40 90 51 69 47 100 70 58 72 66 73 60 67 21 50 42 8 59 98 87 68 86 19 62 32 52 94 22 1 39 83 33 88 16 13 15 71 37 65 96 11 43 49 25 77 79 6 34 75 74 54 31 9 89 84 63 5 14 80 27 95 55 78 57 91 18 28 2 30 97 85 24 93 20 82 81 4 36 44 76 64 17 53 56 92 48 41 38 |
289069 |
|
|
5 |
5 |
1 3 2 4 5 |
124 |
|
|
5 |
10 |
5 1 4 x x x x x 2 3 |
150 |
|
|
6 |
10 |
2 x x x x 1 6 5 4 3 |
292 |
|
|
7 |
10 |
4 1 6 5 7 3 2 x x x |
468 |
|
|
8 |
10 |
2 6 x x 1 7 3 5 4 8 |
724 |
|
|
9 |
10 |
1 3 8 7 4 2 9 5 x 6 |
866 |
|
|
10 |
10 |
9 5 4 1 6 3 2 8 10 7 |
1132 |
|
|
10 |
12 |
7 8 2 10 3 4 6 1 5 x x 9 |
1272 |
|
|
10 |
15 |
9 7 8 2 10 3 4 6 1 5 x x x x x |
1378 |
|
|
10 |
20 |
x x x x x x 1 6 5 4 3 10 2 8 7 9 x x x x |
1402 |
|
|
10 |
25 |
x x x x x x x 1 6 5 4 3 10 2 8 7 9 x x x x x x x x |
1402 |
|
|
10 |
30 |
x x x x x x x x x x x x x x x x x x 1 6 5 4 3 10 2 8 7 9 x x |
1402 |
|
|
15 |
20 |
6 4 7 8 14 9 11 12 13 2 15 10 3 x x x x x 1 5 |
4818 |
|
|
15 |
30 |
x x x 5 1 4 6 7 8 14 9 11 12 13 2 10 15 3 x x x x x x x x x x x x |
5134 |
|
|
20 |
30 |
x x 4 12 1 11 16 5 18 15 6 20 19 13 9 14 8 7 3 17 2 10 x x x x x x x x |
12600 |
|
|
12 |
20 |
x x x x x x x x 2 9 1 3 5 12 4 6 10 7 11 8 |
4409 |
|
|
13 |
20 |
3 1 8 x x x x x x x 11 7 6 10 5 4 13 2 9 12 |
5781 |
|
|
13 |
30 |
x x x x 8 1 3 12 9 2 13 4 5 10 6 7 11 x x x x x x x x x x x x x |
5897 |
|
|
14 |
20 |
5 13 2 9 3 1 8 x x x x x x 11 7 10 6 14 12 4 |
7027 |
|
|
15 |
20 |
12 14 6 7 11 10 x x x x x 8 15 2 3 1 9 13 5 4 |
8377 |
|
|
16 |
20 |
x x x 11 10 7 14 6 12 16 4 5 1 3 9 2 13 15 8 x |
10044 |
|
|
17 |
20 |
4 5 13 9 2 15 1 3 8 x x x 12 16 10 6 14 11 7 17 |
11567 |
|
|
18 |
20 |
11 7 17 4 13 5 2 9 15 1 3 18 8 12 16 x x 10 6 14 |
13208 |
|
|
19 |
20 |
13 4 19 2 15 9 1 3 8 18 12 16 x 5 6 10 14 7 11 17 |
15000 |
|
|
20 |
30 |
1 3 15 2 9 18 12 20 16 10 13 4 17 5 6 14 7 11 x x x x x x x x x x 8 19 |
21234 |
|
|
21 |
30 |
x x x x x x x x x 21 8 19 1 3 15 2 9 18 20 12 16 10 4 13 17 5 6 14 7 11 |
23896 |
|
|
22 |
30 |
7 22 11 x x x x x x x x 21 8 19 1 3 18 9 2 15 20 16 12 5 4 13 10 14 6 17 |
27021 |
|
|
23 |
30 |
11 x x x x x x x 19 8 21 1 18 20 9 2 15 3 16 12 23 5 13 4 6 14 10 17 7 22 |
30613 |
|
|
24 |
30 |
x x 8 21 1 18 20 9 2 15 3 5 13 23 16 12 4 6 14 10 17 22 7 24 11 19 x x x x |
34004 |
|
|
25 |
30 |
8 1 19 3 5 25 16 12 23 24 6 14 4 10 7 22 17 13 11 x x x x x 20 15 2 9 21 18 |
37444 |
|
|
6 |
6 |
6 4 5 1 3 2 |
1063 |
|
|
6 |
10 |
5 1 4 3 2 6 x x x x |
1372 |
|
|
7 |
10 |
x x 4 5 6 2 3 7 1 x |
1733 |
|
|
8 |
10 |
2 7 6 8 5 1 x x 4 3 |
2088 |
|
|
9 |
10 |
5 6 8 2 3 9 4 1 x 7 |
2432 |
|
|
10 |
10 |
5 1 2 10 6 9 4 3 8 7 |
2711 |
|
|
10 |
20 |
x x x x x 9 6 3 8 4 7 10 2 5 1 x x x x x |
3508 |
|
|
11 |
11 |
2 4 6 8 9 7 5 10 11 1 3 |
3083 |
|
|
11 |
12 |
7 5 10 11 1 3 x 2 4 6 8 9 |
3350 |
|
|
11 |
20 |
x x x x x x x x x 3 1 11 10 5 7 9 8 2 4 6 |
4022 |
|
|
12 |
12 |
11 4 1 3 8 2 7 10 6 5 12 9 |
3677 |
|
|
12 |
20 |
11 1 4 12 x x x x x x x x 7 2 10 6 8 5 9 3 |
4765 |
|
|
13 |
13 |
4 12 2 13 1 10 6 11 8 5 7 9 3 |
4196 |
|
|
13 |
20 |
12 2 10 11 13 1 6 x x x x x x x 7 3 9 5 4 8 |
5367 |
|
|
14 |
14 |
10 11 13 4 8 1 2 14 12 6 7 3 9 5 |
4296 |
|
|
14 |
20 |
4 10 11 5 9 3 7 13 2 6 1 14 12 x x x x x x 8 |
6179 |
|
|
15 |
20 |
7 9 13 x x x x x 6 4 10 11 12 8 5 3 2 14 1 15 |
6884 |
|
|
15 |
30 |
x x x x x x x x x x x x x 13 9 7 15 1 14 2 3 5 12 11 10 8 6 4 x x |
7359 |
|
|
20 |
30 |
x x x 6 16 1 9 10 13 5 14 3 17 15 19 20 2 12 18 11 7 4 8 x x x x x x x |
11885 |
|
|
25 |
30 |
1 23 12 6 24 7 10 25 11 5 3 9 15 14 21 13 4 x x x x x 2 18 19 17 22 20 16 8 |
18011 |
|
|
30 |
60 |
x x x x x x x x x 29 11 21 4 24 17 13 23 8 9 14 6 30 20 27 16 12 3 25 26 22 1 19 10 2 7 5 18 15 28 x x x x x x x x x x x x x x x x x x x x x |
27673 |
|
|
35 |
60 |
x x x x x x x x x x x x x x x x x x x x 1 7 35 5 29 28 8 33 10 11 3 20 32 22 26 6 2 9 18 17 23 15 27 14 25 12 30 4 19 34 16 31 21 13 24 x x x x x |
38014 |
|
|
40 |
60 |
21 30 15 34 x x x x x x x x x x x x x x x x x x x x 26 13 25 10 31 17 27 11 1 38 2 14 22 18 6 7 28 3 24 9 12 39 20 32 4 40 33 5 8 29 19 16 35 37 36 23 |
46333 |
|
|
45 |
60 |
19 44 41 25 27 20 x x x x x x x x x x x x x x x 12 16 34 36 35 2 8 29 39 18 5 3 4 6 45 1 26 14 33 43 42 9 22 13 37 23 32 30 10 28 15 7 40 31 24 38 11 17 21 |
58815 |
|
|
50 |
60 |
32 12 24 8 26 7 28 42 47 1 23 37 48 25 45 14 17 5 11 13 39 36 46 43 6 15 31 10 18 44 9 40 2 41 16 21 29 50 3 33 22 34 27 49 38 19 20 4 30 x x x x x x x x x x 35 |
73329 |
|
|
60 |
100 |
x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x 25 43 15 14 36 45 2 37 7 28 9 32 22 4 42 57 60 21 55 11 1 5 40 39 41 8 44 19 17 30 46 31 52 48 47 20 23 10 12 6 58 29 24 27 13 18 26 35 16 51 3 38 33 34 59 49 56 54 50 53 x x x x x x x x x |
111219 |
References:
[1] M. F. Anjos, A. Kennings, A. Vannelli, A semidefinite optimization ap
proach for the single-row layout problem with unequal dimensions, Discrete
Optimization 2 (2) (2005) 113–122.
[2] M. F. Anjos, G. Yen, Provably near-optimal solutions for very large single
row facility layout problems, Optimization Methods & Software 24 (4-5)
(2009) 805–817.
This page was created on April 1, 2017.