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

Nikolai Krivulin; Vadim Simonenko

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

Nikolai Krivulin Saint Petersburg State University, Universitetskaya nab. 7–9, St. Petersburg, 199034, Russian Federation https://orcid.org/0000-0003-3070-9355
Vadim Simonenko Saint Petersburg State University, Universitetskaya nab. 7–9, St. Petersburg, 199034, Russian Federation

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

Keywords: tropical optimization, two-criteria optimization problems, Pareto optimality, project scheduling, time constraints

Abstract

The paper considers two-criteria problems to schedule a project that consists in performing a given set of activities with restrictions on the start and end times of the activities. The maximum time of the working cycle and the spread of the start time of activities that need to be minimized are taken as the optimality criteria of the plan for one of the problems. The other problem is to minimize the total duration of the project and the spread of the start time of activities. The solution of the problems is based on representation in terms of tropical algebra, which studies algebraic systems with idempotent operations. By applying methods of tropical optimization, results are obtained that analytically describe all Pareto-optimal solutions to the considered problems in parametric form. Illustrative numerical examples of solving two-criteria problems for a project of three activities are given.

Author Biographies

Nikolai Krivulin, Saint Petersburg State University, Universitetskaya nab. 7–9, St. Petersburg, 199034, Russian Federation

Dr. Sci. (Phys.-Math.), Professor at the Department of Statistical Modeling, St. Petersburg State University, nkk@math.spbu.ru

Vadim Simonenko, Saint Petersburg State University, Universitetskaya nab. 7–9, St. Petersburg, 199034, Russian Federation

Student at St. Petersburg State University, vadimka.simonenko@gmail.com

References

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

Solution of Two-Criteria Project Scheduling Problems Using Methods of Tropical Optimization

Abstract

Author Biographies

References