Geodesic
Solution of a project scheduling problem by using methods of tropical optimization
Vestnik Sankt-Peterburgskogo universiteta. Prikladnaâ matematika, informatika, processy upravleniâ, no. 3 (2016), pp. 62-72 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

The paper deals with the application of methods of tropical optimization to the solution of project scheduling problems. A problem is considered to find an optimal schedule for a project, which consists of a set of activities to be performed under various constraints on the initiation and completion times of the activities. The optimal scheduling objective takes the form of the minimum of maximum deviation between completion times of the activities. In the paper, the scheduling problem is first formulated in the form of an ordinary constrained optimization problem. Next, certain basic definitions and results of tropical mathematics are presented, required for the subsequent analysis and solution of tropical optimization problems. A new tropical optimization problem with constraints is formulated, and its solution is derived. Finally, the scheduling problem under study is solved by reduction to the tropical optimization problem, which was previously investigated. To conclude, a numerical example is given. Refs 18.
Keywords: project management, project scheduling, idempotent semifield, tropical optimization problem. 
@article{VSPUI_2016_3_a5,
     author = {N. Krivulin and S. A. Gubanov},
     title = {Solution of a project scheduling problem by using methods of tropical optimization},
     journal = {Vestnik Sankt-Peterburgskogo universiteta. Prikladna\^a matematika, informatika, processy upravleni\^a},
     pages = {62--72},
     year = {2016},
     number = {3},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/VSPUI_2016_3_a5/}
}
TY  - JOUR
AU  - N. Krivulin
AU  - S. A. Gubanov
TI  - Solution of a project scheduling problem by using methods of tropical optimization
JO  - Vestnik Sankt-Peterburgskogo universiteta. Prikladnaâ matematika, informatika, processy upravleniâ
PY  - 2016
SP  - 62
EP  - 72
IS  - 3
UR  - http://geodesic.mathdoc.fr/item/VSPUI_2016_3_a5/
LA  - ru
ID  - VSPUI_2016_3_a5
ER  - 
%0 Journal Article
%A N. Krivulin
%A S. A. Gubanov
%T Solution of a project scheduling problem by using methods of tropical optimization
%J Vestnik Sankt-Peterburgskogo universiteta. Prikladnaâ matematika, informatika, processy upravleniâ
%D 2016
%P 62-72
%N 3
%U http://geodesic.mathdoc.fr/item/VSPUI_2016_3_a5/
%G ru
%F VSPUI_2016_3_a5
N. Krivulin; S. A. Gubanov. Solution of a project scheduling problem by using methods of tropical optimization. Vestnik Sankt-Peterburgskogo universiteta. Prikladnaâ matematika, informatika, processy upravleniâ, no. 3 (2016), pp. 62-72. http://geodesic.mathdoc.fr/item/VSPUI_2016_3_a5/

[1] I. I. Mazur, V. D. Shapiro (eds.), Project management, Vysshaya Shkola Publ., M., 2001, 875 pp. (In Russian)

[2] Gray C. G., Larson E. W., Project Management, McGraw-Hill Irwin, New York, 2002, 574 pp.

[3] A Guide to the Project Management Body of Knowledge (PMBOK Guide), Project Management Institute, Newtown Square, 2008, 459 pp.

[4] Kelley J. E., “Critical-path planning and scheduling: mathematical basis”, Oper. Res., 9:3 (1961), 296–320 | DOI | MR | Zbl

[5] Malcolm D. G., Roseboom J. H., Clark C. E., Fazar W., “Application of a technique for research and development program evaluation”, Oper. Res., 7:5 (1959), 646–669 | DOI | Zbl

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

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

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

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

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

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

[12] 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

[13] 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

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

[15] Krivulin N., “Extremal properties of tropical eigenvalues and solutions to tropical optimization problems”, Linear Algebra Appl., 468 (2015), 211–232 | DOI | MR | Zbl

[16] Krivulin N., “Tropical optimization problems in project scheduling”, Proc. 7th Multidisciplinary Intern. Conf. on Scheduling: Theory and Applications, MISTA 2015, eds. Z. Hanzálek, G. Kendall, B. McCollum, P. Šůcha, 492–506 (accessed: 01.04.2016) http://schedulingconference.org/proceedings/2015/mista2015.pdf | MR

[17] Krivulin N., “Tropical optimization problems with application to project scheduling with minimum makespan”, Ann. Oper. Res., 2015, 1–18 | MR

[18] T'kindt V., Billaut J. C., Multicriteria Scheduling, Springer, Berlin, 2006, 360 pp. | Zbl