Genetic algorithm for placing requirements in a flow-type production process planning problem

全文:

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

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

К современным инструментам решения задач среднесрочного планирования производственных процессов относят системы класса APS (Advanced Planning and Scheduling). Среди популярных отечественных систем данного класса можно выделить такие, как AVM.APS, BFG APS, БИА.APS и Аскон Гольфстрим. Из зарубежных разработок класса APS широкое распространение получила Tecnomatix Plant Simulation. Основными методами решения задач оптимизации в данных системах выступают алгоритмы имитационного моделирования и машинного обучения [2–4]. В настоящей статье для решения рассматриваемой комплексной задачи планирования используется система, в основе которой лежат подходы математического программирования [5]. Рассматриваемая комплексная задача планирования производственных процессов потокового типа включает два этапа. На первом этапе для фиксированного по времени и машинам множества требований (работ) формируется график их обработки на основных подготовительных агрегатах. На следующем этапе для фиксированных по времени, машинам и подготовительным агрегатам требований формируется детализированный технологический маршрут. Такой декомпозированный подход обусловлен практическими аспектами рассматриваемого типа производства и, кроме того, позволяет существенно снизить размерности оптимизационных задач, возникающих на каждом этапе. Однако часто уже на первом этапе решения комплексной задачи (назначение подготовительных агрегатов) возникающие оптимизационные модели оказываются несовместными. Природа такой несовместности во многом обусловлена исходным размещением требований по машинам и фиксированным временем начала и длительности их обработки. В этой связи в настоящей статье предлагается рассмотрение вспомогательного этапа размещения требований в целях обеспечения последующей гарантированной разрешимости этапов назначения подготовительных агрегатов и формирования детализированных технологических маршрутов. Для решения задачи размещения требований предлагается генетический алгоритм, реализуемый в качестве автономного модуля системы планирования [5].

Генетические алгоритмы определяют одно из фундаментальных направлений современных исследований в области случайно направленного поиска [6, 7]. Эффективность их применения для решения различных прикладных задач подтверждается многочисленными работами отечественных и зарубежных авторов. Так, например, авторы работы [8] применяют генетические алгоритмы для решения задач размещения, возникающих при проектировании интегральных схем. В [9, 10] генетические алгоритмы предложены для решения задач планирования процесса перевозок на железнодорожном транспорте. В задачах планирования в машиностроении и других серийных производствах также эффективно применяются метаэвристические подходы, в том числе генетические алгоритмы [11, 12]. Обзор различных задач производственного планирования класса RCPSP (Resource Constrained Project Scheduling Problem) и метаэвристические подходы к решению подробно обсуждаются в работах [13, 14]. Также широко распространены гибридные подходы на базе генетических алгоритмов. Например, в работе [15] рассматривается частный случай задачи производственного планирования потокового типа с применением гибридного алгоритма. В [16, 17] для задач с критерием минимизации простоев оборудования предложены эффективные эволюционные алгоритмы. Подходы нечеткой логики развиваются авторами [18] для решения комплексных задач производственного планирования.

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

Постановка задачи

Пусть заданы множество требований S = {s₁, …, s_n} и множество машин $R=\left\{r_1,\dots ,r_m\right\}.$ Для каждого требования определим ρ_i ⊆ R как подмножество машин, доступных для размещения σ_i. С прикладной точки зрения подмножество машин ρ_i определяется технологическими характеристиками требования σ_i. Пусть для каждого σ_i определены также t_i, ${\widehat{\tau }}_i$ – минимально необходимое и максимально допустимое время ожидания с момента подготовки на специализированном агрегате из множества K = {k₁, …, k_l}. Допустимые минимальную и максимальную длительности обработки σ_i на машине из подмножества ρ_i обозначим соответственно через ${\mu }_i, \widehat{{\mu }_i}$ (рис. 1).

 

Рис. 1. Длительность ожидания и время обработки требования σ_i

Fig. 1. Waiting and processing time of requirement σ_i

 

Определим период времени [T₀, T], доступный для размещения требований S по машинам R, где T₀ принимает любое произвольное значение и

$T=T_0+\underset{j=\overline{\mathrm{1,}m}}{\max }\sum _{i=1}^n\left\{\left.{\widehat{\mu }}_i\right|r_j\in {\rho }_i\right\}.$ (1)

Задача размещения требований S по машинам R состоит в построении отображения вида

$f:S\to \left\{\left.\left(r,t,m\right)\right|r\in R,t,m\in {\mathbb{Z}}^{+}\right\},$ (2)

где $f\left({\sigma }_i\right)=\left(r_i,t_i,m_i\right)$, если требование σ_i выполняется на машине r_i с началом в момент времени t_i и продолжительностью m_i, с ограничениями:

• для любого f (σ_i) выполняется r_i ∈ ρ_i;
• для любого f (σ_i) выполняется $T_0-\underset{i=\overline{\mathrm{1,}n}}{\max }\left\{{\widehat{\tau }}_i\right\}\le t_i\le T;$
• для любого f (σ_i) выполняется $m_i\in \left[{\mu }_i,{\widehat{\mu }}_i\right];$
• для любых f (σ_i), $\left.f\left({\sigma }_j\right)\right|r_i=r_j$ выполняется

$\left\{\begin{array}{c}{t}_j\ge t_i+m_i,\text{\hspace{0.33em}если }{t}_i\le t_j,\\ t_i\ge t_j+m_j\text{\hspace{0.33em}иначе. }\end{array}\right.$ (3)

Замечание 1. В расширенной постановке задача (2) может включать также и ограничения на длительность δ_ij подготовки машины r_i = r_j при последовательном назначении требований f (s_i), f (s_j) (рис. 2). Авторы не рассматривают данную группу ограничений ввиду декомпозиции множества $R=\underset{i=1}{\overset{n}{\cup }}{\rho }_i$ в предположении, что длительность подготовки постоянна для требований с идентичными технологическими характеристиками и включена в интервал [t_i, t_i + m_i] для любых f (σ_i), f (σ_j), где r_i = r_j и t_i ≤ t_j.

 

Рис. 2. Длительность подготовки при последовательном назначении требований

Fig. 2. Preparation time for sequential assignment of requirements

 

Замечание 2. В случае l ≤ m задача размещения требований на горизонте [T₀, T], где T определяется по правилу (1), становится тривиальной с точки зрения поиска допустимого отображения вида (2) и может быть решена жадным алгоритмом. В этой связи далее будем полагать, что $l\le ⌈\frac{m}{2}⌉$, где

 

$⌈\frac{m}{2}⌉=\underset{x\in \mathbb{Z}}{\min }\left\{\left.x\right|x\ge \frac{m}{2}\right\}.$

В настоящей работе в качестве критерия оптимизации размещения вида (2) рассматривается потенциальная загрузка агрегатов подготовки требований. Такой подход связан с тем, что практические задачи размещения требований, как правило, рассматриваются отдельно от задач назначения подготовительных агрегатов и последующих машин обработки. Так, в частности, время начала выполнения требования σ_i на машине r выступает входными данными и фиксировано для задачи о назначении агрегатов подготовки (рис. 3 (пунктирной линией обозначены возможные варианты назначения агрегата k для подготовки фиксированного требования σ_i)).

 

Рис. 3. Задача о назначении подготовительных агрегатов

Fig. 3. Problem of assigning preparation units

 

В работе [19] для решения задачи о назначениях подготовительных агрегатов разрабатывается модель целочисленного линейного программирования (ЦЛП).

Далее время завершения подготовки требования σ_i на агрегате k, а также время начала выполнения на машине r выступают входными данными и фиксированы для задачи о формировании детализированных технологических маршрутов (рис. 4 (пунктирной линией обозначены варианты назначения машин a₁ и a₂ для обработки фиксированного требования σ_i)).

 

Рис. 4. Задача о формировании детализированных технологических маршрутов

Fig. 4. Problem of forming detailed technological routes

 

Для задачи формирования детализированных технологических маршрутов в работе [20] также предлагаются каскадная схема и модели ЦЛП. Важным обстоятельством при этом является то, что уже на этапе назначения подготовительных агрегатов для фиксированного множества требований система ограничений может оказаться несовместной. Именно в этой связи, то есть для снижения рисков противоречивости входных данных, этап размещения требований выделяется в самостоятельную задачу.

Обозначим через F множество всех возможных назначений вида (2), и для каждого f ∈ F определим множество I_f следующим образом:

$I_f=\underset{i=1}{\overset{n}{\cup }}\left\{t_i-{\widehat{\tau }}_i;t_i-{\tau }_i\right\}.$ (4)

Другими словами, множество I_f есть множество точек пересечения интервалов $\left[t_i-{\widehat{\tau }}_i; t_i-{\tau }_i\right]$, а также точек концов интервалов по всем требованиям σ_i ∈ S. Например, для $S=\left\{{\sigma }_1,{\sigma }_2\right\}$ и $f\left({\sigma }_1\right),$ $f\left({\sigma }_2\right)$, таких, что $\left[t_2-{\widehat{\mu }}_2;t_2-{\tau }_2\right]\subset \left[t_1-{\widehat{\tau }}_1;t_1-{\tau }_1\right],$ множество I_f примет вид

$I_f=\left\{t_1-{\widehat{\tau }}_1,t_2-{\widehat{\tau }}_2,t_2-{\tau }_2,t_1-{\tau }_1\right\}.$

Пусть длительность подготовки любого требования σ_i ∈ S постоянна для всех агрегатов k₁, …, k_l и равна λ. Для любых f ∈ F и $d^k\in I_f,k=\overline{\mathrm{1,}\left|I_f\right|-1}$, определим величину

$L\left(d^k,f\right)=\frac{\left|d^{k+1}-d^k\right|l}{\lambda \left|\left\{f\left({\sigma }_i\right):d^k\le t_i<d^{k+1}\right\}\right|}$ (5)

и критерий

$P\left(f\right)=\underset{k=\overline{\mathrm{1,}\left|I_f-1\right|}}{\max }\left\{L\left(d^k,f\right)\right\}.$ (6)

Величина (5) по сути отражает количество требований, потенциально задействующих каждый из l агрегатов подготовки в момент времени d^k. При этом ясно, что внутри интервала [d^k, d^k+1] значение (5) не меняется, чем и обусловлено его вычисление только в точках из множества I_f. Таким образом, для заданных S, R, K и [T₀, T] задача размещения требований S по машинам R может быть сведена к оптимизационной задаче поиска отображения вида (2), такого, что

$P\left(f\right)\to \underset{f\in F}{\min }$. (7)

Для решения задач (2) и (7) разработан генетический алгоритм.

Генетический алгоритм размещения требований

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

Пусть заданы множество требований S = {σ₁, …, σ_n}, период планирования [T₀, T] и множество подготовительных агрегатов K = {k₁, …, k_l} с фиксированной длительностью λ(k₁) = … = λ(k_l) = λ для подготовки любого требования σ_i ∈ S. Под особью, или представителем популяции, будем понимать назначение вида f(S) = = {f(σ₁), …, f(σ_n)}. При этом различными генами особи f(S) являются назначения вида f (σ_i) = (r_i, t_i, m_i). Обозначим через Fⁱ популяцию для i-й итерации алгоритма, где

Fⁱ = {f₁(S), f₂(S), …}.

Определим следующий набор параметров генетического алгоритма:

• размерность K₁ для начальной популяции F⁰;
• отбор K₂ представителей популяции в порядке возрастания значения критерия (6);
• формирование K₃ потомков для каждой пары отобранных представителей;
• мутация K₄ генов;
• ограничение τ (мин.) для процедуры мутации генов;
• критерий останова по совокупному числу K₅ эпох;
• критерий ε (%) улучшения целевого функционала для последовательных итераций алгоритма;
• критерий останова по числу K₆ эпох (итераций алгоритма) без улучшения целевого функционала.

Далее при описании алгоритмов после символа // дается комментарий к соответствующей строке.

Генетический алгоритм размещения требований:

1. Выполнить процедуру формирования начальной популяции F⁰ из K₁ особей
2. k = 0, c = 0 // счетчики совокупного числа эпох и числа эпох без улучшения целевого функционала
3. Выполнить процедуру отсечения популяции F⁰
4. Пока k ≠ K₅ или c ≠ K₆
5. Выполнить процедуру отбора K₂ представителей текущей популяции F^k в порядке возрастания критерия (6)
6. Выполнить процедуру скрещивания всех $\frac{K_2\cdot \left(K_2-1\right)}{2}$ пар представителей, отобранных на шаге 5 // увеличить счетчик числа эпох, включить в новую популяцию лучшего представителя текущей и сформировать K₃ представителей-потомков для каждой пары
7. Выполнить процедуру мутации генов
8. Выполнить процедуру отсечения текущей популяции F^k
9. Вернуть $f:P\left(f\right)\to \underset{f\in F^k}{\min }$ // наилучший по критерию (6) представитель текущей популяции
10. Если минимальное значение критерия (6) на шаге 5 отклоняется от значения на шаге 9 менее, чем на ε (%), то
11. Увеличить счетчик числа эпох без улучшения целевого функционала

Рассмотрим подробнее этапы данного генетического алгоритма.

Процедуры формирования начальной популяции и отсечения

Для формирования начальной популяции F⁰ размещение f (S) требований производится случайным образом посредством выбора некоторых значений для машины, времени начала и длительности обработки из числа допустимых. Далее будем полагать, что время T₀, T определяются целым числом в формате timestamp (ts). Время t_i начала обработки каждого требования также будем определять в формате ts, а длительность обработки m_i – в формате целого числа (количество минут).

Алгоритм 1. Процедура формирования начальной популяции

1. F⁰ = {}
2. Для всех $k=\overline{\mathrm{1,}n}$ // количество особей n = K₁
3. f_k(S) = {}
4. Для всех σ_i ∈ S
5. $t_i=Rnd\left(T_0,T\right)$ // случайное число в диапазоне от T₀ до T
6. $m_i=Rnd\left({\mu }_i,{\widehat{\mu }}_i\right)$
7. $r_i=Rnd\left(\mathrm{1,}\left|{\rho }_i\right|\right)$
8. $f\left({\sigma }_i\right)=\left(r_i,t_i,m_i\right)$
9. $f_k\left(S\right)=f_k\left(S\right)+\left\{f\left({\sigma }_i\right)\right\}$ // сформировать ген f (s_i) для текущей особи f_k(S)
10. $F^0=F^0+\left\{f_k\left(S\right)\right\}$
11. Вернуть $F^0=\left\{f_1\left(S\right),\dots ,f_n\left(S\right)\right\}$

Фрагмент начальной популяции из двух особей с пятью генами отображен на рисунке 5. Например, для требования σ₁ на итерации k = 1 внешнего цикла алгоритма 1 установлена машина обработки r₁ = r¹, а на итерации k = 2 машина r₁ = r². Аналогично для итераций k = 1 и k = 2 на рисунке 5 представлены различные значения для t₁ и m₁ и т.д. для всех рассматриваемых требований ${\sigma }_i,i=\overline{\mathrm{1,5}}$.

 

Рис. 5. Фрагмент начальной популяции

Fig. 5. Initial population fragment

 

Таким образом, в строках 5–7 алгоритма 1 для каждого требования σ_i ∈ S выбираются произвольные время начала t₁ ∈ [T₀, T], длительность $m_i\in \left[{\mu }_i,{\widehat{\mu }}_i\right]$ и машина обработки r₁ ∈ ρ_i. При этом ясно, что некоторые особи f (S) ∈ F⁰ могут оказаться противоречивыми с точки зрения ограничений (3) задачи (2) (время начала и длительность обработки требований σ_i, σ_j при их последовательном размещении на одну и ту же машину r_i = r_j). На рисунке 6 представлен пример особи f (S) с противоречивыми генами f (σ₁) и f (σ₂), такими, что r₁ = r₂, t₁ < t₂ и t₁ + m₁ > t₂.

 

Рис. 6. Пересечение требований

Fig. 6. Intersection of requirements

 

Процедура отсечения популяции выполняется для начальной популяции и на каждой итерации внешнего цикла генетического алгоритма, обеспечивая тем самым рассмотрение только допустимых назначений вида (2). При этом размерность текущей популяции после выполнения процедуры отсечения во многом определяется значениями параметров K₁ и K₂ алгоритма. Так, в случае тенденции вымирания соответствующие параметры могут быть существенно увеличены в целях стабилизации размерности.

Алгоритм 2. Процедура отсечения популяции

1. Для всех $f\left(S\right)\in F^k$
2. Для всех $f\left({\sigma }_i\right)\in f\left(S\right)$ // по всем парам различных генов
3. Для всех $\left.f\left({\sigma }_j\right)\in f\left(S\right)\right|{\sigma }_i\ne {\sigma }_j$
4. Если r_i = r_j и t_j ≤ t_i и t_i + m_j > t_i то // ограничения (3) нарушены
5. $F^k=F^k-\left\{f\left(S\right)\right\}$ // исключить особь из текущей популяции
6. Выход из цикла
7. Если r_i = r_j и t_i < t_j и t_j + m_j > t_i то
8. F^k = F^k – { f (S)}
9. Выход из цикла
10. Вернуть F^k

Процедура отбора представителей

Рассмотрим начальную популяцию:

$F^0=\left\{f_1\left(S\right),f_2\left(S\right),\dots \right\},$

где

$f_j\left(S\right)=\left\{f_j\left({\sigma }_1\right),f_j\left({\sigma }_2\right),\dots \right\}$ для всех j = 1, 2, ...

и

$f_j\left({\sigma }_i\right)=\left(r_i,t_i,m_i\right)$ для всех σ_i ∈ S .

Напомним, что любое размещение требований f_j (S) ∈ F⁰ является допустимым с точки зрения ограничений задачи (2) ввиду структуры алгоритма 1 и с учетом выполнения процедуры отсечения согласно алгоритму 2.

Для каждого представителя f_j (S) ∈ F⁰ определим множество (4) и значение критерия (6) при фиксированных l и λ для рассматриваемого количества подготовительных агрегатов и длительности подготовки каждого требования соответственно. На рисунке 7 приведен пример множества I_f для некоторого представителя f (S) с пятью генами $f\left({\sigma }_i\right),i=\overline{\mathrm{1,5}}$ – точки на верхней горизонтальной прямой.

 

Рис. 7. Множество I_f

Fig. 7. Set I_f

 

Аналогично множество I_f и значение критерия (6) могут быть определены для представителей любой популяции F^k (условие допустимости всех представителей f_j (S) произвольной популяции F^k с точки зрения ограничений задачи (2) будут обоснованы несколько позже на этапе обсуждения процедуры мутации генов).

Алгоритм 3. Процедура отбора представителей

1. Для всех f_j (S) ∈ F^k
2. f = f_j (S)
3. Сформировать множество точек $I_f=\left\{d^1,d^2,\dots \right\}$
4. Для всех $d^n\in I_f$ // $n=\overline{\mathrm{1,}\left|I_f\right|-1}$
5. $L\left(d^n,f\right)=\frac{\left|d^{k+1}-d^k\right|l}{\lambda \left|\left\{f\left({\sigma }_i\right)\in f:d^k\le t_i<d^{k+1}\right\}\right|}$
6. $L_j=\underset{n}{\max }\left\{L\left(d^n,f\right)\right\}$
7. Вернуть {L₁, L₂, …}
8. Отсортировать F^k в порядке возрастания значений L_j ее представителей: $\left\{f_{j_1}\left(S\right),\right\}$, $\left\{f_{j_1}\left(S\right),f_{j_2}\left(S\right),\dots \right\},$ где $L_{j_1}\le L_{j_2}\le \dots$
9. Вернуть $F^k=\left\{f_{j_1}\left(S\right),\dots ,f_{j_n}\left(S\right)\right\}$ // n = K₂
10. Вернуть $f^{*}=f_{i_1}\left(S\right)$ // наилучший представитель текущей популяции

Процедуры скрещивания и мутации

Рассмотрим популяцию $F^k=\left\{f_{j_1}\left(S\right),\dots ,f_{j_n}\left(S\right)\right\}$, построенную в результате выполнения алгоритма 3 как подмножество n = K₂ лучших представителей по критерию (6). Для каждой пары представителей f_i(S), f_j(S) ∈ F^k гены представителя-потомка f (S) определяются посредством прямого наследования от случайным образом выбранного родителя f_i (S) или f_j (S). На рисунке 8 приведен пример формирования представителя потомка f (S) для родителей f₁(S), f₂(S) с генами $f\left({\sigma }_i\right),i=\overline{\mathrm{1,5}}$, где гены $f\left({\sigma }_i\right),i=\overline{\mathrm{1,3}}$, наследуются от родителя f₁(S) и гены $f\left({\sigma }_i\right),i=\overline{\mathrm{4,5}}$, от родителя f₂(S) соответственно.

 

Рис. 8. Представитель-потомок f (S)

Fig. 8. Descendant representative f (S)

 

Алгоритм 4. Процедура скрещивания

1. $F=F^k,k=k+\mathrm{1,}{F}^k=\left\{f^{*}\right\}$
2. Для всех $f_i\left(S\right)\in F,i=\overline{\mathrm{1,}n}$ // n = K₂
3. Для всех $f_j\left(S\right)\in F,j=\overline{i+\mathrm{1,}n}$ // для всех пар родителей
4. Для всех $l=\overline{\mathrm{1,}m}$ // сформировать m = K₃ потомков
5. f_l (S) = {}
6. Для всех σ ∈ S
7. $p=Rnd\left(\mathrm{0,1}\right)$
8. Если p ≤5 то
9. $f\left(\sigma \right)=f_i\left(\sigma \right)$ // наследовать текущий ген от родителя f_i (S)
10. Иначе
11. $f\left(\sigma \right)=f_j\left(\sigma \right)$
12. $f_l\left(S\right)=f_l\left(S\right)+\left\{f\left(\sigma \right)\right\}$
13. $F^k=F^k+\left\{f_l\left(S\right)\right\}$
14. Вернуть F^k, k

На шаге 1 алгоритма 4 формируется новая популяция F^k, в состав которой включается наилучший по критерию (6) представитель f ^* предшествующей популяции F. Данная процедура обеспечивает сохранение на каждой итерации текущего локально оптимального решения и последующий контроль числа K₆ итераций без существенного улучшения целевого функционала – параметр ε (%) алгоритма.

Для каждого представителя текущей популяции f (S) ∈ F^k случайным образом выбранные K₄ генов f (σ) мутируют в части времени начала и длительности исполнения соответствующего требования σ ∈ S по процедуре, описанной в алгоритме 1.

Алгоритм 5. Процедура мутации генов

1. Для всех f (S) ∈ F^k
2. Для всех $i=\overline{\mathrm{1,}n}$ // мутация n = K₄ случайно выбранных генов
3. $j=Rnd\left(\mathrm{1,}\left|S\right|\right)$ // выбор произвольного σ ∈ S
4. $t_j=t_j+Rnd\left(-\tau ,\tau \right)$
5. $f\left({\sigma }_j\right)=\left(r_j,t_j,m_j\right)$
6. Вернуть F^k

Аналогично алгоритмам 1 и 2 структура алгоритма 5 и последующий вызов процедуры отсечения в строке 8 генетического алгоритма обеспечивают допустимость любого размещения требований f (S) ∈ F^k с точки зрения ограничений задачи (2).

Вычислительный эксперимент

Предложенный генетический алгоритм размещения требований, включая процедуры, описанные в алгоритмах 1–5, были реализованы на языке Python 3.8 как автономный модуль комплексной системы планирования производственных процессов потокового типа [2]. Анализ эффективности применения генетического алгоритма на предварительном этапе решения комплексной задачи проводится в двух направлениях: с точек зрения оптимизации входных данных для задачи о назначении подготовительных агрегатов (в случае ее исходной противоречивости) и трудоемкости этой задачи (в случае наличия решения для исходной постановки). Общая структура вычислительного эксперимента представлена на рисунке 9.

 

Рис. 9. Структура вычислительного эксперимента

Fig. 9. Computational experiment structure

 

Вычислительный эксперимент был проведен на реальных производственных данных. Рассматриваются годовой период и множество требований S = {σ₁, …, σ_n}, подлежащих исполнению в каждые сутки рассматриваемого периода. Таким образом, для каждого экземпляра входных данных период планирования [T₀, T] составляет 24 часа. Множество S содержит n = 100 требований с параметрами:

• $30\le {\tau }_i<{\widehat{\tau }}_i\le 180$ (мин.),
• $30\le {\mu }_i<{\widehat{\mu }}_i\le 60$ (мин.),
• ρ_i = R

для всех $i=\overline{\mathrm{1,100}}$, где $R=\left\{r_j\right\},j=\overline{\mathrm{1,5}}$ – множество машин, доступных для исполнения требований множества S. Для множества подготовительных агрегатов $K=\left\{k_l\right\},l=\overline{\mathrm{1,3}},$ длительность обработки каждого требования фиксированная и составляет λ = 40 (мин.).

Определим параметры генетического алгоритма:

• размерность начальной популяции K₁ = 1 000 представителей;
• отбор K₂ = 30 представителей популяции в порядке возрастания значения критерия (6);
• формирование K₃ = 50 потомков для каждой пары отобранных представителей;
• мутация K₄ = 2 гена;
• ограничение τ = 5 (мин.) для процедуры мутации генов;
• критерий останова по числу K₅ = 10 эпох (итераций алгоритма) без улучшения целевого функционала;
• критерий ε = 10 (%) улучшения целевого функционала для последовательных итераций алгоритма;
• критерий останова по совокупному числу K₆ = 500 эпох.

Замечание 3. Если размерность популяции на некоторой итерации алгоритма не превышает значение параметра K₂ = 30, то процедура формирования K₃ = 50 потомков производится для каждой пары представителей соответствующей популяции.

На рисунке 10 показано соотношение величины [5] в каждой точке множества I_f соответственно для размещения, сформированного посредством жадного алгоритма (см. поток [1] на рисунке 9), и для размещения, построеннного с использованием генетического алгоритма (см. потоки [6] и [7] на рисунке 9).

 

Рис. 10. Значение L(d^k, f) для точек множества I_f

Fig. 10. The value of L(d^k, f) for the points of set I_f

 

В среднем значение величины L(d^k, f) (потенциальная нагрузка на подготовительные агрегаты) составляет 0,6 в обоих случаях. Однако разброс значений по всем точкам d^k ∈ I_f для размещения, построенного с использованием генетического алгоритма, существенно меньше и равен [0, 35;0, 83] по сравнению с [0, 3;1, 39] соответственно для размещения, сформированного посредством жадного алгоритма.

В примере на графике значение максимума потенциальной нагрузки на подготовительные агрегаты (6) составляет 1,39 и 0,83 для жадного и генетического алгоритмов соответственно. Аналогичные расчеты были проведены для каждого экземпляра входных данных в рассматриваемом годовом периоде. Результаты сравнительного анализа по критерию (6) представлены на графике (http://www.swsys.ru/uploaded/image/2025-1/25.jpg).

Диапазон значений критерия (6) в случае размещения, сформированного посредством жадного алгоритма, составляет [1, 01;2, 8] со средним значением 1,91. В то же время для размещения, построенного с использованием генетического алгоритма, диапазон значений критерия (6) составляет [0, 8;1, 27] со средним значением 1,07.

На последующем этапе назначения подготовительных агрегатов (см. потоки [2] и [8] на рисунке 9) фиксировалось время в минутах, затраченное системой на поиск решения. Для случаев, когда решение не было найдено, данный показатель принимался равным 0 (см. потоки [3] и [5] на рисунке 9). Проведен анализ данного показателя временных затрат для каждого экземпляра входных данных в рассматриваемом годовом периоде (http://www.swsys.ru/uploaded/image/2025-1/26.jpg).

Можно сделать вывод, что решения нет во всех случаях, когда значение критерия (6) превышает 2,1. Доля таких случаев для размещения, построенного с использованием жадного алгоритма, составляет 40 %, а для размещения, сформированного посредством генетического алгоритма, значение критерия (6) не превышает 1,27 в 100 % случаев. В 60 % случаев, когда решение было найдено для размещения, построенного по жадному алгоритму, время поиска решения варьируется в диапазоне [2, 01;6, 96] со средним значением 2,71 мин. Для размещения, построенного по генетическому алгоритму, диапазон времени поиска решения на этапе назначения подготовительных агрегатов составляет [1;2, 92] со средним значением 1,97 мин.

Из результатов проведенного вычислительного эксперимента следует, что применение генетического алгоритма на этапе размещения требований существенно снижает критерий максимальной потенциальной нагрузки на подготовительные агрегаты по сравнению с решением данного этапа посредством жадного алгоритма. Последующий этап назначения подготовительных агрегатов оказывается разрешимым в 100 % случаев в рассматриваемом годовом периоде, в то время как для жадного размещения в 40 % случаев решение не найдено. Наконец, сравнительный анализ временных затрат демонстрирует потенциал ускорения в среднем до 27 % в случаях, когда для жадного размещения найдено решение на этапе назначения подготовительных агрегатов.

Заключение

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

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

作者简介

Andrey Kibzun

Institute of Computer Sciences and Applied Mathematics, Moscow Aviation Institute (National Research University) (MAI)

Email: kibzun@mail.ru

Dr.Sci. (Physics and Mathematics), Professor, Head of Chair

俄罗斯联邦, Moscow, 125993

Varvara Rasskazova

Institute of Computer Sciences and Applied Mathematics, Moscow Aviation Institute (National Research University) (MAI)

编辑信件的主要联系方式.
Email: varvara.rasskazova@mail.ru

Cand. of Sci. (Physics and Mathematics), Associate Professor

俄罗斯联邦, Moscow, 125993

参考

补充文件