---

Впервые задача балансировки автоматизированной линии механической обработки (Transfer Line Balancing Problem, TLBP) была рассмотрена в работе [3]. По сравнению с хорошо известными задачами балансировки автоматической сборочной линии (Assembly Line Balancing Problems), в задаче TLBP учитывается много предположений, отражающих особенности используемого оборудования, такие как параметризованное время выполнения операции, нестрогие отношения предшествования и параллельное выполнение операций. Из-за этих особенностей применение к задаче TLBP известных методов, разработанных для задач балансировки автоматической сборочной линии, становится невозможным.  

Рассматривается автоматизированная линия механической обработки, состоящая из последовательно расположенных синхронно работающих рабочих станций, соединенных транспортным механизмом. В линиях этого типа каждая рабочая станция оборудована несколькими шпиндельными головками, причем каждая головка выполняет свой блок операций по механической обработке детали. Все операции блока выполняются одновременно. Параллельное выполнение операций возможно благодаря тому, что шпиндельные головки имеют несколько одновременно применяемых инструментов. Когда обработка на текущей станции окончена (все блоки операций, размещенные на этой станции, выполнены) деталь передвигается к следующей станции. Промежуток времени между переходом детали от одной станции к другой, называемый цикловым временем, не должен превышать заданного значения T₀. Задача заключается в том, чтобы назначить заданное множество операций на блоки и станции при заданных ограничениях на назначения.

Цель задачи состоит в том, чтобы сформировать автоматизированную линию, которая состоит из последовательности рабочих станций, между которыми нет буферных накопителей. Каждая машина оснащена шпиндельными головками, которые активируются последовательно заменой активной насадки или смещением детали к следующей головке. Переход к следующей рабочей станции линии происходит одновременно для всех деталей.

Для TLBP разработано несколько точных методов, основанных на частично целочисленном программировании и теории графов, а также эвристические алгоритмы, такие как FSIC и мульти-стартовый алгоритм декомпозиции, краткое описание этих методов содержится в [6]. Позднее в [2,7] предложены рандомизированный жадный алгоритм (GRASP) и генетический алгоритм решения этой задачи.

 Обозначения

Пусть N (i Î N)  – множество всех операций необходимых для обработки детали. Тогда решение TLBP может быть представлено набором подмножеств ,  определяющим назначение операций последовательности машин (k=1, 2, и разбиение операций, назначенных одной и той же станции k на n_k блоков.

Пусть N_k  - множество операций для станции k (k=1, 2, …, m) и N_kl – множество операций сгруппированных в один блок l ( l=1, 2, …, n_k) на станции k.

Далее, для простоты, “станцией” будем называть множество операций, назначенных на одну рабочую станцию, а “блоком” будем называть множество операций назначенных на одну шпиндельную головку.

Входными данными, описывающими множество операций, являются:

• Отношения предшествования между операциями. Согласно технологическому процессу на множестве операций установлен частичный порядок. Он может быть задан с помощью ориентированного графа G = (N, D). Дуга (i, j) Î N´N принадлежит множеству D, тогда и только тогда, когда операция j не может предшествовать операции i, то есть либо операция i выполняется перед операцией j, либо операции i и j выполняются одновременно на составном инструменте.

• Отношения включения определены для группы операций, которые должны быть назначены на одну и ту же машину по технологическим требованиям. Отношения включения задаются семейством ES подмножеств множества N, так что все операции одного подмножества e должны быть назначены на одну станцию. Никакие два множества семейства ES не могут содержать одну и ту же операцию, в противном случае такие множества должны быть объединены.

• Отношения исключения для станции представляют собой группу операций, которые не могут быть назначены на одну станцию по технологическим требованиям. Задаются семейством  подмножеств множества N, так что каждое подмножество e не может быть полностью назначено на одну и ту же установку.

• Отношения исключения для блоков определены на группе операций, которые не могут быть назначены на одну и ту же шпиндельную головку. Задаются семейством  подмножеств множества N, так что все операции каждого подмножества  не могут принадлежать одному блоку целиком.

Следующие входные данные определяют оборудование, используемое в конвейере:

t ^b — дополнительное время, необходимое для активации шпиндельной головки;;

t ^S — дополнительное время, необходимое для загрузки/разгрузки детали на станцию;

 C₁ — относительная стоимость одной станции;

C₂ — относительная стоимость одного блока;

n₀ — максимальное число блоков на станции;

Следующие входные данные задают ограничения, относящиеся ко всей линии:

m₀ — максимальное число станций. Наличие этого параметра сокращает число допустимых решений. Значение этого параметра определяется исходя из максимальных допустимых затрат или совпадает с верхней оценкой на число машин m. 

T₀ — максимально допустимое цикловое время. Для того, чтобы найти цикловое время какой-либо линии и проверить выполнение ограничений потребуются следующие вычисления:

1. Для каждой операции j заданы длина рабочего хода инструмента l_j и максимально допустимая глубина подачи инструмента в минуту s_j. Длина рабочего хода инструмента включает в себя глубины выполняемого разреза и расстояния между рабочим инструментом и поверхностью детали.

2. Время обработки блока t^b(N_kl)  определяется по формуле:

t ^b(N_kl) = max{l_j | j Î N_kl} / min{s_j | j Î N_kl } + t^b.

3. Т.к. блоки на одной станции активируются последовательно, то время обработки установки t^S(N_k) складывается из времен обработки блоков:

Представление TLBP в виде задачи частично целочисленного программирования может быть найдено в [4,6].

Обозначения, используемые в модели:

q — индекс для блока, например, для блока l станции k, q = (k – 1)n₀ + l;

q₀ — максимальное возможное значение q, q₀ = m₀n₀;

S(k) = {(k – 1)n₀ + 1, …, kn₀} — множество индексов блоков, выполняемых на станции k;

Q(j) — множество индексов блоков q, в которые назначена операция j;

K(j) — множество индексов станций k, в которые назначена операция j;

e — множество операций, являющееся элементом ES, или ;

j(e) — некоторая зафиксированная операция из множества  e.

t_j = l_j/s _j — время выполнения операции j, если она одна выполняется в блоке;

t_ij = max{l_i, l_j } / min{s_i, s_j}  — время выполнения двух операций i и j, если они выполняются в одном блоке; если величины s_j все одинаковые, то это значение не используется.

Переменные:

X_jq — бинарная переменная, принимает значение 1, если операция j назначена в блок q, иначе значение равно 0;

F_q ³ 0 — вспомогательная переменная для подсчета времени выполнения блока q;

Y_qÎ{0, 1} — вспомогательная бинарная переменная, принимает значение 1, если блок q существует, иначе значение равно 0;

Z_k Î{0, 1} — вспомогательная бинарная переменная, принимает значение 1, если станция k существует, иначе значение равно 0;

Переменные Y_q и Z_k необходимы для подсчета числа блоков и станций, соответственно.

В [5], проанализировав все ограничения, удалось установить диапазоны возможных значений чисел Q(j) и K(j) для каждой операции, это позволяет сократить число переменных и ограничений в модели.

Ниже приводится модель частично целочисленного программирования.

(1)

subject to:

	(2)
	(3)
	(4)
	(5)
	(6)
Fq ³ (ti + t b) Xiq,    iÎN,    qÎQ(i)	(7)
Fq ³ (tij + t b)(Xiq + Xjq  – 1),      i,j ÎN,    i < j,    qÎQ(i)Ç Q(j)	(7¢)
	(8)
Yq ³ Xjq,     jÎN,     qÎQ(j);	(9)
Zk ³ Yq,     k=1, 2,…, m0,     q = (k – 1)n0 + 1;	(10)
Yq-1 – Yq ³ 0,     qÎS(k)\{(k – 1)n0 + 1},     k = 1, 2,…, m0;	(11)
Zk–1 – Zk ³ 0,      k = 2, 3,…, m0;	(12)
Fq Î [0, T0 – t s – t b],     q = 1, 2,…, q0.	(13)

Выражение (1) представляет целевую функцию задачи. Ограничения предшествования задаются с помощью (2). Ограничения (3) гарантируют, что каждая операция должна быть назначена только в один блок. Условия  (4) определяют необходимость группировки соответствующих операций в одну станцию. Ограничения (5), (6) контролируют невозможность группировки соответствующих операций в один блок или выполнение определенных операций на одной станции, соответственно. Ограничения (7), (7¢) определяют время выполнения блока: неравенства (7) соответствуют случаю с одной операцией в блоке, неравенства (7¢) покрывают случаи с двумя и более операциями. Если все s_j одинаковы, то неравенства (7’) являются избыточными. Ограничения (8) определяют цикловое время. Условия (9) обеспечивают наличие блока q в решении, тогда и только тогда, когда
X_jq = 1 по крайней мере для одной операции j. Условия (10) обеспечивают наличие станции k в решении тогда и только тогда, когда Y_q = 1 по крайней мере для одного блока qÎS(k). Ограничения (11) гарантируют, что блок q обработан на станции k только, если блок (q – 1) существует для этой станции. Ограничения (12) обеспечивают использование станции k, только если в линии существует станция (k – 1). Неравенства (11) и (12) в этой модели введены главным образом как нарушающие симметрию отсечения, можно заметить, что простой модификацией условий (10) эти неравенства можно сделать избыточными. Граничные условия (13) так же введены с целью сокращения многогранника релаксированной задачи.

Модель запрограммирована в системе GAMS и содержится в файле file. Входные данные взяты из problem.gms и отформатированы согласно стандарту тестовых серий S1 – S7. Результаты сохранены в файл results.csv.

 

REFERENCES

[1] Baybars, I., 1986. A survey of exact algorithms for the simple assembly line balancing. Management Science 32, 909–932.

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

[3] Dolgui, A., Guschinsky, Levin, G., 2000. Approaches to balancing of transfer lines with blocks of parallel operations; Preprints No 8, Institute of Engineering Cybernetics of Academy of Sciences of Belarus/University of Technology of Troyes, 42p.

[4] Dolgui, A., Finel, B., Guschinsky, N., Levin, G. and Vernadat, F., 2006a. MIP approach to balancing transfer lines with blocks of parallel operations, IIE Transactions 38, 869–882.

[5] Dolgui, A., Guschinsky, N., Levin, G. , 2006b A special case of transfer lines balancing by graph approach, European Journal of Operational Research 168 (3), 732-746.

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

[7] Guschinskaya, O., Dolgui A., 2007. Balancing transfer lines with multiple-spindle machines using GRASP. Unpublished manuscript.