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

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и в каждом цикле ("галочка"), основанном на периоде задачи, помещать элемент в соответствующую очередь.

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