×

Direct solution to constrained tropical optimization problems with application to project scheduling. (English) Zbl 1397.90312

Summary: We examine a new optimization problem formulated in the tropical mathematics setting as a further extension of certain known problems. The problem is to minimize a nonlinear objective function, which is defined on vectors over an idempotent semifield by using multiplicative conjugate transposition, subject to inequality constraints. As compared to the known problems, the new one has a more general objective function and additional constraints. We provide a complete solution in an explicit form to the problem by using an approach that introduces an auxiliary variable to represent the values of the objective function, and then reduces the initial problem to a parametrized vector inequality. The minimum of the objective function is evaluated by applying the existence conditions for the solution of this inequality. A complete solution to the problem is given by solving the parametrized inequality, provided the parameter is set to the minimum value. As a consequence, we obtain solutions to new special cases of the general problem. To illustrate the application of the results, we solve a real-world problem drawn from time-constrained project scheduling, and offer a representative numerical example.

MSC:

90C26 Nonconvex programming, global optimization
90B35 Deterministic scheduling theory in operations research
90C30 Nonlinear programming
90B70 Theory of organizations, manpower planning in operations research
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Baccelli FL, Cohen G, Olsder GJ, Quadrat JP (1993) Synchronization and linearity. Wiley series in probability and statistics. Wiley, Chichester
[2] Butkovič P (2010) Max-linear systems. Springer monographs in mathematics. Springer, London. doi:10.1007/978-1-84996-299-5
[3] Cuninghame-Green R (1979) Minimax algebra. Lecture notes in economics and mathematical systems, vol 166. Springer, Berlin. doi:10.1007/978-3-642-48708-8 · Zbl 0399.90052
[4] Cuninghame-Green, RA, Describing industrial processes with interference and approximating their steady-state behaviour, Oper Res Q, 13, 95-100, (1962) · doi:10.2307/3007584
[5] Demeulemeester EL, Herroelen WS (2002) Project scheduling. International series in operations research and management science, vol 49. Springer, New York. doi:10.1007/b101924
[6] Elsner, L; Driessche, P, MAX-algebra and pairwise comparison matrices, Linear Algebra Appl, 385, 47-62, (2004) · Zbl 1056.15009 · doi:10.1016/S0024-3795(03)00476-2
[7] Elsner L, van den Driessche P (2010) Max-algebra and pairwise comparison matrices, II. Linear Algebra Appl 432(4):927-935. doi:10.1016/j.laa.2009.10.005 · Zbl 1191.15019
[8] Engel, GM; Schneider, H, Diagonal similarity and equivalence for matrices over groups with 0, Czechoslovak Math J, 25, 389-403, (1975) · Zbl 0329.15007
[9] Golan JS (2003) Semirings and affine equations over them. Mathematics and its applications, vol 556. Kluwer Acad. Publ, Dordrecht. doi:10.1007/978-94-017-0383-3
[10] Gondran M, Minoux M (2008) Graphs, dioids and semirings. Operations research/ computer science interfaces, vol 41. Springer, New York. doi:10.1007/978-0-387-75450-5 · Zbl 1201.16038
[11] Gursoy, BB; Mason, O; Sergeev, S, The analytic hierarchy process, MAX algebra and multi-objective optimisation, Linear Algebra Appl, 438, 2911-2928, (2013) · Zbl 1282.90087 · doi:10.1016/j.laa.2012.11.020
[12] Heidergott B, Olsder GJ, van der Woude J (2006) Max-plus at work. Princeton series in applied mathematics. Princeton University Press, Princeton
[13] Hoffman, AJ, On abstract dual linear programs, Naval Res Logist Q, 10, 369-373, (1963) · Zbl 0122.15301 · doi:10.1002/nav.3800100131
[14] Hudec, O; Zimmermann, K, A service points location problem with MIN-MAX distance optimality criterion, Acta Univ Carolin Math Phys, 34, 105-112, (1993) · Zbl 0802.90062
[15] Kolokoltsov VN, Maslov VP (1997) Idempotent analysis and its applications. Mathematics and its applications, vol 401. Kluwer Acad. Publ, Dordrecht. doi:10.1007/978-94-015-8901-7
[16] Krivulin N (2014) A constrained tropical optimization problem: complete solution and application example. In: Litvinov GL, Sergeev SN (eds) Tropical and idempotent mathematics and applications. Contemporary mathematics, vol 616. AMS, Providence, pp 163-177. doi:10.1090/conm/616/12308 · Zbl 1320.65101
[17] Krivulin, N, Extremal properties of tropical eigenvalues and solutions to tropical optimization problems, Linear Algebra Appl, 468, 211-232, (2015) · Zbl 1307.65089 · doi:10.1016/j.laa.2014.06.044
[18] Krivulin, N, A multidimensional tropical optimization problem with nonlinear objective function and linear constraints, Optimization, 64, 1107-1129, (2015) · Zbl 1311.65086 · doi:10.1080/02331934.2013.840624
[19] Krivulin N (2015c) Tropical optimization problems in project scheduling. In: Hanzálek Z, Kendall G, McCollum B, Šůcha P (eds) MISTA 2015 proceedings, MISTA, pp 492-506
[20] Krivulin N (2015d) Tropical optimization problems with application to project scheduling with minimum makespan. Ann Oper Res 1-18. doi:10.1007/s10479-015-1939-9 · Zbl 1411.90325
[21] Krivulin, NK, An extremal property of the eigenvalue for irreducible matrices in idempotent algebra and an algebraic solution to a rawls location problem, Vestnik St Petersburg Univ Math, 44, 272-281, (2011) · Zbl 1272.15007 · doi:10.3103/S1063454111040078
[22] Maclagan D, Sturmfels B (2015) Introduction to tropical geometry. Graduate studies in mathematics, vol 161. AMS, Providence · Zbl 1321.14048
[23] Neumann K, Schwindt C, Zimmermann J (2003) Project scheduling with time windows and scarce resources, 2nd edn. Springer, Berlin. doi:10.1007/978-3-540-24800-2 · Zbl 1059.90001
[24] Pandit SNN (1961) A new matrix calculus. J SIAM 9(4):632-639. doi:10.1137/0109052 · Zbl 0111.01702
[25] Romanovskiĭ, IV, Asymptotic behavior of dynamic programming processes with a continuous set of states, Soviet Math Dokl, 5, 1684-1687, (1964) · Zbl 0294.49009
[26] Superville L (1978) Various aspects of max-algebra. PhD thesis, The City University of New York, New York
[27] T’kindt V, Billaut JC (2006) Multicriteria scheduling, 2nd edn. Springer, Berlin. doi:10.1007/b106275
[28] Vorob’ev, NN, The extremal matrix algebra, Soviet Math Dokl, 4, 1220-1223, (1963) · Zbl 0168.02602
[29] Zimmermann, K, Optimization problems with unimodal functions in MAX-separable constraints, Optimization, 24, 31-41, (1992) · Zbl 0814.65064 · doi:10.1080/02331939208843777
[30] Zimmermann U (1981) Linear and combinatorial optimization in ordered algebraic structures. Annals of discrete mathematics, vol 10. Elsevier, Amsterdam · Zbl 0466.90045
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.