Kybernetika 58 no. 5, 816-841, 2022

Minimizing maximum lateness in two-stage projects by tropical optimization

Nikolai Krivulin and Sergeĭ SergeevDOI: 10.14736/kyb-2022-5-0816

Abstract:

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.

Keywords:

tropical optimization, tropical linear algebra, minimax optimization problem, project scheduling, maximum lateness

Classification:

90C24, 15A80, 90C47, 90B50, 90B35

paper.pdf

References:

  1. X. Allamigeon, P. Benchimol, S. Gaubert and M. Joswig: Tropicalizing the simplex algorithm. SIAM J. Discrete Math. 29 (2015), 2, 751-795.   DOI:10.1137/130936464
  2. F. L. Baccelli, G. Cohen, G. J. Olsder and J.-P. Quadrat: Synchronization and Linearity. Wiley Series in Probability and Statistics, Wiley, Chichester 1993.   CrossRef
  3. J.-L. Bouquard, C. Lenté and J.-C. Billaut: Application of an optimization problem in max-plus algebra to scheduling problems. Discrete Appl. Math. 154 (2006), 15, 2064-2079.   DOI:10.1016/j.dam.2005.04.011
  4. P. Butkovič: Max-linear Systems. Springer Monographs in Mathematics, Springer, London 2010.   CrossRef
  5. B. A. Carré: An algebra for network routing problems. IMA J. Appl. Math. 7 (1971), 3, 273-294.   DOI:10.1093/imamat/7.3.273
  6. R. Cuninghame-Green: Minimax Algebra. Lecture Notes in Economics and Mathematical Systems 166, Springer, Berlin 1979.   DOI:10.1007/978-3-642-48708-8
  7. R. A. Cuninghame-Green: Describing industrial processes with interference and approximating their steady-state behaviour. Oper. Res. Quart. 13 (1962), 1, 95-100.   DOI:10.2307/3007584
  8. R. A. Cuninghame-Green: Minimax algebra and applications.    CrossRef
  9. M. J. de la Puente: Quasi-{E}uclidean classification of alcoved convex polyhedra. Linear Multilinear Algebra 68 (2020), 10, 2110-2142.   DOI:10.1080/03081087.2019.1572065
  10. E. L. Demeulemeester and W. S. Herroelen: Project Scheduling. International Series in Operations Research and Management Science 49, Springer, New York 2002.   DOI:10.1007/b101924
  11. M. Ehrgott: Multicriteria Optimization. Second edition. Springer, Berlin 2005.   DOI:10.1007/3-540-27659-9
  12. S. Gaubert and R. D. Katz: The Minkowski theorem for max-plus convex sets. Linear Algebra Appl. 421 (2007), 2, 356-369.   DOI:10.1016/j.laa.2006.09.019
  13. S. Gaubert, R. D. Katz and S. Sergeev: Tropical linear-fractional programming and parametric mean payoff games. J. Symbolic Comput. 47 (2012), 12, 1447-1478.   DOI:10.1016/j.jsc.2011.12.049
  14. B. Giffler: Scheduling general production systems using schedule algebra. Naval Res. Logist. Quart. 10 (1963), 1, 237-255.   DOI:10.1002/nav.3800100119
  15. J. S. Golan: Semirings and Affine Equations Over Them. Mathematics and Its Applications 556, Kluwer Acad. Publ., Dordrecht 2003.   DOI:10.1007/978-94-017-0383-3
  16. M. Gondran and M. Minoux: Graphs, Dioids and Semirings. Operations Research / Computer Science Interfaces 41, Springer, New York 2008.   DOI:10.1007/978-0-387-75450-5
  17. H. Goto: Robust MPL scheduling considering the number of in-process jobs. Eng. Appl. Artif. Intell. 22 (2009), 4, 603-607.   DOI:10.1016/j.engappai.2008.11.007
  18. B. Heidergott, G. J. Olsder and J. van der Woude: Max Plus at Work. Princeton Series in Applied Mathematics, Princeton Univ. Press, Princeton 2006.   CrossRef
  19. R. D. Katz, V. Nitica and S. Sergeev: Characterization of tropical hemispaces by (P,R)-decompositions. Linear Algebra Appl. 440 (2014), 131-163.   DOI:10.1016/j.laa.2013.10.029
  20. V. N. Kolokoltsov and V. P. Maslov: Idempotent Analysis and Its Applications. Mathematics and Its Applications 401, Springer, Dordrecht 1997.   DOI:10.1007/978-94-015-8901-7
  21. N. Krivulin: 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:10.1090/conm/616/12308
  22. N. Krivulin: Extremal properties of tropical eigenvalues and solutions to tropical optimization problems. Linear Algebra Appl. 468 (2015), 211-232.   DOI:10.1016/j.laa.2014.06.044
  23. N. Krivulin: A multidimensional tropical optimization problem with nonlinear objective function and linear constraints. Optimization 64 (2015), 5, 1107-1129.   DOI:10.1080/02331934.2013.840624
  24. N. Krivulin: Direct solution to constrained tropical optimization problems with application to project scheduling. Comput. Manag. Sci. 14 (2017), 1, 91-113.   DOI:10.1007/s10287-016-0259-0
  25. N. Krivulin: Tropical optimization problems in time-constrained project scheduling. Optimization 66 (2017), 2, 205-224.   DOI:10.1080/02331934.2016.1264946
  26. N. Krivulin: Tropical optimization problems with application to project scheduling with minimum makespan. Ann. Oper. Res. 256 (2017), 1, 75-92.   DOI:10.1007/s10479-015-1939-9
  27. N. Krivulin: Tropical optimization technique in bi-objective project scheduling under temporal constraints. Comput. Manag. Sci. 17 (2020), 3, 437-464.   DOI:10.1007/s10287-020-00374-5
  28. K. Neumann, C. Schwindt and J. Zimmermann: Project Scheduling with Time Windows and Scarce Resources. Second edition. Springer, Berlin 2003.   DOI:10.1007/978-3-540-24800-2
  29. S. Sergeev and Z. Liu: 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.   CrossRef
  30. V. T'kindt and J.-C. Billaut: Multicriteria Scheduling. Second edition. Springer, Berlin 2006.   DOI:10.1007/b106275
  31. M. Yoeli: A note on a generalization of boolean matrix theory. Amer. Math. Monthly 68 (1961), 6, 552-557.   DOI:10.2307/2311149