Benchmarks Library ballred.gif (861 bytes) Transfer Line Balancing Problem
line.jpg (1129 bytes)

Benchmarks

ballred.gif (861 bytes)  Transfer Line Balancing Problem 

ballred.gif (861 bytes)  Benchmarks

ballred.gif (861 bytes)  GAMS-model


Series S1 S5 (Guschinskaya, Dolgui, 2006)

Each of the series S1S5 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 = 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 Kb

Optimum

Problem

All tests
in GAMS-format S4.zip 163 Kb
 

Optimum

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 Kb

Upper 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 S1S5. Both series S6 and S7 consist of 20 instances, here C1 = 1, C2 = 0.5, n0 = 4, t= 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 S1S5, 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
in GAMS-format
S6.zip 319 Kb

Upper bound

Problem

All tests
in GAMS-format
S7.zip 628 Kb

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].

 

REFERENCES

[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, 1719 May 2006, A. Dolgui, G. Morel, C. Pereira, eds., Elsevier Science, ISBN: 978-0-08-044654-7, Vol. 2, p. 395400.

[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, 869882.