Algebraic solution of optimal scheduling problems subject to due dates for start time of project jobs
DOI:
https://doi.org/10.21638/spbu01.2022.403Abstract
A direct solution is proposed for problems of drawing up the optimal schedule for jobs in a project based on using models and methods of tropical optimization. The problems of the development of an optimal plan are reduced to problems of tropical optimization, which consist in minimizing the objective function under given strict constraints on the start and finish time of jobs. As optimality criteria of the plan the maximum deviation from the due dates of the start of the jobs of the project is taken, which needs to be minimized. Strict time constraints for the jobs are given in the form of precedence relations and bounds for the start and finish times of the jobs. Such tasks arise if it is necessary for one reason or another (for example, due to technological limitations or safety requirements) to start jobs at specified time. In the article constraints and objective functions are first described in terms of ordinary mathematics and then the considered problems of project sheduling are set. Elements of tropical mathematics are discussed which are necessary for the presentation of the problems of drawing up the optimal schedule in a tropical form. Then the sheduling problems are formulated in terms of the idempotent mathematics and reduced to the problem of tropical optimization. Solution of the problems are presented in an explicit analytical form, which well suited for both formal analysis and numerical computations. An explanatory numerical example is provided at the end of the article.Keywords:
tropical mathematics, idempotent semifield, tropical optimization, project sheduling, network planning
Downloads
Download data is not yet available.
References
Литература
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.)
Downloads
Published
2022-12-26
How to Cite
Gubanov S. А. (2022). Algebraic solution of optimal scheduling problems subject to due dates for start time of project jobs. Vestnik of Saint Petersburg University. Mathematics. Mechanics. Astronomy, 9(4), 602–611. https://doi.org/10.21638/spbu01.2022.403
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.
