Разработка и реализация программных средств регрессионного тестирования алгоритмов при решении задач производственного планирования
- Авторы: Афраймович Л.Г.1, Куликов М.С.1, Кумагина Е.А.1, Прилуцкий М.Х.1, Старостин Н.В.1
-
Учреждения:
- Нижегородский государственный университет им. Н.И. Лобачевского
- Выпуск: № 1 (2025)
- Страницы: 7-14
- Раздел: Информатика, управление и системный анализ
- Статья опубликована: 30.05.2025
- URL: https://archivog.com/1816-210X/article/view/680771
- EDN: https://elibrary.ru/XMJEVB
- ID: 680771
Цитировать
Полный текст
Аннотация
Разработан программный продукт, предназначенный для решения задач распределения производственных ресурсов при автоматизации процесса изготовления высокотехнологичных изделий, типичных для предприятий машиностроительного дивизиона ГК «Росатом». Рассматривается NP-трудная задача производственного планирования, при решении которой используются эвристические процедуры, использующие, в зависимости от специфики задачи, различные сценарии работы. В основе решающих алгоритмов, реализованных в программном продукте СМАРТ-ресурс, лежат авторские фронтальные алгоритмы, имеющие возможность за счет информации, получаемой с учетом реализованных обратных связей, использовать для решения задачи различные сценарии. Приведена математическая модель проблемы распределения производственных ресурсов, в рамках которой поставлена задача распределения производственных ресурсов по критерию минимизации отклонений от заданных директивных сроков изготовления запланированных изделий. Показана ее NP-трудность. Приведены алгоритмы ее решения. Разработано и реализовано программное средство, позволяющее регрессионно тестировать и настраивать на целевые задачи внутренние параметры фронтальных алгоритмов с обратной связью при решении NP-трудных задач производственного планирования с использованием системы производственного планирования СМАРТ-ресурс.
Полный текст
Введение
Вопросы решения оптимизационных задач производственного планирования широко обсуждаются в современной научной литературе. Они относятся, как правило, к классу NP-трудных, что обуславливает применение эвристических процедур для их решения. В работах [1-5] обсуждаются вопросы применения гибридных алгоритмов и алгоритмов, основанных на методах машинного обучения. Для задач небольшой размерности предлагаются подходы, основанные на методах целочисленного линейного программирования [6, 7]. Значительный вклад внесли работы Нижегородской школы по вопросам распределения производственных ресурсов для высокотехнологичных предприятий [8-17]. В работах [15, 16] описана разработанная и программно реализованная система производственного планирования СМАРТ-ресурс, предназначенная для решения задач распределения производственных ресурсов при автоматизации процесса изготовления высокотехнологичных изделий, свойственных предприятиям машиностроительного дивизиона ГК «Росатом».
В настоящей статье представлено разработанное и программно реализованное программное средство, позволяющее регрессионно тестировать и настраивать на целевые задачи внутренние параметры алгоритмов, реализованных в системе производственного планирования.
Содержательное описание объекта
Заданы множество операций, выполнение которых необходимо спланировать, и множество ресурсов предприятия. На множестве операций задано отношение предшествования (операция не может быть выполнена до тех пор, пока не будут выполнены все предшествующие). Данное отношение предшествования определяет технологический процесс (технологию) заказа. Для каждой из операций задана длительность выполнения и необходимый для выполнения ресурс. Каждая операция выполняется без прерывания. Каждый из ресурсов в каждый из тактов времени может использоваться не более чем одной операцией. Множество операций разбито на заказы, для каждого из которых заданы ранее время начала (время, раньше которого запрещено выполнение операций заказа) и директивный срок (время, к которому необходимо стремиться завершить выполнение операций заказа).
Необходимо составить производственный план (для каждой операции определить время начала выполнения), при котором будет минимизировано суммарное запаздывание заказов относительно их директивных сроков.
Математическая модель и постановка задачи
Исходные параметры математической модели:
{1, ..., n} – множество операций;
{1, ..., m} – множество ресурсов;
{1, ..., k} – множество заказов;
{1, ..., T} – множество тактов планирования;
Vl – множество операций заказа l, ;
при этом , и ;
, – граф без петель и контуров, определяющий технологию заказа l, ;
– длительность операции i, ;
– необходимый для выполнения операции i ресурс, ;
– ранее начало и директивный срок заказа l, .
Варьируемые параметры математической модели:
– время начала выполнения операции i,
Ограничения математической модели:
(1)
(2)
(3)
(4)
Постановка задачи:
Поставленная задача производственного планирования относится к классу NP-трудных задач, поскольку к ней за полиномиальное время сводится задача о камнях.
Общая структура алгоритма
Для удобства обозначим:
- l(i) – номер заказа, содержащего операцию i, т.е. , что , ;
- p(i) – множество операций, непосредственно предшествующих операции i, т.е. , .
Общая структура фронтального алгоритма [8, 9]
Шаг 1. . Шаг 2.
Шаг 2.
и
.
Шаг 3.
Шаг 3. Для каждой операции выполнить:
{
Если ,
то .
}
Шаг 4.
Шаг 4. .
Если или , то Шаг 2, иначе завершить.
Комментарии:
- на шаге 1 происходит инициализация переменных;
- на шаге 2 строится фронт операций F(t), т.е. множество операций, удовлетворяющих условиям:
- операция в данный момент не запланированы (условие ),
- текущий такт времени t больше или равен раннего времени начала заказа операции (условие ),
- все предшествующие операции уже запланированы (условие ),
- необходимый для операции ресурс в текущий такт времени t свободен (условие );
- на шаге 3 по очереди назначаются на выполнение операции, для которых необходимый ресурс свободен на текущем такте времени t (данное условие дублирует условие на шаге 2, так как операции текущего фронта могу занять данный ресурс);
- на шаге 4 происходит переход к следующему такту планирования и проверяется условие останова.
Предложенный фронтальный алгоритм представляет собой эвристический алгоритм решения задачи планирования.
Стратегии сортировки фронта
С целью повышения качества работы фронтального алгоритма могут быть использованы различные стратегии сортировки. Таким образом, на шаге 2 фронтального алгоритма фронт представляется в виде , и операции фронта выбираются в соответствующем порядке. В качестве стратегии может быть рассмотрена, например, сортировка по директивному сроку соответствующего заказа: Возможна сортировка по незавершенному объему работ заказа, доле незавершенного объема работ от общего объема работ заказа, оценкам резервов времени и т.д.
Итерационный фронтальный алгоритм
Фронтальный алгоритм может вызываться итерационно, определяя рекорд среди решений итераций фронтального алгоритма. В данном случае стратегия сортировки должна быть вариативной (меняться на различных итерациях запуска фронтального алгоритма). Пример такой вариативной стратегии – рандомистическая сортировка, оценка «важности» заказа с точки зрения его нарушений директивных сроков, которые вычисляются, исходя из решений предыдущих итераций [10].
Оптимизация фронтального алгоритма
Предложенная структура фронтального алгоритма обладает экспоненциальной трудоемкостью, поскольку число вызовов шага 2 составляет . C целью построения полиномиального по сложности алгоритма необходимо на шаге 4 итерировать не каждый такт времени, а только такты, соответствующие событиям, где событиями являются ранние времена начала партий, момента завершения операций (данные события формируются динамически при назначении новых операций). При таком подходе число вызовов шага 2 будет составлять .
Регрессионное тестирование алгоритмов решения задач производственного планирования
Разработанная система регрессионного тестирования [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
Россия, Нижний Новгород
Список литературы
- Гладков, Л.А. Гибридная модель решения задач оперативного производственного планирования / Л.А. Гладков, Н.В. Гладкова, С.А. Громов // Известия ЮФУ. Технические науки. 2018. № 4 (198). С. 99-110.
- Шкурба, В.В. Календарное планирование. Конструктивная оптимизация. Индустрия праксеотехники // Автоматика и телемеханика. 2010. № 10. С. 122-132.
- Гераськин, М.И. Оптимальные механизмы планирования позаказного производства по финан-совым и временным критериям / М.И. Гераськин, В.В. Егорова // Управление большими систем-ами: сборник трудов. 2015. № 58. С. 179-211.
- Грачев, С.П. Методы и средства построения интеллектуальных систем для решения сложных задач адаптивного управления ресурсами в реальном времени / С.П. Грачев, А.А. Жиляев, В.Б. Ларюхин [и др.] // Автоматика и телемеханика. 2021. № 11. С. 30-67.
- Сотсков, Ю.Н. Область оптимальности перестановки обслуживания на одном приборе требований с неопределенными длительностями // Автоматика и телемеханика. 2020. № 5. С. 60-90.
- Кибзун, А.И. Модель целочисленного линейного программирования как математическое обес-печение системы оптимального планирования потокового производства на этапе оперативного графикования / А.И. Кибзун, В.А. Рассказова // Автоматика и телемеханика. 2023. № 5. С. 113-132.
- Куприянов, Б.В. Оценка и оптимизация производительности рекурсивного конвейера // Автоматика и телемеханика. 2020. № 5. С. 6-25.
- Afraimovich, L. Control Activities Planning Problem / L. Afraimovich, M. Prilutskii, V. Vlasov // Lecture Notes in Electrical Engineering. 2021. Т. 729. LNEE. С. 341-350.
- Прилуцкий, М.Х. Управляемый фронтальный алгоритм решения задачи распределения ресурсов в сетевых канонических структурах / М.Х. Прилуцкий, Е.А. Кумагина // Вестник Нижегородского университета им. Н.И. Лобачевского. 2008. № 6. С. 152-155.
- Куликов, М.С. Ранговый итерационный алгоритм решения задачи распределения ресурсов в сетевых системах // Системы управления и информационные технологии. 2011. № 4. С. 37-43.
- Прилуцкий, М.Х. Задачи оптимального планирования как задачи распределения ресурсов в сетевых канонических структурах / М.Х. Прилуцкий, В.С. Власов, О.В. Кривошеев // Информационные технологии. 2017. Т. 23. № 9. С. 650-657.
- Прилуцкий, М.Х. Задачи календарного планирования для предприятий с единичным и мелкосерийным характером производства / М.Х. Прилуцкий, И.В. Нетронин // Системы управления и информационные технологии. 2019. № 3 (77). С. 46-51.
- Прилуцкий, М.Х. Задачи объемно-календарного планирования для предприятий с единичным и мелкосерийным характером производств / М.Х. Прилуцкий, И.В. Нетронин // Труды НГТУ им. Р.Е. Алексеева. 2019. № 4 (127). С. 36-43.
- Кумагина, Е.А. Задачи распределения разнородных ресурсов в сетевых канонических структурах / Е.А. Кумагина, М.Х. Прилуцкий // Известия ТРТУ. 2001. № 4(22). С. 194-200.
- Афраймович, Л.Г. Система производственного планирования Смарт-ресурс / Л.Г. Афраймович, М.С. Куликов, М.Х. Прилуцкий, Н.В. Старостин // VIII Молодежная конференция по управлению проектами: сборник тезисов докладов. ‒ Н. Новгород: ООО «Литера», 2023. С. 7.
- Производственное планирование в условиях неполноты данных / Л.Г. Афраймович, В.Е. Костюков, М.С. Куликов и др. // XIV Всероссийское совещание по проблемам управления: сборник научных трудов. ‒ М.: Институт проблем управления им. В.А. Трапезникова РАН, 2024. С. 1829-1834.
- Прилуцкий, М.Х. Программа для ЭВМ «Разработка программного средства регрессионного тестирования системы производственного планирования» / М.Х. Прилуцкий, Л.Г. Афраймович, Н.В. Старостин и др. Заявка 2024690711 от 16.12.2024.
Дополнительные файлы
