ВЫБОР РАЦИОНАЛЬНЫХ МАРШРУТОВ ПОТОКОВ ПРОДУКТОВ В ТЕХНОЛОГИЧЕСКОЙ СЕТИ

АННОТАЦИЯ

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

Ключевые слова: технологическая сеть; потоки продуктов; маршруты потоков; структура; многокритериальный выбор; сокращенный перебор; рациональные решения.

В статье рассматривается задача формирования оптимальной по принятым критериям структуры технологической сети. Задача может иметь смысл в технологических сетях, в которых связи между звеньями носят организационный характер, т.е. устанавливаются управленческим персоналом по различным соображениям, преимущественно направленным на сокращение различных видов затрат (например, на переналадку оборудования), безусловно, с учетом технологических ограничений. Как уже было ранее отмечено, в производствах дискретного типа нередки случаи, когда производственный процесс или его фрагмент может быть реализован с использованием различных технологических средств. Другими словами, для некоторых изделий партии сырья, исходных материалов, заготовок и других полупродуктов могут перемещаться в производстве по различным технологическим маршрутам.  Среди них, как правило, выделяется основной маршрут, остальные (альтернативные) считаются резервными и используются либо в случае сбоев на основном маршруте, либо для достижения тех или иных оперативных целей. В числе таких целей может быть повышение показателей эффективности производства, например, за счет лучшего использования оборудования, сокращения межоперационных запасов, сокращения эксплуатационных расходов. Включение резервных маршрутов в модели управления производственными процессами с целью повышения его устойчивости к возмущениям различного рода стало стандартом де-факто при использовании информационных систем производственного назначения классов MRP и ERP [1].

Если технологический план производства некоторого изделия включает n последовательно выполняемых операций, и каждая i-я операция может быть реализована s_i способами, то максимально возможное число теоретически допустимых вариантов маршрутов N_max равно произведению s₁×s₂...×s_n. При заданных параметрах потока и производительности звеньев (исполнителей) с помощью модели движения потока через сеть (см. [2]) могут быть рассчитаны показатели запасов в накопителях и уровни использования производственных возможностей звеньев. Введение и расчет на основе значений этих показателей соответствующих критериев позволит упорядочить варианты структур по предпочтительности и, следовательно, выбрать среди них наиболее предпочтительную структуру. Отметим также, что отношение предпочтительности может быть задано и на множестве возможных исполнителей каждой операции.

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

N – число потоков в составе многопродуктового потока;

S_(k) = {s_ki(k) } – множество альтернативных маршрутов для k-го потока, k = 1,…,N; i(k) = 1,…,n(k) (i(k) –  индекс маршрута для  k-го потока; n(k) – число допустимых маршрутов для k-го потока, n(k) > 0);

C_(q) – q-й вариант структуры сети, q = 1,…,q_max (формально представляет собой q-ю комбинацию из допустимых маршрутов каждого потока C_(q) = {s_1i(k),…,s_Ni(k)}, s_ki S_(k));

f(C_(q) ) = f_q = (f_q1,…,f_qK) – векторный критерий оценки q-го варианта структуры сети (K – число принятых критериев).

В укрупненном изложении алгоритм включает следующие шаги.

Шаг 1. Генерирование альтернативных маршрутов для каждого из потоков, образующих многопродуктовый поток (формирование множеств S_(k)).

Шаг 2. Генерирование комбинаций из альтернативных маршрутов для отдельных потоков (формирование множества вариантов структуры сети) с помощью циклической процедуры, последовательно включающей в очередную комбинацию «представителей» множеств S_(k)).

Шаг 3. Экспертный анализ и отбор по эвристическим соображениям из множества сгенерированных вариантов структуры сети подмножества более предпочтительных вариантов (при умеренной размерности задачи это действие может быть исключено, и могут быть проанализированы все сгенерированные варианты).

Для каждого из вариантов структуры путем прогона модели движения потоков через сеть (см. описание модели и алгоритма в [2]) устанавливаются значения принятых локальных критериев (f_q1,…,f_qK). В результате формируется матрица (расширенный вид матрицы см. табл. 1):

Таблица 1.

Варианты структуры сети и значения критериев

Шаг 4. Выбор наиболее предпочтительного варианта структуры сети. Возможные схемы организации выбора:

а) выбор формы интегрального критерия (примеры форм интегрального критерия, гарантирующих выбор Парето-оптимального решения: аддитивная, мультипликативная, минимаксная [3]); введение данных об относительной важности локальных критериев. Расчет значений принятого интегрального критерия для каждого из вариантов структуры. Выбор варианта по наилучшему значению интегрального критерия.

б) выделение в множестве сгенерированных вариантов структуры сети подмножества Парето-оптимальных вариантов (путем попарного сравнения и установления отношения доминирования). Экспертный анализ и выбор из этого подмножества наиболее предпочтительного варианта.

Остановимся подробнее на содержании шага 3 приведенного выше алгоритма. Отметим, что, общее число q_max комбинаций, формируемых из  представителей множеств допустимых маршрутов S_(k), составленных для каждого из потоков, равно

   K

q_max =  П n(k).

  k=1

В тех случаях, когда это число относительно невелико, может быть использован метод полного перебора (при этом следует исключить из рассмотрения комбинации, недопустимые по технологическим или организационным причинам). Для каждой комбинации выполняется прогон модели движения многопродуктового потока через сеть, в результате устанавливаются значения каждого из принятых критериев (например, возникающие размеры запасов продуктов в накопителях звеньев сети, уровни использования мощностей и др.), и осуществляется переход к шагу 4 алгоритма, завершающему поиск предпочтительного варианта структуры сети. Если же число комбинаций велико либо ресурсы (например, время, отведенное на решение задачи или имеющиеся вычислительные мощности) ограничены, может быть использован метод сокращенного перебора, дающий экономию ресурсов при поиске, но сопряженный с риском нахождения не самого предпочтительного варианта структуры. Сокращение перебора может быть достигнуто различными способами. Далее предлагается один из возможных приемов.

Предположим, что для каждого из продуктовых потоков, обрабатываемых в сети, сформировано множество допустимых маршрутов S_(k), k = 1,…,N. Предположим также, что маршруты, входящие в каждое из множеств S_(k),  упорядочены по убыванию предпочтительности и пронумерованы в соответствии с этим порядком. Предпочтительность того или иного маршрута для конкретного продукта по сравнению с другим возможным маршрутом может быть обусловлена различными факторами общего или локального характера: общей нормативной длительностью производственного цикла, ожидаемым уровнем качества выполнения отдельных операций, загрузкой отдельных технологических звеньев, квалификацией персонала на отдельных операциях и, возможно, другими факторами.

Простейшим правилом ранжирования комбинаций маршрутов является учет номеров мест, занимаемых конкретными маршрутами в ранжировках, составленных для каждого из потоков. При таком подходе более предпочтительными логично считать комбинации, имеющие меньшую сумму мест (рангов) входящих в них маршрутов. Значения этого показателя, очевидно, будут находиться в диапазоне от N (число потоков) до величины, равной сумме (n(1)+n(2)+…+n(N)). В первом случае комбинация составлена из наиболее предпочтительных вариантов маршрутов отдельных потоков; во втором случае – из наименее предпочтительных вариантов.

 Анализу и оценке по принятым критериям следует подвергнуть только комбинации, имеющие ранги, не превышающие значение R, выбранное из указанного диапазона по соображениям экономии ресурсов на поиск приемлемого варианта структуры сети. Такие комбинации, принятые к дальнейшему анализу, будем для краткости называть «рабочими».  Множество выделенных по этому принципу комбинаций отличается тем, что в них преобладает использование исполнителей, более предпочтительных для каждого потока.

Приведем пример. Пусть в технологической сети должны быть обработаны три потока продуктов (N=3). Для каждого потока составлены множества допустимых маршрутов S₍₁₎ = {s₁₁, s₁₂, s₁₃}, S₍₂₎ = {s₂₁, s₂₂, s₂₃},     S₍₃₎ = {s₃₁, s₃₂}. Внутри этих множеств маршруты пронумерованы в порядке убывания предпочтительности их использования. Все возможные комбинации маршрутов и их ранги приведены в таблице 2.

Как видно из приведенных данных, в этом примере  по методу полного перебора следует рассмотреть все 18 вариантов комбинаций маршрутов. Ранги этих маршрутов находятся в диапазоне [3;8]. В таблице 2 приведены количества комбинаций (вариантов структур сети), которые придется рассмотреть при выборе в качестве пороговых значений суммарного ранга R комбинаций различных чисел из диапазона [3;8] (для каждого значения порога количество просматриваемых комбинаций определяется как сумма комбинаций, соответствующих всем значениям порога, не превосходящим принятого значения).

Таблица 2.

Комбинации маршрутов (варианты структуры сети) и их ранги

Таблица 3.

Объем перебора вариантов структур сети при различных порогах суммарного ранга допустимых комбинаций

В наиболее вероятном случае, когда для каждого потока указаны два допустимых маршрута (основной и резервный), наряду с указанной процедурой может быть использована и иная процедура. Для этого случая введем следующие кодовые обозначения: выбор для потока основного маршрута обозначим «1», выбор резервного маршрута обозначим «0». В результате комбинация, соответствующая некоторому варианту структуры сети, будет представлена в виде N-разрядного двоичного вектора (кода). Наиболее предпочтительной логично считать структуру, в которой все потоки перемещаются по основным для себя маршрутам. Код такой структуры, очевидно, включает N единиц. Любой другой вариант структуры будет менее предпочтительным и будет содержать в своем коде от одного до N нулей. Близость кода произвольного варианта к наиболее предпочтительному варианту структуры можно оценить, рассчитав по некоторому правилу «расстояние» между кодовыми векторами двух вариантов. Удобной мерой такого расстояния является мера Хемминга, определяемая суммой несовпадающих по значению разрядов сравниваемых кодов [4]. Чем меньше по величине мера Хемминга, тем ближе вариант структуры к наиболее предпочтительному. В рассматриваемой задаче расстояние по Хеммингу рассчитывается по числу нулей в двоичном коде варианта, сравниваемого с кодом наиболее предпочтительного варианта (состоящего из N единиц). Указав предельное значение расстояния, можно установить окрестность наилучшего (по предпочтительности) варианта и сравнивать между собой по другим критериям только варианты, принадлежащие этой окрестности. В этом случае легко оценить количество вариантов, которые придется рассмотреть при выбранном максимальном значении расстояния Хемминга. При этом следует учесть, что в множестве N-разрядных двоичных векторов число векторов с нулями в m разрядах равно числу сочетаний из N по m, т.е. равно  С_N^m = N!/(m!(N – m)!). Если выбрано максимальное допустимое расстояние d от лучшего по предпочтительности варианта, то общее количество вариантов в его окрестности будет равным сумме

                                                                                 (1)

Приведем пример применения указанной процедуры.

Пусть число потоков в многомерном потоке, обрабатываемом в технологической сети, равно четырем (N = 4). Каждый из потоков может быть обработан с использованием одного из двух маршрутов – основного либо менее предпочтительного, резервного (m = 2). Всего вариантов структур сети, насчитывается 2^N = 2⁴ = 16. Наиболее предпочтительной будем считать структуру, образованную маршрутами, наиболее предпочтительными для отдельных потоков. Двоичный код такой структуры, как ранее было пояснено, имеет вид 4-разрядного двоичного кода с единицами в каждом разряде: (1111). В таблице 4 приведены коды всех комбинаций маршрутов потоков (структур сети) и их расстояния по Хеммингу от наиболее предпочтительной комбинации.

Таблица 4.

Двоичные коды вариантов структур сети и оценки их близости к наиболее предпочтительному варианту

Пользуясь формулой (1), определим количества вариантов, которые придется рассмотреть при выборе различных пороговых значений расстояния по Хеммингу. В таблице 5 приведены эти величины, а также номера вариантов, которые должны быть просмотрены при каждом выбранном значении d.

 Таблица 5.

Количество и перечни вариантов структур, просматриваемых при выборе различных порогов расстояния Хемминга

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

Список литературы:

1. Гаврилов Д.А. Управление производством на базе стандарта MRP II. – СПб.: Питер, 2003. – 352 с.
2. Платонов Д.Е. Модель преобразования потока работ в обрабатывающих звеньях технологических сетей / Д.Е. Платонов // Наука в ХХI веке: инновационный потенциал развития / Сборник научных статей по материалам X Международной научно-практической конференции. Ч.1 / Издательство НИЦ Вестник науки. – Уфа, 30.12.2022. – Номер: МНК-338. – С. 59-68.
3. Подиновский В.В., Ногин В.Д. Парето-оптимальные решения многокритериальных задач – М.: Наука, 1982. – 286 с.
4. https://helpiks.org/7-16055.html. Расстояние Хемминга