Algebraic solution of a problem of optimal project scheduling in project management
DOI:
https://doi.org/10.21638/spbu01.2021.107Abstract
A problem of optimal scheduling is considered for a project that consists of a certain set of works to be performed under given constraints on the times of start and finish of the works. As the optimality criterion for scheduling, the maximum deviation of the start time of works is taken to be minimized. Such problems arise in project management when it is required, according to technological, organizational, economic or other reasons, to provide, wherever possible, simultaneous start of all works. The scheduling problem under consideration is formulated as a constrained minimax optimization problem and then solved using methods of tropical (idempotent) mathematics which deals with the theory and applications of semirings with idempotent addition. First, a tropical optimization problem is investigated defined in terms of a general idempotent semifield (an idempotent semiring with invertible multiplication), and a complete analytical solution of the problem is derived. The result obtained is then applied to find a direct solution of the scheduling problem in a compact vector form ready for further analysis of solutions and straightforward computations. As an illustration, a numerical example of solving optimal scheduling problem is given for a project that consists of four works.Keywords:
idempotent semifield, tropical optimization, minimax optimization problem, project scheduling, project management
Downloads
Download data is not yet available.
References
Литература
1. Троцкий М., Груча Б., Огонек К. Управление проектами, пер. с польск. Москва, Финансы и статистика (2006).
2. Kerzner H. Project Management. 10th ed. Hoboken, Wiley (2010).
3. Pinedo M. L. Scheduling. 3rd ed. New York, Springer (2008).
4. Vanhoucke M. Project Management with Dynamic Scheduling. 2nd ed. Berlin, Springer (2012). https://doi.org/10.1007/978-3-642-40438-2
5. Blazewicz J., Ecker K.H., Pesch E., Schmidt G., Sterna M., Weglarz J. Handbook on Scheduling. In: International Handbooks on Information Systems. Cham, Springer (2019). https://doi.org/10.1007/978-3-319-99849-7
6. Бурков В.Н., Буркова И.В., Засканов В. Г. Метод сетевого программирования в зада- чах календарного планирования. Автомат. и телемех., (6), 17–28 (2020). https://doi.org/10.31857 /S0005231020060025
7. Baccelli F. L., Cohen G., Olsder G. J., Quadrat J.-P. Synchronization and Linearity. In: Wiley Series in Probability and Statistics. Chichester, Wiley (1993).
8. Маслов В.П., Колокольцов В.Н. Идемпотентный анализ и его применение в оптималь- ном управлении. Москва, Физматлит (1994).
9. Golan J. S. Semirings and Affine Equations Over Them. In: Mathematics and Its Applications, vol. 556. New York, Springer (2003). https://doi.org/10.1007/978-94-017-0383-3
10. Heidergott B., Olsder G. J., van der Woude J. Max Plus at Work. In: Princeton Series in Applied Mathematics. Princeton, Princeton Univ. Press (2006).
11. Gondran M., Minoux M., Graphs, Dioids and Semirings. In: Operations Research/Computer Science Interfaces, vol. 41. New York, Springer (2008). https://doi.org/10.1007/978-0-387-75450-5
12. Butkovi c P. Max-linear Systems. In: Springer Monographs in Mathematics. London, Springer (2010). https://doi.org/10.1007/978-1-84996-299-5
13. Krivulin N. A multidimensional tropical optimization problem with nonlinear objective function and linear constraints. Optimization 64 (5), 1107–1129 (2015). https://doi.org/10.1080/02331934.2013. 840624
14. Krivulin N. A constrained tropical optimization problem: complete solution and application example. In: G. L. Litvinov, S. N. Sergeev (eds). Tropical and Idempotent Mathematics and Applications. Contemporary Mathematics, vol. 616, 163–177. Providence, AMS (2014). https://doi.org/10.1090/conm/616/12308
15. Krivulin N. Extremal properties of tropical eigenvalues and solutions to tropical optimization problems. Linear Algebra Appl. 468, 211–232 (2015). https://doi.org/10.1016/j.laa.2014.06.044
16. Krivulin N. Direct solution to constrained tropical optimization problems with application to project scheduling. Comput. Manag. Sci. 14 (1), 91–113 (2017). https://doi.org/10.1007/s10287-016- 0259-0
17. Krivulin N. Tropical optimization problems with application to project scheduling with minimum makespan. Ann. Oper. Res. 256 (1), 75–92 (2017). https://doi.org/10.1007/s10479-015-1939-9
18. Krivulin N. Tropical optimization problems in time-constrained project scheduling. Optimization 66 (2), 205–224 (2017). https://doi.org/10.1080/02331934.2016.1264946
19. Кривулин Н.К., Губанов С.А. Решение задачи сетевого планирования на основе методов тропической оптимизации. Вестник Санкт-Петербургского университета. Сер. 10. Прикладная математика. Информатика. Процессы управления 12, вып. 3, 62–72 (2016). https://doi.org/10.21638/11701/spbu10.2016.306
20. Кривулин Н.К., Губанов С.А. Использование методов тропической оптимизации в задачах сетевого планирования. Вестник Санкт-Петербургского университета. Прикладная математи- ка. Информатика. Процессы управления 13, вып. 4, 384–397 (2017). https://doi.org/10.21638/11701/ spbu10.2017.405
21. Kantorovich L.V. Mathematical methods of organizing and planning production. Management Sci. 6 (4), 366–422 (1960). https://doi.org/10.1287/mnsc.6.4.366
22. Романовский И.В. Алгоритмы решения экстремальных задач. Москва, Наука (1977).
23. Васильев Ф.П., Иваницкий А.Ю. Линейное программирование. 3-е изд. Москва, Факто- риал Пресс (2008).
24. Karmarkar N. A new polynomial-time algorithm for linear programming. Combinatorica 4 (4), 373–395 (1984). https://doi.org/10.1007/BF02579150
References
1. Trocki M., Grucza B., Ogonek K. Zaraza˛dzanie Projectami. Warszawa, PWE (2003). (In Polish) [Russ. ed.: Upravlenie proektami. Moscow, Finansy i statistika Publ. (2006)].
2. Kerzner H. Project Management. 10th ed. Hoboken, Wiley (2010).
3. Pinedo M. L. Scheduling. 3rd ed. New York, Springer (2008).
4. Vanhoucke M. Project Management with Dynamic Scheduling. 2nd ed. Berlin, Springer (2012). https://doi.org/10.1007/978-3-642-40438-2
5. Blazewicz J., Ecker K.H., Pesch E., Schmidt G., Sterna M., Weglarz J. Handbook on Scheduling. In: International Handbooks on Information Systems. Cham, Springer (2019). https://doi.org/10.1007/978-3-319-99849-7
6. Burkov V.N., Burkova I.V., Zaskanov V.G. The network programming method in project scheduling problems. Avtomat. i Telemekh., (6), 17–28 (2020). https://doi.org/10.31857 /S0005231020060025 (In Russian) [Engl. transl.: Autom. Remote Control 81 (6), 978–987 (2020). https://doi.org/10.1134/S000511792006003X].
7. Baccelli F. L., Cohen G., Olsder G. J., Quadrat J.-P. Synchronization and Linearity. In: Wiley Series in Probability and Statistics. Chichester, Wiley (1993).
8. Maslov V. P., Kolokoltsov V.N. Idempotent analysis and its applications to optimal control theory. Moscow, Nauka Publ. (1994). (In Russian)
9. Golan J. S. Semirings and Affine Equations Over Them. In: Mathematics and Its Applications, vol. 556. New York, Springer (2003). https://doi.org/10.1007/978-94-017-0383-3
10. Heidergott B., Olsder G. J., van der Woude J. Max Plus at Work. In: Princeton Series in Applied Mathematics. Princeton, Princeton Univ. Press (2006).
11. Gondran M., Minoux M., Graphs, Dioids and Semirings. In: Operations Research/Computer Science Interfaces, vol. 41. New York, Springer (2008). https://doi.org/10.1007/978-0-387-75450-5
12. Butkovi c P. Max-linear Systems. In: Springer Monographs in Mathematics. London, Springer (2010). https://doi.org/10.1007/978-1-84996-299-5
13. Krivulin N. A multidimensional tropical optimization problem with nonlinear objective function and linear constraints. Optimization 64 (5), 1107–1129 (2015). https://doi.org/10.1080/02331934.2013. 840624
14. Krivulin N. A constrained tropical optimization problem: complete solution and application example. In: G. L. Litvinov, S. N. Sergeev (eds). Tropical and Idempotent Mathematics and Applications. Contemporary Mathematics, vol. 616, 163–177. Providence, AMS (2014). https://doi.org/10.1090/conm/616/12308
15. Krivulin N. Extremal properties of tropical eigenvalues and solutions to tropical optimization problems. Linear Algebra Appl. 468, 211–232 (2015). https://doi.org/10.1016/j.laa.2014.06.044
16. Krivulin N. Direct solution to constrained tropical optimization problems with application to project scheduling. Comput. Manag. Sci. 14 (1), 91–113 (2017). https://doi.org/10.1007/s10287-016- 0259-0
17. Krivulin N. Tropical optimization problems with application to project scheduling with minimum makespan. Ann. Oper. Res. 256 (1), 75–92 (2017). https://doi.org/10.1007/s10479-015-1939-9
18. Krivulin N. Tropical optimization problems in time-constrained project scheduling. Optimization 66 (2), 205–224 (2017). https://doi.org/10.1080/02331934.2016.1264946
19. Krivulin N.K., Gubanov S.A. Solution of a project scheduling problem by using methods of tropical mathematics. Vestnik of Saint Petersburg University. Series 10. Applied mathematics. Computer science. Control processes 12, iss. 3, 62–72 (2016). https://doi.org/10.21638/11701/spbu10.2016.306 (In Russian)
20. Krivulin N.K., Gubanov S.A. The use of tropical optimization methods in problems of project scheduling. Vestnik of Saint Petersburg University. Applied Mathematics. Computer Science. Control Processes 13, iss. 4, 384–397 (2017). https://doi.org/10.21638/11701/spbu10.2017.405 (In Russian)
21. Kantorovich L.V. Mathematical methods of organizing and planning production. Management Sci. 6 (4), 366–422 (1960). https://doi.org/10.1287/mnsc.6.4.366
22. Romanovskiy I.V. Algorithms for Solving Extremal Problems. Moscow, Nauka Publ. (1977). (In Russian)
23. Vasilyev F.P., Ivanitskiy A.Y. Linear Programming. 3rd ed. Moscow, Factorial Press (2008). (In Russian)
24. Karmarkar N. A new polynomial-time algorithm for linear programming. Combinatorica 4 (4), 373–395 (1984). https://doi.org/10.1007/BF02579150
Downloads
Published
2021-05-29
How to Cite
Krivulin, N. K., & Gubanov, S. A. (2021). Algebraic solution of a problem of optimal project scheduling in project management. Vestnik of Saint Petersburg University. Mathematics. Mechanics. Astronomy, 8(1), 73–87. https://doi.org/10.21638/spbu01.2021.107
Issue
Section
Mathematics
License
Articles of "Vestnik of Saint Petersburg University. Mathematics. Mechanics. Astronomy" are open access distributed under the terms of the License Agreement with Saint Petersburg State University, which permits to the authors unrestricted distribution and self-archiving free of charge.
