Geodesic
Dispatching of circular-type applications
News of the Kabardin-Balkar scientific center of RAS, no. 6 (2021), pp. 50-57.

Voir la notice de l'article provenant de la source Math-Net.Ru

The article deals with the polynomial-time-consuming initial-ring and sequential approximation algorithm to discuss the question of the practical feasibility of their application in Grid systems. The first coordinate quadrant serves as a model of a Grid system with a centralized architecture, and the application model is represented by a resource rectangle. The quality of the algorithms is assessed by a nonEuclidean heuristic measure. The proposed algorithms are based on the operations of dynamic integration along the horizontal and vertical lines with a local optimum. The proposed algorithms are analysed on test arrays obtained from the facing of a square with strips of smaller squares. The heuristic measures of the resource shells of the initial-ring and the algorithm of successive approximations are calculated, which do not exceed the value of 0.61, and the magnitude of the error relative to the optimal value is determined, which does not exceed 22%. A recommendation is given to use these algorithms for dispatching circulartype claims in Grid-systems of a centralized architecture by arrays.
Keywords: dispatching, non-Euclidean heuristic measure, polynomial complexity of the algorithm, initial-ring algorithm, sequential approximation algorithm, array of applications of circular type, Grid-system. 
@article{IZKAB_2021_6_a3,
     author = {V. V. Kureichik and A. E. Saak},
     title = {Dispatching of circular-type applications},
     journal = {News of the Kabardin-Balkar scientific center of RAS},
     pages = {50--57},
     publisher = {mathdoc},
     number = {6},
     year = {2021},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/IZKAB_2021_6_a3/}
}
TY  - JOUR
AU  - V. V. Kureichik
AU  - A. E. Saak
TI  - Dispatching of circular-type applications
JO  - News of the Kabardin-Balkar scientific center of RAS
PY  - 2021
SP  - 50
EP  - 57
IS  - 6
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/IZKAB_2021_6_a3/
LA  - ru
ID  - IZKAB_2021_6_a3
ER  - 
%0 Journal Article
%A V. V. Kureichik
%A A. E. Saak
%T Dispatching of circular-type applications
%J News of the Kabardin-Balkar scientific center of RAS
%D 2021
%P 50-57
%N 6
%I mathdoc
%U http://geodesic.mathdoc.fr/item/IZKAB_2021_6_a3/
%G ru
%F IZKAB_2021_6_a3
V. V. Kureichik; A. E. Saak. Dispatching of circular-type applications. News of the Kabardin-Balkar scientific center of RAS, no. 6 (2021), pp. 50-57. http://geodesic.mathdoc.fr/item/IZKAB_2021_6_a3/

[1] A. Sungkar, T. Kogoya, “A review of grid computing”, Computer Science IT Research Journal, 1:1 (2020), 1–6 | DOI

[2] M. Mishra, Y. Patel, M. Ghosh, G. Mund, “A Review and Classification of Grid Computing Systems”, International Journal of Computational Intelligence Research, 13:3 (2017), 369–402

[3] F. Magoules, Fundamentals of grid computing: theory, algorithms and technologies, Numerical analysis and scientific computing, CRC Press, UK, 2010

[4] N. Antonopoulos, G. Exarchakos, M. Li, A. Liotta, Handbook of research on p and grid systems for service-oriented computing: models, methodologies and applications, IGI Global publisher, USA, 2010, 2 pp.

[5] U. Schwiegelshohn, R. Badia, M. Bubak, M. Danelutto, S. Dustdar et al, “Perspectives on grid computing”, Future Generation Computer Systems, 26:8 (2010), 1104–1115 | DOI

[6] A. Lodi, S. Martello, M. Monaci, “Two-dimensional packing problems: A survey”, European Journal of Operational Research, 141 (2002), 241–252 | DOI | MR | Zbl

[7] V. Yu. Bakenrot, A. G. Chefranov, “Efficiency of Approximate Algorithms for Program Distribution in a Homogeneous Computing System”, Izv. Academy of Sciences of the USSR. Tech. cybernetics, 1985, no. 4, 15–148 (In Russian)

[8] E. A. Mukhacheva, A. S. Mukhacheva, “The technology of block structures of local search for optimum in problems of rectangular packing”, Novyye tekhnologii. Informatsionnyye tekhnologii, 2004, no. 5. Supplement, 19–31, Moscow (In Russian)

[9] A. E. Saak, A. G. Chefranov, “Evaluation of the efficiency of parallel conveyor systems in processing packages of independent problems”, Izvestiya RAN. Theory and control systems, 1996, no. 2, 179–186 (In Russian) | Zbl

[10] K. Jansen, M. Rau, “Linear time algorithms for multiple cluster scheduling and multiple strip packing”, European Conference on Parallel Processing, 2019, 103–116 | Zbl

[11] Soren Henning, Klaus Jansen, Malin Rau, Lars Schmarje, “Complexity and inapproximability results for parallel task scheduling and strip packing”, Theory of Computing Systems, 64:1 (2020), 120–140 | DOI | MR | Zbl

[12] A. E. Saak, “Polynomial algorithms for resource allocation in grid-systems based on quadratic typification of arrays of applications”, Information Technologies, 2013, no. 7, 1–32 (In Russian) | Zbl

[13] A. E. Saak, “Management of resources and user requests in Grid-systems with a centralized architecture”, Proceedings of the XII All-Russian meeting on control problems of VSPU-2014 (June 16-19, 2014), RAS Institute of Management Problems n.a. V.A. Trapeznikov, Moscow, 2014, 7489–7498 (In Russian)

[14] A. Saak, V. Kureichik, E. Kuliev, “Ring Algorithms for Scheduling in Grid Systems”, Advances in Intelligent Systems and Computing, 349 (2015), 201–209 | DOI

[15] A. Saak, V. Kureichik, Y. Kravchenko, “To scheduling quality of sets of precise form which consist of tasks of circular and hyperbolic type in grid systems”, Advances in Intelligent Systems and Computing, 464 (2016), 157–166 | DOI

[16] A. Saak, V. Kureichik, A. Lezhebokov, “Scheduling of Parabolic-Type Tasks Arrays in GRID Systems”, Advances in Intelligent Systems and Computing, 575 (2017), 292–298 | DOI

[17] M. Caramia, S. Giordani, A. Iovanella, “Grid scheduling by on-line rectangle packing”, Networks, 44:2 (2004), 106–119

[18] A. E. Saak, “Level algorithms for dispatching arrays of circular-type applications in Grid systems”, Bulletin of Southern Fed.U. Technical science, 2015, no. 6 (167), 223–231 (In Russian)

[19] A. E. Saak, “Dispatching of circular-type claims in Grid systems”, Information Technologies, 22:1 (2016), 37–41 (In Russian) | MR

[20] E. Friedman, Problem of the Month. Tiling squares with strips of smaller squares, , 2001 https://erich-friedman.github.io/mathmagic/1201.html