Автоматика и телемеханика, № 5, 2020

(Высшая национальная школа горного дела и телекоммуникаций Бретани

и земель Луары ИМТ Атлантик, Нант),

Г.М. ЛЕВИН, д-р техн. наук (levin@newman.bas-net.by),

Б.М. РОЗИН, канд. техн. наук (rozin@newman.bas-net.by),

(Объединенный институт проблем информатики НАН Беларуси, Минск)

СТРУКТУРНО-ПАРАМЕТРИЧЕСКАЯ ОПТИМИЗАЦИЯ КОМПЛЕКСА

ПЕРЕСЕКАЮЩИХСЯ МНОЖЕСТВ ОПЕРАЦИЙ

В УСЛОВИЯХ НЕСТАЦИОНАРНОГО СПРОСА¹

Рассматривается задача оптимизации агрегирования операций, про-

граммы выпуска и интенсивностей выполнения операций при групповой

серийной обработке заданного семейства продуктов на многопозиционной

реконфигурируемой производственной системе в заданных (временных)

интервалах при нестационарном детерминированном спросе. Допускает-

ся отложенный спрос. Агрегирование операций неизменно на весь период

планирования, состав группы и интенсивности выполнения операций об-

работки неизменны в пределах интервала, но могут меняться от интер-

вала к интервалу.

В качестве целевой функции используется планируемая прибыль. Ин-

вестиционные затраты определяются вариантом агрегирования. Матери-

альные и временные затраты на выпуск группы продуктов в каждом ин-

тервале зависят от агрегирования операций, интенсивностей их выполне-

ния и затрат на реконфигурацию оборудования. Логистические затраты

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

добавленную стоимость и штрафы за неудовлетворенный спрос.

Предложен трехуровневый декомпозиционный метод решения задачи.

Ключевые слова: производственная система, группа продуктов, агрегиро-

вание операций, интенсивность обработки, нестационарный спрос, макси-

мизация прибыли, декомпозиционный метод.

DOI: 10.31857/S0005231020050037

1. Введение

Задачам планирования процессов выполнения комплексов операций в си-

стемах различного назначения в последние десятилетия уделялось значитель-

ное внимание [1-9]. В ряде публикаций (в том числе в работах [7-9] авторов

настоящей статьи) предлагаются модели и методы решения ряда задач, свя-

занных с оптимизацией управления интенсивностью выполнения комплекса

взаимосвязанных операций в предположении, что структура этого комплек-

са, а также структура реализующей его системы уже определены.

Вместе с тем значительный научный и практический интерес представляет

также разработка моделей и методов решения более сложных задач совмест-

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

¹ Авторы благодарны региональному правительству Земель Луары (Франция) за фи-

нансовую поддержку этого проекта.

производственных системах групповой обработки продуктов, так и програм-

мы выпуска семейства продуктов наряду с интенсивностями выполнения опе-

раций комплекса. Под ¾операцией¿ понимается набор взаимосвязанных ша-

гов обработки, рассматриваемый как неделимое действие, выполняемое на

одной рабочей станции системы посредством общего исполнительного органа.

Под интенсивностью операции подразумевается некоторый параметр, опре-

деляющий время выполнения единицы ее объема.

В данной статье исследуется одна из ситуаций, когда структура комплекса

определяется выбираемым вариантом агрегирования его операций в непересе-

кающиеся группы (блоки операций), каждая из которых выполняется посред-

ством своего исполнительного органа системы, причем все операции одного

блока в любой момент времени выполняются с одной и той же интенсивно-

стью. Объединение операций в блоки, как правило, способствует снижению

инвестиционных затрат на производственную систему и на ее обслуживание,

но одновременно приводит к возрастанию текущих эксплуатационных мате-

риальных и временных затрат на выполнение каждой из операций комплек-

са в отдельности. Последнее объясняется тем, что объединение операций в

блоки исключает возможность индивидуального выбора для каждой из них

наилучших (с точки зрения текущих затрат) интенсивностей их выполнения.

Динамически изменяющиеся потребности рынка диктуют необходимость

модификации от одного (временного) интервала к другому состава группы

выпускаемых продуктов посредством реконфигурации системы.

Классификации задач планирования производства партий продуктов с

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

[10, 11] и др.

Большая часть исследований в области детерминированных задач пла-

нирования выпуска продуктов на конечном горизонте с динамически изме-

няющимся спросом и ограничениями на мощность производственной системы

касается выпуска продуктов одного наименования [12]. Вместе с тем большое

внимание уделяется также многопродуктовым задачам [13]. Поскольку клас-

сические постановки обоих типов этих задач являются NP-трудными [14-16],

большинство предложенных алгоритмов их решения являются эвристически-

ми (см., например, [17-19]). Здесь особо следует отметить эвристики, предпо-

лагающие использование при их формулировке и реализации методов мате-

матического программирования ([18] и др.), а также эвристики, основанные

на методе ¾ветвей и границ¿ [19].

Для решения однопродуктовых задач с динамически изменяющимся спро-

сом часто применялись методы динамического программирования [20-22].

В последнее время внимание многих исследователей однопродуктовых за-

дач с ограниченной мощностью системы привлекали вполне полиномиаль-

ные многошаговые аппроксимационные схемы [12], позволяющие находить

приближенное решение задачи с заданной относительной погрешностью оп-

тимального значения целевой функции.

Исследуемая в статье комплексная задача заключается в выборе вариан-

та агрегирования операций в блоки, в определении для каждого временного

интервала состава группы, количества выпускаемых групп и интенсивностей

выполнения операций, максимизирующих в совокупности планируемую при-

быль при ограничениях на общую длительность выполнения комплексов опе-

раций в каждом временном интервале.

Компонента рассматриваемой задачи, связанная с планированием выпуска

семейства продуктов, относится к задачам среднесрочного планирования се-

рийного выпуска системой ограниченной мощности групп переменного соста-

ва продуктов заданной номенклатуры с детерминированным динамическим

спросом. Невыполненные заказы по каждому из продуктов остаются в систе-

ме и могут быть удовлетворены на последующих интервалах (допускается

отложенный спрос).

В качестве основных особенностей исследуемой постановки можно отме-

тить следующие. Выбранный вариант агрегирования операций в блоки оста-

ется неизменным на всем периоде планирования. Как состав группы про-

дуктов, так и интенсивности операций не изменяются в рамках текущего

интервала, но могут быть изменены в следующем интервале. Объемы спро-

са на различные продукты семейства в различных интервалах не связаны

между собой. Решения о количестве выпускаемых групп в любом интервале

принимаются одновременно с выбором интенсивностей операций обработки

продуктов группы, определяющих как возможность такого размера выпус-

ка, так и стоимость самого выпуска. Следует отметить, что если пропорции

спроса на различные продукты группы не изменяются от интервала к ин-

тервалу, то такую задачу можно свести к однопродуктовой, где в качестве

продукта рассматривается группа в целом. Таким образом, рассматриваемая

задача занимает промежуточное место между многопродуктовыми и одно-

продуктовыми задачами.

Рассмотренные в [7, 9] задачи являются фрагментами исследуемой, полу-

чаемыми при фиксации варианта агрегирования операций на единственном

временном интервале и при некоторых дополнительных предположениях. На-

личие в исследуемой задаче комбинаторной составляющей, связанной с поис-

ком наилучшего агрегирования операций, а также дискретной составляющей,

связанной с выбором варианта состава группы, делает эту задачу достаточ-

но сложной, требующей специальных методов решения. Ниже предлагается

один из возможных подходов к разработке таких методов.

2. Общая постановка задачи и ее математическая модель

Рассматривается одна из задач, возникающих при проектировании произ-

водственных систем для группового выпуска продуктов d заданной номенкла-

туры D на периоде ℑ планирования, состоящем из n временных интервалов с

длительностями T_t, в условиях, когда известен ожидаемый спрос λ_dt на про-

дукт d ∈ D в интервале t ∈ T = {1, . . . , n}. Система состоит из ряда специа-

лизированных рабочих станций, на каждой из которых может выполняться

некоторое множество операций. Операции, выполняемые на различных стан-

циях, считаются различными. В дальнейшем J - множество всех операций в

системе.

Продукты в систему поступают последовательно. Входная последователь-

ность в интервале t состоит из циклически повторяющихся идентичных под-

последовательностей (групп) π_t = (d_t1, . . . , d_tr , . . . , dth(πt))изh(πt) продуктов

d_tr ∈ D, причем отдельные продукты могут входить в группу π_t в количе-

стве h_d(π_t) экземпляров. Каждый продукт группы последовательно один за

другим проходит обработку на каждой станции системы в порядке нумера-

ции станций, причем в каждый момент времени на каждой станции обра-

батывается один продукт. Работа системы состоит из последовательности

тактов. В каждом такте при заданной группе π_t на каждой рабочей стан-

ции параллельно выполняются множества операций над соответствующими

(станции, группе и моменту времени) продуктами. По завершении такта все

находящиеся в системе продукты синхронно перемещаются на следующие

(для каждого из них) станции, с последней станции сходит готовый продукт,

а на первую станцию поступает очередной продукт из входной последова-

тельности. Затем выполняется очередной такт. Обработка одной группы π_t

в интервале t состоит изh(π_t) тактов. Эта последовательность тактов обра-

зует цикл обработки группы π_t в интервале t. В общем случае цикл может

содержать идентичные такты, но для простоты изложения будем считать

все такты цикла различными. В дальнейшем I(π_t) = {1, . . . , i, . . . ,h(π_t)} -

множество номеров тактов обработки группы π_t продуктов. Без ограничения

общности будем считать, что в интервале t в такте 1 цикла на первой рабо-

чей станции обрабатывается продукт d_t1 текущей группы π_t. Тогда в такте i

операция j будет выполняться для продукта dtχ(πt,i,j) ∈ D этой группы, где

χ(π_t, i, j) = 1 + mod((h(π_t) + i - mod(k(j),h(π_t))),h(π_t)) и k(j) - номер стан-

ции, на которой выполняется операция j ∈ J.

Поскольку в разных тактах на одной и той же станции обрабатываются,

вообще говоря, разные продукты операциями из одного и того же набора опе-

раций, то в данном случае цикл обработки группы представляет собой выпол-

нение последовательности пересекающихся множеств операций, причем все

операции одного множества выполняются параллельно. Эти множества об-

разуют совокупности операций соответствующих тактов. Следует отметить,

что одни и те же операции для разных продуктов могут иметь различные

параметры, а для некоторых продуктов отдельные операции могут вообще

не выполняться.

При проектировании системы операции могут агрегироваться в один ли-

бо несколько блоков операций. Каждый блок выполняется с единой интен-

сивностью посредством одного общего для операций блока исполнительного

органа.

Агрегирование операций способствует, как правило, снижению капиталь-

ных затрат на систему и затрат на ее обслуживание, но одновременно мо-

жет приводить к возрастанию текущих материальных и временных затрат

на выполнение каждой из агрегируемых операций в отдельности. Последнее

объясняется, в частности, тем, что такое агрегирование операций исключает

возможность индивидуального выбора для каждой из них наилучших (с точ-

ки зрения производственных затрат) интенсивностей их выполнения.

Возможности агрегирования операций задаются семейством W непересе-

кающихся неединичных подмножеств из множества J, каждое из которых яв-

ляется потенциальным блоком операций, причем любое подмножество w ∈ W

может содержать такие операции, выполнение которых для некоторых про-

дуктов не требуется. В данной работе ограничимся случаем, когда каждое из

множеств операций w ∈ W может выполняться либо только полностью аг-

регированным (т.е. как один блок), либо полностью разагрегированным (т.е.

каждая операция автономна). В этом случае множество возможных вари-

антов агрегирования представимо множеством Q допустимых значений дво-

ичного вектора q = (q_w|w ∈ W ), где q_w = 0 при агрегированном выполнении

операций множества w ∈ W и q_w = 1 в противном случае.

В работе исследуется ситуация, когда структура системы (число рабочих

станций, множества операций, выполняемых на каждой станции, и выбран-

ный вариант q их агрегирования) остается неизменной на всем периоде пла-

нирования, в то время как состав группы π_t продуктов, планируемое количе-

ство x_t выпуска групп и интенсивности z_jt выполнения операций j ∈ J могут

изменяться от интервала к интервалу. Ограничимся случаем, когда интен-

сивность z_jt выполнения каждой операции (а значит, и блока операций) для

каждого интервала выбирается однократно, не зависит от такта, в составе

которого эта операция выполняется, и не изменяется во времени.

Искомыми параметрами в рамках рассматриваемой проектной задачи яв-

ляются вариант q агрегирования операций, вектора π = (π₁, . . . , π_t, . . . , π_n)

и x = (x₁,...,x_t,...,x_n) планируемых к выпуску групп продуктов и пла-

нов выпуска этих групп на периоде планирования, а также вектор z = (z_t =

= (z_jt|j ∈ J)|t ∈ T ) интенсивностей выполнения операций в различных интер-

валах.

Диапазон Z_jd = [z_1jd, z_2jd] возможных значений интенсивности z_jt выпол-

нения операции j ∈ J для продукта d ∈ D предполагается заданным. По-

скольку интенсивность z_jt выполнения операции j ∈ J в интервале t ∈ T оди-⋂

накова для всех d ∈ D, то предполагается, что диапазон Z_j =

Z_jd воз-

d∈D

можных значений интенсивности z_jt операции j ∈ J не пуст, в дальнейшем

Z_j = [z_1j,z_2j]. Аналогично, предполагается, что для любого w ∈ W диапа-

зон Z_w = [z_1w = max{z_1j |j ∈ w}, z_2w = min{z_2j |j ∈ w}] возможных значений

интенсивности z_wt операций блока в интервале t также не пуст. В против-

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

следовательно, это множество должно быть исключено из W .

В работе при выборе наиболее рационального значения набора (q, π, x, z)

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

продукции, выпущенной системой за общий период планирования, так и об-

щие производственные и логистические затраты за этот период.

Указанная добавленная стоимость Д (π, x) может быть оценена как сум-

марная добавленная стоимость каждого произведенного и поставленного

(в соответствии с ожидаемым спросом) продукта d ∈ D:

{

}

∑

Д (π, x) =

σ_d min

h_d(π_t)x_t,

λ_dt

d∈D

t=1

(1)

{

}

∑ n∑

∑

= σ_d λdt - σd max

λ_dt -

h_d(π_t)x_t

d∈D t=1

d∈D

t=1

где σ_d > 0 - добавленная стоимость одного продукта d. Здесь Д (π, x) =

{

}

∑

σ_d max

λ_dt - h_d(π_t)x_t можно рассматривать как недополу-

d∈D

t=1

ченную добавленную стоимость (что эквивалентно недополученной прибы-

ли).

Анализ реальных ситуаций показывает, что для многих из них с достаточ-

ной для практики точностью можно считать, что общие как материальные,

так и временные затраты на выпуск продукции на всем периоде планирова-

ния складываются из:

инвестиционных затрат на систему за вычетом ее остаточной стоимости,

амортизационных затрат, включая затраты на оборудование, производствен-

ные площади и т.п.;

текущих эксплуатационных затрат в процессе функционирования систе-

мы (далее - эксплуатационные затраты), включающих оплату труда основ-

ного и вспомогательного персонала и накладные расходы на нее, стоимости

расходуемых ресурсов и затрат на их восстановление, затраты на реконфи-

гурацию системы при переходе системы на выпуск в очередном временном

интервале другой группы продуктов;

логистических затрат, включающих затраты на хранение произведен-

ной, но невостребованной продукции и/или штрафы за неудовлетворенный

спрос для каждого из интервалов времени периода планирования.

Инвестиционные и амортизационные затраты зависят от принимаемого

в процессе проектирования варианта q агрегирования операций. Во многих

реальных ситуациях с достаточной для практики точностью эта зависимость∑

может быть представлена функцией C^ин(q) = C₀ +

C_wq_w, где C₀ и C_w

w∈W

предполагаются известными для всех w ∈ W .

Рассмотрим зависимости материальных и временных затрат в процессе

эксплуатации проектируемой системы от значений набора (q, π, x, z) искомых

проектных параметров для каждого интервала t ∈ T .

Длительность выполнения в интервале t для продукта d ∈ D операции

j ∈ J при фиксированной ее интенсивности z_jt равна V_jdz_jt, где V_jd - задан-

ный объем операции j ∈ J для продукта d. Предполагается, что V_jd = 0, если

операция j для продукта d не выполняется. Учитывая параллельность выпол-

нения операций как на каждой станции, так и операций различных станций,

длительность выполнения всех операций такта i равна max{V_ij (π_t)z_jt|j ∈ J},

где V_ij (π_t) = Vjdtχ(π

- объем операции j ∈ J для обрабатываемого в этом

t,i,j)

такте продукта dtχ(πt,i,j) из группы πt. В дальнейшем условно предполагается,

что при V_jd = 0 диапазон Z_jd не ограничен.

Анализ реальных ситуаций показывает, что для многих из них с достаточ-

ной для практики точностью можно считать, что общие эксплуатационные

как материальные, так и временные затраты складываются из двух основных

частей. Первой является сумма затрат, связанных с восстановлением ресур-

сов, расходуемых при выполнении каждой из операций. Вторую часть пред-

ставляют дополнительные материальные и временные затраты, связанные

со вспомогательными временами тактов, зарплатой персонала с накладными

расходами, обслуживанием оборудования, реконфигурацией системы и т.д.

Рассматривается ситуация, когда максимально возможный объем каждого

из расходуемых ресурсов в системе ограничен и заранее известен. Предпола-

гается, что восстановление любого из ресурсов осуществляется после завер-

шения последнего обеспеченного соответствующим ресурсом такта. Выпол-

нение следующего такта может начаться лишь после восстановления этого

ресурса. Материальные и временные затраты на восстановление каждого из

ресурсов, как правило, известны. Известна обычно также и зависимость ско-

рости расхода соответствующих ресурсов на выполнение единицы объема опе-

рации j ∈ J для продукта d ∈ D от интенсивности z_jt ее выполнения [23, 24].

На базе этой информации для каждой пары (j, d) могут быть построены опре-

деленные на диапазоне Z_jd функции f_pjd(z_jt), представляющие зависимости

удельных (отнесенных к единице объема операции) материальных (p = 1) и

временных (p = 2) затрат на ресурсы и их восстановление от принимаемой

интенсивности z_jt операции j в интервале t. Как правило, функции f_pjd(z_jt)

являются невозрастающими в области их определения для любых j, d, p.

Материальные (p = 1) и временные (p = 2) затраты на реконфигурацию

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

выпуску в интервалах t и t - 1. Эти затраты c_p(π_t-1, π_t) предполагаются из-

вестными.

Остальные общие материальные и временные затраты при эксплуатации

системы можно рассматривать относительно каждого цикла. Эти затраты

также можно считать состоящими из двух частей, первая из которых про-

порциональна числу тактов в цикле, а вторая пропорциональна сумме дли-

тельностей всех тактов цикла. Коэффициенты пропорциональности E_pt(q),

R_pt(q) этиx зависимостей для группы π_t и интервала t предполагаются задан-

ными для каждого из возможных вариантов агрегирования q ∈ Q, где p = 1

для материальных затрат и p = 2 для временных. Аналогично предыдуще-

му во многих реальных ситуациях с достаточной для практики точностью

можно считать, что зависимости коэффициентов E_pt(q) (как и коэффициен-

тов R_pt(q)) от варианта агрегирования q имеют следующую структуру:

∑

E_pt(q) = e^′pt +

e_ptwq_w,

w∈W

где e^′pt > 0 - величина удельных затрат в случае агрегированного выполне-

ния операций для всех множеств w ∈ W ; e_piw > 0 - дополнительные удельные

затраты при автономном выполнении операций множества w ∈ W . Здесь па-

раметры e^′pt и e_piw предполагаются известными для всех w ∈ W .

Таким образом, в интервале t ∈ T общие эксплуатационные материальные

(p = 1) и временные (p = 2) затраты на цикл обработки группы π_t продуктов

при фиксированных значениях искомых параметров q и z_t равны

∑

Fpt(q, πt, zt) = Ept(q)h(πt) + Rpt(q)

max{V_ij (π_t)z_jt|j ∈ J} +

i∈I(πt)

∑

V_ij(π_t)f_pij(z_jt),

i∈I(πt) j∈J

где f_pij(z_jt) = fpjdtχ(π

(z_jt) - материальные (p = 1) и временные (p = 2) за-

t,i,j)

траты на единицу объема операции j для обрабатываемого в такте i продукта

dtχ(πt,i,j) при фиксированном значении zjt. В функциях Fpt(q,πt,zt) целочис-

ленность числа тактов за время расходования восстановленного ресурса не

учитывается, поскольку это число обычно достаточно велико.

При оценке логистических затрат рассматривается ситуация, когда до-

пускается отложенный спрос, т.е. заказы, не выполненные к концу текущего

интервала, могут быть удовлетворены в последующие интервалы с выплатой

штрафов за просрочку. Логистические затраты рассматриваются по каждому

продукту в отдельности и задаются посредством функций H_dt(y), представ-

ляющих затраты на хранение (при y > 0) либо штраф за неудовлетворенный

спрос (при y < 0) для |y| единиц продуктов d ∈ D в интервале t. Предполага-

ется, как обычно, что функции H_dt(y) не возрастают при y < 0, не убывают

при y > 0 и H_dt(0) = 0.

Суммарные логистические затраты в системе, выпускающей заданную но-

менклатуру D продуктов, за весь период планирования при фиксированных

значениях искомых проектных параметров q, π, x, z равны

(

)

∑

L(q, π, x) =

H_dt

h_d(π_r)x_r - Λ_dt

t=1 d∈D

r=1

где

∑

Λ_dt =

λ_dr

r=1

ожидаемый кумулятивный спрос на продукт d ∈ D за первые t интервалов.

Общие затраты (инвестиционные, эксплуатационные и логистические) на

выпуск и реализацию заданной номенклатуры D продуктов за весь период

планирования при фиксированных значениях искомых проектных парамет-

ров q, π, x, z равны

∑

Φ(q, π, x, z) = C₀ +

C_wq_w + c₁(π_t-1,π_t) +

w∈W

t=1

(

)

∑

+ x_tF_1t(q,π_t,z_t) +

H_dt

h_d(π_r)x_r - Λ_dt

t=1

t=1 d∈D

r=1

Рассматриваемая проектная задача заключается в нахождении такого до-

пустимого набора (q, π, x, z) проектных параметров, который максимизирует

планируемую прибыль Π(q, π, x, z) = Д (π, x) - Φ(q, π, x, z) от эксплуатации

системы за весь период планирования.

С учетом (1) максимизации прибыли Π(q,π,x,z) соответствует миними-

зация суммы общих затрат Φ(q, π, x, z) и недополученной добавленной стои-

мости Д (π, x). Последнюю условно можно рассматривать как сумму допол-

нительных штрафов за недопоставку каждого из продуктов d ∈ D в конце

интервала n. В дальнейшем предполагается, что эти дополнительные штра-

фы включены в модифицированные функции H_dn(•). В этом случае решение

рассматриваемой проектной задачи сводится к решению следующей задачи

смешанного математического программирования:

∑

Φ(q, π_t, x, z) =

c₁(π_t-1,π_t) +

F_1t(q,π_t,z_t)x_t +

t=1

(2)

(

)

∑

H_dt

h_d(π_r)x_r - Λ_dt

→ min

t=1 d∈D

r=1

при ограничениях

(3)

F_2t(q,π_t,z_t)x_t ≤ T_t - c₂(π_t-1,π_t

t∈T,

(4)

q ∈ Q,

(5)

π_t ∈ D_t

t∈T,

(6)

x_t ≤ x_t(π_t

t∈T,

(7)

z_t

∈ Z(q), t ∈ T,

где D_t - множество допустимых вариантов групп π_t во временном интерва-

ле t, определяемое возможностями системы; x_t(π_t) - предельное количество

групп π_t продуктов из D, которое может быть произведено системой в интер-∏

вале t; Z(q) - множество таких векторов (z_j |j ∈ J) ∈_j∈J Z_j , что для любых

w ∈ W и j ∈ w выполняется z_j = z_w ∈ Z_w при q_w = 0.

Здесь ограничение (3) учитывает возможность выпуска x_t групп π_t продук-

тов с учетом длительности T_t интервала t и общих временных затрат F_2t(•)

на цикл выпуска этой группы. Задачу (2)-(7) в дальнейшем будем называть

задачей A.

3. Декомпозиционная схема метода решения задачи

Задача A представляет собой достаточно сложную задачу смешанного

нелинейного программирования, в которой искомыми являются переменные

различной природы: q - |W |-мерный двоичный вектор, π_t - размещение с

повторениями элементов множества D, x - n-мерный целочисленный вектор,

а z_t - |J|-мерный вещественный вектор, t ∈ T.

Отметим некоторые особенности задачи A:

для любого t ∈ T структура функции F_2t(q, π_t, z_t)x_t в левой части огра-

ничения (3) совпадает со структурой слагаемого F_1t(q, π_t, z_t)x_t в первой части

целевой функции (2);

если векторы q^′, q^′′ ∈ Q таковы, что q^′w ≤ q^′′w для всех w ∈ W, то Z(q^′)⊆

⊆Z(q^′′) и для всех z ∈ Z(q^′), t ∈ T и p = 1,2 выполняется F_pt(q^′,π_t,z_t) ≤

≤ F_pt(q^′′,π_t,z_t), если при этом q^′ = q^′′, то F_pt(q^′,π_t,z_t) < F_pt(q^′′,π_t,z_t).

Учитывая указанные особенности задачи A предлагается следующий трех-

уровневый подход к ее решению.

На нижнем уровне для фиксированных значений набора (q, π_t, x_t) искомых

переменных и t ∈ T решаются автономные подзадачи B1_t(q, π_t, x_t) нелиней-

ного программирования, каждая из которых заключается в определении та-

кого значения z^∗t(q, π_t, x_t) вектора z_t ∈ Z(q), которое минимизирует функцию

F_1t(q,π_t,z_t) при условии, чт

F_2t(q,π_t,z_t) ≤ T^0t(q,π_t-1,π_t,x_t), где

Fpt(q, πt, zt) = Fpt(q, πt, zt) -h(πt)Ept(q) =

∑

= R_pt(q)

max{V_ij (π_t)z_jt|j ∈ J} +

V_ij(π_t)f_pij(z_jt), p = 1,2,

i∈I(πt)

i∈I(πt) j∈J

T_t - c₂(π_t-1,π_t)

T^0t(q,π_t-1,π_t,x_t) =

-h(π_t)E_2t(q).

x_t

Обозначим через Θ(q, π_t, x_t) оптимальное значение

F_1t(q,π_t,z^∗t(q,π_t,x_t))

целевой функции

F_1t(q,π_t,z_t) в этой подзадаче. Предполагается, что

Θ(q, π_t, x_t) = ∞, если подзадача B1_t(q, π_t, x_t) не имеет решения.

На среднем уровне для фиксированных значений вектора q решаются

подзадачи B2(q) дискретного программирования по поиску такого значения

(π^∗(q), x^∗(q)) набора (π, x), который минимизирует функцию

∑

G(q, π, x) =

c₁(π_t-1,π_t) +

t=1

[

(

)]

∑

(

)

∑

Θ_t(q,π_t,x_t) +h(π_t)E_1t(q)

x_t +

H_dt

h_d(π_r)x_r - Λ_dt

t=1

d∈D

r=1

при условии, что (π_t, x_t) ∈ D_t × [0, x_t(π_t)] для всех t ∈ T . Оптимальное зна-

чение G(q, π^∗(q), x^∗(q)) функции G(q, π, x) обозначим через Ψ(q). Если

Ψ (q) = ∞ для некоторого q ∈ Q, то исходная задача A с этим значением q

не имеет решения.

На верхнем уровне решается подзадача B3 дискретного программи-

рования по определению значения q^∗ двоичного вектора q ∈ Q, мини-

мизирующего функцию Ψ(q). Очевидно, если Ψ(q) = ∞ для всех q ∈ Q,

то исходная задача A не имеет решения. В противном случае, если

q^∗,π^∗(q),x^∗(q) и z^∗(q,π,x) являются точными решениями соответствующих

подзадач, то набор (q^∗, π^∗(q^∗), x^∗(q^∗), z^∗(q^∗, π^∗(q^∗), x^∗(q^∗))) искомых пара-

метров q, π^∗, x, z является точным решением исходной задачи. Если какие-

либо из подзадач B1_t(•), B2(•) или B3 решаются приближенно, то набор

(q^∗, π^∗(q^∗), x^∗(q^∗), z^∗(q^∗, π^∗(q^∗), x^∗(q^∗))) можно принять в качестве прибли-

женного решения этой задачи.

Укрупненная схема предлагаемого подхода приведена на рисунке.

Рассмотрим некоторые подходы к решению выделенных подзадач. Целе-

сообразность того или иного подхода к решению подзадач B1_t(•) во многом

зависит от свойств функций f_pjd(z) на областях их определения. Остановимся

Укрупненная схема декомпозиции задачи A.

на широко распространенном на практике случае, когда эти функции (следо-

вательно, и функции f_pij(z)) выпуклы на отрезках Z_j для всех j ∈ J, d ∈ D и

p = 1,2. В этом случае задача B1_t(•) является задачей выпуклого программи-

рования и для ее решения могут быть использованы известные общие методы

решения задач этого класса. Вместе с тем специфика этих задач (вид первых

слагаемых функци

F_1t(•)

F_2t(•), сепарабельность их последних слагаемых

и невозрастание функций f_pij(z_jt) на отрезках Z_j ) позволяют предложить

для их решения специальные методы.

Один из них основан на параметрической декомпозиции [24] задачи B1_t(•)

с параметризацией max{V_ij (π_t)z_jt|j ∈ J} = τ_i, i ∈ I(π_t). Пусть

W⁰(q) = {w ∈ W | q_w = 0}, J⁰(q) = {j ∈ w | w ∈ W⁰(q)}, τ = (τ_i | i ∈ I(π_t)),

{

}

{

}}

τ_ki(q,π_t) = max max

V_ij(π_t)z_kj |j ∈ J\J⁰(q)

,max

V_ij(π_t)z_kw |w ∈ W⁰(q)

{

}}

z^∗jt(τ) = min z_2j,min

τ_2i(q,π_t)/V_ij(π_t) | i ∈ I(π_t)

при j ∈ J\J⁰(q)

{

}}

z^∗jt(τ) = min z_2w,min

τ_2i(q,π_t)/V_ij(π_t) | i ∈ I(π_t)

при j ∈ w ∈ W⁰(q).

Тогда задача B1_t(•) сводится к следующей задаче выпуклого программиро-

вания:

∑

(8)

F_1t(q,π_t,τ) = R_1t(q)

τ_i +

V_ij(π_t)f_1ij(z^∗jt

(τ )) → min,

i∈I(πt)

i∈I(πt) j∈J

∑

F2t(q, πt, τ ) = R2t(q)

τ_i +

i∈I(πt)

(9)

∑

V_ij(π_t)f_2ij(z^∗jt(τ)) ≤ T^0t(q,π_t-1,π_t,x_t),

i∈I(πt) j∈J

(10)

τ_i ∈ [τ_1i(q,π_t),τ_2i(q,π_t)], i ∈ I(π_t

В качестве начального решения задачи (8)-(10) можно принять такое

значение τ⁰ вектора τ , которое минимизирует функцию

F_2t(q,π_t,τ). Если

F_2t(q,π_t,τ⁰) > T^0t(q,π_t-1,π_t,x_t), то задача B1_t(•) не имеет решения. Заме-

тим, что x_t(q, π_t) = (T_t - c₂(π_t-1, π_t))/

F_2t(q,π_t,τ⁰) +h(π_t)E_2t(q)) является

верхней оценкой допустимого значения параметра x_t в задаче B2(q).

Для приближенного решения задачи B1_t(•) может быть адаптирован под-

ход, предложенный в [9] для решения аналогичных задач и основанный на

их аппроксимации задачей линейного программирования.

Подзадача B2(q) может быть сформулирована в терминах многошаговой

оптимизации с последующим использованием методов динамического про-

граммирования для ее решения. При этом в качестве управляющего на шаге

t ∈ T может быть принят вектор u_t = (π_t,x_t), а в качестве состояния - век-(

)

∑

тор s_t = (π_t, a_t), где a_t = a_dt =

h_d(π_t)x_r|d ∈ D

. При большой размерно-

r=1

сти пространства состояний для приближенного решения подзадачи B2(q)

можно воспользоваться соответствующими приближенными методами (на-

пример, методом ¾блуждающих трубок¿) в сочетании с некоторыми эври-

стиками. Одной из эвристик при построении начального приближения явля-

ется выбор на очередном шаге t ∈ T такого управления u_t = (π_t, x_t) из всех

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

кумулятивного спроса минимизирует сумму затрат на реконфигурацию, про-

изводство, хранение запасов продуктов и штрафов за их недопоставку либо

(в более упрощенном варианте) лишь два последних слагаемых этой суммы.

В подзадаче B3 верхнего уровня верхняя граница числа возможных зна-

чений вектора q равна 2^|W|, поэтому ее решение полным перебором всего

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

небольших значениях |W | и практически нереализуемо при больших |W |. Для

сокращения перебора могут быть использованы известные методы, основан-

ные на идеях случайного поиска, эвристиках и метаэвристиках в сочетании с

предлагаемым ниже вариантом метода последовательной фиксации перемен-

ных (МПФП).

Пусть имеется некоторое значение q⁰ вектора q ∈ Q, полученное с исполь-

зованием перечисленных выше эвристических подходов. Для последующей

оптимизации q⁰ предлагается следующий алгоритм МПФП. Алгоритм фор-

мирует последовательность векторов из Q такую, что каждый следующий

вектор отличается от предыдущего только значением ровно одной его компо-

ненты. Компоненты, значения которых были изменены, считаются зафикси-

рованными и в дальнейшем не меняются. Выбор очередного вектора после-

довательности на текущей итерации выполняется следующим образом. Для

текущего вектора q^c формируется подмножество Q(q^тек) ⊂ Q векторов, ко-

торые отличаются от q^тек одной из его нефиксированных компонент. Для

каждого вектора q ∈ Q(q^тек) решается подзадача B2(q). В качестве следую-

щего вектора последовательности выбирается вектор q^′ ∈ Q(q^тек), которо-

му соответствует минимальное значение функции Ψ(q) среди этих подзадач.

Компонента, по которой векторы q^′ и q^тек различаются между собой, фик-

сируется. Число векторов в подмножествах Q(q^c) от итерации к итерации

уменьшается с |W | до 1. Соответственно сокращается и число решаемых под-

задач. На каждой итерации в общем случае получается новый лучший вектор

q ∈ Q. Алгоритм завершает работу, когда либо значение Ψ(q^тек) не уменьши-

лось, либо подмножество Q(q^тек) = ∅. Полученный вектор q^c принимается в

качестве решения подзадачи B3. Общее число подзадач B2(q) вычисления

функции Ψ(q) для различных q не превышает числа 0,5(|W |² + |W |).

Алгоритм МПФП может быть применен повторно для нового начального

значения q⁰. В качестве такового может быть принято, в частности, получен-

ное ранее решение.

Одно из возможных направлений развития алгоритма МПФП связано с

проверкой целесообразности изменения одновременно нескольких компонент

вектора q^тек, отбираемых по полученным значениям Ψ(q).

4. Заключение

Предложены математическая модель и метод решения задачи комплекс-

ной оптимизации агрегирования операций, программы выпуска и интенсивно-

стей выполнения пересекающихся множеств операций при групповой серий-

ной обработке заданного семейства продуктов на многопозиционной рекон-

фигурируемой производственной системе в заданных временных интервалах

при нестационарном детерминированном спросе.

Рассмотрен частный случай задачи, когда выбранный вариант агрегирова-

ния операций системы остается неизменным на всем периоде планирования,

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

агрегированно с общей для этого множества интенсивностью, либо каждая

операция со своей индивидуальной интенсивностью, состав группы продук-

тов и интенсивности операций в рамках текущего интервала неизменны, но

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

материальных и временных затрат на выполнение любой операции от ее ин-

тенсивности представимы выпуклыми функциями, объемы спроса на различ-

ные продукты в различных интервалах известны и не связаны между собой.

Описана трехуровневая декомпозиционная схема решения рассматривае-

мой задачи. Метод приближенного решения задачи верхнего уровня основан

на комбинации эвристических методов и методе последовательной фиксации

переменных. Метод для задачи среднего уровня выбора состава группы об-

рабатываемых продуктов и плана выпуска групп на каждом из временных

интервалов при фиксированном варианте агрегирования операций в блоки с

учетом затрат на сам выпуск, на хранение излишне произведенных продук-

тов, штрафов за не поставленные в срок заказчику продукты и упущенной

добавленной стоимости основан на идеях метода динамического программи-

рования.

Для подзадачи нижнего уровня поиска оптимальных интенсивностей опе-

раций в случае выпуклых функций затрат на операции при фиксированных

варианте агрегирования, составе группы продуктов и объеме выпуска пред-

ложен метод параметрической декомпозиции для точного ее решения и ме-

тод аппроксимации задачей линейного программирования для приближенно-

го решения.

В дальнейшем предполагается исследовать более общие постановки рас-

смотренной выше задачи, в которых, в частности, варианты агрегирования

операций в составе заданных подмножеств операций определяются различны-

ми комбинациями подмножеств этих операций, фактический спрос и степень

его удовлетворения на отдельные продукты в начальные временные интер-

валы влияет на последующих интервалах как на возможный спрос на эти

продукты, так и на штрафы за их возможную недопоставку. Интерес пред-

ставляет также исследование возможностей эффективного решения подзада-

чи нижнего уровня для невыпуклых (в частности, квазивыпуклых, вогнутых,

и др.) функций f_pjd(z_jt), представляющих зависимости удельных материаль-

ных и временных затрат на ресурсы и их восстановление от принимаемой

интенсивности z_jt операции j.

СПИСОК ЛИТЕРАТУРЫ

Alting L., Zhang H. Computer Aided Process Planning: the state-of-the-art survey //

Int. J. Prod. Res. 1989. V. 27. No. 4. P. 553-585.

Halevi G. Process and Operation Panning. Springer, 2003.

Bukchin J., Tzur M. Design of flexible assembly line to minimize equipment cost //

IIE Transact. 2000. V. 32. P. 585-598.

Burkov V.N., Novikov D.A. Models and methods of multiprojects’ management //

Syst. Sci. 1999. V. 256. No. 2. P. 5-4.

Dolgui A., Guschinsky N., Levin G. Enhanced mixed integer programming model

for a transfer line design problem / A. Dolgui // Comput. Industr. Engineer. 2012.

V. 62. No. 2. P. 570-578.

Левин Г.М., Розин Б.М. Оптимизация режимов параллельной многоинструмен-

тальной обработки деталей на агрегатном оборудовании с учетом групповой сме-

ны инструментов // Информатика. 2011. № 3. С. 33-47.

Левин Г.М., Розин Б.М. Оптимизация последовательно-параллельного выпол-

нения комплекса взаимосвязанных операций // Веcцi НАН Беларуci. Сер. фiз.-

мат. навук. 2013. № 1. С. 111-116.

Dolgui A., Rozin B., Levin G. Optimisation of processing conditions for multi-

product batch production lines with series-parallel operations under uncertainty on

demands for finished products // Proc. 18th APIEMS Conf. Industr. Engineer. Man-

agement Syst. Bandung, Indonesia, 2017. Р. А2-7-А2-12.

Левин Г.М., Розин Б.М., Долгий А.Б. Линейная аппроксимация задачи оптими-

зации интенсивностей последовательно-параллельного выполнения пересекаю-

щихся множеств операций // Информатика. 2014. № 3. С. 44-51.

10.

Karimi B., Fatemi Ghomi S.M.T., Wilson J.M. The capacitated lot sizing problem:

a review of models and algorithms // Omega. 2003. V. 31. No. 5. P. 365-378.

11.

Ullah H., Parveen S. A Literature Review on Inventory Lot Sizing Problems //

Global J. Res. Engineer. 2010. V. 10. No. 5. P. 21-36.

12.

Chubanov S., Pesch E. An FPTAS for the single-item capacitated economic lot-sizing

problem with supply and demand // Oper. Res. Lett. 2012. V. 40. No. 6. P. 445-449.

13.

Absi N., Kedad-Sidhoum S. The multi-item capacitated lot-sizing problem with safety

stocks and demand shortage costs // Comput. Oper. Res. 2009. V. 36. No. 11.

P. 2926-2936.

14.

Florian M., Lenstra J.K., Kan A.H.G.R. Deterministic production planning: Algo-

rithms and complexity // Management Sci. 1980. V. 26. P. 669-679.

15.

Bitran G.R., Yanasse H.H. Computational complexity of the capacitated lot size

problem // Management Sci. 1982. V. 28. No. 10. P. 1174-1186.

16.

Chen W.H., Thizy J.M. Analysis of relaxations for the multi-item capacitated lot-

sizing problem // Ann. Oper. Res. 1990. V. 26. P. 29-72.

17.

Dixon P.S., Silver E.A. A heuristic solution procedure for the multi-item, single

level, limited capacity, lot sizing problem // J. Oper. Management. 1981. V. 21.

No. 1. P. 23-40.

18.

Thizy J.M., Van Wassenhove L.N. Lagrangean relaxation for the multi-item capac-

itated lot-sizing problem: a heuristic implementation // IIE Transact. 1985. V. 17.

No. 4. P. 308-313.

19.

Gelders L.F., Maes J., Van Wassenhove L.N. A branch and bound algorithm for

the multi item single level capacitated dynamic lotsizing problem / Axaster S.,

Schneeweiss CH., Silver E., ed. Multistage production planning and inventory con-

trol. Lecture notes in economics and mathematical systems. V. 266. Berlin: Springer,

1986. P. 92-108.

20.

Wagelmans A., Van Hoesel S., Kolen A. Economic lotsizing: an O(n log n) algorithm

that runs in linear time in the Wagner-Whitin case // Oper. Res. 1992. V. 40.

P. 145-155.

21.

Aggarwal A., Park J.K. Improved algorithms for economic lot-size problem // Oper.

Res. 1993. V. 41. No. 3. P. 549-571.

22.

Federgruen A., Tzur M.A. A simple forward algorithm to solve general dynamic lot

sizing models with n periods in O(n log n) or O(n) time // Management Sci. 1991.

V. 37. No. 8. P. 909-925.

23.

Левин Г.М. Розин Б.М., Долгий А.Б. Оптимизация выпуска и интенсивностей

обработки группы деталей при нестационарном спросе // Веcцi Нац. акад. навук

Беларуci. Сер. фiз.-мат. навук. 2016. № 3. С. 102-109.

24.

Левин Г.М., Танаев В.С. Декомпозиционные методы оптимизации проектных

решений. Минск.: Наука и техника, 1978.

Статья представлена к публикации членом редколлегии А.А. Лазаревым.

Поступила в редакцию 17.07.2019

После доработки 12.10.2019

Принята к публикации 28.11.2019