Решение двухкритериальных задач планирования проектов с помощью методов тропической оптимизации

Николай Кимович Кривулин; Вадим Викторович Симоненко

doi:10.32603/2071-2340-2026-1-5-21

Николай Кимович Кривулин Санкт-Петербургский государственный университет, Российская Федерация, 199034, Санкт-Петербург, Университетская наб., 7–9 https://orcid.org/0000-0003-3070-9355
Вадим Викторович Симоненко Санкт-Петербургский государственный университет, Российская Федерация, 199034, Санкт-Петербург, Университетская наб., 7–9

DOI: https://doi.org/10.32603/2071-2340-2026-1-5-21

Ключевые слова: тропическая оптимизация, задачи двухкритериальной оптимиза- ции, Парето-оптимальность, планирование проектов, временные ограничения

Аннотация

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

Биографии авторов

Николай Кимович Кривулин, Санкт-Петербургский государственный университет, Российская Федерация, 199034, Санкт-Петербург, Университетская наб., 7–9

доктор физ.-мат. наук, профессор кафедры статистического моделирования, СПбГУ, nkk@math.spbu.ru

Вадим Викторович Симоненко, Санкт-Петербургский государственный университет, Российская Федерация, 199034, Санкт-Петербург, Университетская наб., 7–9

Студент, СПбГУ, vadimka.simonenko@gmail.com

Литература

H. Kerzner, Project management: A Systems Approach to Planning, Scheduling, and Controlling, 13th ed., Hoboken, NJ, USA: Wiley, 2022.

J. E. Kelley, “The critical path method: resources planning and scheduling,” in Industrial Scheduling, J. F. Muth and G. L. Thompson eds., Englewood Cliffs, NJ, USA: Prentice-Hall, 1963, pp. 347–365.

D. G. Malcolm, J. H. Roseboom, C. E. Clark, and W. Fazar, “Application of a technique for research and development program evaluation,” Operations Research, vol. 7, no. 5, pp. 646–669, 1959; doi:10.1287/opre.7.5.646

J. J. Moder and C. R. Phillips, Project Management with CPM and PERT, 2nd ed., New York, NY, USA: Van Nostrand, 1970.

E. L. Demeulemeester and W. S. Herroelen, Project Scheduling. vol. 49 of International Seri- es in Operations Research and Management Science, New York, NY, USA: Springer, 2002; doi:10.1007/b101924

V. T’kindt and J.-C. Billaut, Multicriteria Scheduling, 2nd ed., Berlin: Springer, 2006; doi:10.1007/b106275

M. Vanhoucke, Project Management with Dynamic Scheduling, Berlin: Springer, 2012; doi:10.1007/978- 3-642-40438-2

D. T. Luc, “Pareto optimality,” in Pareto Optimality, Game Theory and Equilibria, A. Chinchuluun et al. eds., New York, NY, USA: Springer, 2008, pp. 481–515; doi:10.1007/978-0-387-77247-9_18

M. Ehrgott, Multicriteria Optimization, 2nd ed., Berlin: Springer, 2005; doi:10.1007/3-540-27659-9

F. L. Baccelli, G. Cohen, G. J. Olsder, and J.-P. Quadrat, Synchronization and Linearity. Wiley Series in Probability and Statistics, Chichester, UK: Wiley, 1993; doi:10.2307/2583959

V. P. Maslov and V. N. Kolokol’tsov, Idempotentnyi analiz i ego primenenie v optimal’nom upravlenii [Idempotent analysis and its application in optimal control], Moscow: Fizmatlit, 1994 (in Russian).

J. S. Golan, Semirings and afﬁne equations over them, Mathematics and Its Applications, vol. 556, New York, NY, USA: Springer, 2003; doi:10.1007/978-94-017-0383-3

B. Heidergott, G. J. Olsder, and J. van der Woude, Max Plus at Work. Princeton Series in Applied Mathematics, Princeton, NJ, USA: Princeton Univ. Press, 2006; doi:10.1515/9781400865239

N. K. Krivulin, Metody idempotentnoi algebry v zadachakh modelirovaniya i analiza slozhnykh sistem [Idempotent algebra methods in modeling and analysis of complex systems], St. Petersburg, Russia: Izdatel’stvo Sankt-Peterburgskogo universiteta, 2009 (in Russian).

P. Butkovic, ˇ Max-Linear Systems. Springer Monographs in Mathematics, London: Springer, 2010; doi:10.1007/978-1-84996-299-5

J.-L. Bouquard, C. Lente, and J.-C. Billaut, “Application of an optimization problem in max-plus ˊ algebra to scheduling problems,” Discrete Applied Mathematics, vol. 154, no. 15, pp. 2064-–2079, 2006; doi:10.1016/j.dam.2005.04.011

M. Singh and R. P. Judd, “Efﬁcient calculation of the makespan for job-shop systems without recirculati- on using max-plus algebra,” International Journal of Production Research, vol. 52, no. 19, pp. 5880– 5894, 2014; doi:10.1080/00207543.2014.925600

H. Goto, “Forward-compatible framework with critical-chain project management using a max-plus linear representation,” Opsearch, vol. 54, no. 1, pp. 201–216, 2017; doi:10.1007/s12597-016-0276-3

N. Krivulin, “Extremal properties of tropical eigenvalues and solutions to tropical opti- mization problems,” Linear Algebra and its Applications, vol. 468, pp. 211–232, 2015; doi:10.1016/j.laa.2014.06.044

N. Krivulin, “Tropical optimization problems in time-constrained project scheduling,” Optimization, vol. 66, no. 2, pp. 205–224, 2017; doi:10.1080/02331934.2016.1264946

N. Krivulin, “Tropical optimization problems with application to project scheduling with minimum makespan,” Annals of Operations Research, vol. 256, no. 1, pp. 75–92, 2017; doi:10.1007/s10479-015- 1939-9

N. K. Krivulin and S. A. Gubanov, “Solution of a project scheduling problem by using methods of tropi- cal mathematics,” Vestnik of St Petersburg University. Applied Mathematics. Computer Science. Control Processes, no. 3, pp. 62–72, 2016 (in Russian); doi:10.21638/11701/spbu10.2016.306

N. K. Krivulin and S. A. Gubanov, “The use of tropical optimization methods in problems of project scheduling,” Vestnik of St Petersburg University. Applied Mathematics. Computer Science. Control Processes, vol. 13, no. 4, pp. 384–397, 2017 (in Russian); doi:10.21638/11701/spbu10.2017.405

N. K. Krivulin and S. A. Gubanov, “Algebraic solution of a problem of optimal project scheduling in project management,” Vestnik of St Petersburg University. Mathematics. Mechanics. Astronomy, vol. 8(66), no. 1, pp. 73–87, 2021 (in Russian); doi:10.21638/spbu01.2021.107

S. A. Gubanov, “Algebraic solution to optimal scheduling problems taking into account the scheduled start time of jobs in projects,” Vestnik of St Petersburg University. Mathematics. Mechanocs. Astronomy, vol. 9(67), no. 4, pp. 602–611, 2022 (in Russian); doi:10.21638/spbu01.2022.403

N. Krivulin, “Tropical optimization technique in bi-objective project scheduling under temporal constraints,” Computational Management Science, vol. 17, no. 3, pp. 437–464, 2020 (in Russian); doi:10.1007/s10287-020-00374-5

N. K. Krivulin and M. A. Tsobenko, “Solution of the two-criteria problem of rating alternatives using tropical optimization,” Computer Tools in Education, no. 4, pp. 15–32, 2019; doi:10.32603 /2071-2340-2019-4-15-32