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

Authors

  • 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 DOI: https://doi.org/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 DOI: https://doi.org/10.1007/b101924

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

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

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 DOI: https://doi.org/10.1007/978-0-387-77247-9_18

M. Ehrgott, Multicriteria Optimization, 2nd ed., Berlin: Springer, 2005; doi:10.1007/3-540-27659-9 DOI: https://doi.org/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 DOI: https://doi.org/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 affine equations over them, Mathematics and Its Applications, vol. 556, New York, NY, USA: Springer, 2003; doi:10.1007/978-94-017-0383-3 DOI: https://doi.org/10.1007/978-94-017-0383-3_1

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 DOI: https://doi.org/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 DOI: https://doi.org/10.1007/978-1-84996-299-5_7

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 DOI: https://doi.org/10.1016/j.dam.2005.04.011

M. Singh and R. P. Judd, “Efficient 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 DOI: https://doi.org/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 DOI: https://doi.org/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 DOI: https://doi.org/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 DOI: https://doi.org/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 DOI: https://doi.org/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 DOI: https://doi.org/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 DOI: https://doi.org/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 DOI: https://doi.org/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 DOI: https://doi.org/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 DOI: https://doi.org/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 DOI: https://doi.org/10.32603/2071-2340-2019-4-15-32

Downloads

Published

2026-03-31

Issue

No. 1 (2026)

Section

Algorithmic mathematics and mathematical modelling

License

Copyright (c) 2026 Nikolai Krivulin, Vadim Simonenko

Creative Commons License

This work is licensed under a Creative Commons Attribution 4.0 International License.

Public offer

How to Cite

[1]
N. Krivulin and V. Simonenko, “Solution of Two-Criteria Project Scheduling Problems Using Methods of Tropical Optimization”, Comput. Tools Educ., no. 1, pp. 5–21, Mar. 2026, doi: 10.32603/2071-2340-2026-1-5-21.

Most read articles by the same author(s)