Сибирский федеральный университет

Тип публикации: статья из журнала

Год издания: 2020

Идентификатор DOI: 10.17212/1814-1196-2020-4-65-80

Ключевые слова: algorithm, measure of difference, metric, diversification, diversity, Diversity metric, production plan, scheduling, algorithms diversity, алгоритм, мера различия, метрика, диверсификация, метрика диверсифицированности, производственный план, составление расписания, диверсификация на уровне алгоритмов

Аннотация: В процессе проектирования производственных планов одним из важных шагов является составление расписаний выполнения технологических операций. Расписание может составляться как вручную, так и с помощью программного обеспечения. Если расписание составляется программным средством, то для исключения возможных ошибок используют несколько алгоритмов генерации расписания. Набор таких алгоритмов называют «пачкой». В «пачку» целесообразно включать только различные алгоритмы. Это необходимо для исключения однотипных ошибок. Поэтому поиск клонов алгоритмов в «пачке» является актуальной производственной задачей. Для ее решения в ходе выполнения настоящей работы была разработана метрика диверсифицированности алгоритмов. Такая метрика численно (в процентах) определяет, насколько алгоритмы различны. Данная метрика основывается на характеристиках трасс выполнения алгоритмов. Трассы алгоритмов строятся в N-мерном пространстве по полученным точкам. Координатами точек трасс являются значения, с которыми работает алгоритм на каждом шаге своего выполнения или в каждой из контрольных точек выполнения алгоритма. Для подтверждения корректности работы данной метрики был поставлен эксперимент. В его рамках были вычислены характеристики трасс трех алгоритмов сортировки. На основании полученных характеристик были определены показатели для сравнения алгоритмов в метрическом пространстве. Эксперимент подтвердил эффективность использования метрики диверсифицированности для нахождения клонов в «пачке алгоритмов». Область применения данной метрики не ограничивается лишь поиском клонов. Она может быть применена как самостоятельный показатель качества программного обеспечения. In the process of designing a production plan, one of the important steps is scheduling the execution of technological operations. The schedule can be created either manually or by using software. If the schedule is compiled by software, then several schedule generation algorithms are used to eliminate possible errors. A set of such algorithms is called a "batch". It is advisable that only different algorithms should be included in the batch. This is necessary to eliminate errors of the same type. Therefore, the search for clones of algorithms in the batch is an urgent production task. To solve it a diversity metric of algorithms was developed in the course of this work. Such a metric numerically (as a percentage) determines how much the algorithms differ. This metric is based on the properties of the algorithm execution. Algorithm traces are constructed in the N-dimensional space using the obtained points. The coordinates of the trace points are the values with which the algorithm works at each step of its execution or each of the control points of the algorithm execution. An experiment was performed to confirm the correctness of this metric. Within this experiment, the trace properties of three sorting algorithms were calculated. Based on the properties obtained, indicators were determined for comparing algorithms in the metric space. The experiment confirmed the effectiveness of using the diversity metric to find clones in the algorithms batch. The scope of this metric is not limited to clone searches. It can be used as an independent indicator of software quality.

Журнал: Научный вестник Новосибирского государственного технического университета

Выпуск журнала: № 4

Номера страниц: 65-80

ISSN журнала: 18141196

Место издания: Новосибирск

Издатель: Новосибирский государственный технический университет

• Грузенкин Денис Владимирович (Сибирский федеральный университет)
• Кузнецов Александр Сергеевич (Сибирский федеральный университет)
• Селезнев Игорь Валерьевич (Сибирский федеральный университет)

• РИНЦ (eLIBRARY.RU)