Kybernetika 58 no. 5, 708-732, 2022

Interval multi-linear systems for tensors in the max-plus algebra and their application in solving the job shop problem

Sedighe Khaleghzade, Mostafa Zangiabadi, Aljoša Peperko and Masoud HajarianDOI: 10.14736/kyb-2022-5-0708

Abstract:

In this paper, we propose the notions of the max-plus algebra of the interval tensors, which can be used for the extension of interval linear systems to interval multi-linear systems in the max-plus algebra. Some properties and basic results of interval multi-linear systems in max-plus algebra are derived. An algorithm is developed for computing a solution of the multi-linear systems in the max-plus algebra. Necessary and sufficient conditions for the interval multi-linear systems for weak solvability over max-plus algebra are obtained as well. Also, some examples are given for illustrating the obtained results. %some examples are given for illustrating the effectiveness of the newly proposed method. Moreover, we briefly sketch how our results can be used in the max-plus algebraic system theory for synchronized discrete event systems.

Keywords:

max-plus algebra, interval tensor, multi-linear systems, weak solvability, job shop problem

Classification:

15A80, 15A06, 65G30, 15A69

paper.pdf

References:

  1. H. R. Afshin and A. R. Shojaeifard: Max-plus algebra on tensor s and its properties. Wavelet and Linear Algebra 3 (2016), 1-11.   CrossRef
  2. A. A. Aminu, S. E. Olowo, I. M. Sulaiman, N. A. Bakar and M. Mamat: On application of max-plus algebra to synchoronized discrete event system. Math. Statist. 9 (2021), 81-92.   DOI:10.13189/ms.2021.090201
  3. H. Bozorgmanesh, M. Hajarian and A. T. Chronopoulos: Interval tensors and their application in solving multi-linear systems of equations. Computers Math. Appl. 79 (2020), 697-715.   DOI:10.1016/j.camwa.2019.07.024
  4. P. Butkovič: Max-linear Systems: Theory and Algorithms. Springer Science and Business Media, 2010.   CrossRef
  5. K. Cechlárová and R. A. Cuninghame-Green: Interval systems of max-separable linear equations. Linear Algebra Appl. 340 (2002), 215-224.   DOI:10.1016/S0024-3795(01)00405-0
  6. R. A. Cuninghame-Green: Minimax Algebra. Vol. 166. Springer Science and Business Media, 2012.   CrossRef
  7. M. K. Fijavž, A. Peperko and E. Sikolya: Semigroups of max-plus linear operators. Semigroup Forum 94 (2017), 463-476.   CrossRef
  8. S. Friedland and S. Gaubert: Spectral inequa lities for nonnegative tensors and their tropical analogues. Vietnam J. Math. 48 (2020), 893-928.   DOI:10.1007/s10013-020-00432-0
  9. S. Gaubert and M. Plus: Methods and applications of (max,+) linear algebra. In: Annual Symposium on Theoretical Aspects of Computer Science, Springer, Berlin, Heidelberg 1997.   CrossRef
  10. M. Gavalec and K. Zimmermann: Solving systems of two-sided (max, min)-linear equations. Kybernetika 46 (2010), 405-414.   DOI:10.1007/s11135-010-9378-9
  11. M. Gavalec, J. Plavka and D. Ponce: Strong, strongly universal and weak interval eigenvectors in max-plus algebra. Mathematics 8 (2020), 1348.   CrossRef
  12. H. Goto: Robust MPL scheduling considering the number of in-process jobs. Engrg. Appl. Artificial Intell. 22 (2009), 603-607.   DOI:10.1016/j.engappai.2008.11.007
  13. Q. Guo and J. G. Liu: An two phase abs method for solving over determined systems of linear inequalities. J. Appl. Math. Comput. 21 (2006), 259-267.   DOI:10.1007/BF02896404
  14. N. Krivulin: Direct solution to constrained tropical optimization problems with application to project scheduling. Comput. Management Sci. 14 (2017), 91-113.   DOI:10.1007/s10287-016-0259-0
  15. V. Muller and A. Peperko: On the spectrum in max algebra. Linear Algebra and its Applications 485 (2015), 250-266.   DOI:10.1016/j.laa.2015.07.013
  16. H. Myšková: Interval systems of max-separable linear equations. Linear Algebra Appl. 403 (2005), 263-272.   DOI:10.1016/j.laa.2005.02.011
  17. H. Myšková: Interval max-plus systems of linear equations. Linear Algebra Appl. 437 (2012), 1992-2000.   DOI:10.1016/j.laa.2012.04.051
  18. H. Myšková: Max-min interval systems of linear equations with bounded solution. Kybernetika 48 (2012), 299-308.   DOI:10.1134/S000143381203005X
  19. M. Singh: Mathematical Models, Heuristics and Algorithms for Efficient Analysis and Performance Evaluation of Job Shop Scheduling Systems Using Max-Plus Algebraic Techniques. Dissertation, Ohio University; 2013.   CrossRef
  20. M. Singh and R. P. Judd: Efficient calculation of the makespan for job-shop systems without recirculation using max-plus algebra. Int. J. Product. Res. 52 (2014), 5880-5894.   DOI:10.1080/00207543.2014.925600
  21. T. Žužek, A. Peperko and J. Kušar: A max-plus algebra approach for generating non-delay schedule. Croatian Oper. Res. Rev. 4 (2019), 35-44.   CrossRef