Software & Systems

Articles of journal № 1 at 2022 year.

Order result by: Public date | Title | Authors |

11. Software for solving the precedence constrained generalized traveling salesman problem [№1 за 2022 год]
Authors: Petunin A.A., Ukolov S.S., Khachay M.Yu.
Visitors: 2551
The paper considers the generalized problem of the precedence constraint traveling salesman (PCGTSP). Like the classical traveling salesman problem (TSP), the authors search a minimum cost closed cycle in this problem, while the set of vertices is divided into nonempty pairwise disjoint sub-sets that are clusters; each feasible route must visit each cluster in a single vertex. In addition, the set of valid routes is constrained by an additional restriction on the order of visiting clusters, that is, some clusters must be visited earlier than others. In contrast to the TSP and the generalized traveling sales-man problem (GTSP), this problem is poorly studied both theoretically and from the point of view of algorithm design and implementation. The paper proposes the first specialized branch-and-bound algorithms using the solutions obtained using the recently developed PCGLNS heuristic as an initial guess. The original PCGTSP problem un-dergoes several relaxations, therefore there are several lower bounds for the original problem; the larg-est of them is used to cut off the branches of the search tree and thereby reduce the enumeration. The algorithms are implemented as open source software in the Python 3 programming language using the specialized NetworkX library. The performance of the proposed algorithms is evaluated on test exam-ples from the PCGTSPLIB public library in comparison with the state-of-the-art Gurobi solver using the MILP model recently proposed by the authors, and seems to be quite competitive even in the cur-rent implementation. The developed algorithms can be used in a wide class of practical problems, for example, for opti-mal tool routing for CNC sheet cutting machines, as well as for assessing the quality of solutions ob-tained using other methods.

12. Architecture of the software development and testing platform neural network models for creating specialized dictionaries [№1 за 2022 год]
Authors: Purtov D.N., I.G. Sidorkina
Visitors: 2496
The authors propose the implementation of a software platform for creating neural network models with their testing, used to create specialized dictionaries for automated systems. The software platform allows speeding up the process of finding the optimal method for creating a neural network model. The platform is based on an overview of existing tools and methods used to create clock analysis models and software virtualization technologies. A research result is the proposed architecture of a software platform for creating specialized dic-tionaries that ensures the simultaneous creation of different neural network models in virtual contain-ers. A container virtualization of software elements that create and test neural network models provides all mathematical calculations for processing text-based information; decentralized, in parallel and iso-lated training and testing a neural network model. The data exchange between virtual containers, as well as the storage of all the results of the container's operation occurs through a special data bus, which is disk space that all containers have access to. The use of the developed platform can speed up the process of searching for an algorithm for creat-ing specialized dictionaries through testing various hypotheses based on various methods for con-structing models. The process acceleration occurs due to the parallelism and reuse of the mathematical results of the general stages of algorithms whose mathematical calculations were carried out by a simi-lar algorithm. This allows scaling and splitting the learning process not only through the parallel crea-tion of various models, but also at the level of individual model creation stages. The proposed platform was successfully used to find a locally optimal method for creating a model in highly specialized lim-ited-field texts.

13. Time tracking automation for employees working remotely [№1 за 2022 год]
Authors: Shevnina Yu.S., Buravov A.N.
Visitors: 1561
The paper describes a method for solving the problem of time tracking of enterprise employees who work remotely. The method is based on the development of a separate information system with the ability to integrate into the existing project management system. According to surveys made by the IDC research company, the procedure of filling out the time sheet by employees of many companies is ra-ther inconvenient and long. However, in order to manage projects, managers need to know the actual time spent on work. For the server side, the authors used the NestJS framework, for the client web ap-plication – the Angular JS framework. In the process of modeling the information system, diagrams of the time tracking process before au-tomation and after automation were obtained using modern notations for their construction. MS SQL Server has become a relational database management system. The paper presents a comparative analysis of existing solutions for time tracking of enterprise em-ployees, such as: TMetric, StaffCop, WorkPoint, Kickidler, ManicTime, CrocoTime, identifies their main advantages and disadvantages. It also describes the methodology, analysis, selection of develop-ment tools, design and development of an information system that has been successfully implemented in the internal structure of a small enterprise with 70 % of its employees switched to a remote mode of operation. The calculation of the automation equipment efficiency has shown a decrease in the labor intensity of filling out time sheets by 80 % and a 60 % decrease in time costs. Detailed reporting of elapsed time allow more efficient allocation of resources by tasks resulting in increased overall project manageability.

14. Using job scheduler simulator to evaluate the effectiveness of job run time prediction [№1 за 2022 год]
Authors: Shumilin S.S., Vorobev M.Yu.
Visitors: 1834
The paper investigates the efficiency of queue scheduling using pre-trained models. A supercomputer cluster uses a scheduler to distribute the incoming job flow among the available computing resources. In order to place a job in the queue, the scheduler uses the data specified by a user, including the or-dered program runtime. However, users often misjudge the runtime and choose an upper estimate. If the job completes earlier than specified, then the scheduler needs to reschedule the queue. A large number of such events can reduce the efficiency of resource allocation. Recently, there have been many papers describing the use of machine learning to predict the job run time. This allows using the run time calculated by a pre-trained model during the scheduling process. However, all the models contain an estimation error. Therefore, the problem is the need to assess the efficiency of planning for a given value of the model error. This paper investigates the effectiveness of the proposed approach by comparing the scheduling ef-ficiency in two scenarios: 1) the scheduler uses the time specified by a user and 2) the scheduler uses the real job runtime. For this purpose, the SLURM scheduler simulator performs simulation on the sta-tistical data of the MVS-10P OP2 supercomputer installed at the Joint Supercomputer Center of the Russian Academy of Sciences. The results show that average waiting time in scenario 2 reduced by 25 %. Slowdown reduced by 50 %. Resource utilization did not change significantly. The experimental results indicate the practicability of using machine learning algorithms to predict the running time of jobs arriving at a supercomputer cluster. Thus, the article provides an estimate of the ultimate optimization, since the experiment assumes a hundred percent prediction accuracy, which to date is not demonstrated by any of the presented works on runtime prediction.

15. A formal model of multiagent systems for federated learning [№1 за 2022 год]
Authors: Yuleisy G.P., I.I. Kholod
Visitors: 3202
Recently, the concept of federated learning has been actively developing. This is due to the tightening of legislation in the field of working with personal data. Federated learning involves performing data training directly on the nodes where the data is stored. As a result, there is no need to transfer data an-ywhere, and they remain with the owners. To generalize the trained models, they are sent to the server that performs the aggregation. The concept of federated learning is very close to a multi-agent system, since agents allow training machine learning models on local devices while maintaining confidential information. The ability of agents to interact with each other makes it possible to generalize (aggregate) such models and reuse them. Taking into account the tasks that are solved by the federated learning methods, there are several learning strategies. Learning be carried out as follows: sequentially when the model is trained in turn at each node; centrally when models are trained in parallel at each node and aggregated on a central serv-er; or decentralized where training and aggregation is performed on each of the nodes. Interaction and coordination of agents should be carried out taking into account these learning strategies. This article presents a formal model of multi-agent systems for federated learning. It highlights the main types of agents required to complete the full cycle of federated learning: an agent that accepts a task from a user; an agent that collects information about the environment; an agent performing train-ing planning; an agent performing training on a data node; an agent providing information and access to data; an agent performing model aggregation. For each of them, the paper defines the main actions and types of messages exchanged by such agents. It also analyzes and describes the configurations of agent placement for each of the federated learning strategies.

◄ ← Preview | 1 | 2