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

I. A. Lesik; Лесик И. А.; A. G. Perevozchikov; Перевозчиков А. Г.; P. A. Yudina; Юдина П. А.

doi:10.31857/S0424738825010119

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

Authors: Lesik I.A.¹, Perevozchikov A.G.², Yudina P.A.³
Affiliations:
1. Limited Liability Company “Brainhub Group”
2. Joint-Stock Company “Scientific and Production Association Russian basic information technology”
3. Joint-Stock Company “Scienttific and Production Association Russian basic information technology”
Issue: Vol 61, No 1 (2025)
Pages: 118-124
Section: Mathematical analysis of economic models
URL: https://rjmseer.com/0424-7388/article/view/682166
DOI: https://doi.org/10.31857/S0424738825010119
ID: 682166

Cite item

Full Text

Open Access
Restricted Access

Access granted
Restricted Access

Subscription Access

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.

Keywords

scheduling theory, performance problem, absence of interruptions, method of branches and boundaries, lower estimates of the criterion

Full Text

References

Васин А. А., Григорьева О. М., Цыганов Н. И. (2017). Оптимизация транспортной системы энергетического рынка // Доклады Академии наук. Т. 475. № 4. С. 377–381. [Vasin A. A., Grigor’eva O.M., Cyganov N. I. (2017). Optimization of the transport system of the energy market. Reports of the Russian Academy of Sciences (Doklady Akademii Nauk), 475, 4, 377–381 (in Russian).]
Васин А. А., Морозов В. В. (2005). Теория игр и модели математической экономики. М.: МАКС Пресс. [Vasin A. A., Morozov V. V. (2005). Game theory and models of mathematical economics. Moscow: MAKS Press (in Russian).]
Кривулин Н. К. (2009). Методы идемпотентной алгебры в задачах моделирования и анализа сложных систем. СПб.: Изд-во С.- Петербургского ун-та. 256 с. [Krivulin N. K. (2009). Methods of idempotent algebra in problems of modeling and analysis of complex systems. St. Petersburg: Publishing House of St. Petersburg University. 256 p. (in Russian).]
Кривулин Н. К., Губанов С. А. (2021). Алгебраическое решение задачи оптимального планирования сроков проекта в управлении проектами // Вестник Санкт-Петербургского университета. Математика. Механика. Астрономия. Т. 8. Вып. 1. С. 73–87. [Krivulin N. K., Gubanov S. A. (2021). An algebraic solution to the problem of optimal planning of project deadlines in project management. Vestnik of Saint Petersburg University. Mathematics. Mechanics. Astronomy, 8, 1, 73–87 (in Russian).]
Кривулин Н. К., Романовский И. В. (2017). Решение задач математического программирования с использованием методов тропической оптимизации // Вестник Санкт-Петербургского университета. Математика. Механика. Астрономия. Т. 4 (62). Вып. 3. С. 7–9. [Krivulin N. K., Romanovsky I. V. (2017). Solving problems of mathematical programming using methods of tropical optimization. Vestnik of Saint Petersburg University. Mathematics. Mechanics. Astronomy, 4 (62), 3, 7–9 (in Russian).]
Перевозчиков А. Г., Лесик И. А. (2014). Нестационарная модель инвестиций в основные средства предприятия // Прикладная математика и информатика: труды факультета ВМК МГУ имени М. В. Ломоносова. № 46. С. 76–88. Под ред. В. И. Дмитриева. М.: МАКС Пресс. [Perevozchikov A. G., Lesik I. A. (2014). Non-stationary model of investment in fixed assets of the enterprise. Computational Mathematics and Informatics: Proceedings of the Faculty of Computational Mathematics and Cybernetics at Lomonosov Moscow State University, 46, 76–88. V. I. Dmitriev (ed.). Moscow: MAKS Press (in Russian).]
Перевозчиков А. Г., Лесик И. А. (2016). Определение оптимальных объемов производства и цен реализации в линейной модели многопродуктовой монополии // Экономика и математические методы. Т. 52. № 1. C. 140–148. [Perevozchikov A. G., Lesik I. A. (2016). Determination of optimal production volumes and sales prices in a linear model of a multi-product monopoly. Economics and Mathematical Methods, 52, 1, 140–148 (in Russian).]
Перевозчиков А. Г., Лесик И. А. (2020). Динамическая модель инвестиций в научные исследования олигополии // Экономика и математические методы. Т. 56. № 2. C. 101–113. [Perevozchikov A. G., Lesik I. A. (2020). A dynamic model of investment in scientific research of an oligopoly. Economics and Mathematical Methods, 56, 2, 101–113 (in Russian).]
Перевозчиков А. Г., Лесик И. А. (2021). Динамическая модель разработки программного обеспечения на основе задачи о назначении на узкие места // Экономика и математические методы. Т. 56. № 4. C. 108–116. [Perevozchikov A. G., Lesik I. A. (2021). A dynamic model of software development market based on the assignment problem on pain points. Economics and Mathematical Methods, 56, 4, 108–116 (in Russian).]
Перевозчиков А. Г., Лесик И. А. (2023). Сведение динамической модели рынка разработки программного обеспечения к блочной задаче выпуклого программирования // Экономика и математические методы. Т. 59. № 1. C. 119–130. [Perevozchikov A. G., Lesik I. A. (2023). Reducing the dynamic model of the software development market to a block problem of convex programming. Economics and Mathematical Methods, 59, 1, 119–130 (in Russian).]
Танаев В. С., Гордон В. С., Шафранский Я. М. (1984). Теория расписаний. Одностадийные системы. М.: Наука. [Tanaev V. S., Gordon V. S., Shafransky Y. M. (1984). Scheduling theory. Single-stage systems. Moscow: Nauka (in Russian).]
Танаев В. С., Сотсков Ю. Н., Струсевич В. А. (1989). Теория расписаний. Многостадийные системы. М.: Наука. [Tanaev V. S., Sotskov Y. N., Strusevich V. A. (1989). Scheduling theory. Multistage systems. Moscow: Nauka (in Russian).]
Устюжанина Е. В., Дементьев В. Е., Евсюков С. Г. (2021). Трансакционные цифровые платформы: задача обеспечения эффективности // Экономика и математические методы. Т. 57. № 1. C. 5–18. [Ustyuzhanina E. V., Dementiev V. E., Evsyukov S. G. (2021). Digital transaction platforms: Ensuring their efficiency. Economics and Mathematical Methods, 57, 1, 5–18 (in Russian).]
Ding X., K. Ding, P. Wang, Gibbons B., ZhangX. (2012). BWS: Balanced work stealing for time-sharing multicores. Proceedings of the 7th ACM European Conference on Computer Systems. EuroSys, 12. N.Y., 365–378.