Development and implementation of software tools for regression testing of algorithms in solving production planning problems

Full Text

Введение

Вопросы решения оптимизационных задач производственного планирования широко обсуждаются в современной научной литературе. Они относятся, как правило, к классу NP-трудных, что обуславливает применение эвристических процедур для их решения. В работах [1-5] обсуждаются вопросы применения гибридных алгоритмов и алгоритмов, основанных на методах машинного обучения. Для задач небольшой размерности предлагаются подходы, основанные на методах целочисленного линейного программирования [6, 7]. Значительный вклад внесли работы Нижегородской школы по вопросам распределения производственных ресурсов для высокотехнологичных предприятий [8-17]. В работах [15, 16] описана разработанная и программно реализованная система производственного планирования СМАРТ-ресурс, предназначенная для решения задач распределения производственных ресурсов при автоматизации процесса изготовления высокотехнологичных изделий, свойственных предприятиям машиностроительного дивизиона ГК «Росатом».

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

Содержательное описание объекта

Заданы множество операций, выполнение которых необходимо спланировать, и множество ресурсов предприятия. На множестве операций задано отношение предшествования (операция не может быть выполнена до тех пор, пока не будут выполнены все предшествующие). Данное отношение предшествования определяет технологический процесс (технологию) заказа. Для каждой из операций задана длительность выполнения и необходимый для выполнения ресурс. Каждая операция выполняется без прерывания. Каждый из ресурсов в каждый из тактов времени может использоваться не более чем одной операцией. Множество операций разбито на заказы, для каждого из которых заданы ранее время начала (время, раньше которого запрещено выполнение операций заказа) и директивный срок (время, к которому необходимо стремиться завершить выполнение операций заказа).

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

Математическая модель и постановка задачи

Исходные параметры математической модели:

{1, ..., n} – множество операций;

{1, ..., m}  – множество ресурсов;

{1, ..., k}  – множество заказов;

{1, ..., T}  – множество тактов планирования;

V_l – множество операций заказа l, $l=\overline{\mathrm{1,}k}$;

при этом ${\cup }_{l=1}^k{V}_l=\left\{\mathrm{1,}\dots ,n\right\}$, $V_{l\text{'}}\cap V_{l^{\text{'}\text{'}}}=\varnothing ,l^{\text{'}},l^{\text{'}\text{'}}\in \left\{\mathrm{1,}\dots ,n\right\}$ и $l^{\text{'}}\ne l^{\text{'}\text{'}}$;

$G_l=\left(V_l,A_l\right)$, $A_l\subseteq V_l^2$ – граф без петель и контуров, определяющий технологию заказа l, $l=\overline{\mathrm{1,}k}$;

$t_i\in N$ – длительность операции i, $i=\overline{\mathrm{1,}n}$;

$r_i\in \left\{\mathrm{1,}\dots ,m\right\}$ – необходимый для выполнения операции i ресурс, $i=\overline{\mathrm{1,}n}$;

$t_l^{р}, t_l^{д}$ – ранее начало и директивный срок заказа l, $l=\overline{\mathrm{1,}k}$.

Варьируемые параметры математической модели:

$x_i\in \left\{\mathrm{1,}\dots ,T\right\}$ – время начала выполнения операции i, $i=\overline{\mathrm{1,}n}$

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

$x_i\in \left\{\mathrm{1,}\dots ,T\right\},i=\overline{\mathrm{1,}n},$ (1)

$x_i\ge t_l^{\text{р}},i\in V_l,l=\overline{\mathrm{1,}k},$ (2)

$x_{i\text{'}}+t_{i\text{'}}\le x_i,i^{\text{'}}:\left(i^{\text{'}},i\right)\in A_l,i\in V_l,l=\overline{\mathrm{1,}k},$ (3)

$\left|\left\{i\text{|}{r}_i=j,x_i\le t\le x_i+t_i\right\}\right|\le \mathrm{1,}t=\overline{\mathrm{1,}T},j=\overline{\mathrm{1,}m}.$ (4)

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

$\sum _{l=1}^k\text{max}\left(\mathrm{0,}\underset{i\in V_l}{\max }\left(x_i+t_i-t_l^{\text{д}}\right)\right)\to min.$

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

Общая структура алгоритма

Для удобства обозначим:

• l(i) – номер заказа, содержащего операцию i, т.е. $l\left(i\right)\in \left\{\mathrm{1,}\dots ,k\right\}$, что $i\in V_{l\left(i\right)}$, $i=\overline{\mathrm{1,}n}$;
• p(i) – множество операций, непосредственно предшествующих операции i, т.е. $p\left(i\right)=\left\{i^{\text{'}}\right|\left(i^{\text{'}},i\right)\in A_{l\left(i\right)}\}$, $i=\overline{\mathrm{1,}n}$.

Общая структура фронтального алгоритма [8, 9]

Шаг 1. $x_i:=\mathrm{0,} i=\overline{\mathrm{1,}n}, t:=1$. $\to$ Шаг 2.

Шаг 2. $F\left(t\right)\text{:={}i\text{|}$   

$x_i=0 и$

$t\ge t_{l\left(i\right)}^{н} и$

$x_{i^{\text{'}}}>\mathrm{0,} i^{\text{'}}\in p\left(i\right)$ и

$\left|\left\{i^{\text{'}}\text{|}{i}^{\text{'}}\in \left\{\mathrm{1,}\dots ,n\right\},x_{i^{\text{'}}}>\mathrm{0,}{x}_{i^{\text{'}}}\le t\le x_{i^{\text{'}}}+t_{i^{\text{'}}},r_i=r_{i^{\text{'}}}\right\}\right|=0\}$.

$\to$ Шаг 3.

Шаг 3. Для каждой операции $i\in F\left(t\right)$ выполнить:

{  

Если $\left|\left\{i^{\text{'}}\text{|}{i}^{\text{'}}\in \left\{\mathrm{1,}\dots ,n\right\},x_{i^{\text{'}}}>\mathrm{0,}{x}_{i^{\text{'}}}\le t\le x_{i^{\text{'}}}+t_{i^{\text{'}}},r_i=r_{i^{\text{'}}}\right\}\right|=0$,

то $x_i:=t$.

}

$\to$ Шаг 4.

Шаг 4. $t:=t+1$.

Если $t\le T$ или $\exists i:x_i=0$, то $\to$Шаг 2, иначе завершить.

Комментарии:

• на шаге 1 происходит инициализация переменных;
• на шаге 2 строится фронт операций F(t), т.е. множество операций, удовлетворяющих условиям:
• операция в данный момент не запланированы (условие $x_i=0$),
• текущий такт времени t больше или равен раннего времени начала заказа операции (условие $t\ge t_{l\left(i\right)}^{н}$),
• все предшествующие операции уже запланированы (условие $x_{i^{\text{'}}}>\mathrm{0,} i\text{'}\in p\left(i\right)$),
• необходимый для операции ресурс в текущий такт времени t свободен (условие $\left|\left\{i^{\text{'}}\text{|}{i}^{\text{'}}\in \left\{\mathrm{1,}\dots ,n\right\},x_{i^{\text{'}}}>\mathrm{0,}{x}_{i^{\text{'}}}\le t\le x_{i^{\text{'}}}+t_{i^{\text{'}}},r_i=r_{i^{\text{'}}}\right\}\right|=0$);
• на шаге 3 по очереди назначаются на выполнение операции, для которых необходимый ресурс свободен на текущем такте времени t (данное условие дублирует условие на шаге 2, так как операции текущего фронта могу занять данный ресурс);
• на шаге 4 происходит переход к следующему такту планирования и проверяется условие останова.

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

Стратегии сортировки фронта

С целью повышения качества работы фронтального алгоритма могут быть использованы различные стратегии сортировки. Таким образом, на шаге 2 фронтального алгоритма фронт представляется в виде $F\left(t\right)=\left\{i_1^t,\dots ,i_{n_t}^t\right\}$, и операции фронта выбираются в соответствующем порядке. В качестве стратегии может быть рассмотрена, например, сортировка по директивному сроку соответствующего заказа: $t_{l\left(i_s^t\right)}^{\text{д}}\le t_{l\left(i_{s+1}^t\right)}^{\text{д}},s=\overline{\mathrm{1,}{n}_t-1}.$ Возможна сортировка по незавершенному объему работ заказа, доле незавершенного объема работ от общего объема работ заказа, оценкам резервов времени и т.д.

Итерационный фронтальный алгоритм

Фронтальный алгоритм может вызываться итерационно, определяя рекорд среди решений итераций фронтального алгоритма. В данном случае стратегия сортировки должна быть вариативной (меняться на различных итерациях запуска фронтального алгоритма). Пример такой вариативной стратегии – рандомистическая сортировка, оценка «важности» заказа с точки зрения его нарушений директивных сроков, которые вычисляются, исходя из решений предыдущих итераций [10].

Оптимизация фронтального алгоритма

Предложенная структура фронтального алгоритма обладает экспоненциальной трудоемкостью, поскольку число вызовов шага 2 составляет . C целью построения полиномиального по сложности алгоритма необходимо на шаге 4 итерировать не каждый такт времени, а только такты, соответствующие событиям, где событиями являются ранние времена начала партий, момента завершения операций (данные события формируются динамически при назначении новых операций). При таком подходе число вызовов шага 2 будет составлять $\text{O}\left(\text{n}\right)+\text{O}\left(\text{k}\right)$.

Регрессионное тестирование алгоритмов решения  задач производственного планирования

Разработанная система регрессионного тестирования [17] позволяет запускать фронтальный алгоритм на наборе тестовых задач и оценивать показатели качества работы алгоритмы с точки зрения целевых показателей. Система позволяет решать две основные задачи: отслеживать прогресс при модификациях алгоритма и оптимизировать гиперпараметры алгоритма.

Характеристика разработанного программного обеспечения

Программное обеспечение реализовано на языке Java и предназначено для выполнения в операционных системах Windows и Linux с установленной Java машиной openjdk 12 и выше. При реализации графического интерфейса пользователя применялся инструментарий JAVA Swing.

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

В данном разделе представлены результаты вычислительного эксперимента по сравнению результатов расчета с использованием различных настроек алгоритма на задаче размерности более 500 тыс. операций, предназначенных для выполнения более 28 тыс. составных частей. В силу размерности ручной анализ результатов расчета при различных настройках для таких задач затруднен, однако анализ может быть оперативно проведен благодаря разработанному ПО.

В табл. 1 представлены характеристики рассматриваемой задачи. В табл. 2 представлены настройки алгоритмов, применяемых для решения задачи, и представлены количественные характеристики результатов решения, полученные при помощи разработанного ПО, предназначенные для последующего анализа.

 

Таблица 1.  Характеристики задачи

Table 1. Task characteristics

Характеристика	Значение
Начало интервала планирования	01.01.2025
Конец интервала планирования	01.01.2125
Количество заказов	6
Общее количество партий (заказы, изделия, составные части изделий)	28 586
Минимальная трудоемкость партии	9 ч 15 м 0 с
Максимальная трудоемкость партии	5 дней 1 ч 45 м 0 с
Количество партий с директивными сроками	28 586
Количество различных приоритетов партий	2
Средняя глубина вложенности изделий	5
Среднее количество вложенных изделий	6
Количество операций	500 005
Суммарная длительность операций	45568 дней 13 ч 15 м 0 с
Средняя длительность операции	2 ч 11 м 14 с
Медианная длительность операции	1 ч. 30 м 0 с
Число групп взаимозаменяемых ресурсов верхнего уровня	25
Число атомарных ресурсов	221

 

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

 

Таблица 2.  Сравнение результатов решения при разных настройках разработанного ПО

Table 2. Comparison of results with different settings of the developed software

Настройки алгоритма
Параметр расчета	Набор параметров 1	Набор параметров 2
Количество шагов алгоритма	0	5
Максимальное время работы алгоритма, мин.	10	10
Резервное время, сек.	0	0
Важность равномерности, %	0	0
Допустимость использования  альтернативных ресурсов	да	да
Критерий оптимизации	Суммарное нарушение директивных сроков	Лексикографический учет нарушений директивных сроков по приоритетам
Характеристики решения
Количество партий, нарушивших директивный срок	28 388	28 240
Количество партий, нарушивших директивный срок, %	99	98
Суммарный объем нарушений заказов	27 793	20 391
Суммарный объем нарушений операций	779 317 572	789 131 160
Суммарный объем нарушений самых приоритетных заказов, дни	8 960	1 566
Суммарный объем нарушений операций самых приоритетных	195 083 852	46 487 918
Количество неназначенных операций	0	0
Время завершения последней назначенной операции	2038-09-01T13:00	2038-09-02T12:45
Средняя загрузка единичных ресурсов по месяцам, %	1,666709184	1,666853741
Средняя загрузка максимально загруженного ресурса по месяцам, %	13,57	13,57
Максимальная загрузка единичных ресурсов по месяцам, %	100	100
Средняя загрузка единичных ресурсов по месяцам на эффективном интервале, %	21,3559599	21,35199608
Средняя загрузка максимально загруженного ресурса по месяцам на эффективном интервале, %	99,29268293	99,29268293

 

Заключение

Разработано и реализовано программное средство [17], позволяющее регрессионно тестировать и настраивать на целевые задачи внутренние параметры алгоритмов при решении NP-трудных задач распределения производственных ресурсов при автоматизации процесса изготовления высокотехнологичных изделий, свойственных предприятиям машиностроительного дивизиона ГК «Росатом».

 

About the authors

L. G. Afraimovich

Nizhny Novgorod State University n.a. N.I. Lobachevsky

Author for correspondence.
Email: lev.afraimovich@itmm.unn.ru
ORCID iD: 0000-0002-7320-8086
Russian Federation, Nizhny Novgorod

M. S. Kulikov

Nizhny Novgorod State University n.a. N.I. Lobachevsky

Email: vokil@mail.ru
ORCID iD: 0000-0002-4777-771X
Russian Federation, Nizhny Novgorod

E. A. Kumagina

Nizhny Novgorod State University n.a. N.I. Lobachevsky

Email: elena.kumagina@itmm.unn.ru
ORCID iD: 0000-0002-5199-8814
Russian Federation, Nizhny Novgorod

M. Kh. Prilutskii

Nizhny Novgorod State University n.a. N.I. Lobachevsky

Email: pril@iani.unn.ru
ORCID iD: 0000-0002-7694-3916
Russian Federation, Nizhny Novgorod

N. V. Starostin

Nizhny Novgorod State University n.a. N.I. Lobachevsky

Email: nvstar@iani.unn.ru
ORCID iD: 0000-0003-1415-7511
Russian Federation, Nizhny Novgorod

References

Supplementary files