ON THE SIMILARITY OF THE PLANNING PROBLEM FROM SCHEDULE THEORY AND PROBLEMS OF TASK DISTRIBUTION IN A SWARM OF UNMANNED AIRCRAFT

In combinatorial optimization, many examples can be given when problems of different classes are solved according to the same computational scheme. This situation is connected with the property of similarity of different problems of this class. In order to develop universal methods and algorithms for their solution, it is necessary to identify the characteristic features of this similarity This property is considered on the example of a planning problem from the theory of schedules and the problem of task allocation in a swarm of unmanned aerial vehicles (UAVs). The scheduling problem is formulated as follows. Some details are given. Each of them must undergo sequential processing on a specific machine. It is necessary to draw up such a schedule for the processing of parts that the time used for these operations would be minimal, provided that it does not exceed the given value. In this problem, each part requires one operation for its processing. Each machine also performs one operation. One of the problems of distributing tasks in a swarm of UAVs is based on the mechanism of the sequence of tasks. A swarm consists of a large number of small drones that have limited resources to perform tasks and operate mostly autonomously in real time. By setting the sequence of tasks, each UAV clearly separates the required task execution time and synchronization waiting time. For new targets found, each UAV quickly determines its available time period. In both tasks, a certain number of machines (or drones) are set, which perform a given operation (processing of parts or a task that is transferred from a previous UAV). These operations are performed sequentially. The time spent on a certain task in both tasks is constant. Only the idle time changes. The optimization problem in both of these problems is reduced to the minimization of idle time (or synchronization). Both problems relate to the theory of schedules. Since they involve a selection of options, they are modeled within the framework of combinatorial optimization theory. The argument of the objective function in them is such a combinatorial configuration as placement without repetitions. That is, they are also similar by the argument of the objective function. Based on this feature, the described problems are solved using the same approaches: an algorithm using a structural-alphabetic search and dynamic programming.