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

Динамическая модель рынка разработки программного обеспечения на основе задачи о быстродействии без прерываний в теории расписаний

Авторы: Лесик И.А.¹, Перевозчиков А.Г.², Юдина П.А.²
Учреждения:
1. ООО «Брейнхаб Групп»
2. НПО «РусБИТех»
Выпуск: Том 61, № 1 (2025)
Страницы: 118-124
Раздел: Математический анализ экономических моделей
URL: https://modernonco.orscience.ru/0424-7388/article/view/682166
DOI: https://doi.org/10.31857/S0424738825010119
ID: 682166

Цитировать

Полный текст

Открытый доступ
Доступ закрыт

Доступ предоставлен
Доступ закрыт

Только для подписчиков

Аннотация
Полный текст
Об авторах
Список литературы
Дополнительные файлы
Статистика

Аннотация

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

Ключевые слова

теория расписаний, задача о быстродействии, отсутствие прерываний, метод ветвей и границ, нижние оценки критерия

Полный текст

Список литературы

Васин А. А., Григорьева О. М., Цыганов Н. И. (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.