Предварительное планирование повторяющихся задач

Question

На работе нам предоставляется набор ограничений формы (имя задачи, частота), где частота - это целое число, которое означает число тактов между каждым вызовом задачи "имя задачи". Две задачи не могут выполняться одновременно, и для каждого вызова задачи требуется один тик. Наша цель - найти лучший график с точки зрения соответствия набору ограничений.

Например, если нам даны ограничения {(a, 2), (b, 2)}, лучшим графиком будет «ab ab ab ...» С другой стороны, если нам дадут ограничения ({a, 2}, {b, 5}, {c, 5}), лучшим графиком, вероятно, будет «abaca abaca abaca ...»

В настоящее время мы находим лучшее расписание, запуская генетический алгоритм, который пытается минимизировать расстояние между фактическими частотами и заданными ограничениями. На самом деле это работает довольно хорошо, но мне интересно, есть ли какой-нибудь алгоритм, который лучше подходит для такого рода проблем. Я пытался выполнить поиск в Google, но мне, кажется, не хватает нужных слов (планирование обычно связано с выполнением задач :(). Вы можете помочь?

Answer 1

Прежде всего, рассмотрите достоинства комментария jldupont! :)

Во-вторых, я думаю, что точка - это точное описание второго элемента кортежа, например, {Name, Period [icity]}.

Тем не менее, посмотрите на сетевые алгоритмы. Некоторые варианты взвешенной очереди , вероятно, применимы здесь.

Например, для заданных N задач создайте N очередей, соответствующих задачам T0 ... Tn , и в каждом цикле (" tick ") в зависимости от периода выполнения задачи поставьте в очередь элемент в соответствующую очередь.

Алгоритм планировщика затем будет стремиться минимизировать (в среднем) общее количество официантов в очередях. Простой отправной точкой будет простое удаление из квен Qx с наибольшим количеством предметов. (Параметр на элементе в очереди, указывающий «возраст», поможет расставить приоритеты.)