Автоматика и телемеханика, № 5, 2023
Оптимизация, системный анализ
и исследование операций
© 2023 г. А.И. КИБЗУН, д-р физ.-мат. наук (kibzun@mail.ru),
В.А. РАССКАЗОВА, канд. физ.-мат. наук (varvara.rasskazova@mail.ru)
(Московский авиационный институт
(национальный исследовательский университет))
МОДЕЛЬ ЦЕЛОЧИСЛЕННОГО ЛИНЕЙНОГО
ПРОГРАММИРОВАНИЯ КАК МАТЕМАТИЧЕСКОЕ
ОБЕСПЕЧЕНИЕ СИСТЕМЫ ОПТИМАЛЬНОГО
ПЛАНИРОВАНИЯ ПОТОКОВОГО ПРОИЗВОДСТВА
НА ЭТАПЕ ОПЕРАТИВНОГО ГРАФИКОВАНИЯ1
Исследуется задача оптимального планирования потокового производ-
ства на этапе оперативного графикования. В качестве примера рассмат-
ривается отделение внепечной обработки конвертерного передела стале-
литейного производства в отрасли черной металлургии. Для решения
этой задачи предлагается модель целочисленного линейного программи-
рования, в полной мере описывающая специфику исследуемых техноло-
гических процессов. Важным преимуществом такого подхода является
его масштабируемость для решения смежных оптимизационных задач в
отрасли цеховой логистики, а также гибкость к изменчивости и тонкой
настройке системы ограничений и целевого функционала. Программная
реализация разработанной модели составляет основу модуля оперативно-
го графикования системы оптимального планирования потокового про-
изводства, с использованием которой проводится масштабный вычисли-
тельный эксперимент на реальных данных.
Ключевые слова: математическое обеспечение, целочисленное линейное
программирование, потоковое производство, оперативное планирование.
DOI: 10.31857/S0005231023050069, EDN: AIRUYJ
1. Введение
Целочисленное линейное программирование (ЦЛП) широко используется
в различных областях науки и техники, включая транспортное и производ-
ственное планирование. В [1, 2] были разработаны модели ЦЛП для решения
прикладных задач планирования транспортных процессов на железной доро-
ге. В [3] методы ЦЛП рассматривались в контексте решения задач о потоках
1 Работа выполнена при финансовой поддержке Российского научного фонда (проект
№ 23-21-00293).
113
в сетях. В [4, 5] различные задачи теории расписаний были сведены к рас-
смотрению соответствующих задач ЦЛП. В [6] модели ЦЛП были предложе-
ны для решения некоторых задач промышленного планирования. Основные
трудности, возникающие при сведении прикладных задач к рассмотрению
соответствующих моделей ЦЛП, связаны с описанием комплексной системы
ограничений, присущей многим задачам прикладной природы. В настоящей
статье предлагается модель ЦЛП для решения задачи оптимального плани-
рования потокового производства на этапе оперативного графикования, ко-
торая в полной мере отражает все значимые особенности рассматриваемых
технологических процессов. Программная реализация предложенной модели
составляет основу модуля оперативного графикования интеллектуальной си-
стемы принятия решений в задачах планирования и логистики потокового
производства в отрасли черной металлургии.
В [7-10] приводится расширенный обзор приложений моделей ЦЛП, а так-
же современных методов решения. В [7, 8] детально обсуждаются классиче-
ские постановки и методы решения задач ЦЛП, включая булевское ЦЛП.
В [9, 10] особое внимание уделяется разработке моделей ЦЛП для решения
различных прикладных задач в области управления, планирования и при-
нятия решений. Предлагаемый в настоящей статье подход также является
масштабируемым и может быть продолжен для решения смежных задач оп-
тимизации технологических процессов на металлургическом производстве.
Такими смежными задачами могут быть транспортная цеховая логистика,
управление крановым хозяйством, переназначение технологических маршру-
тов и другие.
Поскольку задача ЦЛП является хорошо известной N P-трудной зада-
чей, методы ее решения продолжают активно исследоваться и развиваться.
Расширенный обзор современных методов решения задач ЦЛП представлен
в [11, 12]. В настоящей статье не обсуждаются подробно методы решения
задач ЦЛП. Основной целью здесь является разработка адекватной и мас-
штабируемой математической модели, в полной мере описывающей техноло-
гические особенности рассматриваемых процессов. При этом для получения
решения может быть использовано любое современное программное обеспе-
чение.
В [13-15] обсуждались некоторые прикладные задачи, связанные с опти-
мальным планированием технологических процессов на металлургическом
производстве, ориентированные в основном на повышение качества конечной
продукции. В [13] была предложена методология для решения комплексных
задач принятия решений в управлении металлургическим производством. Ро-
бастные оптимизационные подходы к решению смежных задач на сталепла-
вильном производстве были предложены в [16-18]. В [14, 15] также были раз-
работаны алгоритмы для улучшения качества конечной продукции на стане
горячей прокатки. В настоящей работе рассматривается идеологически дру-
гой подход к оптимизации производства, когда основное внимание уделяется
энергоэффективности каждого этапа производственной цепочки. В частно-
114
сти, оптимимальная реализация рассматриваемого в работе этапа оператив-
ного графикования позволит существенно повысить качество производства в
целом за счет повышения показателей исполнимости плана и равномерной
загрузки оборудования.
Хорошо известно, что различные классы задач Machine Scheduling и Shop
Scheduling могут быть успешно сведены к задаче Resources Constraind Project
Scheduling Problem (RCPSP). Исследуемая в настоящей работе прикладная
задача планирования потокового производства на этапе оперативного графи-
кования также характеризуется свойствами, схожими с RCPSP. Для задан-
ного множества ресурсов (машин, агрегатов внепечной обработки) требуется
построить график обработки требований (работ, сталь-ковшей с плавками
горячего металла) в рамках заданного набора технологических ограничений.
Таким образом, исследуемая задача оперативного графикования потокового
производства может быть классифицирована как RCPSP с фиксированной
длительностью обработки и с ограничениями на время начала и завершения
обработки каждого требования. Широкий обзор различных классов задач
RCPSP представлен в [19].
RCPSP является N P-трудной задачей в сильном смысле даже в своей про-
стейшей постановке. Наилучший точный алгоритм для ее решения был пред-
ложен в [20] и доставляет решение на входах размера до n = 60, где n — коли-
чество требований. Ясно, что такая размерность оказывается недостаточной
в практических задачах. Что касается алгоритмов полиномиальной сложно-
сти с гарантированной погрешностью (когда ошибка не превосходит заданной
константы), они не известны даже для случая K = 1, где K — количество ре-
сурсов. Популярный подход к решению RCPSP основан на формировании
верхних и нижних оценок для оптимального решения. В [21, 22] верхние и
нижние оценки решения RCPSP были получены с использованием методов
линейного программирования. Среди эффективных полиномиальных алго-
ритмов для решения RCPSP следует выделить алгоритм List Scheduling (LS).
Важным недостатком алгоритма LS является ограничение на размерность за-
дачи — даже в случае небольшого (несколько единиц) количества требований
алгоритм не гарантирует оптимальности полученного решения. Но, кроме то-
го, LS оказывается недостаточно гибким к имплементации в модель специ-
фических ограничений прикладного характера, таким, как посменный план
производства (когда в указанный интервал времени должно быть исполнено
заданное число требований в совокупности по всем машинам). То же самое
верно и для различных модификаций LS, включая Ant Colony и другие мета-
эвристики. Таким образом, актуальной представляется разработка обобщен-
ной модели, допускающей тонкую настройку ограничений и функционала с
учетом особенностей рассматриваемых процессов. В настоящей статье для
этих целей предлагается модель ЦЛП.
Статья имеет следующую структуру. В разделе 1 приводится общая по-
становка задачи, в том числе в терминах предметной области. Раздел 2 по-
священ описанию модели ЦЛП для решения исследуемой задачи и алгорит-
115
мов формирования функционального пространства. В разделе 3 приводятся
результаты вычислительного эксперимента с использованием разработанной
модели ЦЛП. В заключении обсуждаются пути дальнейшего развития тема-
тики, наращивание функционала модели на случай несовместности системы
ограничений, а также продолжение методологии в решении смежных задач
цеховой логистики.
2. Математическая модель задачи оперативного
графикования потокового производства
Под задачей оперативного графикования потокового производства пони-
мается формирование детализированного графика движения требований (ра-
бот, подлежащих исполнению) по машинам цеха с ограничениями на после-
довательность машин в технологической цепочке, интервалы и длительность
обработки каждого требования в зависимости от заданных характеристик
и типа машины. Рассмотрим участок потокового производства на примере
отделения внепечной обработки конвертерного сталелитейного цеха. Обозна-
чим:
T — количество различных типов машин для внепечной обработки стали
(установка доводки стали, агрегат циркуляционного вакуумирования стали и
т.п.),
k(i) ∈ N — количество машин типа i = 1, T (установка доводки стали № 1,
установка доводки стали № 2, установка печь-ковш № 1 и т.д. по каждому
типу машин),
∑
K = k(i)
i=1
— количество всех машин в цехе.
Нормативную длительность транспортировки (минимальное время в ми-
нутах) для каждой пары машин в цехе определим квадратной матрицей вида
Δ = ∥δij∥, i,j = 1,K,
где δij ∈ {0} ∪ N и выполняются следующие условия:
1) равенство δij = 0 достигается в том и только в том случае, когда транс-
портировка работы (сталь-ковша) от машины i до машины j запрещена;
2) транспортировка допускается только между различными машинами,
т.е.
δii = 0 для всех i = 1, K;
3) длительность транспортировки для любой пары машин не зависит от
начала движения, т.е.
δij = δji для всех i,j = 1,K.
116
При последовательном назначении нескольких работ на одну и ту же ма-
шину требуется время на ее настройку. Это обусловлено тем, что разные
работы могут иметь разные технологические характеристики и требования к
обработке и тогда машина (агрегат внепечной обработки) должна быть под-
готовлена для выполнения соответствующих требований. И даже при одина-
ковых технологических требованиях необходима проверка работоспособности
машины перед назначением ее на выполнение следующей работы. В предпо-
ложении, что нормативы настройки определяются только типом машины,
обозначим вектор длительностей настройки через
Π = (π1,...,πT),
где πi — минимально необходимое время (в минутах).
В период планирования работ для любой машины могут быть предусмот-
рены ремонтные и обслуживающие мероприятия — технический осмотр (ТО)
или планово-предупредительный ремонт (ППР). Обозначим множество всех
запланированных ТО и ППР (далее ТО) через
R = {ρi|i = 1,...,Ro},
где Ro — число таких осмотров и ремонтов. Для каждого элемента ρi опре-
(
)
делены параметры
s(ρi), f(ρi), m(ρi)
, где s(ρi), f(ρi) — время начала и за-
вершения, а m(ρi) ∈ 1, . . . , K — идентификатор машины (агрегата внепечной
обработки), для которой планируется ТО.
Сортамент стали является важнейшей характеристикой работ, подлежа-
щих назначению на машины. Именно сортамент стали определяет техноло-
гическую инструкцию для формирования работы уже на уровне прогнозно-
го графикования. Так, в частности, для разных сортаментов стали опреде-
лены различные нормативы по минимальной и максимальной допустимым
выдержкам металла в сталь-ковшах. На этапе оперативного графикования
сортамент стали также играет определяющую роль, поскольку различные
сортаменты подлежат различным процедурам внепечной обработки (по ти-
пу и по количеству агрегатов в технологическом маршруте, по длительности
обработки стали на агрегате определенного типа и т.п.) Пусть для рассмат-
риваемого потокового производства (конвертерного цеха) задано множество
сортаментов стали
S = {σi|i = 1,s}.
Нормативные минимальную и максимальную длительности обработки для
каждого сортамента стали и для каждого типа машин определим матрицами
M = ∥μij∥, i = 1,s, j = 1,T
и
M= ∥μij∥, i = 1,s, j = 1,T,
117
где μij, μij ∈ {0} ∪ N характеризуют соответственно минимальное и макси-
мальное время обработки (в минутах) для стали сортамента i на машине
типа j и μij = μij = 0, если сталь сортамента i не подлежит обработке на
машине типа j.
Пусть для каждого сортамента σi ∈ S также определены допустимые ти-
пы технологических маршрутов (множество обобщенных технологических
маршрутов, обобщенных ТМ), т.е.
{
}
P (σi) =
p1(i),... ,pn(i)
,
где n = n(σi) ∈ N — количество различных обобщенных ТМ для обработки
сортамента σi, и каждый обобщенный ТМ pj (i) представляет собой последо-
вательность типов машин вида
(
)
pj(i) =
τ1(i,j),... ,τl(i,j)
,
где l = l(σi, j) ∈ N — количество машин в обобщенном ТМ j для обработки
сортамента σi, и τk(i, j) ∈ {1, 2, . . . , T } — тип k-й машины в рассматриваемом
ТМ. При этом для всех σi множество P (σi) содержит первым элементом ос-
новной ТМ и допустимые альтернативные в порядке убывания приоритета.
По существу приоритет определяется показателем энергоэффективности про-
изводства, следующего по данному ТМ. Так, в частности, для основного ТМ
закладывается меньшая совокупная длительность транспортировки (даже с
учетом минимально возможной длительности обработки на каждой машине)
с тем, чтобы машины не простаивали, а сырье не остывало (дополнительный
нагрев требует значительных расходов ресурсов).
2.1. Исходные данные
Пусть Z = {ζi|i = 1, z} — множество работ прогнозного графика. Для каж-
дой работы ζi заданы (ki, ri, ui, di, σi), где ki — позиция начала (конвертер),
ri — время начала, ui — позиция завершения (машина непрерывной разлив-
ки стали), di — время завершения, σi ∈ S — сортамент стали. Необходимо
определить конкретные технологические маршруты и сроки выполнения всех
работ.
Поскольку позиции начала и завершения работ прогнозного графика по
сути своей также являются некоторыми опорными точками цеха, то опреде-
лим нормативную длительность транспортировки работы (сталь-ковша) от
каждой такой позиции до остальных машин. Обозначим:
Δ′ = ∥δ′ij∥, i = 1,K′, j = 1,K,
где K′ — количество начальных позиций в цехе (количество конвертеров),
δ′ij — минимальное время транспортировки (в минутах) от начальной пози-
ции i до машины j, и δ′ij = 0, если транспортировка запрещена. Аналогично
Δ′′ = ∥δ′′ij∥, i = 1,K′′, j = 1,K,
118
где K′′ — количество конечных позиций в цехе (количество установок непре-
рывной разливки стали), δ′′ij — минимальное время транспортировки (в ми-
нутах) от машины j до конечной позиции i, и δ′′ij = 0, если транспортировка
запрещена.
2.2. Постановка задачи
Задача формирования оперативного графика назначения плавок (задача
оперативного графикования) может быть сформулирована следующим обра-
зом. Для каждой работы ζi ∈ Z, i = 1, z должен быть назначен детализиро-
ванный по времени и по машинам технологический маршрут (расширенный
ТМ) вида
(
)
f (ζi) =
s1(i),m1(i),f1(i),... ,sl(i),ml(i),fl(i)
с ограничениями:
1) для любого f(ζi) такого, что σ = σi, и некоторого j ∈ {1, . . . , n(σ)} выпол-
няется l = l(σ, j), т.е. длина (по количеству машин) расширенного ТМ соот-
ветствует длине некоторого обобщенного ТМ для обработки сортамента σ;
2) для любого f(ζi) и соответствующего j ∈ {1, . . . , n(σ)} выполняется
t (mk(i)) = τk(i, j)
для всех k = 1, l, где t (mk(i)) — тип k-й машины в расширенном ТМ;
3) для всех f(ζi) и mk(i), mh(i) таких, что k < h, выполняется
sh(i) - fk(i) ≥ δkh,
где δkh — минимальная длительность транспортировки от машины mk(i) до
машины mh(i);
4) для всех f(ζi) и mk(i) таких, что t (mk(i)) = t, выполняется
μσt ≤ fk(i) - sk(i) ≤ μσt,
где μσt, μσt — соответственно минимальная и максимальная длительности
обработки сортамента σ на машине типа t;
5) для любых f(ζi), f(ζj ) и m = mk(i) = mh(j) таких, что t(m) = t, выполня-
ется
{
sh(i) - fk(j) ≥ πt, если sk(i) ≤ sh(j),
sk(i) - fh(j) ≥ πt иначе,
где πt — минимальное время (в минутах), необходимое для настройки маши-
ны типа t при последовательном назначении работ;
119
6) для всех f(ζi) и ТО ρj ∈ R таких, что mk(i) = m = m(ρj ) для некоторого k,
выполняется
{
{
sk(i) > s(ρj),
sk(i) < s(ρj),
или
sk(i) ≥ f(ρj)
fk(i) ≤ s(ρj),
где s(ρj), f(ρj) — время начала и завершения ТО на машине m;
7) для всех f(ζi) таких, что ki = k и m1(i) = m, выполняется
s1(i) - ri ≥ δ′km,
где s1(i) — время прибытия работы i на первую машину в расширенном ТМ
f (ζi), ri — начало выполнения i-й работы, ki — позиция начала выполнения
работы, δ′km — минимальное время транспортировки (в минутах) от позиции
начала выполнения работы до первой машины в расширенном ТМ;
8) для всех f(ζi) таких, что ui = u и ml(i) = m, выполняется
di - fl(i) ≥ δ′′um,
где fl(i) — время завершения выполнения работы i на последней машине
в расширенном ТМ, di — время завершения выполнения i-й работы, δ′′um —
минимальное время транспортировки (в минутах) от последней машины в
расширенном ТМ до позиции завершения работы.
Целевой функционал определим как минимальную совокупную длитель-
ность транспортировки, что соответствует максимальной совокупной дли-
тельности обработки всех требований на каждой машине в ТМ обработки,
т.е.
∑
(fj(i) - sj(i)) -→ max,
i=1 j=1
где l(i) — длина (по количеству машин) ТМ f(ζi), назначенного для испол-
нения работы ζi ∈ Z. Выбор данного функционала обусловлен тем, что дли-
тельная транспортировка влечет необходимость в доводке требований на оче-
редной машине в ТМ и сопутствующие дополнительные расходы ресурсов
(температурный или химический нагрев). Таким образом, суммарная дли-
тельность транспортировки, как уже было отмечено при обсуждении при-
оритетов ТМ, отражает показатель энергоэффективности процесса, а мини-
мизация ее (т.е. максимизация длительности обработки, времени пребывания
на агрегате) соответствует целям повышения энергоэффективности.
Другими словами, задача оперативного графикования состоит в том, что-
бы для каждого требования был построен детальный ТМ в условиях задан-
ных ограничений на последовательность и длительность обработки на каж-
дой машине, а также с учетом нормативной длительности транспортировки.
Для решения этой задачи предлагается модель ЦЛП, обсуждению и описа-
нию которой посвящен следующий раздел.
120
3. Модель целочисленного линейного программирования
для решения задачи оперативного графикования
потокового производства
В моделировании прикладных задач методами ЦЛП основополагающая
роль отводится структуре функционального пространства (переменных моде-
ли), поскольку эффективная и адекватная реализация этого этапа заклады-
вает как структуру системы ограничений, так и последующие возможности
тонкой настройки модели с учетом дополнительных технологических особен-
ностей исследуемых процессов. Остановимся подробнее на этой процедуре.
В алгоритме 1 для каждого требования формируется набор булевских пе-
ременных, соответствующих обработке требования на одной из машин цеха
с указанием времени начала и окончания, а также длительности операций.
При этом:
• функция end(i, s, j, k) — фиксирует l(s, j) - k машин в маршруте (начиная
с окончания) с минимальной длительностью обработки и транспортировки,
где i — идентификатор требования, j — обобщенный ТМ для обработки сор-
тамента s = σi, и k — количество фиксируемых машин;
• функция start(i, s, j, k) — фиксирует k - 1 машин в маршруте (начиная с
начала) аналогично финкции end(i, s, j, k);
• функция move(i, s, j, k, r) — для фиксированных начала и окончания марш-
рута формирует варианты начала и окончания обработки требования i на k-й
машине с минимальной длительностью обработки.
Алгоритм 1. Формирование функционального пространства
1: c = 0
⊲ глобальный счетчик переменных
2: s1 = 0, s2 = 0, f1 = 0, f2 = 0
⊲ вспомогательные счетчики
3: Для всех i = 1, z выполнять
4:
s=σi
⊲ сортамент
5:
n = n(s)
⊲ количество обобщенных ТМ
6:
Для всех j = 1, n выполнять
7:
Для всех k = 1, l(s, j) выполнять
8:
Если k = l(s, j) то
9:
end(i, s, j, k)
⊲ зафиксировать l(s, j) - k машин от конца ТМ
10:
Иначе
11:
s1 = 0, s2 = 0
12:
Если k = 1 то
13:
start(i, s, j, k)
⊲ зафиксировать k - 1 машин от начала
14:
Иначе
15:
f1 = 0, f2 = 0
16:
t = τk(s,j)
⊲ тип k-й машины
17:
Для всех r = 1, k(t) выполнять
18:
move(i, s, j, k, t, r)
⊲ перемещение k-й машины
121
Алгоритм 2. Функция end(i, s, j, k)
1: Для всех h = 1, l(s, j) - k выполнять
2:
t = τl(s,j)-h+1(s,j)
3:
Для всех r = 1, k(t) выполнять
4:
m = m(t,r)
⊲ идентификатор r-й машины типа t
5:
Для всех ii = f1, f2 выполнять
6:
c=c+1
7:
Если ii = 0 то
8:
u=ui
9:
f (c) = di - δ′′um
⊲ отступить влево длительность транспортировки
10:
Иначе
11:
f (c) = s(ii) - δm(ii)m
12:
s(c) = f(c) - μst
⊲ отступить влево длительность обработки
13:
id(c) = i, p(c) = j, num(c) = l(s, j) - h + 1, α(c) = j
14:
Если f2 = 0 то
15:
f1 = c - k(t) + 1
16:
Иначе
17:
f1 = f2 + 1
18:
f2 = c
Алгоритм 3. Функция start(i, s, j, k)
1: Для всех h = 1, k - 1 выполнять
2:
t = τh(s,j)
3:
Для всех r = 1, k(t) выполнять
4:
m = m(t,r)
5:
Для всех ii = s1, s2 выполнять
6:
c=c+1
7:
Если ii = 0 то
8:
v=ki
9:
s(c) = ri + δ′vm ⊲ отступить вправо длительность транспортировки
10:
Иначе
11:
s(c) = f(ii) + δm(ii)m
12:
f (c) = s(c) + μst
⊲ отступить вправо длительность обработки
13:
id(c) = i, p(c) = j, num(c) = h, α(c) = j
14:
Если s2 = 0 то
15:
s1 = c - k(t) + 1
16:
Иначе
17:
s1 = s2 + 1
18:
s2 = c
122
Алгоритм 4. Функция move(i, s, j, k, t, r)
1: m = m(t, r)
2: Для всех ii = s1, s2 выполнять
3:
Для всех jj = f1, f2 выполнять
4:
Если ii = 0 то
5:
t1 = ri, v = ki, δ = δ′vm
6:
Иначе
7:
t1 = f(ii), δ = δm(ii)m
8:
Если jj = 0 то
9:
u = ui,t2 = di - δ′′um - μst
10:
Иначе
11:
t2 = s(jj) - δm(ii)m - μst
12:
Пока t2 - t1 ≥ δ выполнять
13:
c = c + 1, s(c) = t2, f(c) = s(c) + μst, id(c) = i, p(c) = j, num(c) = k,
m(c) = m, α(c) = j, t2 = t2 - step
⊲ переместить начало обработки
на k-й машине влево
Ясно, что реализация алгоритма 1 возможна и в иной конфигурации, ко-
гда в первую очередь фиксируется начало маршрута и только затем его окон-
чание. В общем случае формируемые в разных подходах подмножества пе-
ременных модели могут оказаться различными, что влечет за собой струк-
турные различия последующих ограничений и функционала. Кроме того, в
предложенном варианте для каждого требования i фиксируется минималь-
ная длительность обработки на каждой машине, что снижает оптимизаци-
онный потенциал. Однако с целью сокращения размерности модели в целом
задача оперативного графикования потокового производства может быть де-
композирована на два этапа, первым из которых и является предложенная
конфигурация алгоритма 1 с фиксированной минимальной длительностью
обработки. Последующее расширение в допустимых пределах для каждой
машины может быть реализовано в рамках вспомогательной модели ЦЛП с
гарантированным решением, что составляет область развития предложенной
методологии.
Отдельно отметим содержательный смысл параметра step в алгорит-
ме 4 — это настраиваемый параметр, соответствующий дискрету формиро-
вания функционального пространства. Так, в частности, при достаточно ма-
лом значении параметра step переменные, соответствующие одному и тому
же требованию i и обработке по одному и тому же ТМ j, будут иметь разли-
чия в длительности транспортировки пропорционально величине параметра
step. Соответственно малые значения параметра step (в экстремальном слу-
чае, равном 1 мин) существенно увеличивают размерность функционального
пространства. В этой связи возникает естественная задача поиска баланса
между величиной параметра step и быстродействием модели в целом (по-
скольку большая размерность функционального пространства влечет значи-
тельное увеличение расхода вычислительных ресурсов).
123
По результатам работы алгоритма 1 (включая вложенные функции алго-
ритмов 2, 3 и 4) будут сформированы массивы параметров переменных мо-
дели ЦЛП. При этом для каждой переменной xi ∈ {0, 1}, i = 1, c определены
idi, pi, numi, mi, si, fi, αi,
где idi — идентификатор работы, для которой производится назначение ма-
шины, pi — обобщенный ТМ, numi — порядковый номер машины в ТМ, mi —
идентификатор машины, si — время начала обработки, fi — время заверше-
ния обработки, αi — коэффициент целевой функции, определяемый в про-
стейшем случае как порядковый номер выбранного обобщенного ТМ.
Важнейшим ограничением в решении задачи оперативного графикования
является выполнение всех работ множества Z. Тогда
∑
(1)
{xi : idi = id, numi
= 1} = 1
i=1
для всех id = 1, z. Условие (1) обеспечивает выбор единственного расширен-
ного ТМ для выполнения каждой работы. Причем признак numi = 1 позво-
ляет избежать конструкции “если, то”, связанной с длиной выбираемого ТМ.
Далее выбранное в ограничении (1) начало ТМ должно быть продолжено
в соответствии с его длиной по количеству машин, т.е.
∑
∑
(2)
{xi : idi = id, pi = p} = l(σ, p) ·
{xi : idi = id, pi = p, numi
= 1}
i=1
i=1
для всех id = 1, z и p = 1, n(σ), где σ = σid. Другими словами, ограничение (2)
призвано “отследить” выбор полного (по количеству машин) ТМ, начало ко-
торого определяется ограничением (1). В то же время ограничение (2) не
противоречит выбору таких xi = xj = 1, что numi = numj = k для некото-
рых k > 1. С целью исключения подобных ошибок введем в рассмотрение
следующие ограничения:
∑
(3)
{xi : idi = id, pi = p, numi
= k} ≤ 1
i=1
для всех id = 1, z, p = 1, n(σ) и k = 2, l(σ, p), где σ = σid.
Таким образом, ввиду ограничений (1) в решение будет выбран единствен-
ный ТМ. Далее ввиду ограничений (2) этот ТМ будет достроен до l(σ, p) по
числу машин. Причем каждая машина k будет выбрана только один раз вви-
ду ограничения (3).
Сформулируем теперь ограничения на производительность машин. При
последовательном назначении работ на одну и ту же машину время на под-
готовку должно быть не менее заданного параметра производительности для
124
соответствующего типа машины, т.е.
∑
{
}
(4)
xi +
xj : mi = mj,|si - fj| ≤ πt
≤1
j=1,j=i
для всех mi = 1, K, где t = τk(σ, p) при k = numi, idi = id, σ = σid, p = pi,
и πt — нормативная длительность подготовки машины типа t. Ясно, что огра-
ничения (4) оказываются избыточными, поскольку некоторые из них могут
быть подмножеством других. Для формирования набора максимальных по
включению ограничений вида (4) может быть использовано простое лекси-
кографическое правило (попарное сравнение двоичных строк длины K, где
каждая строка соответствует ограничению для переменной xi и j-й элемент
строки принимает значение 1, если mj входит в ограничение для xi).
Ограничения на ТО могут быть введены на этапе формирования функ-
ционального пространства посредством обращения в нуль всех переменных,
для которых
∑{
}
(5)
xi : s(ρ) ≤ si ≤ f(ρ),mi = m(ρ)
= 0,
i=1
∑{
}
(6)
xi : si ≤ s(ρ) ≤ fi,mi = m(ρ)
=0
i=1
для всех запланированных ТО ρ ∈ R, где m(ρ) — машина, на которой пла-
нируется ТО, s(ρ), f(ρ) — начало и завершение. Другими словами, для лю-
бых xi таких, что время начала или завершения обработки требования i на
машине mi приходится на период запланированного ТО этой машины, долж-
но выполняться xi = 0. Это условие может быть выполнено как на уровне
формирования множества переменных модели (за счет предварительной про-
верки), так и на уровне ограничений. Последний вариант оказывается более
предпочтительным в условиях модифицированной постановки поиска мак-
симальной совместной подсистемы ограничений, когда часть из них может
быть нарушена в соответствии с установленными приоритетами. Однако та-
кая постановка остается за пределами настоящего исследования и составляет
направление развития.
В общем случае целевым функционалом в задаче оперативного графи-
кования потокового производства выступает показатель энергоэффективно-
сти. Однако с целью декомпозиции задачи и снижения размерности основной
модели в простейшей конфигурации коэффициентами переменных использу-
ются порядковые номера обобщенных ТМ — основной ТМ является более
энергоэффективным по сравнению с альтернативными, причем для каждого
следующего альтернативного ТМ имеет место снижение показателей энер-
гоэффективности обработки. Таким образом, задача состоит в минимизации
125
целевой функции вида
∑
(7)
αi · xi
−→ min
i=1
с ограничениями
⎧
∑
⎪
⎪
{xi : idi = id, numi = 1} = 1,
⎪
⎪
i=1
⎪
⎪
∑
∑
⎪
⎪
{xi : idi = id, pi = p} = l(σ, p) ·
{xi : idi = id, pi = p, numi = 1},
⎪
⎪
i=1
i=1
⎪
⎪
∑
⎪
⎪
{xi : idi = id, pi = p, numi = k} ≤ 1,
⎪
⎪
i=1
⎨
∑
(8)
⎪
xi +
{xj : mi = mj, |si - fj| ≤ πt} ≤ 1,
⎪
⎪
j=1,j=i
⎪
⎪
∑{
}
⎪
⎪
xi : s(ρ) ≤ si ≤ f(ρ),mi = m(ρ)
= 0,
⎪
⎪
i=1
⎪
⎪
∑{
}
⎪
⎪
xi : si ≤ s(ρ) ≤ fi,mi = m(ρ)
= 0,
⎪
⎪
i=1
⎪
⎩xi ∈ {0,1},
где
• id = 1, z — множество требований, подлежащих назначению на после-
довательность машин,
• p = 1,n(σ) — множество обобщенных ТМ для обработки сортамента
σ=σid,
• l(σ,p) — длина ТМ по числу машин,
• k = 1,l(σ,p) — порядковый номер машины в ТМ p,
• t = τk(σ,p) — тип k-й машины в ТМ p,
• πt - нормативная длительность настройки для машины типа t,
• ρ ∈ R — множество запланированных ТО,
• m(ρ) — машина, на которой планируется ТО ρ,
• s(ρ),f(ρ) — начало и завершение ТО ρ.
Для решения задачи (7) с ограничениями (8) может быть использовано любое
прикладное программное обеспечение (ПО) для решения задач математиче-
ского программирования (IBM CPLEX, Analytic Solver VBA Excel, Gurobi,
Google OR-Tools и т.д.) или встроенные библиотеки языков программирова-
ния высокого уровня (Optimization Toolbox, CVXOPT, HeO и др.).
126
4. Вычислительный эксперимент
Модель ЦЛП (7), (8) была реализована на языке Python версии 3.8.5 с
использованием библиотеки PuLP для поиска решения в модуле оперативного
графикования системы планирования потокового производства. Простейшая
схема компонент системы и потоков данных представлена на рисунке, где
[1] запрос параметров суточного задания, передача набора серий разливки
с указанием времени начала разливки, количества плавок, идентифи-
каторов серий;
[2] запрос параметров суточного задания по идентификаторам серий (сор-
тамент стали, цикл разливки, рекомендованный технологический марш-
рут внепечной обработки);
[3] передача параметров суточного задания из внешних систем в базу дан-
ных;
[4] передача параметров суточного задания из базы данных на ВЭБ-
интерфейс Пользователя;
[5] запрос на расчет прогнозного графика, передача набора серий разливки
с указанием начала разливки, количества плавок и параметров суточ-
ного задания;
[6] запрос нормативно-справочной информации по допустимым выдерж-
кам по сортаментам и статистики расходов энергоресурсов в зависимо-
сти от длительности обработки (формирование коэффициентов целево-
го функционала);
[7] передача нормативно-справочной информации из базы данных в модуль
прогнозного графикования;
[8] передача параметров прогнозного графика (перечень плавок с указани-
ем сортамента, выдержки, времени окончания продувки на конвертере
4
4
1
5
6
1
Модуль
прогнозного
графикования
7
2
База
Пользователи
данных
3
8
12
Модуль
9
12
11
оперативного
графикования
10
Схема компонент системы.
127
и начала разливки, рекомендованного технологического маршрута вне-
печной обработки);
[9] запрос нормативно-справочной информации (альтернативные техноло-
гические маршруты внепченой обработки, длительность обработки на
каждой машине в зависимости от сортамента и выдержки, длительность
транпсортировки сталь-ковша с плавкой между агрегатами цеха);
[10] передача нормативно-справочной информации из базы данных в модуль
оперативного графикования;
[11] передача результатов расчета прогнозного и оперативного графиков
(полный маршрут обработки каждой плавки в суточном задании с ука-
занием времени начала и окончания обработки на каждом агрегате,
включая конвертер и машину непрерывного литья);
[12] сохранение результатов расчета прогнозного и оперативного графиков
для последующего отображения (по запросу) и анализа.
Вычислительный эксперимент проводился на персональном компьютере с
характеристиками Intel Core m3 1.2 GHz, 8Gb 1867 MHz LPDDR3, macOS
10.13.6. Входными данными выступили данные о фактически реализованных
сценариях производства, зафиксированных в конвертерном цехе № 2 Ново-
липецкого металлургического комбината (г. Липецк, Россия). Для каждого
зафиксированного суточного задания (по месяцам 2020 и 2021 г.) был предло-
жен оптимизированный график внепечной обработки (оперативный график)
и сравнивались средневзвешенные затраты по расходу энергоресурсов каждо-
го типа в денежном эквиваленте. Результаты проведенного вычислительного
эксперимента частично представлены в табл. 1, 2, где были использованы
следующие обозначения.
• В столбце “Дата” указан день рассматриваемого месяца, для которого
было зафиксировано суточное задание и произведено сравнение затрат
на производство в фактически реализованном сценарии и в оптимизи-
рованном, полученном с помощью разработанной модели ЦЛП.
• В столбцах “F1” и “F2” приводятся значения целевой функции фактиче-
ски реализованного и оптимизированного сценариев соответственно —
суммарный расход на производство всех плавок суточного задания по
типам ресурсов в денежном эквиваленте (в сотнях рублей). Данные зна-
чения рассчитываются по каждой плавке, исходя из маршрута ее обра-
ботки и с учетом заданных средних расходов (например, расход элек-
тродов при нагреве плавки низколегированного сортамента на установке
печь-ковш составляет 25 кг, что в денежном выражении эквивалентно
4644,2 руб).
• В столбце “Δ, %” указана разница между значениями “F1” и “F2”, т.е.
если значение в столбце “Δ, %” отрицательно, то достигнутое значение
функционала в оптимизированном сценарии оказывается больше, чем
для фактически реализованного (это объясняется тем, что в фактиче-
ски реализованных сценариях некоторые технологические ограничения
128
модели могут быть нарушены, что по сути влечет принципиально дру-
гую постановку задачи в части нормативно-справочной информации).
• В столбце “t, с” указано процессорное время в секундах, затраченное на
поиск решения для оптимизированного сценария.
Таблица 1. Май, 2020
Дата F1
F2
Δ, %
t, с
Дата
F1
F2
Δ, %
t, с
01
1961,6
1852,1
5,58
7,11
02
1859,8
1759
5,42
5,20
03
1730,9
1690,2
2,35
3,22
05
1953,4
1843,8
5,61
6,64
06
1816,3
1627,7
10,38
3,92
07
1894,8
1835
3,16
4,64
08
1893,3
1832,8
3,20
9,25
09
1801,9
1717,2
4,70
8,69
10
2162,4
1823,8
15,66
60,75
11
1673,3
1251,6
25,20
1,08
12
1426,8
1101,8
22,78
0,55
13
2921,7
1131,3
61,28
0,74
14
1632,0
931,5
42,92
0,44
15
1364,2
1080,5
20,80
0,88
16
1434,8
1086,9
24,25
0,50
17
1488,4
1133,2
23,86
0,42
18
1527,8
1283,7
15,98
0,74
19
1641,3
1233,4
24,85
0,51
20
1781,4
1383
22,36
0,52
21
1877,2
1704,7
9,19
2,65
22
1820,3
1723,2
5,33
16,07
24
1990,7
2065,5
-3,76
33,47
25
1787,1
1632,2
8,67
34,85
26
1887,2
1925,6
-2,03
10,34
27
1905,0
1770,6
7,06
3,94
28
2136,1
1982,8
7,18
3,71
29
1887,9
1990,8
-5,45
25,17
30
2017,1
1891,7
6,22
26,67
31
2052,3
1935,3
5,70
15,39
Таблица 2. Июнь, 2020
Дата F1
F2
Δ, %
t, с
Дата
F1
F2
Δ, %
t, с
01
2297,0
2205,9
3,97
23,05
02
1952,1
1833,3
6,09
16,67
03
2291,1
1815,4
20,76
7,52
04
2045,3
1659,5
18,86
10,29
05
1997,5
2005,2
-0,39
24,68
06
1915,3
1880,5
1,82
4,63
07
1942,8
2044,4
-5,23
6,93
08
1599,5
1321,3
17,39
5,67
09
1648,8
1299,8
21,17
3,79
10
1786,3
1535,1
14,06
5,11
11
2228,7
1903,2
14,60
32,12
12
1723,8
1507,4
12,55
2,69
13
1483,7
1228
17,23
0,66
14
1554,5
984,9
36,64
0,46
15
1195,7
1030,9
13,78
0,67
16
1104,1
873,9
20,85
0,71
17
1461,5
1123,6
23,12
0,55
18
918,9
748,1
18,59
0,67
19
1692,3
1439,8
14,92
1,71
20
1959,7
1790,9
8,61
20,54
21
1956,8
1566,8
19,93
3,37
22
2305,3
2126,6
7,75
23,25
23
1986,4
1567,8
21,07
24,78
24
1839,5
1807,7
1,73
41,31
25
1732,3
1556
10,18
7,64
26
1721,3
1742,4
-1,23
22,03
27
1921,4
1691,6
11,96
4,98
28
1679,7
1424,8
15,18
13,14
29
1831,0
1462,7
20,11
3,86
30
1963,9
1503,8
23,43
4,13
Таблица 3. Результаты вычислительного эксперимента
Месяц
Avg, % Месяц
Avg, % Месяц
Avg, %
2020, May
13,05
2020, June
13,65
2020, July
9,76
2020, August
8,81
2020, September
11,10
2020, October
18,09
2020, November
9,64
2020, December
19,16
2021, January
9,39
2021, February
13,58
2021, March
10,59
2021, April
18,15
129
Аналогичные расчеты были произведены для периодов с августа по де-
кабрь 2020 г. и с января по апрель 2021 г. В табл. 3 представлены обобщен-
ные результаты по каждому месяцу рассматриваемого периода со средним
значением параметра “Δ, %”, где:
• в столбце “Месяц” указан месяц рассматриваемого периода 2020-2021 гг.,
• в столбце “Avg, %” приводятся значения показателя улучшения целевой
функции в среднем, рассчитанное как среднее арифметическое по всем
значениям “Δ, %” в указанном месяце.
Как видно из табл. 3, разработанная в настоящей статье модель ЦЛП как
математическое обеспечение модуля оперативного графикования системы оп-
тимального планирования потокового производства доставляет существенное
улучшение функционала качества на реальных данных — до 19,16% в среднем
(максимальное значение в столбце “Avg, %” в табл. 3). Экономический эффект
достигается за счет перераспределения машин цеха между требованиями, что
влечет в свою очередь преимущественный выбор основного ТМ для обработ-
ки. Другими словами, в фактическом сценарии по основному ТМ обрабаты-
ваются требования, которые в оптимизированном сценарии были назначены
на альтернативные ТМ. В совокупности это приводит к тому, что суммар-
ный показатель энергоэффективности по суточному заданию в целом ока-
зывается выше в оптимизированном сценарии. Следует также отметить, что
значение имеет не только количественный признак (когда количество требо-
ваний, следующих по основному ТМ, в оптимизированном сценарии больше,
чем в фактическом), но и качественный — если одно из двух фиксирован-
ных требований необходимо подлежит назначению на альтернативный ТМ,
то приоритетным с точки зрения целевого функционала является вариант на-
значения, для которого совокупный расход ресурсов меньше (с учетом сорта-
мента каждого требования). При этом вычислительные затраты оказываются
вполне приемлемыми с точки зрения оперативности функционирования си-
стемы (значения в столбце “t, с” в табл. 1, 2). Таким образом, можно ожидать
высокую эффективность внедрения системы в целом и, в частности, модуля
оперативного графикования, основанного на разработанной модели ЦЛП, в
практику эксплуатации потокового производства.
5. Заключение
В статье исследовалась задача оптимального планирования потокового
производства на этапе оперативного графикования на примере отделения вне-
печной обработки конвертерного цеха сталелитейного производства в отрасли
черной металлургии. Для решения этой задачи была предложена модель це-
лочисленного линейного программирования, в полной мере описывающая все
технологические особенности исследуемых процессов, а также допускающая
гибкую настройку и модификацию системы ограничений и целевого функцио-
нала. Программная реализация предложенной модели была положена в осно-
ву модуля оперативного графикования системы оптимального планирования
130
потокового производства, с использованием которой был проведен масштаб-
ный вычислительный эксперимент на реальных данных. Результаты прове-
денного вычислительного эксперимента демонстрируют высокую эффектив-
ность предложенного подхода и перспективу достижения значительного эко-
номического эффекта от внедрения системы в практику эксплуатации пото-
кового производства.
Дальнейшее развитие тематики связано, в первую очередь, с оснащени-
ем разработанной модели дополнительным функционалом для улучшения
качества получаемых решений за счет увеличения длительности обработки
требований на каждой машине в пределах допустимых интервалов. Другой
функционал, также подлежащий развитию и имплементации в разработан-
ную модель, связан с поиском максимально совместных подсистем ограни-
чений с приоритетами в условиях противоречивости модели в ее исходной
постановке.
Продолжением предложенного подхода к моделированию производствен-
ных задач методами целочисленного линейного программирования являет-
ся исследование смежных задач цеховой логистики, включая транспортное
планирование и управление крановым хозяйством. В таких задачах также ча-
сто имеет место несовместность системы ограничений в исходной постановке.
В этой связи планируемые к исследованию и разработке методы формирова-
ния максимальных совместных подсистем ограничений с приоритетами так-
же могут получить широкое и эффективное приложение.
СПИСОК ЛИТЕРАТУРЫ
1. Лазарев А.А., Мусатова Е.Г. Целочисленные постановки задачи формирования
железнодорожных составов и расписания их движения // Управление большими
системами. 2012. № 38. С. 161-169.
2. Гайнанов Д.Н., Игнатов А.Н., Наумов А.В., Рассказова В.А. О задаче назначе-
ния “технологического окна” на участках железнодорожной сети // АиТ. 2020.
Gainanov D.N., Ignatov A.N., Naumov A.V., Rasskazova V.A. On Track Procession
Assignment Problem at the Railway Network Sections // Autom. Remote Control.
3. Ху Т. Целочисленное программирование и потоки в сетях. М.: Мир, 1974.
4. Ryan D.M., Foster B.A. An Integer Programming Approach to Scheduling. Compu-
ter Scheduling of Public Transport Urban Passenger Vehicle and Crew Scheduling /
Eds. Wren A. Amsterdam: North-Holland, 1981. P. 269-280.
5. Wagner H.M. An Integer Linear-Programming Model for Machine Scheduling //
Nav. Res. Logist. Quart. 1959. V. 6. No. 2. P. 131-140.
6. Pochet Y., Wolsey L.A. Production Planning by Mixed Integer Programming.
Switzerland: Springer Series in Operations Research & Financial Engineering, 2006.
7. Шевченко В.Н., Золотых Н.Ю. Линейное и целочисленное линейное програм-
мирование. Нижний Новгород: Изд-во Нижегород. гос. ун-та им. Н.И. Лобачев-
ского, 2004.
131
8.
Схрейвер А. Теория линейного и целочисленного программирования. М.: Мир,
1991.
9.
Сигал И.Х., Иванова А.П. Введение в прикладное дискретное программирова-
ние. Модели и вычислительные алгоритмы. М.: Физматлит, 2007.
10.
Appa G.M., Pitsoulis L.S., Paul W.H. Handbook on Modeling for Discrete Optimi-
zation. Switzerland: Springer Series in Operations Research & Management Science.,
2006.
11.
Wolsey L.A. Integer Programming. NJ: John Wiley & Sons, 2020.
12.
Hu T.C., Kahng A.B. Linear and Integer Programming Made Easy. Switzerland:
Springer, 2016.
13.
Кабулова Е.Г. Интеллектуальное управление многостадийными системами ме-
таллургического производства // Моделирование, оптимизация и информаци-
онные технологии. 2019. Т. 7. № 1(24). С. 341-351.
14.
Столбов В.Ю., Гитман М.Б., Федосеев С.А. Управление процессом формиро-
вания качества продукции промышленного предприятия // Прикладная мате-
матика и вопросы управления. 2016. № 3. С. 79-98.
15.
Gainanov D.N., Berenov D.A. Algorithm for Predicting the Quality of the Product
of Metallurgical Production // CEUR Workshop Proceedings. 2017. V. 1987.
P. 194-200.
16.
Qiu Y., Wang L., Xu X., Fang X., Pardalos P.M. Scheduling a Realistic Hybrid
Flow Shop with Stage Skipping and Adjustable Processing Time in Steel Plants //
Appl. Soft Comput. 2018. V. 64. P. 536-549.
17.
Kong M., Pei J., Xu J., Liu X., Pardalos P.M. A Robust Optimization Approach for
Integrated Steel Production and Batch Delivery Scheduling with Uncertain Rolling
Times and Deterioration Effect // Int. J. Prod. Res. 2020. V. 58. No. 17. P. 5132-
18.
Long J., Sun Z. et al. A Robust Dynamic Scheduling Approach Based on Release
Time Series Forecasting for the Steelmaking Continuous Casting Production // Appl.
Soft Comput. 2020. V. 92. P. 106271.
19.
Лазарев А.А., Гафаров А.А. Теория расписаний. Задачи и алгоритмы. М.: Наука,
2011.
20.
Brucker P., Knust S. Complex Scheduling. Germany: Springer-Verlag Berlin, 2006.
21.
Mingozzi A., Maniezzo V., Ricciardelli S., Bianco L. An Axact Alforithm for Project
Scheduling with Recource Constraints Based on New Mathematical Formulation //
Management Sci. 1998. V. 44. P. 714-729.
22.
Burkov V.N. Problems of Optimum Distribution of Recources // Control Cibernet.
1972. V. 1. No. 1(2). P. 27-41.
Статья представлена к публикации членом редколлегии А.А. Лазаревым.
Поступила в редакцию 08.11.2022
После доработки 22.02.2023
Принята к публикации 20.03.2023
132
