Series S1 – S5 (Guschinskaya, Dolgui, 2006)

Каждая серия S1 – S5 состоит из 50 задач балансировки автоматизированной линии механической обработки. Исходные данные отличаются по двум параметрам: числу операций необходимых для обработки детали |N| и числу ограничений, которое определяется порядком графа отношений предшествования между операциями, числом подмножеств в семействах ES,  и . Порядок графа – это число ребер в транзитивном замыкании графа отношений предшествования, деленное на (|N| – 1) ∙ |N|/2  (Scholl and Klein, 1998). Каждый пример сгенерирован датчиком случайных чисел. Времена обработки – это случайные величины с равномерным распределением на отрезке [10, 20]. Граф отношений предшествования генерируется следующим образом. В граф добавляются дуги между случайно выбранной парой вершин до тех пор, пока заданный порядок графа не будет достигнут. Отношения совместимости задаются случайным образом, но так, чтобы не противоречить друг другу и гарантировать существование допустимого решения. Остальные параметры: n₀ = 4, t ^b = 0, t ^S = 0, T₀ = 100, s_j = 1 для всех j, C₁ = 10, и C₂ = 2. Число m₀ меняется для каждой серии примеров.

Задачи небольшой размерности, серии S1 и S2. Число операций |N|=25.

В серии S1: OS = 0.5, m₀ = 5. В серии S2: OS = 0.15, |ES| = 1, m₀ =4. Для всех задач найдено оптимальное решение (Guschinskaya, Dolgui, 2006).[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

 

Задачи средней размерности, серии S3 и S4. Число операций |N|=50.

В серии S3: OS= 0.9, m₀ = 10. В серии S4: OS= 0.45, m₀ = 15. Для всех задач серии S3 оптимальное решение найдено (Guschinskaya, Dolgui, 2006 [3]). Для некоторых задач серии S4 оптимальное решение найдено, для остальных задач из S4 эвристическими алгоритмами найдена верхняя оценка (Dolgui, Eremeev, Guschinskaya 2008 [1]).

 

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

 

Задачи большой размерности, серия S5. Число операций |N|=100.

OS = 0.25, m₀ = 15. В таблицах приводятся верхние оценки, полученные эвристическим алгоритмом (Dolgui, Eremeev, Guschinskaya 2008 [1]).

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

 

Серии S6-S7 (Guschinskaya, 2007)

Для тестов серии S6 и S7 данные генерировались случайным образом, но ближе к реальным исходным данным, чем в задачах серий S1-S5. Тесты серий S6 и S7 содержат 20 задач с C₁ = 1, C₂ = 0.5, n₀ = 4, t ^b = 0.2, t ^S = 0.4. Число операций |N| для тестов серии S6 варьируется от 46 до 92, для серий S7 от 94 до 125. Максимальное число станций m₀ в серии S6 меняется от 23 to 46, в серии S7 от 43 до 62. Более детальное описание генерации этих тестовых примеров можно найти в работе Guschinskaya, 2008.

Дополнительная информация приводится в прикрепленных файлах.

Для числа блоков Q(j) и числа станций K(j) для каждой операции j заданы интервалы: a(j) – нижняя оценка, b(j) – верхняя оценка на число блоков для операции j; AA(j) – нижняя оценка на минимальное число станций, BB(j) – верхняя оценка на максимальное число станций для операции j. Эти оценки получены проанализировав все ограничения (Dolgui и др., 2006).

 

ЛИТЕРАТУРА

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