Системы анализа и обработки данных

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

Выпуск № 4 (80) Октябрь - Декабрь 2020

Авторы:

Грузенкин Денис Владимирович,

Кузнецов Александр Сергеевич,

Селезнев Игорь Валерьевич

DOI: http://dx.doi.org/10.17212/1814-1196-2020-4-65-80

Скачать полный текст

Аннотация
Авторы
Список литературы
Благодарности. Финансирование

Аннотация

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

Ключевые слова: алгоритм, мера различия, метрика, диверсификация, метрика диверсифицированности, производственный план, составление расписания, диверсификация на уровне алгоритмов

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

1. Kuznetsov A.S., Noskova E.E. Assessment of planning methods at job-order manufacturing facilities // IOP Conference Series: Materials Science and Engineering. – 2020. – Vol. 862. – P. 042024. – DOI: 10.1088/1757-899X/862/4/042024.

2. Цуканов М.А., Божкова О.А. Разработка и реализация алгоритма построения расписания сталеплавильного производства на основе адаптации фрактала Кантора // Вестник Воронежского государственного технического университета. – 2017. – № 6. – С. 32–37.

3. Стохастическая модель оптимизации затрат при планировании технологических процессов лесозаготовок / И.В. Бачериков, Ф.В. Свойкин, А.Р. Бирман, В.А. Соколова // Системы. Методы. Технологии. – 2017. – № 4 (36). – С. 182–186.

4. Обоснование эффективности планирования технологических процессов водопользования и оперативное управление водораспределением на базе использования метода Монте-Карло / В.И. Ольгаренко, И.Ф. Юрченко, И.В. Ольгаренко, Г.Г. Костюнин, М.С. Эфендиев, В.И. Ольгаренко // Научный журнал Российского НИИ проблем мелиорации. – 2018. – № 1 (29). – С. 49–65.

5. Бутаков А.С. Автоматизация планирования технологических процессов сборки радиоэлектронной аппаратуры: выпускная квалификационная работа бакалавра / Сибирский федеральный университет. – Красноярск, 2018. – URL: http://elib.sfu-kras.ru/bitstream/handle/2311/72191/vkr_butakov.pdf?sequence (дата обращения: 14.12.2020).

6. Егоршин А.А., Атеняев Е.С., Носкова Е.Е. Автоматизация планирования технологических процессов сборки радиоэлектронной аппаратуры // Современные проблемы радиоэлектроники / науч. ред. А.И. Громыко. – Красноярск: СФУ, 2018. – С. 388–390.

7. Определение метрики диверсифицированности мультиверсионного программного обеспечения на уровне алгоритмов / Д.В. Грузенкин, И.А. Якимов, А.С. Кузнецов, Р.Ю. Царев // Фундаментальные исследования. – 2017. – № 6. – С. 36–40.

8. Васильев Н. Метрические пространства // Квант. – 1990. – № 1. – С. 16–23.

9. Багов М.А., Кудаев В.Ч. Математическое моделирование и оптимизация трубопроводной сети Штейнера // Известия Кабардино-Балкарского научного центра РАН. – 2017. – № 1 (75). – С. 5–11.

10. Астриков Д.Ю., Кузьмин Д.А., Панасюк А.И. Моделирование системы планирования распределенного высокопроизводительного вычислительного комплекса // Доклады Академии наук высшей школы Российской Федерации. – 2014. – № 2–3 (23–24). – С. 34–41.

11. Григорьева М.В. Эколого-экономическая оценка методов ручной и оптической сортировки твердых бытовых отходов // Вестник Пермского национального исследовательского политехнического университета. Урбанистика. – 2012. – № 3. – С. 62–73.

12. Дупленко А.Г. Сравнительный анализ алгоритмов сортировки данных в массивах // Молодой ученый. – 2013. – № 8. – С. 50–53.

13. Fonseca R. ESMT-Smith: Smiths algorithm for the Euclidean Steiner Minimal Tree problem. – 2015. – 23 March. – URL: https://github.com/RasmusFonseca/ESMT-Smith (accessed: 20.11.2020).

14. Chen L., Avizienis A. N-version programming: A fault-tolerance approach to reliability of software operation // FTCS-8: the Eighth Annual International Conference on Fault-Tolerant Computing: digest of papers. – Toulouse, France, 1978. – Vol. 1. – P. 3–9.

15. Бураков Д.П., Кожомбердиева Г.И. Использование формулы Байеса при оценивании качества программного обеспечения согласно стандарту ISO/IEC 9126 // Программные продукты и системы. – 2019. – Т. 32, № 1. – С. 34–41.

16. Грузенкин Д.В., Михалев А.С. Определение метрики диверсифицированности мультиверсионного программного обеспечения на уровне языков программирования // Программная инженерия. – 2019. – Т. 10, № 9–10. – С. 384–390.

Для цитирования:

Грузенкин Д.В., Кузнецов А.С., Селезнев И.В. Оценка меры различия алгоритмов в многовариантной системе составления производственных планов // Научный вестник НГТУ. – 2020. – № 4 (80). – С. 65–80. – DOI: 10.17212/1814-1196-2020-4-65-80.

For citation:

Gruzenkin D.V., Kuznetsov A.S., Seleznev I.V. Otsenka mery razlichiya algoritmov v mnogovariantnoi sisteme sostavleniya proizvodstvennykh planov [An assessment of the algorithm difference measure in a multivariate system for production plans scheduling]. Nauchnyi vestnik Novosibirskogo gosudarstvennogo tekhnicheskogo universiteta = Science bulletin of the Novosibirsk state technical university, 2020, no. 4 (80), pp. 65–80. DOI: 10.17212/1814-1196-2020-4-65-80.

Просмотров: 1040

СИСТЕМЫ АНАЛИЗА И ОБРАБОТКИ ДАННЫХ

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