Geodesic
Interval multi-linear systems for tensors in the max-plus algebra and their application in solving the job shop problem
Kybernetika, Tome 58 (2022) no. 5, pp. 708-732
Cet article a éte moissonné depuis la source Czech Digital Mathematics Library

Voir la notice de l'article

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. Moreover, we briefly sketch how our results can be used in the max-plus algebraic system theory for synchronized discrete event systems.
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. Moreover, we briefly sketch how our results can be used in the max-plus algebraic system theory for synchronized discrete event systems.
DOI : 10.14736/kyb-2022-5-0708
Classification : 15A06, 15A69, 15A80, 65G30
Keywords: interval tensor; max-plus algebra; multi-linear systems; weak solvability; job shop problem 
@article{10_14736_kyb_2022_5_0708,
     author = {Khaleghzade, Sedighe and Zangiabadi, Mostafa and Peperko, Aljo\v{s}a and Hajarian, Masoud},
     title = {Interval multi-linear systems for tensors in the max-plus algebra and their application in solving the job shop problem},
     journal = {Kybernetika},
     pages = {708--732},
     year = {2022},
     volume = {58},
     number = {5},
     doi = {10.14736/kyb-2022-5-0708},
     mrnumber = {4538622},
     zbl = {07655856},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.14736/kyb-2022-5-0708/}
}
TY  - JOUR
AU  - Khaleghzade, Sedighe
AU  - Zangiabadi, Mostafa
AU  - Peperko, Aljoša
AU  - Hajarian, Masoud
TI  - Interval multi-linear systems for tensors in the max-plus algebra and their application in solving the job shop problem
JO  - Kybernetika
PY  - 2022
SP  - 708
EP  - 732
VL  - 58
IS  - 5
UR  - http://geodesic.mathdoc.fr/articles/10.14736/kyb-2022-5-0708/
DO  - 10.14736/kyb-2022-5-0708
LA  - en
ID  - 10_14736_kyb_2022_5_0708
ER  - 
%0 Journal Article
%A Khaleghzade, Sedighe
%A Zangiabadi, Mostafa
%A Peperko, Aljoša
%A Hajarian, Masoud
%T Interval multi-linear systems for tensors in the max-plus algebra and their application in solving the job shop problem
%J Kybernetika
%D 2022
%P 708-732
%V 58
%N 5
%U http://geodesic.mathdoc.fr/articles/10.14736/kyb-2022-5-0708/
%R 10.14736/kyb-2022-5-0708
%G en
%F 10_14736_kyb_2022_5_0708
Khaleghzade, Sedighe; Zangiabadi, Mostafa; Peperko, Aljoša; Hajarian, Masoud. Interval multi-linear systems for tensors in the max-plus algebra and their application in solving the job shop problem. Kybernetika, Tome 58 (2022) no. 5, pp. 708-732. doi: 10.14736/kyb-2022-5-0708

[1] Afshin, H. R., Shojaeifard, A. R.: Max-plus algebra on tensor s and its properties. Wavelet and Linear Algebra 3 (2016), 1-11.

[2] Aminu, A. A., Olowo, S. E., Sulaiman, I. M., Bakar, N. A., Mamat, M.: On application of max-plus algebra to synchoronized discrete event system. Math. Statist. 9 (2021), 81-92. | DOI

[3] Bozorgmanesh, H., Hajarian, M., Chronopoulos, A. T.: Interval tensors and their application in solving multi-linear systems of equations. Computers Math. Appl. 79 (2020), 697-715. | DOI

[4] Butkovič, P.: Max-linear Systems: Theory and Algorithms. Springer Science and Business Media, 2010. | Zbl

[5] Cechlárová, K., Cuninghame-Green, R. A.: Interval systems of max-separable linear equations. Linear Algebra Appl. 340 (2002), 215-224. | DOI | Zbl

[6] Cuninghame-Green, R. A.: Minimax Algebra. Vol. 166. Springer Science and Business Media, 2012.

[7] Fijavž, M. K., Peperko, A., Sikolya, E.: Semigroups of max-plus linear operators. Semigroup Forum 94 (2017), 463-476. | DOI

[8] Friedland, S., Gaubert, S.: Spectral inequa lities for nonnegative tensors and their tropical analogues. Vietnam J. Math. 48 (2020), 893-928. | DOI

[9] Gaubert, S., Plus, M.: Methods and applications of (max,+) linear algebra. In: Annual Symposium on Theoretical Aspects of Computer Science, Springer, Berlin, Heidelberg 1997.

[10] Gavalec, M., Zimmermann, K.: Solving systems of two-sided (max, min)-linear equations. Kybernetika 46 (2010), 405-414. | DOI

[11] Gavalec, M., Plavka, J., Ponce, D.: Strong, strongly universal and weak interval eigenvectors in max-plus algebra. Mathematics 8 (2020), 1348. | DOI

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

[13] Guo, Q., Liu, J. G.: An two phase abs method for solving over determined systems of linear inequalities. J. Appl. Math. Comput. 21 (2006), 259-267. | DOI

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

[15] Muller, V., Peperko, A.: On the spectrum in max algebra. Linear Algebra and its Applications 485 (2015), 250-266. | DOI

[16] Myšková, H.: Interval systems of max-separable linear equations. Linear Algebra Appl. 403 (2005), 263-272. | DOI | Zbl

[17] Myšková, H.: Interval max-plus systems of linear equations. Linear Algebra Appl. 437 (2012), 1992-2000. | DOI

[18] Myšková, H.: Max-min interval systems of linear equations with bounded solution. Kybernetika 48 (2012), 299-308. | DOI

[19] Singh, M.: 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.

[20] Singh, M., Judd, R. P.: Efficient calculation of the makespan for job-shop systems without recirculation using max-plus algebra. Int. J. Product. Res. 52 (2014), 5880-5894. | DOI

[21] Žužek, T., Peperko, A., Kušar, J.: A max-plus algebra approach for generating non-delay schedule. Croatian Oper. Res. Rev. 4 (2019), 35-44. | DOI

Cité par Sources :