Разработка и реализация программных средств регрессионного тестирования алгоритмов при решении задач производственного планирования

Обложка

Цитировать

Полный текст

Аннотация

Разработан программный продукт, предназначенный для решения задач распределения производственных ресурсов при автоматизации процесса изготовления высокотехнологичных изделий, типичных для предприятий машиностроительного дивизиона ГК «Росатом». Рассматривается NP-трудная задача производственного планирования, при решении которой используются эвристические процедуры, использующие, в зависимости от специфики задачи, различные сценарии работы. В основе решающих алгоритмов, реализованных в программном продукте СМАРТ-ресурс, лежат авторские фронтальные алгоритмы, имеющие возможность за счет информации, получаемой с учетом реализованных обратных связей, использовать для решения задачи различные сценарии. Приведена математическая модель проблемы распределения производственных ресурсов, в рамках которой поставлена задача распределения производственных ресурсов по критерию минимизации отклонений от заданных директивных сроков изготовления запланированных изделий. Показана ее NP-трудность. Приведены алгоритмы ее решения. Разработано и реализовано программное средство, позволяющее регрессионно тестировать и настраивать на целевые задачи внутренние параметры фронтальных алгоритмов с обратной связью при решении NP-трудных задач производственного планирования с использованием системы производственного планирования СМАРТ-ресурс.

Полный текст

Введение

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

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

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

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

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

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

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

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

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

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

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

Vl – множество операций заказа l, l=1,k¯;

при этом l=1kVl=1,,n, Vl'Vl''=, l',l''1,,n и l'l'';

Gl=Vl,Al, AlVl2 – граф без петель и контуров, определяющий технологию заказа l, l=1,k¯;

tiN – длительность операции i, i=1,n¯;

ri1,,m – необходимый для выполнения операции i ресурс, i=1,n¯;

tlр, tlд – ранее начало и директивный срок заказа l, l=1,k¯.

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

xi1,,T – время начала выполнения операции i, i=1,n¯

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

xi1,,T, i=1,n¯, (1)

xitlр, iVl, l=1,k¯, (2)

xi'+ti'xi, i':i',iAl, iVl, l=1,k¯, (3)

i|ri=j, xitxi+ti1, t=1,T¯, j=1,m¯. (4)

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

l=1kmax0,maxiVlxi+titlдmin.

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

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

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

  • l(i) – номер заказа, содержащего операцию i, т.е. li1,,k, что iVli, i=1,n¯;
  • p(i) – множество операций, непосредственно предшествующих операции i, т.е. pi={i'|i',iAli}, i=1,n¯.

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

Шаг 1. xi:=0, i=1,n¯, t:=1.  Шаг 2.

Шаг 2. Ft:={i|   

xi=0 и  

ttliн и

xi'>0, i'pi и

i'|i'1,,n,xi'>0,xi'txi'+ti',ri=ri'=0}.

 Шаг 3.

Шаг 3. Для каждой операции iFt выполнить:

{  

Если i'|i'1,,n,xi'>0,xi'txi'+ti',ri=ri'=0,

то xi:=t.

}

 Шаг 4.

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

Если tT или i:xi=0, то Шаг 2, иначе завершить.

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

  • на шаге 1 происходит инициализация переменных;
  • на шаге 2 строится фронт операций F(t), т.е. множество операций, удовлетворяющих условиям:
  • операция в данный момент не запланированы (условие xi=0),
  • текущий такт времени t больше или равен раннего времени начала заказа операции (условие ttliн),
  • все предшествующие операции уже запланированы (условие xi'>0, i'pi),
  • необходимый для операции ресурс в текущий такт времени t свободен (условие i'|i'1,,n,xi'>0,xi'txi'+ti',ri=ri'=0);
  • на шаге 3 по очереди назначаются на выполнение операции, для которых необходимый ресурс свободен на текущем такте времени t (данное условие дублирует условие на шаге 2, так как операции текущего фронта могу занять данный ресурс);
  • на шаге 4 происходит переход к следующему такту планирования и проверяется условие останова.

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

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

С целью повышения качества работы фронтального алгоритма могут быть использованы различные стратегии сортировки. Таким образом, на шаге 2 фронтального алгоритма фронт представляется в виде Ft=i1t,,intt, и операции фронта выбираются в соответствующем порядке. В качестве стратегии может быть рассмотрена, например, сортировка по директивному сроку соответствующего заказа: tlistдtlis+1tд,  s=1,nt1¯. Возможна сортировка по незавершенному объему работ заказа, доле незавершенного объема работ от общего объема работ заказа, оценкам резервов времени и т.д.

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

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

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

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

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

Разработанная система регрессионного тестирования [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-трудных задач распределения производственных ресурсов при автоматизации процесса изготовления высокотехнологичных изделий, свойственных предприятиям машиностроительного дивизиона ГК «Росатом».

 

×

Об авторах

Л. Г. Афраймович

Нижегородский государственный университет им. Н.И. Лобачевского

Автор, ответственный за переписку.
Email: lev.afraimovich@itmm.unn.ru
ORCID iD: 0000-0002-7320-8086
Россия, Нижний Новгород

М. С. Куликов

Нижегородский государственный университет им. Н.И. Лобачевского

Email: vokil@mail.ru
ORCID iD: 0000-0002-4777-771X
Россия, Нижний Новгород

Е. А. Кумагина

Нижегородский государственный университет им. Н.И. Лобачевского

Email: elena.kumagina@itmm.unn.ru
ORCID iD: 0000-0002-5199-8814
Россия, Нижний Новгород

М. Х. Прилуцкий

Нижегородский государственный университет им. Н.И. Лобачевского

Email: pril@iani.unn.ru
ORCID iD: 0000-0002-7694-3916
Россия, Нижний Новгород

Н. В. Старостин

Нижегородский государственный университет им. Н.И. Лобачевского

Email: nvstar@iani.unn.ru
ORCID iD: 0000-0003-1415-7511
Россия, Нижний Новгород

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

  1. Гладков, Л.А. Гибридная модель решения задач оперативного производственного планирования / Л.А. Гладков, Н.В. Гладкова, С.А. Громов // Известия ЮФУ. Технические науки. 2018. № 4 (198). С. 99-110.
  2. Шкурба, В.В. Календарное планирование. Конструктивная оптимизация. Индустрия праксеотехники // Автоматика и телемеханика. 2010. № 10. С. 122-132.
  3. Гераськин, М.И. Оптимальные механизмы планирования позаказного производства по финан-совым и временным критериям / М.И. Гераськин, В.В. Егорова // Управление большими систем-ами: сборник трудов. 2015. № 58. С. 179-211.
  4. Грачев, С.П. Методы и средства построения интеллектуальных систем для решения сложных задач адаптивного управления ресурсами в реальном времени / С.П. Грачев, А.А. Жиляев, В.Б. Ларюхин [и др.] // Автоматика и телемеханика. 2021. № 11. С. 30-67.
  5. Сотсков, Ю.Н. Область оптимальности перестановки обслуживания на одном приборе требований с неопределенными длительностями // Автоматика и телемеханика. 2020. № 5. С. 60-90.
  6. Кибзун, А.И. Модель целочисленного линейного программирования как математическое обес-печение системы оптимального планирования потокового производства на этапе оперативного графикования / А.И. Кибзун, В.А. Рассказова // Автоматика и телемеханика. 2023. № 5. С. 113-132.
  7. Куприянов, Б.В. Оценка и оптимизация производительности рекурсивного конвейера // Автоматика и телемеханика. 2020. № 5. С. 6-25.
  8. Afraimovich, L. Control Activities Planning Problem / L. Afraimovich, M. Prilutskii, V. Vlasov // Lecture Notes in Electrical Engineering. 2021. Т. 729. LNEE. С. 341-350.
  9. Прилуцкий, М.Х. Управляемый фронтальный алгоритм решения задачи распределения ресурсов в сетевых канонических структурах / М.Х. Прилуцкий, Е.А. Кумагина // Вестник Нижегородского университета им. Н.И. Лобачевского. 2008. № 6. С. 152-155.
  10. Куликов, М.С. Ранговый итерационный алгоритм решения задачи распределения ресурсов в сетевых системах // Системы управления и информационные технологии. 2011. № 4. С. 37-43.
  11. Прилуцкий, М.Х. Задачи оптимального планирования как задачи распределения ресурсов в сетевых канонических структурах / М.Х. Прилуцкий, В.С. Власов, О.В. Кривошеев // Информационные технологии. 2017. Т. 23. № 9. С. 650-657.
  12. Прилуцкий, М.Х. Задачи календарного планирования для предприятий с единичным и мелкосерийным характером производства / М.Х. Прилуцкий, И.В. Нетронин // Системы управления и информационные технологии. 2019. № 3 (77). С. 46-51.
  13. Прилуцкий, М.Х. Задачи объемно-календарного планирования для предприятий с единичным и мелкосерийным характером производств / М.Х. Прилуцкий, И.В. Нетронин // Труды НГТУ им. Р.Е. Алексеева. 2019. № 4 (127). С. 36-43.
  14. Кумагина, Е.А. Задачи распределения разнородных ресурсов в сетевых канонических структурах / Е.А. Кумагина, М.Х. Прилуцкий // Известия ТРТУ. 2001. № 4(22). С. 194-200.
  15. Афраймович, Л.Г. Система производственного планирования Смарт-ресурс / Л.Г. Афраймович, М.С. Куликов, М.Х. Прилуцкий, Н.В. Старостин // VIII Молодежная конференция по управлению проектами: сборник тезисов докладов. ‒ Н. Новгород: ООО «Литера», 2023. С. 7.
  16. Производственное планирование в условиях неполноты данных / Л.Г. Афраймович, В.Е. Костюков, М.С. Куликов и др. // XIV Всероссийское совещание по проблемам управления: сборник научных трудов. ‒ М.: Институт проблем управления им. В.А. Трапезникова РАН, 2024. С. 1829-1834.
  17. Прилуцкий, М.Х. Программа для ЭВМ «Разработка программного средства регрессионного тестирования системы производственного планирования» / М.Х. Прилуцкий, Л.Г. Афраймович, Н.В. Старостин и др. Заявка 2024690711 от 16.12.2024.

Дополнительные файлы

Доп. файлы
Действие
1. JATS XML

© Афраймович Л.Г., Куликов М.С., Кумагина Е.А., Прилуцкий М.Х., Старостин Н.В., 2025

Creative Commons License
Эта статья доступна по лицензии Creative Commons Attribution 4.0 International License.

СМИ зарегистрировано Федеральной службой по надзору в сфере связи, информационных технологий и массовых коммуникаций (Роскомнадзор).
Регистрационный номер и дата принятия решения о регистрации СМИ: серия ПИ № ФС 77 - 56417 от 11 декабря 2013.