By this author

Dynamic model of the software development market based on the problem of performance without interruptions in the scheduling theory

Issue number 1 from 19.09.2025

Предлагается постановка дискретной динамической модели рынка разработки программного обеспечения с последействием на основе задачи о быстродействии без прерываний в теории расписаний. В отличие от существующей задачи о быстродействии в нашей модели прерываний не допускаются. В результате такая задача становится NP-трудной даже в случае двух обслуживающих приборов, что приводит к необходимости использовать метод ветвей и границ в полученной дискретной динамической задаче с последействием в сочетании с точной формулой для наименьшего времени выполнения расписания с прерываниями для определения нижних оценок критерия в промежуточных узлах поискового орграфа. Известна теорема, что в задаче о рюкзаке эпсилон-версия метода ветвей и границ является полиномиальной со степенью полинома, обратно пропорциональной эпсилон. Возникает гипотеза, что это верно и для нашей задачи. Для проверки гипотезы проведен статистический эксперимент, когда параметры выбираются при помощи датчика случайных чисел, а размерность монотонно увеличивается. Кривизна графика числа раскрытых вершин от размерности в логарифмическом масштабе позволяет судить о полиномиальности или экспоненциальности эпсилон-версии метода ветвей и границ в нашей задаче. Показано, что хотя приближенный алгоритм как раз и оказался экспоненциальным, но относительное число раскрываемых вершин убывает очень быстро, что свидетельствует о его практической эффективности.

48 0