Geodesic
The use of tropical optimization methods in problems of project scheduling
Vestnik Sankt-Peterburgskogo universiteta. Prikladnaâ matematika, informatika, processy upravleniâ, Tome 13 (2017) no. 4, pp. 384-397 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

The paper is devoted to the solution of problems in project scheduling by using methods of tropical optimization. Problems are examined that are to develop an optimal schedule for a project consisting in the execution of a set of interrelated tasks under given constraints on their initiation and completion time. The optimal schedule criteria are considered, which require the maximization of the deviation of the initiation or the deviation of the completion time of tasks. Such problems arise when, for some reason (such as a lack of resources, technical constraints, security requirements, and the like), there is a need to avoid a simultaneous start or finish for all tasks in the project. The paper begins with the formulation of scheduling problems in the form of usual optimization problems. Then, definitions and results of tropical mathematics are given, which are used in the subsequent analysis and solution of tropical optimization problems. New constrained problems of tropical optimization are considered, and their solutions are obtained. The scheduling problems are solved by reducing to tropical optimization problems. To illustrate the results obtained, numerical examples are presented. Refs 15.
Keywords: tropical mathematics, idempotent semifield, tropical optimization, project management, project scheduling. 
@article{VSPUI_2017_13_4_a4,
     author = {N. K. Krivulin and S. A. Gubanov},
     title = {The use of tropical optimization methods in problems of project scheduling},
     journal = {Vestnik Sankt-Peterburgskogo universiteta. Prikladna\^a matematika, informatika, processy upravleni\^a},
     pages = {384--397},
     year = {2017},
     volume = {13},
     number = {4},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/VSPUI_2017_13_4_a4/}
}
TY  - JOUR
AU  - N. K. Krivulin
AU  - S. A. Gubanov
TI  - The use of tropical optimization methods in problems of project scheduling
JO  - Vestnik Sankt-Peterburgskogo universiteta. Prikladnaâ matematika, informatika, processy upravleniâ
PY  - 2017
SP  - 384
EP  - 397
VL  - 13
IS  - 4
UR  - http://geodesic.mathdoc.fr/item/VSPUI_2017_13_4_a4/
LA  - ru
ID  - VSPUI_2017_13_4_a4
ER  - 
%0 Journal Article
%A N. K. Krivulin
%A S. A. Gubanov
%T The use of tropical optimization methods in problems of project scheduling
%J Vestnik Sankt-Peterburgskogo universiteta. Prikladnaâ matematika, informatika, processy upravleniâ
%D 2017
%P 384-397
%V 13
%N 4
%U http://geodesic.mathdoc.fr/item/VSPUI_2017_13_4_a4/
%G ru
%F VSPUI_2017_13_4_a4
N. K. Krivulin; S. A. Gubanov. The use of tropical optimization methods in problems of project scheduling. Vestnik Sankt-Peterburgskogo universiteta. Prikladnaâ matematika, informatika, processy upravleniâ, Tome 13 (2017) no. 4, pp. 384-397. http://geodesic.mathdoc.fr/item/VSPUI_2017_13_4_a4/

[1] Kerzner H., Project management, Wiley, Hoboken, 2013, 1296 pp.

[2] Cuninghame-Green R. A., “Projections in minimax algebra”, Math. Program., 10 (1976), 111–123 | DOI | MR | Zbl

[3] Zimmermann U., Linear and combinatorial optimization in ordered algebraic structures, Annals of Discrete Mathematics, 10, Elsevier, Amsterdam, 1981, 390 pp. | DOI | MR

[4] Butkovič P., Aminu A., “Introduction to max-linear programming”, IMA J. Manag. Math., 20:3 (2009), 233–249 | DOI | MR | Zbl

[5] Maslov V. P., Kolokol'tsov V. N., Idempotent analysis and its applications in optimal control, Fizmatlit Press, M., 1994, 144 pp. (In Russian)

[6] Golan J. S., Semirings and affine equations over them, Mathematics and Its Applications, 556, Springer, New York, 2003, 256 pp. | DOI | MR

[7] Heidergott B., Olsder G. J., van der Woude J., Max Plus at work, Princeton Series in Applied Mathematics, Princeton University Press, Princeton, 2006, 226 pp. | MR | Zbl

[8] Krivulin N. K., Methods of idempotent algebra for problems in modeling and analysis of complex systems, Saint Petersburg State University Publ., Saint Petersburg, 2009, 256 pp. (In Russian)

[9] Butkovič P., Max-linear systems, Springer Monographs in Mathematics, Springer, London, 2010, 272 pp. | DOI | MR | Zbl

[10] Krivulin N., “Explicit solution of a tropical optimization problem with application to project scheduling”, Mathematical Methods and Optimization Techniques in Engineering, eds. D. Biolek, H. Walter, I. Utu, C. von Lucken, WSEAS Press, Athens, 2013, 39–45 | MR

[11] Krivulin N., “A multidimensional tropical optimization problem with nonlinear objective function and linear constraints”, Optimization, 64:5 (2015), 1107–1129 | DOI | MR | Zbl

[12] Krivulin N., “A constrained tropical optimization problem: complete solution and application example”, Tropical and Idempotent Mathematics and Applications, Contemporary Mathematics, 616, eds. G. L. Litvinov, S. N. Sergeev, AMS, Providence, 2014, 163–177 | DOI | MR | Zbl

[13] Krivulin N., “A maximization problem in tropical mathematics: a complete solution and application examples”, Informatica, 27:3 (2016), 587–606 | DOI

[14] 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, 2016, no. 3, 62–72 (In Russian) | DOI

[15] Butkovič P., Tam K. P., “On some properties of the image set of a max-linear mapping”, Tropical and Idempotent Mathematics, Contemporary Mathematics, 495, eds. G. L. Litvinov, S. N. Sergeev, AMS, Providence, 2009, 115–126 | DOI | MR | Zbl