The authors propose is formulating a discrete dynamic model of the software development market with aftereffect based on the problem of performance without interruptions in the scheduling theory. In our model unlike the existing problem of performance, interrupts are not allowed. As a result, the problem of performance without interruptions becomes NP-difficult in the case of even two servicing devices, which leads to the need to use the method of branches and boundaries in the resulting discrete dynamic problem with aftereffect in combination with the exact formula for the shortest schedule execution time to determine the lower estimates of the criterion in the intermediate nodes of the search digraph. There is a well-known theorem that in the knapsack problem, the epsilon version of the branches and bounds method is polynomial with a polynomial degree inversely proportional to epsilon. We make an assumption that this is also true for our problem. To test the hypothesis, we conducted the statistical experiment when the parameters of the problem are selected using a random number sensor, and the dimension increases monotonously. The curvature of the graph of the number of exposed vertices from the dimension on a logarithmic scale allows us to estimate the polynomial or exponential nature of the epsilon version of the branch and boundary method in our problem. It is shown that although the approximate algorithm turned out to be exponential, the relative number of revealed vertices decreases very quickly, which shows (reveals) its practical effectiveness.
Предлагается постановка дискретной динамической модели рынка разработки программного обеспечения с последействием на основе задачи о быстродействии без прерываний в теории расписаний. В отличие от существующей задачи о быстродействии в нашей модели прерываний не допускаются. В результате такая задача становится NP-трудной даже в случае двух обслуживающих приборов, что приводит к необходимости использовать метод ветвей и границ в полученной дискретной динамической задаче с последействием в сочетании с точной формулой для наименьшего времени выполнения расписания с прерываниями для определения нижних оценок критерия в промежуточных узлах поискового орграфа. Известна теорема, что в задаче о рюкзаке эпсилон-версия метода ветвей и границ является полиномиальной со степенью полинома, обратно пропорциональной эпсилон. Возникает гипотеза, что это верно и для нашей задачи. Для проверки гипотезы проведен статистический эксперимент, когда параметры выбираются при помощи датчика случайных чисел, а размерность монотонно увеличивается. Кривизна графика числа раскрытых вершин от размерности в логарифмическом масштабе позволяет судить о полиномиальности или экспоненциальности эпсилон-версии метода ветвей и границ в нашей задаче. Показано, что хотя приближенный алгоритм как раз и оказался экспоненциальным, но относительное число раскрываемых вершин убывает очень быстро, что свидетельствует о его практической эффективности.