Benchmarks Library 
Transfer Line Balancing Problem
Benchmarks Library
|
|
Series S1 – S5 (Guschinskaya, Dolgui, 2006)
Each of the series S1–S5 contains 50 transfer line balancing problems. These data sets differ by two parameters: the number of operations |N| and the number of constraints (order strength OS of the precedence graph, number of subsets in families ES,
and
). Note: the order strength is defined as the number of edged in the transitive closure of the precedence graph divided by (|N| – 1)∙|N|/2 . Each instance was generated at random. The operation times are derived from the uniform distribution within [10, 20]. The precedence graph was generated at random by adding arcs between randomly chosen vertexes until desired order strength is obtained. The operations related by compatibility constraints were chosen at random but with the aim to avoid contradicting constraints and assure existence of a feasible solution. Other input parameters were set as follows: n0 = 4, t b = 0, t S = 0, T0 = 100, sj = 1 for all operations j, C1=10, and C2 = 2. The parameter m0 varied for the data sets with different numbers of operations.
Small size problems of series S1 and S2. The first data set contains 25-operation problems with OS = 0.5, m0 = 5. The second data set contains 25-operation problems with OS = 0.15, |ES| = 1, m0 =4. All of these problems are solved to optimality [3].
Series S1
Series S2
Problem
All tests in GAMS-format S1.zip 103 Kb
Optimum
Problem
All tests in GAMS-format S2.zip 99 Kb
Optimum
0
38
0
28
1
38
1
36
2
38
2
36
3
48
3
48
4
60
4
40
5
40
5
38
6
38
6
36
7
38
7
36
8
38
8
38
9
50
9
38
10
54
10
36
11
48
11
38
12
40
12
38
13
48
13
40
14
40
14
38
15
42
15
30
16
38
16
36
17
48
17
38
18
38
18
36
19
48
19
38
20
42
20
28
21
50
21
48
22
38
22
38
23
38
23
36
24
48
24
36
25
42
25
38
26
60
26
38
27
48
27
48
28
38
28
28
29
30
29
28
30
38
30
28
31
50
31
48
32
38
32
36
33
38
33
36
34
38
34
36
35
50
35
48
36
42
36
40
37
60
37
36
38
52
38
38
39
38
39
28
40
38
40
36
41
38
41
38
42
50
42
28
43
38
43
38
44
36
44
36
45
38
45
38
46
48
46
38
47
48
47
38
48
48
48
38
49
38
49
36
Medium size problems of series S3 and S4. The data set S3 contains 50-operation problems with OS = 0.9, m0 = 10. The data set S4 contains 50-operation problems with OS = 0.45, m0 = 15. All of these problems in S3 are solved to optimality [3] as well as some problems in S4, for the rest of the instances in S4 the heuristic solutions [1] provide the upper bounds.
Series S3
Series S4
Problem
All tests
in GAMS-format
S3.zip 144 KbOptimum
Problem
All tests
in GAMS-format S4.zip 163 KbOptimum
Upper Bound
0
112
0
76
76
1
114
1
102
2
100
2
68
3
124
3
74
4
118
4
76
76
5
82
5
66
6
106
6
78
7
94
7
74
8
88
8
76
9
102
9
74
74
10
110
10
86
11
82
11
68
68
12
100
12
76
76
13
92
13
78
14
78
14
76
15
100
15
66
66
16
100
16
78
78
17
88
17
96
18
104
18
76
76
19
102
19
78
78
20
92
20
76
76
21
88
21
66
66
22
100
22
74
74
23
102
23
64
24
104
24
76
25
104
25
78
78
26
80
26
64
64
27
102
27
62
28
96
28
74
74
29
112
29
76
30
112
30
76
76
31
82
31
54
32
104
32
74
74
33
112
33
62
34
100
34
76
76
35
112
35
76
76
36
106
36
76
76
37
102
37
66
66
38
116
38
102
39
108
39
76
40
92
40
86
86
41
114
41
76
76
42
108
42
68
43
114
43
74
74
44
106
44
64
64
45
90
45
64
64
46
100
46
76
47
112
47
86
48
76
48
74
74
49
110
49
98
98
Large size problems of series S5. The data set contains 100-operation problems with OS = 0.25, m0 = 15. The heuristic solutions [1] provide the upper bounds.
Series S5
Problem
All tests in GAMS-format
S5.zip 293 KbUpper bound
0
106
1
72
2
78
3
78
4
102
5
70
6
96
7
68
8
90
9
82
10
70
11
108
12
94
13
78
14
76
15
70
16
82
17
80
18
94
19
80
20
92
21
84
22
82
23
82
24
68
25
90
26
68
27
68
28
104
29
108
30
82
31
78
32
86
33
96
34
72
35
90
36
84
37
94
38
88
39
104
40
88
41
84
42
104
43
80
44
106
45
90
46
102
47
92
48
78
49
68
Series S6 – S7 (Guschinskaya, 2007)
Series S6 and S7 are also randomly generated but with more realistic data sets, compared to S1–S5. Both series S6 and S7 consist of 20 instances, here C1 = 1, C2 = 0.5, n0 = 4, t b = 0.2, t S = 0.4. The number of operations |N| for series S6 is from 46 to 92, and for series S7 it is from 94 to 125. The upper bounds m0 on the number of stations are from 23 to 46 in series S6 and from 43 to 62 in S7. The details on random generation of series S6, S7 can be found in [1].
The series S6 and S7 consist of realistic instances for two reasons. Firstly, they contain non-trivial input data for parameters with various sj. Secondly, in S6 and S7 the pseudo-random choice of operations was not performed independently and uniformly as in series S1–S5, but based on real-life data of typical shapes of the parts manufactured in mechanical transfer lines. The random choice is applied to the shape of parts, which further defines the parameters and mutual compatibility of operations. The heuristic solutions [1] provide the upper bounds.
|
Series S6 |
Series S7 |
||
|
Problem
All tests |
Upper bound |
Problem
All tests |
Upper bound |
|
0 |
28 |
0 |
40.5 |
|
1 |
32 |
1 |
67 |
|
2 |
47.5 |
2 |
50 |
|
3 |
46 |
3 |
58.5 |
|
4 |
27 |
4 |
50.5 |
|
5 |
34.5 |
5 |
50.5 |
|
6 |
38.5 |
6 |
44.5 |
|
7 |
27.5 |
7 |
46 |
|
8 |
26 |
8 |
35.5 |
|
9 |
42 |
9 |
66 |
|
10 |
36 |
10 |
38 |
|
11 |
45.5 |
11 |
36 |
|
12 |
45 |
12 |
50 |
|
13 |
38 |
13 |
47.5 |
|
14 |
38.5 |
14 |
38 |
|
15 |
29 |
15 |
45.5 |
|
16 |
43.5 |
16 |
49.5 |
|
17 |
43.5 |
17 |
39 |
|
18 |
44 |
18 |
43 |
|
19 |
31.5 |
19 |
55.5 |
Additional information given in the problem files
The intervals of possible values of block Q(j) and station K(j) numbers for each operation j are given in terms of their lower and upper bounds: a(j) is lower bound on block number of operation j, b(j) is the upper bound on block number of operation j, AA(j) is the lower bound on minimal station number of operation j, BB(j) is the upper bound on maximal station number of operation j. These bounds are obtained from the analysis of all the constraints [3].
[1] Dolgui, A., Eremeev A, Guschinskaya, 2008. O. MIP-based GRASP and Genetic algorithm for balancing transfer lines. Submitted to Proc. Matheuristics Workshop, June 16-18, 2008, Bertinoro, Italy., 22p.
[2] Guschinskaya, O., 2007. Outils d'aide a la decision pour la conception en avant-projet des systemes d'usinage a boitiers multibroches. PhD thesis, Saint-Etienne, France.
[3] Guschinskaya, O., Dolgui, A., 2006. A Comparative Evaluation of Exact and Heuristic Methods for Transfer Line Balancing Problem, in: Information Control Problems In Manufacturing 2006: A Proceedings volume from the 12th IFAC International Symposium, St Etienne, France, 17–19 May 2006, A. Dolgui, G. Morel, C. Pereira, eds., Elsevier Science, ISBN: 978-0-08-044654-7, Vol. 2, p. 395–400.
[4] Dolgui A., Finel, B., Guschinsky, N., Levin, G. and Vernadat, F., 2006b. MIP approach to balancing transfer lines with blocks of parallel operations, IIE Transactions 38, 869–882.