COMPUTERIZED SYSTEM OF PLANNING REPAIRS OF WAGON DEPOT
Formulation of the problem
All organizational and technological solutions in the distribution of work at enterprises must be made promptly. At the same time, non-optimal solutions significantly reduce the effectiveness of scheduling the production site. Absolutely the same situation is observed in the depot for the repair of wagons. However, until now, the movement of workers' brigades in the production environment (at the production site) in accordance with the technological route in real time has been little studied. The most actual task is the construction of optimal schedules for the work of car-repair brigades in accordance with the technological route. In connection with the problems that have arisen, the system is faced with the following main task: to optimize the distribution of work for the teams.
Distribution of work on teams
The algorithm being developed should effectively allocate the labor resources of the repair depot, which will increase its productivity. The task of distributing the necessary works for the repair of wagons among brigades belongs to the tasks of operational and calendar planning.
Operational planning covers not only the establishment of tasks for the performance of work (although this is the most important part of it), but also other indicators of the enterprise and its shops: labor productivity, the number of workers and the size of the wage fund, the use of the production capacity of the enterprise and its material resources, production, profitability of production.
Most of the techniques developed to date for operational scheduling are based on simplified models, which reduces their accuracy, or these techniques are used only for certain specific conditions. Significant complexity, in addition, is the problem of assessing the quality of the resulting schedules. Analysis of modern works on combinatorial optimization on graphs (especially dynamic problems) shows that one of the most promising approaches is the use of ant algorithms. This approach allows to significantly improve the operational planning system, thereby reducing the time to construct optimal or acceptable production schedules.
Mathematical model
For operational planning of the distribution of work, the technological process is divided into technological operations.
Let us assume that n wagons di (i = 1,2, ..., n) are repaired at this production site. We denote an arbitrary operation that must be performed on the car di, through Oij (j = 1,2, ..., mi), where mi is the total number of operations to be performed on di. Under the technological route of the brigade, it is usually understood how the brigade performs work on the car or the sequence of operations performed (1).
Mi=(O_i1,O_i2,…,O(imi )), (1)
When the operations are performed consistently, a strict ordering of the technological route is envisaged. However, we can assume (and this often corresponds to reality) that the order of the operations changes (is not strict), that is, the orderliness of the operations is partial. The following limitations must be taken into account:
1. Limitations on the terms of manufacture (2):
Tпл ≤ Tф, (2)
Where: Tф – actual repair period of the car di,
Tпл – scheduled repair time for the car di.
2. Limitations on production volumes (3):
Nпл = Nф, (3)
Where: Tф – the actual number of wagons repaired,
Tпл – the number of wagons specified in the production program.
The task of the operational scheduling of the work schedule is to make up a schedule for the production site with the specified technological routes for the repair of wagons that satisfies the formulated conditions, which is represented in the form of a graph. The construction of such a graph is equivalent to determining the numbers tij - the moments of the beginning of the technological operation Oij.
The collection of numbers {iij} (i = 1,2, ..., n; j = 1,2, ..., mi) satisfying the conditions stated [9] is called the schedule of works, or its graph model G (i) [2].
To solve the problem of constructing an optimal schedule, let us assign a certain numerical function F (a criterion function) defined on all graphs G (i), which assigns to each graph G a definite number F (G). In this case, the extremum of the function F must correspond to the best graph. Thus, the problem reduces to constructing a graph that satisfies all the conditions and constraints formulated in the job and on which the function F (G) reaches its extreme value (5).
T_опт = Tпл - Tф → min, (4)
Obviously, there are an infinite number of graphs that satisfy the formulated conditions and constraints. Thus, it is necessary to construct the best graph model in accordance with the selected criterion (4):
F(G) = extr F(G), (5)
Graph model
A graph model consists of a set of nodes and oriented arcs connecting nodes. In the graphical representation of the necessary work, the nodes act as necessary technological processes that need to be carried out over the car, and the arcs show the direction of movement of workers to perform repairs of the car parts (Fig. 1).
It should be noted that the graph model is not a structural (functional) scheme of a real depot. Depending on the task and the function being studied, the number of nodes in the network, their composition and the connections between them change.
The initial node of the graph determines the beginning of the execution of the plan (the starting point) in which the ants are placed, in an amount equal to the number of workers at the production site. The remaining vertices of the graph correspond to a separate technological operation Oij (according to the technological map).
Each node O_ij is uniquely determined by the following parameters (6):
Oij = (Kmin,Kopt,Tvij,Tnij,Nij,Pr,D,Kv), (6)
where: Kmin - the minimum number of workers required to perform the technological operation Oij;
Kopt - the optimal number of workers required to perform the technological operation Oij;
Tvij – time of execution of technological operation Oij;
Tnij – time for the brigade to complete the technological operation Oij;
Nij – number of worker performing work Oij;
Pr – processing priority Oij;
D – availability of technological operation Oij;
Kv – The qualification of the worker, necessary for the execution of the technological operation Oij;
Thus, the node of the graph model is a symbol of the performed technological operation within the framework of a particular job, and the edge displays a sequential transition from one technological operation to another (yellow shows the transitions from one technological operation to another within the framework of one work, and blue shows the set of possible transitions between works).
In this case, ants have a number of characteristics (7):
Mij =(Kv,T,W), (7)
where: Kv - qualification of the ant (worker);
T – The amount of time that an ant (worker) will spend on performing all the work within a single shift;
W – The list of works that an ant (worker) needs to perform for a shift;
Picture 1 - Graph's model
Let us consider in more detail the process of functioning of the distribution of workers for work within the framework of the graph model.
As already mentioned, the nodes represent the technological processes, which in Fig. 1 are represented by yellow dots. The way that workers can move around the graph in search of a suitable job for themselves is marked with yellow and blue arrows. As part of one work, a directed graph is used, and workers can only move forward, while transitions between jobs can be carried out in random order.
The worker, moving along the graph, stops at a suitable technological process (yellow point), thereby starting the process execution and blocking the access of the remaining workers to him, and he himself is considered busy and does not seek another node (technological process) until he completes the current work. Having finished work, the employee is free to move to another technological process that suits him.
Thus, by using the theory of graphs and ant algorithms, the distribution of workers according to works is carried out, which will allow to optimize the work of the repair depot and increase its efficiency.
Conclusions
This algorithm streamlines and rationalizes the employment of employees of the wagon depot and reduces delays in time, and as a consequence increases the productivity of the repair depot.
Список литературы
1. Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн Алгоритмы: построение и анализ = Introduction to Algorithms. – 2-е изд. – М.: «Вильямс», 2006. – С. 1296.
2. M. Dorigo, V. Maniezzo, A. Colorni, 1996. "Ant System: Optimization by a Colony of Cooperating Agents", IEEE Transactions on Systems, Man, and Cybernetics-Part B, 26 (1): 29–41.
3. L. M. Gambardella, M. Dorigo, "Ant-Q: A Reinforcement Learning Approach to the Traveling Salesman Problem" // Twelfth International Conference on Machine Learning, Morgan Kaufmann, p. 252–260, 1995.
4. Ананий В. Левитин Глава 9. Жадные методы: Алгоритм Дейкстры // Алгоритмы: введение в разработку и анализ = Introduction to The Design and Analysis of Aigorithms. – М.: «Вильямс», 2006. – С. 189–195.
5. Рассел С. Дж., Норвиг, П. Искусственный интеллект: современный подход = Artificial Intelligence: A Modern Approach / Пер. с англ. и ред. К. А. Птицына. – 2-е изд. – М.: Вильямс, 2006. – С. 157–162.
6. Лорьер Ж.-Л. Системы искусственного интеллекта / Пер. с фр. и ред. В. Л. Стефанюка. – М.: Мир, 1991. – С. 238–244.
7. C. Blum, 2005 "Ant colony optimization: Introduction and recent trends". Physics of Life Reviews, 2: 353–373.
