Minimizing maximum lateness in two-stage projects by tropical optimization

Krivulin, Nikolai ; Sergeev, Sergeĭ

Kybernetika, Tome 58 (2022) no. 5, pp. 816-841

Abstract (VO)

We are considering a two-stage optimal scheduling problem, which involves two similar projects with the same starting times for workers and the same deadlines for tasks. It is required that the starting times for workers and deadlines for tasks should be optimal for the first-stage project and, under this condition, also for the second-stage project. Optimality is measured with respect to the maximal lateness (or maximal delay) of tasks, which has to be minimized. We represent this problem as a problem of tropical pseudoquadratic optimization and show how the existing methods of tropical optimization and tropical linear algebra yield a full and explicit solution for this problem.

Détail

DOI : 10.14736/kyb-2022-5-0816

Classification : 15A80, 90B35, 90B50, 90C24, 90C47
Keywords: tropical optimization; tropical linear algebra; minimax optimization problem; project scheduling; maximum lateness

Bibliographie

[1] Allamigeon, X., Benchimol, P., Gaubert, S., Joswig, M.: Tropicalizing the simplex algorithm. SIAM J. Discrete Math. 29 (2015), 2, 751-795. | DOI

[2] Baccelli, F. L., Cohen, G., Olsder, G. J., Quadrat, J.-P.: Synchronization and Linearity. Wiley Series in Probability and Statistics, Wiley, Chichester 1993. | Zbl

[3] Bouquard, J.-L., Lenté, C., Billaut, J.-C.: Application of an optimization problem in max-plus algebra to scheduling problems. Discrete Appl. Math. 154 (2006), 15, 2064-2079. | DOI

[4] Butkovič, P.: Max-linear Systems. Springer Monographs in Mathematics, Springer, London 2010.

[5] Carré, B. A.: An algebra for network routing problems. IMA J. Appl. Math. 7 (1971), 3, 273-294. | DOI

[6] Cuninghame-Green, R.: Minimax Algebra. Lecture Notes in Economics and Mathematical Systems 166, Springer, Berlin 1979. | DOI | Zbl

[7] Cuninghame-Green, R. A.: Describing industrial processes with interference and approximating their steady-state behaviour. Oper. Res. Quart. 13 (1962), 1, 95-100. | DOI

[8] Cuninghame-Green, R. A.: Minimax algebra and applications. | Zbl

[9] Puente, M. J. de la: Quasi-Euclidean classification of alcoved convex polyhedra. Linear Multilinear Algebra 68 (2020), 10, 2110-2142. | DOI

[10] Demeulemeester, E. L., Herroelen, W. S.: Project Scheduling. International Series in Operations Research and Management Science 49, Springer, New York 2002. | DOI

[11] Ehrgott, M.: Multicriteria Optimization. Second edition. Springer, Berlin 2005. | DOI

[12] Gaubert, S., Katz, R. D.: The Minkowski theorem for max-plus convex sets. Linear Algebra Appl. 421 (2007), 2, 356-369. | DOI

[13] Gaubert, S., Katz, R. D., Sergeev, S.: Tropical linear-fractional programming and parametric mean payoff games. J. Symbolic Comput. 47 (2012), 12, 1447-1478. | DOI

[14] Giffler, B.: Scheduling general production systems using schedule algebra. Naval Res. Logist. Quart. 10 (1963), 1, 237-255. | DOI

[15] Golan, J. S.: Semirings and Affine Equations Over Them. Mathematics and Its Applications 556, Kluwer Acad. Publ., Dordrecht 2003. | DOI

[16] Gondran, M., Minoux, M.: Graphs, Dioids and Semirings. Operations Research / Computer Science Interfaces 41, Springer, New York 2008. | DOI

[17] Goto, H.: Robust MPL scheduling considering the number of in-process jobs. Eng. Appl. Artif. Intell. 22 (2009), 4, 603-607. | DOI

[18] Heidergott, B., Olsder, G. J., Woude, J. van der: Max Plus at Work. Princeton Series in Applied Mathematics, Princeton Univ. Press, Princeton 2006.

[19] Katz, R. D., Nitica, V., Sergeev, S.: Characterization of tropical hemispaces by (P,R)-decompositions. Linear Algebra Appl. 440 (2014), 131-163. | DOI

[20] Kolokoltsov, V. N., Maslov, V. P.: Idempotent Analysis and Its Applications. Mathematics and Its Applications 401, Springer, Dordrecht 1997. | DOI | Zbl

[21] Krivulin, N.: A constrained tropical optimization problem: Complete solution and application example. In: Tropical and Idempotent Mathematics and Applications (G. L. Litvinov and S. N. Sergeev, eds.), Contemporary Mathematics 616, AMS, Providence 2014, pp. 163-177. | DOI

[22] Krivulin, N.: Extremal properties of tropical eigenvalues and solutions to tropical optimization problems. Linear Algebra Appl. 468 (2015), 211-232. | DOI

[23] Krivulin, N.: A multidimensional tropical optimization problem with nonlinear objective function and linear constraints. Optimization 64 (2015), 5, 1107-1129. | DOI

[24] Krivulin, N.: Direct solution to constrained tropical optimization problems with application to project scheduling. Comput. Manag. Sci. 14 (2017), 1, 91-113. | DOI

[25] Krivulin, N.: Tropical optimization problems in time-constrained project scheduling. Optimization 66 (2017), 2, 205-224. | DOI

[26] Krivulin, N.: Tropical optimization problems with application to project scheduling with minimum makespan. Ann. Oper. Res. 256 (2017), 1, 75-92. | DOI

[27] Krivulin, N.: Tropical optimization technique in bi-objective project scheduling under temporal constraints. Comput. Manag. Sci. 17 (2020), 3, 437-464. | DOI

[28] Neumann, K., Schwindt, C., Zimmermann, J.: Project Scheduling with Time Windows and Scarce Resources. Second edition. Springer, Berlin 2003. | DOI

[29] Sergeev, S., Liu, Z.: Tropical analogues of a Dempe-Franke bilevel optimization problem. In: Optimization of Complex Systems: Theory, Models, Algorithms and Applications (H. A. Le Thi, H. M. Le, and T. Pham Dinh, eds.), Springer, Cham 2020, pp. 691-701.

[30] T'kindt, V., Billaut, J.-C.: Multicriteria Scheduling. Second edition. Springer, Berlin 2006. | DOI

[31] Yoeli, M.: A note on a generalization of boolean matrix theory. Amer. Math. Monthly 68 (1961), 6, 552-557. | DOI | Zbl