Алгебраическое решение задач оптимального планирования с учетом директивных сроков начала работ проекта
DOI:
https://doi.org/10.21638/spbu01.2022.403Аннотация
Предлагается прямое аналитическое решение задач составления оптимального графика выполнения работ проекта, основанное на использовании моделей и методов тропической (идемпотентной) оптимизации. Задачи построения оптимального графика сводятся к задачам тропической оптимизации, которые заключаются в минимизации целевой функции при заданных строгих ограничениях на время выполнения работ. В качестве критерия оптимальности плана рассматривается максимальное отклонение от директивных сроков времени начала работ проекта, которое требуется минимизировать. Строгие ограничения на время выполнения работ проекта выражены в виде условий предшествования и границ на время начала и окончания работ проекта. Подобные задачи возникают при необходимости по тем или иным причинам (например, по технологическим ограничениям или требованиям безопасности) по возможности обеспечить начало работ в заданное время. В статье сначала описываются ограничения и целевые функции в терминах обычной математики и формально задаются исследуемые задачи управления проектами. Далее приводятся необходимые для представления задач составления оптимального графика элементы тропической математики. Затем задачи планирования формулируются в терминах идемпотентной математики и таким образом сводятся к задаче тропической оптимизации. Предлагается решение задачи, представленное в явном виде в аналитической форме, удобной как для формального анализа, так и для численных расчетов. В конце статьи предложен поясняющий численный пример.Ключевые слова:
тропическая математика, идемпотентное полуполе, тропическая оптимизация, управление проектами, сетевое планирование
Скачивания
Данные скачивания пока недоступны.
Библиографические ссылки
Литература
1. Маслов В.П., Колокольцев В.Н. Идемпотентный анализ и его применение воптимальном управлении. Москва, Физматлит (1994).
2. Golan J.S. Semirings and Affine Equations Over Them: Theory and Applications. In Ser.: Mathematics and Its Applications, vol. 556. New York, Springer (2003). https://doi.org/10.1007/978-94- 017-0383-3
3. Heidergott B., Olsder G.J., van der Woude J. Max Plus at Work. Princeton Series in Applied Mathematics. Princeton, Princeton University Press (2006).
4. Butkoviˇc P. Max-linear Systems: Theory and Algorithms. In: Springer Monographs in Mathematics. London, Springer (2010).
5. Кривулин Н.К. Методы идемпотентной алгебры взадачах моделирования и анализа сложных систем. Санкт-Петербург, Изд-во С.-Петерб. ун-та (2009).
6. Krivulin N. Direct solution to constrained tropical optimization problems with application to project scheduling. Computational Management Science 14 (1), 91-113 (2017). https://doi.org/10.1007/s10287-016-319-0259-0
7. Krivulin N. Tropical optimization problems with application to project scheduling with minimum makespan. Annals of Operations Research 256 (1), 75-92 (2017). https://doi.org/10.1007/s10479-015- 1939-9
8. Krivulin N. Tropical optimization problems in time-constrained project scheduling. Optimization 66 (2), 205-224 (2017). https://doi.org/10.1080/02331934.2016.1264946
9. Кривулин Н.К., Губанов С.А. Алгебраическое решение задачи оптимального планирования сроков проекта в управлении проектами. Вестник Санкт-Петербургского университета. Математика. Механика. Астрономия 8 (66), вып. 1, 73-87 (2021). https://doi.org/10.21638 /spbu01.2021.107
10. T’kindt V., Billaut J.C. Multicriteria Scheduling. Theory, Models and Algorithms. Berlin, Springer. 2nd ed. (2006). https://doi.org/10.1007/b106275
11. Kerzner H. Project Management. 10th ed. Hoboken, Wiley (2010).
12. Krivulin N. Complete solution of a constrained tropical optimization problem with application to location analysis. Relational and Algebraic Methods in Computer Science. Cham: Springer, 362-378 (2014). https://doi.org/10.1007/978-3-319-06251-8-22 (Lecture Notes in Computer Science, vol. 8428.)
References
1. Maslov V.P., Kolokoltsev V.N. Idempotent analysis and its application in optimal control. Moscow, Fizmatlit Publ. (1994). (In Russian)
2. Golan J.S. Semirings and Affine Equations Over Them: Theory and Applications. In Ser.: Mathematics and Its Applications, vol. 556. New York, Springer (2003). https://doi.org/10.1007/978-94- 017-0383-3
3. Heidergott B., Olsder G.J., van der Woude J. Max Plus at Work. Princeton Series in Applied Mathematics. Princeton, Princeton University Press (2006).
4. Butkoviˇc P. Max-linear Systems: Theory and Algorithms. In: Springer Monographs in Mathematics. London, Springer (2010).
5. Krivulin N. Methods of Idempotent Algebra in Problems of Complex Systems Modeling and Analysis., St Petersburg, St Petersburg University Press (2009). (In Russian)
6. Krivulin N. Direct solution to constrained tropical optimization problems with application to project scheduling. Computational Management Science 14 (1), 91-113 (2017). https://doi.org/10.1007/s10287-016-319-0259-0
7. Krivulin N. Tropical optimization problems with application to project scheduling with minimum makespan. Annals of Operations Research 256 (1), 75-92 (2017). https://doi.org/10.1007/s10479-015- 1939-9
8. Krivulin N. Tropical optimization problems in time-constrained project scheduling. Optimization 66 (2), 205-224 (2017). https://doi.org/10.1080/02331934.2016.1264946
9. Krivulin N., Gubanov S. Algebraic solution of the problem of assigning a project planning term in project management. Vestnik of Saint Petersburg University. Mathematics. Mechanics. Astronomy 8 (66), iss. 1, 73-87 (2021). https://doi.org/10.21638/spbu01.2021.107 (In Russian) [Eng. transl.: Vestnik St Petersburg University, Mathematics 54, iss. 1, 58-68 (2021). https://doi.org /10.1134/S1063454121010088].
10. T’kindt V., Billaut J.C. Multicriteria Scheduling. Theory, Models and Algorithms. Berlin, Springer. 2nd ed. (2006). https://doi.org/10.1007/b106275
11. Kerzner H. Project Management. 10th ed. Hoboken, Wiley (2010).
12. Krivulin N. Complete solution of a constrained tropical optimization problem with application to location analysis. Relational and Algebraic Methods in Computer Science. Cham: Springer, 362-378 (2014). https://doi.org/10.1007/978-3-319-06251-8-22 (Lecture Notes in Computer Science, vol. 8428.)
Загрузки
Опубликован
26.12.2022
Как цитировать
Губанов, С. А. (2022). Алгебраическое решение задач оптимального планирования с учетом директивных сроков начала работ проекта. Вестник Санкт-Петербургского университета. Математика. Механика. Астрономия, 9(4), 602–611. https://doi.org/10.21638/spbu01.2022.403
Выпуск
Раздел
Математика
Лицензия
Статьи журнала «Вестник Санкт-Петербургского университета. Математика. Механика. Астрономия» находятся в открытом доступе и распространяются в соответствии с условиями Лицензионного Договора с Санкт-Петербургским государственным университетом, который бесплатно предоставляет авторам неограниченное распространение и самостоятельное архивирование.
