Abstract
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.