Minimizing maximum lateness in two-stage projects by tropical optimization

Nikolai Krivulin; Sergeĭ Sergeev

Kybernetika (2022)

  • Volume: 58, Issue: 5, page 816-841
  • ISSN: 0023-5954

Abstract

top
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.

How to cite

top

Krivulin, Nikolai, and Sergeev, Sergeĭ. "Minimizing maximum lateness in two-stage projects by tropical optimization." Kybernetika 58.5 (2022): 816-841. <http://eudml.org/doc/299340>.

@article{Krivulin2022,
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.},
author = {Krivulin, Nikolai, Sergeev, Sergeĭ},
journal = {Kybernetika},
keywords = {tropical optimization; tropical linear algebra; minimax optimization problem; project scheduling; maximum lateness},
language = {eng},
number = {5},
pages = {816-841},
publisher = {Institute of Information Theory and Automation AS CR},
title = {Minimizing maximum lateness in two-stage projects by tropical optimization},
url = {http://eudml.org/doc/299340},
volume = {58},
year = {2022},
}

TY - JOUR
AU - Krivulin, Nikolai
AU - Sergeev, Sergeĭ
TI - Minimizing maximum lateness in two-stage projects by tropical optimization
JO - Kybernetika
PY - 2022
PB - Institute of Information Theory and Automation AS CR
VL - 58
IS - 5
SP - 816
EP - 841
AB - 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.
LA - eng
KW - tropical optimization; tropical linear algebra; minimax optimization problem; project scheduling; maximum lateness
UR - http://eudml.org/doc/299340
ER -

References

top
  1. Allamigeon, X., Benchimol, P., Gaubert, S., Joswig, M., , 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. Zbl0824.93003
  3. Bouquard, J.-L., Lenté, C., Billaut, J.-C., , 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., , IMA J. Appl. Math. 7 (1971), 3, 273-294. DOI
  6. Cuninghame-Green, R., , Lecture Notes in Economics and Mathematical Systems 166, Springer, Berlin 1979. Zbl0739.90073DOI
  7. Cuninghame-Green, R. A., , Oper. Res. Quart. 13 (1962), 1, 95-100. DOI
  8. Cuninghame-Green, R. A., Minimax algebra and applications. Zbl0739.90073
  9. Puente, M. J. de la, , Linear Multilinear Algebra 68 (2020), 10, 2110-2142. DOI
  10. Demeulemeester, E. L., Herroelen, W. S., , International Series in Operations Research and Management Science 49, Springer, New York 2002. DOI
  11. Ehrgott, M., , Springer, Berlin 2005. DOI
  12. Gaubert, S., Katz, R. D., , Linear Algebra Appl. 421 (2007), 2, 356-369. DOI
  13. Gaubert, S., Katz, R. D., Sergeev, S., , J. Symbolic Comput. 47 (2012), 12, 1447-1478. DOI
  14. Giffler, B., , Naval Res. Logist. Quart. 10 (1963), 1, 237-255. DOI
  15. Golan, J. S., , Mathematics and Its Applications 556, Kluwer Acad. Publ., Dordrecht 2003. DOI
  16. Gondran, M., Minoux, M., , Operations Research / Computer Science Interfaces 41, Springer, New York 2008. DOI
  17. Goto, H., , 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., , Linear Algebra Appl. 440 (2014), 131-163. DOI
  20. Kolokoltsov, V. N., Maslov, V. P., , Mathematics and Its Applications 401, Springer, Dordrecht 1997. Zbl0941.93001DOI
  21. Krivulin, N., , 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., , Linear Algebra Appl. 468 (2015), 211-232. DOI
  23. Krivulin, N., , Optimization 64 (2015), 5, 1107-1129. DOI
  24. Krivulin, N., , Comput. Manag. Sci. 14 (2017), 1, 91-113. DOI
  25. Krivulin, N., , Optimization 66 (2017), 2, 205-224. DOI
  26. Krivulin, N., , Ann. Oper. Res. 256 (2017), 1, 75-92. DOI
  27. Krivulin, N., , Comput. Manag. Sci. 17 (2020), 3, 437-464. DOI
  28. Neumann, K., Schwindt, C., Zimmermann, J., , 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., , Springer, Berlin 2006. DOI
  31. Yoeli, M., , Amer. Math. Monthly 68 (1961), 6, 552-557. Zbl0115.02103DOI

NotesEmbed ?

top

You must be logged in to post comments.