Open AccessApplication of the Modified Method of ant Colonies to Search for Rational Assignment of Employees to Tasks Using Fuzzy Sets
Author(s) -
Vladimir Anatolievich Sudakov,
Yu.P. Titov
Publication year - 2020
Publication title -
statistika i èkonomika
Language(s) - English
Resource type - Journals
ISSN - 2500-3925
DOI - 10.21686/2500-3925-2020-3-79-91
Subject(s) - ant colony optimization algorithms , travelling salesman problem , mathematical optimization , computer science , ant colony , graph , path (computing) , task (project management) , set (abstract data type) , algorithm , assignment problem , selection (genetic algorithm) , mathematics , artificial intelligence , theoretical computer science , engineering , systems engineering , programming language
Purpose of the research. The aim of the study is to develop recommendations on the selection of parameters for modifying the ant colony method when searching for a rational solution to the task of appointing employees to work, subject to setting the time to complete the work using fuzzy sets and taking into account the interaction time between employees assigned to one task. The algorithm is proposed for modifying the ant colony method. Various stopping algorithms of the modified ant colony method are considered. Materials and research methods. The use of the ant colony method developed for finding the traveling salesman’s path for the assignment problem requires the creation of a “decision graph” and some modifications of the algorithm associated with entering weights (pheromone) on the graph. The paper proposes to create a graph of solutions by creating a set of vertices that determine the appointment of an employee for tasks for each employee and calculating the path in the graph that determines the solution to the assignment problem. To stop the algorithm of the ant colony method, two different algorithms are considered: the stop when performing a certain number of iterations and the stop when finding a solution that satisfies the constraints. To evaluate the effectiveness of the algorithm, the following criteria were considered: the estimate of the mathematical expectation of the number of iterations of the algorithm, the estimate of the mathematical expectation of the criterion value, the estimate of the mathematical expectation of the number of considered solutions, etc. For all estimates of mathematical expectation, a confidence interval is also calculated. According to the estimates, the paper gives recommendations on the selection of parameters of the ant colony method: the number of agents, evaporation rate, parameters of the elite and ranked method of ant colonies, etc. Both the speed and the ability to find rational solutions for different values of constraints are evaluated. Results. The work considered the task of appointing 35 employees for 15 tasks. As a result, the following recommendations were identified on the choice of parameters to the modified method of ant colonies. The more agents, the better solution found, but the number of the considered solutions increases, which leads to an increase in search time. For the evaporation coefficient, it is recommended to choose a value in the range (0.8; 0.95). It is recommended to use a ranked algorithm with a parameter 4 times less than the number of agents in the group. The problem of “cycling” of the ant colony method, caused by the passage of agents along the same routes, is determined. Conclusion. The developed recommendations make it possible to use the ant colony method to solve the problem of assigning employees to tasks. The proposed recommendations on the parameters provide high speed and accuracy of finding a rational solution to the problem. The problem of “cycling” of the ant colony method is described.