Алгебраическое решение задачи оптимального планирования сроков проекта в управлении проектами

Николай Кимович Кривулин; Сергей Александрович Губанов

doi:10.21638/spbu01.2021.107

Авторы

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

DOI:

https://doi.org/10.21638/spbu01.2021.107

Аннотация

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

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

идемпотентное полуполе, тропическая оптимизация, минимаксная задача оптимизации, временное планирование проекта, управление проектом

Скачивания

Данные скачивания пока недоступны.

Библиографические ссылки

Литература

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).