Колесов Николай Викторович — доктор технических наук, профессор, главный научный сотрудник
Санкт-Петербург, 197046
Nikolai V. Kolesov — D.Sc., Professor, Chief Researcher
Saint Petersburg, 197046
Литуненко Елизавета Геннадьевна — младший научный сотрудник
Санкт-Петербург, 197046
Elisaveta G. Litunenko — Junior Researcher
Saint Petersburg, 197046
Толмачева Марина Владимировна — кандидат технических наук, старший научный сотрудник
Санкт-Петербург, 197046
Marina V. Tolmacheva — PhD, Senior Researcher
Saint Petersburg, 197046
Тюльников Виктор Сергеевич — инженер-программист
Санкт-Петербург, 197046
Viktor S. Tiulnikov — Software Engineer
Saint Petersburg, 197046
Введение. Планирование вычислений занимает важное место в процессе проектирования распределенных систем обработки информации и управления. Эффективные алгоритмы планирования позволяют находить технические решения, адекватные существующим ограничениям. Это становится особенно актуально для вычислителей, размещенных на автономных носителях, таких как беспилотные летательные аппараты, необитаемые подводные аппараты и другие подвижные объекты. В работе предложены и исследованы алгоритмы планирования заданий для распределенной вычислительной недетерминированной системы в случае, когда время выполнения заданий известно неточно и задано в виде временных интервалов. Метод. Решение поставленной задачи достигается путем сведения ее к известной задаче flow shop планирования с последующим применением формализма разрешимых классов распределенных вычислительных систем. Основные результаты. Предложены два алгоритма планирования заданий для недетерминированной распределенной вычислительной системы. Алгоритмы допускают отсутствие изоморфизмов между графами заданий и графом межпроцессорных связей. В этом случае невозможно применение известных алгоритмов flow shop планирования. Алгоритмы предполагают предварительное приведение рассматриваемой системы к требуемому виду и базируются на положениях интервального анализа и понятии разрешимого класса распределенных вычислительных систем. Критерием оптимальности предложенных алгоритмов служит минимум среднего времени пребывания задания в системе. Дополнительно для второго алгоритма используется критерий минимума максимального отклонения от заданных директивных сроков. Для введенных разрешимых классов систем для обоих критериев сформулированы оптимальные алгоритмы планирования полиномиальной сложности. Обсуждение. Предложенные решения могут быть применены при планировании вычислений в распределенных вычислительных системах при неточно известных длительностях решаемых задач, в частности, при планировании экономических процессов.
Computation scheduling is very important in the design of distributed information processing and control systems. Effective scheduling algorithms allow developer to find technical solutions that are adequate to the existing constraints. This is especially important for computers located on autonomous carriers, such as unmanned aerial vehicles, autonomous underwater vehicles, and other vehicles. Scheduling algorithms for tasks in the distributed non-deterministic computing system, when the task execution time is known inaccurately and described as time interval, are proposed and researched. The solution of the problem is achieved by reducing it to a known problem of flow shop scheduling with subsequent application of the formalism of solvable classes of distributed computing systems. Authors propose two algorithms for scheduling tasks for a non-deterministic distributed computing system. Algorithms allow the absence of isomorphisms between task graphs and the graph of interprocessor communications for the system, and the presence of many information outputs and branches between tasks. In these conditions, it is impossible to use known algorithms of flow shop scheduling. Proposed algorithms assume preliminary reduction of the considered system to the required form and base on the provisions of interval analysis and the concept of a solvable class of distributed computing systems. Optimality criterion for proposed algorithms is the criterion of minimum average time a task remains in the system. Additionally, the criterion of minimum of maximum deviation from directive terms is used. For the introduced solvable classes of systems, optimal scheduling algorithms of polynomial complexity are proposed. These algorithms allow us to schedule computations in real distributed computing systems when the system deviates from the canonical form and when the durations of the tasks are not precisely known. Proposed algorithms can be applied when scheduling computations in real distributed computing systems and solving tasks with not precisely known durations and also, for example, in scheduling economic processes.
The authors declare that there are no conflicts of interest present.